Quantum implicit computational complexity
From MaRDI portal
Publication:1044836
DOI10.1016/j.tcs.2009.07.045zbMath1186.68209OpenAlexW1992587415MaRDI QIDQ1044836
Andrea Masini, Margherita Zorzi, Ugo Dal Lago
Publication date: 15 December 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.045
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Functional programming and lambda calculus (68N18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
Characterizing polynomial and exponential complexity classes in elementary lambda-calculus ⋮ A branching distributed temporal logic for reasoning about entanglement-free quantum state transformations ⋮ A programming language characterizing quantum polynomial time ⋮ On session types and polynomial time ⋮ On quantum lambda calculi: a foundational perspective ⋮ Unnamed Item ⋮ $$\mathsf {qPCF}$$ : A Language for Quantum Circuit Computations ⋮ An automated deductive verification framework for circuit-building quantum programs ⋮ QPCF: higher-order languages and quantum circuits ⋮ Formalization of metatheory of the Quipper quantum programming language in a linear logic ⋮ A higher-order characterization of probabilistic polynomial time ⋮ Implicit computation complexity in higher-order programming languages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear logic
- Light affine lambda calculus and polynomial time strong normalization
- Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
- The lambda calculus, its syntax and semantics
- A new recursion-theoretic characterization of the polytime functions
- Light linear logic
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Soft linear logic and polynomial time
- An arithmetic for polynomial-time computation
- Quantum computational networks
- On a measurement-free quantum lambda calculus with classical control
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Complexity Theory
- A Lambda Calculus for Quantum Computation
- Towards a quantum programming language
- Universality in quantum computation
- Functional and Logic Programming
- Foundations of Software Science and Computation Structures
- Quantum programming languages: survey and bibliography
- A lambda calculus for quantum computation with classical control
- Term Rewriting and Applications
- Typed Lambda Calculi and Applications
This page was built for publication: Quantum implicit computational complexity