Complexity limitations on quantum computation
From MaRDI portal
Publication:1961375
zbMath0947.68050MaRDI QIDQ1961375
Lance J. Fortnow, John D. Rogers
Publication date: 17 January 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (17)
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Quantum weakly nondeterministic communication complexity ⋮ Complexity limitations on one-turn quantum refereed games ⋮ An oracle builder's toolkit ⋮ Application of quantum approximate optimization algorithm to job shop scheduling problem ⋮ Unnamed Item ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ Uniformity of quantum circuit families for error-free algorithms ⋮ LWPP and WPP are not uniformly gap-definable ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Classical vs quantum random oracles ⋮ Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\) ⋮ Complexity measures and decision tree complexity: a survey. ⋮ One complexity theorist's view of quantum computing
Cites Work
- Graph isomorphism is low for PP
- Gap-definable counting classes
- On the degree of Boolean functions as real polynomials
- An oracle builder's toolkit
- Complexity Measures for Public-Key Cryptosystems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Computational Complexity of Probabilistic Turing Machines
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity limitations on quantum computation
