One complexity theorist's view of quantum computing

DOI10.1016/S0304-3975(01)00377-2zbMath1026.68056WikidataQ29544201 ScholiaQ29544201MaRDI QIDQ1870556

Lance J. Fortnow

Publication date: 14 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexity theory

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items (9)

Chaitin's omega and an algorithmic phase transition ⋮ Many worlds, the cluster-state quantum computer, and the problem of the preferred basis ⋮ Models of quantum computation and quantum programming languages ⋮ Computational universes ⋮ On the solution of trivalent decision problems by quantum state identification ⋮ Universality and programmability of quantum computers ⋮ Quantum computation and quantum information† ⋮ Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer ⋮ A common algebraic description for probabilistic and quantum computations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Non-deterministic exponential time has two-prover interactive protocols
• On the degree of Boolean functions as real polynomials
• An oracle builder's toolkit
• Relativized worlds with an infinite hierarchy
• Complexity limitations on quantum computation
• Proof verification and the hardness of approximation problems
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• A Fast Monte-Carlo Test for Primality
• Quantum computations: algorithms and error correction
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computability
• On the Power of Quantum Computation
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing
• Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
• Logical Reversibility of Computation

This page was built for publication: One complexity theorist's view of quantum computing