Strengths and Weaknesses of Quantum Computing
Open accessThe DOI matches its Crossref record; 22 of the 23 references it cites were found in a registry or an index, and 1 are not checked yet; 6 of the 16 sources its claims cite were checked for support.
Abstract
Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116--123, SIAM J. Comput., 26 (1997), pp. 1340--1349], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124--134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of $\NP$ can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class $\NP$ cannot be solved on a quantum Turing machine (QTM) in time $o(2^{n/2})$. We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class $\NP \cap \coNP$ cannot be solved on a QTM in time $o(2^{n/3})$. The former bound is tight since recent work of Grover [in {\it Proc.\ $28$th Annual ACM Symposium Theory Comput.}, 1996] shows how to accept the class $\NP$ relative to any oracle on a quantum computer in time $O(2^{n/2})$.
Verified 2026-11-22 · 1 reference not checked yet
Overview
CoChat Summary
TL;DR
The paper proves oracle-relative lower bounds showing that quantum computers cannot solve NP in time o(2^{n/2}) relative to a random oracle, nor NP ∩ co-NP in time o(2^{n/3}) relative to a random permutation oracle. It also shows that any BQP machine can be made “tidy” for safe subroutine use, yielding BQP^BQP = BQP.
Key findings
- Relative to a uniformly random oracle, with probability 1, NP cannot be solved on a quantum Turing machine in time o(2^{n/2}); this is tight because Grover’s algorithm accepts NP relative to any oracle in time O(2^{n/2}).
- Relative to a uniformly random permutation oracle, with probability 1, NP ∩ co-NP cannot be solved on a quantum Turing machine in time o(2^{n/3}).
- Any BQP machine can be modified into a tidy BQP machine whose final superposition consists almost entirely of the input and the single-bit answer, so BQP machines can be safely used as subroutines; consequently BQP^BQP = BQP.
- Relative to a random permutation oracle, with probability 1, there exists a quantum one-way permutation: computable efficiently even classically given the oracle, but requiring exponential time to invert even on a quantum machine.
Methods
- The paper defines oracle quantum Turing machines with a query tape, pre-query and post-query states, and unitary oracle calls, then proves lower bounds using random oracle and random permutation oracle arguments.
- It uses query-magnitude and Euclidean-distance bounds (Theorem 3.3 and Corollary 3.4) to show that changing a small number of oracle answers has limited effect on the final superposition.
- For the subroutine result, it borrows QTM programming primitives from Bernstein and Vazirani, boosts success probability by majority vote over independent runs, and constructs a tidy BQP machine by copying the answer and reversing the computation.
Limitations
- The paper states that the oracle results do not rule out NP ⊆ BQP; they only establish that there is no black-box approach to solving NP-complete problems using uniquely quantum-mechanical features.
- The paper notes that the constant “1/3” in the NP ∩ co-NP permutation-oracle bound is not known to be fundamental and might be replaceable by 1/2, though not by the current proof.
- Evident from the text: the main separations are relative to random oracles or random permutation oracles, not unrelativized; no explicit limitations section is otherwise provided.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
6 Valid · 2 Not valid · 10 Not checked · 48 Own results and interpretations
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“In view of Grover's algorithm [13], we know that the constant '1 / 2' in the statement of Theorem 3.5 cannot be improved.”
What the sources say
- Partly supportedcites [13] [13] Grover, L., 'A fast quantum mechanical algorithm for database search', Proceedings of the 28th Annual ACM Symposium on Theory of Computing , 1996, pp. 212 - 219. - sourceExperimental — accuracy not yet measured
The introduction reports an O(√N)-step search algorithm, and section 6 describes a matching Ω(√N) lower bound. That supports the optimality of the one-half exponent for this search problem, but our copy does not state Theorem 3.5 or establish what its constant ‘1/2’ measures. (LLM, conf=0.75)
boosted- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Partly supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“That this was a real possibility is clear from Grover's [13] result, which gives a black-box approach to solving NP -complete problems in square-root as much time as is required classically.”
What the sources say
- Supportedcites [13] [13] Grover, L., 'A fast quantum mechanical algorithm for database search', Proceedings of the 28th Annual ACM Symposium on Theory of Computing , 1996, pp. 212 - 219. - source
The Abstract gives an O(√N)-step quantum search algorithm versus O(N) steps for classical search. Section 1.1 explicitly uses the NP-complete SAT problem as an example of searching N possible assignments, while distinguishing this square-root speedup from a polynomial-time algorithm for NP-complete problems. (LLM, conf=0.88)
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“However, quantum machines can recognize this language quadratically faster, in time O ( √ 2 n ), using Grover's algorithm [13].”
What the sources say
- Supportedcites [13] [13] Grover, L., 'A fast quantum mechanical algorithm for database search', Proceedings of the 28th Annual ACM Symposium on Theory of Computing , 1996, pp. 212 - 219. - source
Grover’s Abstract states that his quantum search algorithm takes O(√N) steps rather than the O(N) steps required classically. In “The Abstracted Problem,” the search space has N = 2^n states, giving O(√(2^n)); the citing authors’ application of that algorithm to their language L_A is their own framing. (LLM, conf=0.88)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“The former bound is tight since recent work of Grover [13] shows how to accept the class NP relative to any oracle on a quantum computer in time O (2 n/ 2 ).”
What the sources say
- Partly supportedcites [13] [13] Grover, L., 'A fast quantum mechanical algorithm for database search', Proceedings of the 28th Annual ACM Symposium on Theory of Computing , 1996, pp. 212 - 219. - sourceExperimental — accuracy not yet measured
The Abstract gives an O(√N)-step quantum search algorithm, and §1.1 discusses NP-complete SAT as a search over 2^n assignments; together these support the 2^{n/2} search bound. The paper does not establish the stated bound for the whole class NP relative to any oracle. Its discussion of handling multiple satisfying states (p. 114) also describes a procedure with log N repetitions. (LLM, conf=0.83)
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Partly supported
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“A direct quantum analog of the classical algorithm would start in an equally-weighted superposition of 2 n computation paths, query a different string on each path, and finally collapse the superposition by asking whether the query had found the nonempty location. This yields a success probability 1 / 2 n , the same as the classical computer.”
hedged- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
47 more claims
Create a free account to see all 66 claims and every source verdict.
- It may state two separate claims as one. 7
- The quote only partly states this claim. 1
- Probably not a substantial claim. 7
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Whereas polynomial-time quantum algorithms are not expected for NPhard problems, [196] like general optimization problems, more modest speedups, still significant in practice, might be achievable.”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [196]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Interestingly, this particular output is optimal [48].”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [48]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“Quantum computers can speed up exhaustive search [6], but only modestly [7]”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [7]
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · cited 6×
“Note: In view of Grover's algorithm [13], we know that the constant \1=2" in the statement of Theorem 3.”
BackgroundMethodInfluentialAlgorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · cited 4×
“Shor gave polynomial-time quantum algorithms for the factoring and discrete logarithm problems.”
BackgroundMethodInfluentialSimulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597 · cited 1×
“Deutsch [9] de ned a general model of quantum computation | the quantum Turing machine.”
BackgroundLogical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679 · cited 1×
“In the special case where f can be e ciently computed deterministically, it is easy to design the subroutine so that it reversibly erases the scratch-work|simply compute f(x), copy f(x) into safe storage, and then uncompute f(x) to get rid of the scratch work [2].”
MethodSelf-citationRapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700 · cited 1×
“Early work by Deutsch and Jozsa [11] showed how to exploit some inherently quantum mechanical features of QTMs.”
BackgroundBernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Self-citationOn the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · cited 9×
“In this subsection, we present several de nitions, lemmas and theorems from [4].”
BackgroundMethodInfluentialSelf-citationQuantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270 · cited 3×
“Yao [17] extended this by proving that quantum circuits (introduced by Deutsch [10]) are polynomially equivalent to quantum Turing machines.”
Background
Research works printed but not linked: 1
- 1997, SIAM J. Comput., 26, 1340
Cited by
Items 201–300 of 1,466
Childs, A. M., Deotto, E., Farhi, E., Goldstone, J., Gutmann, S., & Landahl, A. J. (2002) · Physical Review A · doi:10.1103/physreva.66.032314 · Cited by 81
One complexity theorist's view of quantum computing
Fortnow, L. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00377-2 · Cited by 88
Applying quantum algorithms to constraint satisfaction problems
Campbell, E., Khurana, A., & Montanaro, A. (2019) · Quantum · doi:10.22331/q-2019-07-18-167 · Cited by 76
“This is close to optimal, as even under the promise that S = 1, Ω( √ N) evaluations of f are required to find the unique x such that f(x) = 1 with high probability [19, 96].”
BackgroundEffects of a random noisy oracle on search algorithm complexity
Shenvi, N., Brown, K. R., & Whaley, K. B. (2003) · Physical Review A · doi:10.1103/physreva.68.052313 · Cited by 92
“, where M is the number of states for which f ( x ) = 1 [14, 15, 16, 17].”
BackgroundThreesomes, Degenerates, and Love Triangles
Grønlund, A., & Pettie, S. (2018) · Journal of the ACM · doi:10.1145/3185378 · Cited by 74
“” 2For example, lower bounds for low-depth circuits [48], monotone circuits [9, 66], data structural problems in the cellprobe model [42, 57, 62], restricted decision trees [8, 39], black-box query models [1, 17], or sublinear-space-bounded computation [16].”
BackgroundAnalysis of generalized Grover quantum search algorithms using recursion equations
Biham, E., Biham, O., Biron, D., Grassl, M., Lidar, D. A., & Shapira, D. (2000) · Physical Review A · doi:10.1103/physreva.63.012310 · Cited by 78
Hybrid Quantum-Classical Computing for Future Network Optimization
Fan, L., & Han, Z. (2022) · IEEE Network · doi:10.1109/mnet.001.2200150 · Cited by 73
“Several studies ([8, 9]) demonstrate that the quantum adiabatic algorithm has a quadratic speed advantage over the classical algorithm in search problems.”
BackgroundQuantum Algorithm Design: Techniques and Applications
Shao, C., Yang, L., & Li, H. (2019) · Journal of Systems Science and Complexity · doi:10.1007/s11424-019-9008-0 · Cited by 75
Quantum Query Complexity of Some Graph Problems
Dürr, C., Heiligman, M., Høyer, P., & Mhalla, M. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27836-8_42 · Cited by 72
The Hidden Subgroup Problem - Review and Open ProblemsPreprint
Lomont, C. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0411037 · Cited by 112
“matching algorithm much faster the best classical algorithms given in [80, 22]. Other quantum algorithms are found in [1, 24, 40, 58, 60, 61, 62, 70, 73, 124]. More quantum algorithm overviews are in [7, 17, 32, 50, 86, 99, 116]. Continuous variable algorithms are considered in [85, 104, 105]. A good point to start le…”
BackgroundHogg, T. (2000) · Physical Review A · doi:10.1103/physreva.61.052311 · Cited by 70
Naik, A. S., Yeniaras, E., Hellstern, G., Prasad, G., & Vishwakarma, S. (2025) · Financial Innovation · doi:10.1186/s40854-025-00751-6 · Cited by 106
Quantum Lightning Never Strikes the Same State Twice
Zhandry, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17659-4_14 · Cited by 104
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
Fenner, S., Green, F., Homer, S., & Pruim, R. (1999) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1999.0485 · Cited by 68
Quantum de finetti theorems under local measurements with applications
Brandão, F. G. S. L., & Harrow, A. W. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488718 · Cited by 88
Nondeterministic Quantum Query and Communication Complexities
de Wolf, R. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702407345 · Cited by 97
“The quantum search lower bounds [9, 6] immediately imply T = Ω( √ n).”
BackgroundQuantum search with certainty based on modified Grover algorithms: optimum choice of parameters
Toyama, F. M., van Dijk, W., & Nogami, Y. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0498-0 · Cited by 76
“This is in contradiction to the proved premise that the Grover algorithm is optimal [29–31].”
ResultImproved Bounds on Quantum Learning Algorithms
Atici, A., & Servedio, R. A. (2005) · Quantum Information Processing · doi:10.1007/s11128-005-0001-2 · Cited by 67
“The most frequently considered problem in this setting is to determine whether or not the black-box oracle (which is typically assumed to belong to some particular a priori fixed class C of possible functions) has some specific property, such as being identically 0 [4, 14], being exactly balanced between outputs 0 and…”
BackgroundEntanglement monotone derived from Grover’s algorithm
Biham, O., Nielsen, M. A., & Osborne, T. J. (2002) · Physical Review A · doi:10.1103/physreva.65.062312 · Cited by 73
A Compressed Classical Description of Quantum States
Brandão, F. G. S. L., Kalev, A., Li, T., Lin, C. Y.-Y., Svore, K. M., & Wu, X. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2018.66 · Cited by 47
Botsinis, P., Ng, S. X., & Hanzo, L. (2013) · IEEE Access · doi:10.1109/access.2013.2259536 · Cited by 64
“in [83] proved that Grover’s QSA is asymptotically optimal, by formally showing that there exists no quantum algorithm that can satisfy the search problem in fewer than O( √ N ) computational steps.”
BackgroundEfficient decoding for the Hayden-Preskill protocol
Yoshida, B., & Kitaev, A. (2017) · arXiv · doi:10.48550/arxiv.1710.03363 · Cited by 64
“The Grover algorithm is known to be optimal for the black box search problem in the sense of query complexity [18].”
Revisiting TESLA in the Quantum Random Oracle Model
Alkım, E., Bindel, N., Buchmann, J. A., Dagdelen, Ö., Eaton, E., Gutoski, G., Krämer, J., & Pawlega, F. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59879-6_9 · Cited by 64
A Leap among Quantum Computing and Quantum Neural Networks: A Survey
Massoli, F. V., Vadicamo, L., Amato, G. M., & Falchi, F. (2022) · ACM Computing Surveys · doi:10.1145/3529756 · Cited by 94
““Provable quantum speedup” stems from the existence of a mathematical proof that there is not any classical algorithm that can perform better than the quantum one [25, 80].”
BackgroundExponential Quantum Speedup in Simulating Coupled Classical Oscillators
Babbush, R., Berry, D. W., Kothari, R., Somma, R. D., & Wiebe, N. (2023) · Physical Review X · doi:10.1103/physrevx.13.041041 · Cited by 152
Nishimura, H., & Ozawa, M. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00111-6 · Cited by 81
“[8] showed that an SNQTM that recognizes L with probability uniformly larger than 1−ε in time ct(n) (here, c is a polynomial in log 1 ε and independent of n) can be constructed.”
BackgroundQuantum Computation Beyond the Circuit ModelPreprint
Jordan, S. P. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0809.2307 · Cited by 79
Quantum Optimization: Potential, Challenges, and the Path Forward
Abbas, A., (NNSA), U. N. N. S. A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D., et al. (2023) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/2229681 · Cited by 67
Towards practical applications in quantum computational biology
Fedorov, A. K., & Gelfand, M. S. (2021) · Nature Computational Science · doi:10.1038/s43588-021-00024-z · Cited by 62
Time-marching based quantum solvers for time-dependent linear differential equations
Fang, D., Lin, L., & Tong, Y. (2023) · Quantum · doi:10.22331/q-2023-03-20-955 · Cited by 146
A lower bound on the quantum query complexity of read-once functions
Barnum, H., & Saks, M. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.02.002 · Cited by 73
Quantum Money from Hidden SubspacesPreprint
Aaronson, S., & Christiano, P. F. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.4740 · Cited by 77
Progress in Quantum Algorithms
Shor, P. W. (2004) · Quantum Information Processing · doi:10.1007/s11128-004-3878-2 · Cited by 71
“There is more evidence in this direction, in that there is a proof that a quantum computer cannot search a space of size N in less than O( p N) time. [ 7 ]. This result shows that a”
BackgroundExperimental realization of a fetching algorithm in a 7-qubit NMR spin Liouville space computer
Long, G. L., & Li, X. (2003) · The Journal of Chemical Physics · doi:10.1063/1.1611177 · Cited by 62
Szymanski, T. H. (2022) · IEEE Access · doi:10.1109/access.2022.3169137 · Cited by 59
“It has been proven that unstructured searches cannot reach exponential speedup [68], and that Grover’s Algorithm is asymptotically optimal [80], [81].”
BackgroundA Perspective on Protein Structure Prediction Using Quantum Computers
Doğa, H., Raubenolt, B. A., Cumbo, F., Joshi, J., DiFilippo, F. P., Qin, J., Blankenberg, D. J., & Shehab, O. (2024) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.4c00067 · Cited by 81
“After O ( √ N ) iterations, a measurement will find the entry with high probability, and it has been shown as optimal [56].”
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Kobayashi, H., Matsumoto, K., & Yamakami, T. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-24587-2_21 · Cited by 112
Post-Quantum Cryptography: State of the Art
Buchmann, J. A., Butin, D., Göpfert, F., & Petzoldt, A. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49301-4_6 · Cited by 83
“Such a belief is suggested by certain complexity theoretic arguments (see [5]).”
BackgroundQuantum computing and polynomial equations over Z_2
Dawson, C. M., Haselgrove, H. L., Hines, A. P., Mortimer, D., Nielsen, M. A., & Osborne, T. J. (2005) · Quantum Information and Computation · doi:10.26421/qic5.2-2 · Cited by 25
Anticoncentration theorems for schemes showing a quantum speedup
Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J. (2018) · Quantum · doi:10.22331/q-2018-05-22-65 · Cited by 58
Parthasarathy, R., & Bhowmik, R. T. (2021) · IEEE Access · doi:10.1109/access.2021.3098775 · Cited by 63
“discrete logarithms by means of Shor’s Algorithm and many more [8], [9].”
MethodSingle quantum querying of a database
Terhal, B. M., & Smolin, J. A. (1998) · Physical Review A · doi:10.1103/physreva.58.1822 · Cited by 56
Variational learning of Grover's quantum search algorithm
Morales, M. E. S., Tlyachev, T., & Biamonte, J. (2018) · Physical Review A · doi:10.1103/physreva.98.062333 · Cited by 57
“Grover’s quantum search algorithm has been shown to be asymptotically optimal [2, 3, 21] and hence provides a limiting test case to apply contemporary variational hybrid quantum/classical algorithms to.”
BackgroundMethodReitzner, D., Nagaj, D., & Bužek, V. (2011) · Acta Physica Slovaca Reviews and Tutorials · doi:10.2478/v10155-011-0006-6 · Cited by 86
“In fact, this algorithm is optimal, and the reader can find the instructive proof – an alternative to the BBBV proof [74] in the Hamiltonian oracle model – in the paper47 by Farhi et al.”
MethodNecessary condition for the quantum adiabatic approximation
Boixo, S., & Somma, R. D. (2010) · Physical Review A · doi:10.1103/physreva.81.032308 · Cited by 57
THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS
Laplante, S., Lee, T., & Szegedy, M. (2006) · Computational Complexity · doi:10.1007/s00037-006-0212-7 · Cited by 63
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?Preprint
Kobayashi, H., Matsumoto, K., & Yamakami, T. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0306051 · Cited by 64
A Survey of Quantum Learning Theory
Arunachalam, S., & de Wolf, R. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.06806 · Cited by 43
“Grover [Gro96, BHMT02] came up with a quantum algorithm that finds a solution with high probability using O ( √ N ) queries (this is also known to be optimal [BBBV97]).”
BackgroundExperimental realization of the one qubit Deutsch-Jozsa algorithm in a quantum dot
Bianucci, P., Müller, A., Shih, C.-K. K., Wang, Q., Xue, Q. K., & Piermarocchi, C. (2004) · Physical Review B · doi:10.1103/physrevb.69.161303 · Cited by 60
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
Aaronson, S., & Ambainis, A. (2018) · SIAM Journal on Computing · doi:10.1137/15m1050902 · Cited by 109
Depth optimization of quantum search algorithms beyond Grover's algorithm
Zhang, K., & Korepin, V. E. (2020) · Physical Review A · doi:10.1103/physreva.101.032346 · Cited by 70
Measuring energy, estimating Hamiltonians, and the time-energy uncertainty relation
Aharonov, Y., Massar, S., & Popescu, S. (2002) · Physical Review A · doi:10.1103/physreva.66.052107 · Cited by 65
Introduction to quantum algorithms
Shor, P. W. (2002) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/058/1922896 · Cited by 76
“If you are searching an unordered database, this square root speed-up is as good as a quantum computer can do; this is proved using techniques developed in [7].”
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Aaronson, S., & Ambainis, A. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746547 · Cited by 120
“[7] C.”
MethodOzols, M., Roetteler, M., & Roland, J. (2013) · ACM Transactions on Computation Theory · doi:10.1145/2493252.2493256 · Cited by 53
Quantum-Access-Secure Message Authentication via Blind-Unforgeability
Alagic, G., Majenz, C., Russell, A. C., & Song, F. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45727-3_27 · Cited by 79
Quantum algorithms for subset finding
Childs, A. M., & Eisenberg, J. M. (2003) · CERN Document Server (European Organization for Nuclear Research) · Cited by 54
Regular Languages Accepted by Quantum Automata
Bertoni, A., & Carpentieri, M. (2001) · Information and Computation · doi:10.1006/inco.2000.2911 · Cited by 56
On the insecurity of quantum Bitcoin mining
Sattath, O. (2020) · International Journal of Information Security · doi:10.1007/s10207-020-00493-9 · Cited by 60
“probability at least 2 3 using only O q N K queries [Gro96] (see also the standard text-book [NC11]). Furthermore, Kneed not be known in advance [BBHT05]. Grover’s algorithm is known to be optimal [BBBV97]. The above paragraph is the standard way Grover’s algorithm is presented. Here is a slightly stronger formulation…”
MethodQuantum Complexities of Ordered Searching, Sorting, and Element Distinctness
Høyer, P., Neerbek, J., & Shi, Y. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_29 · Cited by 81
Symmetry-Assisted Adversaries for Quantum State Generation
Ambainis, A., Magnin, L., Roetteler, M., & Roland, J. (2011) · 2011 IEEE 26th Annual Conference on Computational Complexity · doi:10.1109/ccc.2011.24 · Cited by 49
“Roughly speaking, currently there are two main ideas for proving lower bounds on quantum query complexity: the polynomial method [6], [7], [8], [9], [10], [11] and the adversary method [12].”
BackgroundMethodAaronson, S., Beigi, S., Drucker, A., Fefferman, B., & Shor, P. W. (2009) · Theory of Computing · doi:10.4086/toc.2009.v005a001 · Cited by 79
“For otherwise, by the hybrid argument of Bennett, Bernstein, Brassard, and Vazirani [4], Arthur’s verification algorithm would not have Ω (1 / poly ( n )) soundness (i.e., Arthur would fail to detect a change in f ( x ∗ ) from 1 to 0).”
InfluentialQuantum Computational Complexity
Watrous, J. (2011) · Springer eBooks · doi:10.1007/978-1-4614-1800-9_147 · Cited by 65
Quantum associative memory with distributed queries
Ezhov, A. A., Nifanova, A. V., & Ventura, D. A. (2000) · Information Sciences · doi:10.1016/s0020-0255(00)00057-8 · Cited by 53
“Further, it has been proved that the efficiency of Grover’s algorithm is optimal for quantum search [ 13 ].”
BackgroundQuantum Pseudorandomness and Classical Complexity
Kretschmer, W. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.tqc.2021.2 · Cited by 178
An overview of Quantum Cryptography and Shor’s Algorithm
(2020) · International Journal of Advanced Trends in Computer Science and Engineering · doi:10.30534/ijatcse/2020/214952020 · Cited by 59
“Public-key and secret-key cryptology are the main two currently in use, and in both of Figure 1: Comparing Classical bit and Qubit Source: [14]”
BackgroundCounting, fanout and the complexity of quantum ACC
Green, F., Homer, S. T., Moore, C., & Pollett, C. (2002) · Quantum Information and Computation · doi:10.26421/qic2.1-3 · Cited by 95
Quantum Algorithms for Linear Algebra and Machine Learning.
Prakash, A. (2014) · eScholarship (California Digital Library) · Cited by 105
Somma, R. D., & Boixo, S. (2013) · SIAM Journal on Computing · doi:10.1137/120871997 · Cited by 43
“Quantum algorithms that solve SEARCH with Θ( √ M) uses of Qx, and other x-independent operations, exist [7, 21].”
MethodA quantum computer only needs one universe
Steane, A. M. (2003) · Studies in History and Philosophy of Science Part B Studies in History and Philosophy of Modern Physics · doi:10.1016/s1355-2198(03)00038-8 · Cited by 69
“One practical result is that quantum computation cannot give an efficient algorithm for the unstructured search problem ( Bennett, Bernstein, Brassard, & Vazirani, 1997 ).”
BackgroundCommunication Capacity of Quantum Computation
Bose, S., Rallan, L., & Vedral, V. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.5448 · Cited by 56
Quantum entanglement and the communication complexity of the inner product function
Cleve, R., van Dam, W., Nielsen, M. A., & Tapp, A. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.12.012 · Cited by 101
A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
Farhi, E., Goldstone, J., & Gutmann, S. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0007071 · Cited by 42
“this problem requires exponential time even on a quantum computer[ 2 , 3]. To confirm this we generated 100 instances of EC2 for each of n = 7,8,9,10,11,12.”
BackgroundThe Need for Structure in Quantum SpeedupsPreprint
Aaronson, S., & Ambainis, A. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0911.0996 · Cited by 75
“orithm to solve this problem using O( √ N) queries [20], as compared to the Ω(N) needed classically. However, this quadratic speedup is optimal, as shown by Bennett, Bernstein, Brassard, and Vazirani [10]. For other “unstructured” problems—such as computing the Parityor Majorityof an N-bit string— quantum computers off…”
MethodPost-quantum distributed ledger technology: a systematic survey
Parida, N. K., Jatoth, C., Reddy, V. D., Hussain, M. M., & Faizi, J. (2023) · Scientific Reports · doi:10.1038/s41598-023-47331-1 · Cited by 69
“• Secret key-based cryptosystems: Quantum computing will not be beneficial when it comes to exhaustive search 95,96 .”
BackgroundCatalysis in quantum information theory
Lipka-Bartosik, P., Wilming, H., & Ng, N. H. Y. (2024) · Reviews of Modern Physics · doi:10.1103/revmodphys.96.025005 · Cited by 104
Kashefi, E., Kent, A., Vedral, V., & Banaszek, K. (2002) · Physical Review A · doi:10.1103/physreva.65.050304 · Cited by 65
Effect of unitary noise on Grover’s quantum search algorithm
Shapira, D., Mozes, S., & Biham, O. (2003) · Physical Review A · doi:10.1103/physreva.67.042301 · Cited by 60
Coined quantum walks on percolation graphs
Leung, G., Knott, P., Bailey, J., & Kendon, V. M. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/12/123018 · Cited by 53
“[13] proved that basic quantum walk searching is quadratically faster, the maximum speed up that can be achieved for unordered searching [14].”
BackgroundQuantum Differential Equation Solvers: Limitations and Fast-Forwarding
An, D., Liu, J.-P., Wang, D., & Zhao, Q. (2025) · Communications in Mathematical Physics · doi:10.1007/s00220-025-05358-7 · Cited by 104
Finding spin glass ground states using quantum walks
Callison, A., Chancellor, N., Mintert, F., & Kendon, V. M. (2019) · New Journal of Physics · doi:10.1088/1367-2630/ab5ca2 · Cited by 61
“Due to the absence of structure in the search problem specifically, such a quadratic speed up has been proven to the best possible quantum speed up (Bennett et al 1997).”
BackgroundNew Approaches for Quantum Copy-Protection
Aaronson, S., Liu, J., Liu, Q., Zhandry, M., & Zhang, R. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-84242-0_19 · Cited by 48
An optical model of computation
Woods, D., & Naughton, T. J. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.07.001 · Cited by 48
“[2] have shown the work of Grover is optimal up to a multiplicative constant, and that in fact any quantum mechanical system will require ( √ n) comparisons.”
BackgroundPolynomial degree vs. quantum query complexity
Ambainis, A. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238197 · Cited by 78
“They follow by two methods: adversary [10, 4] and p olynomials method [9].”
BackgroundMethodLower Bounds on Quantum Query ComplexityPreprint
Høyer, P., & Špalek, R. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0509153 · Cited by 67
Distributed Grover's algorithm
Qiu, D., Luo, L., & Xiao, L. (2024) · Theoretical Computer Science · doi:10.1016/j.tcs.2024.114461 · Cited by 83
Application of Quantum Recurrent Neural Network in Low-Resource Language Text Classification
Yu, W., Yin, L., Zhang, C., Chen, Y., & Liu, A. X. (2024) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2024.3373903 · Cited by 54
“As one of the classical subfields of machine learning [1], [2, pp. 14–16], [3, pp. 5–25], natural language processing (NLP) [4], [5] has been a hot research topic in recent years.”
BackgroundQuantum computing and hidden variables
Aaronson, S. (2005) · Physical Review A · doi:10.1103/physreva.71.032325 · Cited by 63
Trade-offs in the quantum search algorithm
Grover, L. K. (2002) · Physical Review A · doi:10.1103/physreva.66.052314 · Cited by 61
Noise-based logic hyperspace with the superposition of states in a single wire
Kish, L. B., Khatri, S. P., & Sethuraman, S. (2009) · Physics Letters A · doi:10.1016/j.physleta.2009.03.059 · Cited by 48
PT -symmetric Hamiltonians and their application in quantum information
Croke, S. (2015) · Physical Review A · doi:10.1103/physreva.91.052113 · Cited by 54
Is partial quantum search of a database any easier?
Grover, L. K., & Radhakrishnan, J. (2005) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1073970.1073997 · Cited by 68
Buhrman, H., Fortnow, L., Newman, I., & Röhrig, H. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539704442416 · Cited by 71
“But by Beals, Buhrman, Cleve, Mosca, and de Wolf [5], the acceptance probability of A can be written as a multi- linear polynomial of degree at most 2q where the n vari- ables are the bits of the input; using results of Bennett, Bernstein, Brassard, and Vazirani [6] and Solovay and Yao [25], any quantum algorithm can…”
MethodInfluentialMosca, M., & Stebila, D. (2010) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/523/10311 · Cited by 70
Dalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., & Veshchezerova, M. (2021) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-021-00100-3 · Cited by 46
An Introduction to Quantum Computing, without the Physics
Nannicini, G. (2020) · SIAM Review · doi:10.1137/18m1170650 · Cited by 59
Quantum algorithms for the ordered search problem via semidefinite programming
Childs, A. M., Landahl, A. J., & Parrilo, P. A. (2007) · Physical Review A · doi:10.1103/physreva.75.032335 · Cited by 46
Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT dualityPreprint
Bouland, A., Fefferman, B., & Vazirani, U. V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.14646 · Cited by 94
“From there, a query lower bound can readily be established by invoking a standard hybrid argument [BBBV97].”
BackgroundResultInfluentialSelf-citationSpatial search by continuous-time quantum walks on crystal lattices
Childs, A. M., & Ge, Y. (2014) · Physical Review A · doi:10.1103/physreva.89.052337 · Cited by 48
“A classical computer takes Θ( N ) steps to find this item with constant probability, but Grover’s algorithm [1] shows that a quantum computer can solve this problem using only O ( √ N ) steps, which is optimal [2].”
BackgroundQuantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise
Morley, J. G., Chancellor, N., Bose, S., & Kendon, V. M. (2019) · Physical Review A · doi:10.1103/physreva.99.022339 · Cited by 54
Metadata
- Authors
- Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U.
- Affiliations
- Microsoft (United States) (US)
- ORCID
- Bennett, Charles H.
- Venue
- SIAM Journal on Computing
- Published
- 1997-10
- Volume
- 26
- Issue
- 5
- Pages
- 1510-1523
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2006290558
- Semantic Scholar
- 76ba917d0b172593b20bbb1acefc64a6fb0682f5
- Cited by
- 1,470
- References
- 18
- Citations by year
- 2026: 44 · 2025: 65 · 2024: 78 · 2023: 94 · 2022: 64 · 2021: 84 · 2020: 61 · 2019: 74 · 2018: 56 · 2017: 34 · 2016: 55 · 2015: 50 · 2014: 46 · 2013: 40 · 2012: 43
- FWCI
- 45.78
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- SIAM Journal on Computing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- SIAM Journal on Scientific and Statistical Computing
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- quantum computing, quantum Turing machines, oracle separation, NP, coNP, quantum algorithms, Grover's algorithm, Shor's algorithm, factoring, discrete logarithm problem, quantum vs classical computation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
The claim verdicts this report counts are experimental: their accuracy is not yet measured.
A language model drew the claims from the paper on 2026-10-21, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-21 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Cited sources are checked with a language model’s help (gpt-6-sol).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.