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 301–400 of 1,466
Nonlinear quantum neuron: A fundamental building block for quantum neural networks
Yan, S., Qi, H., & Cui, W. (2020) · Physical Review A · doi:10.1103/physreva.102.052421 · Cited by 47
Implementation of efficient quantum search algorithms on NISQ computers
Zhang, K., Rao, P., Yu, K., Lim, H., & Korepin, V. E. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03165-2 · Cited by 61
Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
Shimoni, Y., Shapira, D., & Biham, O. (2004) · Physical Review A · doi:10.1103/physreva.69.062303 · Cited by 47
Sublinear quantum algorithms for training linear and kernel-based classifiersPreprint
Li, T., Chakrabarti, S., & Wu, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.02276 · Cited by 91
“We prove both theorems by constructing reductions to the quantum search lower bound (Bennett et al., 1997); their full proofs are deferred to the supplementary material.”
Fifty years of P vs. NP and the possibility of the impossible
Fortnow, L. (2021) · Communications of the ACM · doi:10.1145/3460351 · Cited by 63
“Unfortunately, there are limits to how a quantum algorithm can manipulate these states, and all evidence suggests that quantum computers cannot solve NP-complete problems, 3 beyond a quadratic improvement given by Grover’s algorithm.”
BackgroundBetter-than-classical Grover search via quantum error detection and suppression
Pokharel, B., & Lidar, D. A. (2024) · npj Quantum Information · doi:10.1038/s41534-023-00794-6 · Cited by 65
Computation in generalised probabilisitic theories
Lee, C. M., & Barrett, J. (2015) · New Journal of Physics · doi:10.1088/1367-2630/17/8/083001 · Cited by 58
Generalized quantum search with parallelism
Gingrich, R. M., Williams, C. P., & Cerf, N. J. (2000) · Physical Review A · doi:10.1103/physreva.61.052313 · Cited by 51
“hat if we restrict the analysis some more to the case where |ai is given by equation 7, and there is only one target state then Tavg (nopt) ≃ 0.6900 √ N. This is faster than the lower bounds in [20], [1], [3], and [25], but we are using a somewhat different model. They are looking at the minimum time it would take with…”
BackgroundInfluentialGrover's Algorithm: Quantum Database SearchPreprint
Lavor, C., MANSSUR, L. R. U., & Portugal, R. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0301079 · Cited by 68
Mosca, M. (2009) · Springer eBooks · doi:10.1007/978-0-387-30440-3_423 · Cited by 52
“If we only learn about f by applying the black-box Uf , then any algorithm that finds a solution with high probability for any f (even if we just restrict to functions f with at most one solution) requires Ω( √ 2n) applications of Uf [25].”
MethodOn Finding Quantum Multi-collisions
Liu, Q., & Zhandry, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17659-4_7 · Cited by 57
Quantum Information Processing Algorithms with Emphasis on Machine Learning
Uehara, G. S., Spanias, A., & Clark, W. (2021) · International Conference on Information, Intelligence, Systems & Applications (IISA) · doi:10.1109/iisa52424.2021.9555570 · Cited by 49
Characterizing Grover search algorithm on large-scale superconducting quantum computers
AbuGhanem, M. (2025) · Scientific Reports · doi:10.1038/s41598-024-80188-6 · Cited by 63
“It stands as the optimal search algorithm for quantum architectures [15], finding utility as a foundational component for quantum algorithms [16, 17].”
BackgroundA review of procedures to evolve quantum algorithms
Gepp, A., & Stocks, P. (2009) · Genetic Programming and Evolvable Machines · doi:10.1007/s10710-009-9080-7 · Cited by 46
“Further details on quantum complexity classes are outside the scope of this paper, but more information on the BQP complexity class is presented by Fortnow and Rogers [24], and [8, 77] detail quantum computing complexity in time and space respectively.”
BackgroundSpatial search on a honeycomb network
Abal, G., DONANGELO, R., Marquezino, F. D. L., & PORTUGAL, R. (2010) · Mathematical Structures in Computer Science · doi:10.1017/s0960129510000332 · Cited by 50
Quantum certificate complexity
Aaronson, S. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.06.020 · Cited by 61
Impossibility of a Quantum Speed-Up with a Faulty Oracle
Regev, O., & Schiff, L. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_63 · Cited by 77
“Moreover, it is known that this is optimal (see, e.g., [4, 5, 1]).”
BackgroundAnalogies and differences between quantum and stochastic automata
Bertoni, A., & Carpentieri, M. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00154-7 · Cited by 52
Navigating the quantum computing threat landscape for blockchains: A comprehensive survey
Khodaiemehr, H., Bagheri, K., & Feng, C. (2025) · Computer Science Review · doi:10.1016/j.cosrev.2025.100846 · Cited by 44
Improved Classical and Quantum Algorithms for Subset-Sum
Bonnetain, X., Bricout, R., Schrottenloher, A., & Shen, Y. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64834-3_22 · Cited by 66
Quantum Query Complexity for Some Graph Problems
Bērziņa, A., Dubrovsky, A., Freivalds, R., Lāce, L., & Scegulnaja-Dubrovska, O. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24618-3_11 · Cited by 41
“It is proved in [ 3 ] that no quantum query algorithm exists for PARITY with Ω(N ) queries.”
BackgroundQuantum proofs for classical theorems
(2011) · Theory of Computing · doi:10.4086/toc.gs.2011.002 · Cited by 41
“[27], addressed this problem by providing a general method for quantum lower bounds, the quantum adversary, which exploits unitarity in a crucial way and which in certain cases yields a provably better bound than the polynomial method [15].”
MethodBlack-box Hamiltonian simulation and unitary implementation
Berry, D. W., & Childs, A. M. (2012) · Quantum Information and Computation · doi:10.26421/qic12.1-2 · Cited by 47
“By the lower bound for search [20], preparation of an M - dimensional black-box quantum state requires Ω( √ M ) queries, so this state preparation scheme is optimal.”
BackgroundInfluentialTight Quantum Time-Space Tradeoffs for Function Inversion
Chung, K.-M., Guo, S., Liu, Q., & Qian, L. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00068 · Cited by 50
“Grover [Gro96] considered the same problem in the context of database search, and showed that quantum computers can invert any function in time only ˜ O ( √ N ) , which was subsequently shown to be tight [BBBV97].”
BackgroundA better lower bound for quantum algorithms searching an ordered list
Ambainis, A. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814606 · Cited by 50
“6A hybrid argument[2, 15] is an argument that bounds the difference between the final superpositions of a quantum algorithm on two inputs by”
BackgroundInfluentialQuantum games and quantum algorithms
Meyer, D. (2002) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/305/05221 · Cited by 58
Deriving Grover's lower bound from simple physical principles
Lee, C. M., & Selby, J. H. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/9/093047 · Cited by 47
“The importance of Grover’s algorithm stems from the ubiquitous nature of the search problem and its relation to solvingNP-complete problems [6].”
BackgroundQuantum de Finetti Theorems Under Local Measurements with Applications
Brandão, F. G. S. L., & Harrow, A. W. (2017) · Communications in Mathematical Physics · doi:10.1007/s00220-017-2880-3 · Cited by 66
Zhandry, M. (2021) · Journal of Cryptology · doi:10.1007/s00145-020-09372-x · Cited by 77
Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
Rall, P. (2021) · Quantum · doi:10.22331/q-2021-10-19-566 · Cited by 84
Quantum versus Classical Proofs and Advice
Aaronson, S., & Kuperberg, G. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.27 · Cited by 79
Solving the subset-sum problem with a light-based device
Oltean, M., & Muntean, O. (2007) · Natural Computing · doi:10.1007/s11047-007-9059-3 · Cited by 39
On Quantum ObfuscationPreprint
Alagic, G., & Fefferman, B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.01771 · Cited by 67
“is taken over the uniformly random choice of a and b as well as all of the measurement outcomes of S. The aboveis an easy corollary of the tightness of the Groverbound for unstructured quantum search [9]. Indeed, given the definitions of Ua,b and D′a ,b, it’s clear that with only polynomial queries and no knowledge of…”
BackgroundConvex optimization using quantum oracles
van Apeldoorn, J., Gilyén, A., Gribling, S., & de Wolf, R. (2020) · Quantum · doi:10.22331/q-2020-01-13-220 · Cited by 110
Quantum Identification of Boolean Oracles
Ambainis, A., Iwama, K., Kawachi, A., Masuda, H., Putra, R. H., & Yamashita, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24749-4_10 · Cited by 53
“The classical adversary method was used in [11, 30], which is also called the hybrid argument.”
MethodBuilding Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgård Constructions
Hosoyamada, A., & Yasuda, K. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-03326-2_10 · Cited by 43
“Our tool is developed by generalizing and integrating several existing techniques [5,28,2,15] corresponding to some limited cases of the simplified version.”
MethodNew quantum algorithm for studying NP-complete problemsPreprint
Ohya, M., & Volovich, I. V. (2003) · Cited by 38
Qunity: A Unified Language for Quantum and Classical Computing
Voichick, F., Li, L., Rand, R., & Hicks, M. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3571225 · Cited by 71
The Fiat–Shamir Transformation in a Quantum World
Dagdelen, Ö., Fischlin, M., & Gagliardoni, T. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42045-0_4 · Cited by 37
On Grover’s search algorithm from a quantum information geometry viewpoint
Cafaro, C., & Mancini, S. (2011) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.09.018 · Cited by 45
“Indeed, it was shown in [32] that relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time (cid:16) (cid:17) Drawing on this result, Grover pointed out in [33] that his algorithm is optimal (i.e., the fastest), up to a…”
BackgroundAdiabatic quantum computing with spin qubits hosted by molecules
Yamamoto, S., Nakazawa, S., Sugisaki, K., Sato, K., Toyota, K., Shiomi, D., & Takui, T. (2015) · Physical Chemistry Chemical Physics · doi:10.1039/c4cp04744c · Cited by 40
Quantum search algorithms on a regular lattice
Hein, B., & Tanner, G. (2010) · Physical Review A · doi:10.1103/physreva.82.012326 · Cited by 40
“Note, that the bound for d ≥ 3 is tight, because we know from [11, 19], that the search can not be faster than √ N .”
BackgroundCounting by quantum eigenvalue estimation
Mosca, M. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00217-6 · Cited by 41
Limitations of quantum coset states for graph isomorphism
Hallgren, S., Moore, C., Rötteler, M., Russell, A. C., & Sen, P. (2010) · Journal of the ACM · doi:10.1145/1857914.1857918 · Cited by 59
Decoherence, Control, and Symmetry in Quantum ComputersPreprint
Bacon, D. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0305025 · Cited by 64
PQFabric: A Permissioned Blockchain Secure from Both Classical and Quantum Attacks
Holcomb, A., Pereira, G. C. C. F., Das, B., & Mosca, M. (2021) · IEEE International Conference on Blockchain and Cryptocurrency (ICBC) · doi:10.1109/icbc51069.2021.9461070 · Cited by 48
“Cryptographic hashes are not broken by quantum computers, but their preimage-resistance security is reduced by half and collision-resistance is reduced from N/2-bit security to about N/3 bits for an N -bit output hash [16], [17].”
BackgroundA new quantum-safe multivariate polynomial public key digital signature algorithm
Kuang, R., Perepechaenko, M., & Barbeau, M. (2022) · Scientific Reports · doi:10.1038/s41598-022-15843-x · Cited by 46
Cryptographic Hardness Based on the Decoding of Reed–Solomon Codes
Kiayias, A., & Yung, M. M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.921876 · Cited by 36
Secure identity-based encryption in the quantum random oracle model
Zhandry, M. (2015) · International Journal of Quantum Information · doi:10.1142/s0219749915500148 · Cited by 36
All Quantum Adversary Methods Are Equivalent
Špalek, R., & Szegedy, M. (2005) · Lecture notes in computer science · doi:10.1007/11523468_105 · Cited by 70
The computational landscape of general physical theories
Barrett, J., de Beaudrap, N., Hoban, M. J., & Lee, C. M. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0156-9 · Cited by 54
“50 This speed-up is optimal for quantum computers, 51 – 54 so any set of physical principles which imply it could be argued to capture some of the essence of quantum computation.”
BackgroundA Comprehensive Survey on Quantum Machine Learning and Possible Applications
Umer, M. J., & Sharif, M. I. (2022) · International Journal of E-Health and Medical Communications · doi:10.4018/ijehmc.315730 · Cited by 52
“Bennett et al. presented a study to discuss the strength and weaknesses of quantum computing (Bennett et al., 1997).”
BackgroundVerifiable Quantum Advantage without Structure
Yamakawa, T., & Zhandry, M. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00014 · Cited by 100
“Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.”
ResultOpening the Black Box inside Grover’s Algorithm
Stoudenmire, E. M., & Waintal, X. (2024) · Physical Review X · doi:10.1103/physrevx.14.041029 · Cited by 74
On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
Chung, K.-M., Fehr, S., Huang, Y., & Liao, T.-N. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-77886-6_21 · Cited by 79
Quantum Speedup for Protein Structure Prediction
Wong, R., & Chang, W.-L. (2021) · IEEE Transactions on NanoBioscience · doi:10.1109/tnb.2021.3065051 · Cited by 41
“Grover’s quantum search algorithm, which offers a quadratic improvement in performance over classical search algorithms, asymptotically the best achievable quantum speedup on hard, classically intractable problems [5]–[7] such as PSP.”
BackgroundFast quantum algorithm for protein structure prediction in hydrophobic-hydrophilic model
Wong, R., & Chang, W.-L. (2022) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2022.03.011 · Cited by 44
The geometry of quantum learning
Hunziker, M., Meyer, D., Park, J., Pommersheim, J., & Rothstein, M. J. (2009) · Quantum Information Processing · doi:10.1007/s11128-009-0129-6 · Cited by 43
“This restricted problem is easily seen to be equivalent to an unstructured search on a set of size N/d, which is known to require ( √ N/d) (as shown in [26]).”
BackgroundDuwell, A. (2021) · Cambridge University Press eBooks · doi:10.1017/9781009104975 · Cited by 38
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/82952020 · Cited by 56
Quantum Algorithms for Weighing Matrices and Quadratic Residues
van, D. (2002) · Algorithmica · doi:10.1007/s00453-002-0975-4 · Cited by 45
“…Simon[26], Grover[15], and Buhrman & van Dam[8] define problems for which we have a quantum reduction in the query complexity, whereas the lower bounds of Jozsa[20], Bennett et al. [2], and Beals et al. [1] show that there are limits to the advantage that quantum computation can give us.”
BackgroundA Foundation of Programming a Multi-tape Quantum Turing Machine
Yamakami, T. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48340-3_39 · Cited by 35
Search on a hypercubic lattice using a quantum random walk. I. d>2
Patel, A. D., & Rahaman, M. A. (2010) · Physical Review A · doi:10.1103/physreva.82.032330 · Cited by 33
Quantum Technology for Economists
Hull, I., Sattath, O., Diamanti, E., & Wendin, G. P. (2024) · Contributions to economics · doi:10.1007/978-3-031-50780-9 · Cited by 36
“retic no-cloning theorem combines two elements: (1) the original no-cloning theorem; and (2) the quadratic upper-bound on the quantum speedup achievable in unstructured search problems (Grover, 1996; Bennett et al., 1997). It shows that a counterfeiter who has access to krandom, valid bills needs to perform / p 2n que…”
BackgroundPost-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably
Lombardi, A., Ma, F., & Spooner, N. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00086 · Cited by 53
“7 When defining quantum zero-knowledge simulation, [20, Page 12] requires that the simulator is a quantum Turing machine with expected polynomial runtime, and refers to [22] (which uses the [19] definition of a quantum Turing machine) for the quantum Turing machine model.”
BackgroundOn the power of quantum proofs
Raz, R., & Shpilka, A. (2004) · Conference on Computational Complexity · doi:10.1109/ccc.2004.21 · Cited by 31
Continuous-time quantum search on balanced trees
Philipp, P., Tarrataca, L. D. T. J., & Boettcher, S. (2016) · Physical Review A · doi:10.1103/physreva.93.032305 · Cited by 36
“Grover’s algorithm [14] provides a way to perform a discrete-time quantum search in an unstructured space with O( √ N) oracle queries, which is optimal [3].”
MethodQuantum copy-protection of compute-and-compare programs in the quantum random oracle model
Coladangelo, A., Majenz, C., & Poremba, A. (2024) · Quantum · doi:10.22331/q-2024-05-02-1330 · Cited by 58
Merkle Puzzles in a Quantum World
Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., & Salvail, L. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_22 · Cited by 36
“Even with a quantum computer, the eavesdropper needs Ω( √ N3 ) = Ω(N3/2) queries using Grover, which is optimal [3].”
Self-citationNew quantum algorithm for studying NP-complete problems
Ohya, M., & Volovich, I. V. (2003) · Reports on Mathematical Physics · doi:10.1016/s0034-4877(03)90002-4 · Cited by 34
“It is known that this approach is not powerful enough to solve NP-complete problems [4, 5].”
BackgroundLimitations of quantum advice and one-way communication
Aaronson, S. (2004) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2004.1313854 · Cited by 69
Quantum AlgorithmsPreprint
Mosca, M. (2008) · arXiv (Cornell University) · Cited by 30
Aaronson, S. (2016) · Springer eBooks · doi:10.1007/978-3-319-32162-2_1 · Cited by 70
Golden, J. K., Bärtschi, A., O’Malley, D., & Eidenbenz, S. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00063 · Cited by 61
“We provide a clear example problem in this article showing that a QAOA variation indeed is able to exploit structure by exponentially outperforming unstructured search and thus overcoming the lower bound of unstructured search [11].”
BackgroundHigh-fidelity adiabatic quantum computation via dynamical decoupling
Quiroz, G., & Lidar, D. A. (2012) · Physical Review A · doi:10.1103/physreva.86.042333 · Cited by 37
Quantum Existence Testing and Its Application for Finding Extreme Values in Unsorted Databases
Imre, S. (2007) · IEEE Transactions on Computers · doi:10.1109/tc.2007.1032 · Cited by 34
“gave the first proof of the optimality of Grover’s algorithm in [7].”
BackgroundSearch an unsorted database with quantum mechanics
Long, G., & Liu, Y. (2007) · Frontiers of Computer Science in China · doi:10.1007/s11704-007-0026-z · Cited by 33
Groverian measure of entanglement for mixed states
Shapira, D., Shimoni, Y., & Biham, O. (2006) · Physical Review A · doi:10.1103/physreva.73.044301 · Cited by 32
A UAV-Assisted UE Access Authentication Scheme for 5G/6G Network
Ma, R., Cao, J. P., He, S., Zhang, Y., Niu, B., & Li, H. (2023) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2023.3341829 · Cited by 30
“Additionally, it has been proven that symmetric algorithms and hash functions should be usable in a quantum era [51].”
BackgroundHow to Construct Quantum Random Functions
Zhandry, M. (2021) · Journal of the ACM · doi:10.1145/3450745 · Cited by 69
Number Partitioning With Grover’s Algorithm in Central Spin Systems
Anikeeva, G., Marković, O., Borish, V., Hines, J., Rajagopal, S., Cooper, E. S., Periwal, A., Safavi‐Naeini, A. H., Davis, E. J., & Schleier-Smith, M. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.020319 · Cited by 37
“Thus, the generalized oracle with the critical step width γ c suffices to achieve an O ( √ N ) speedup, the same scaling that is achieved by the ideal oracle and proven to be optimal for an unstructured search [52–54].”
BackgroundEstimating distinguishability measures on quantum computers
Rethinasamy, S., Agarwal, R., Sharma, K., & Wilde, M. M. (2023) · Physical Review A · doi:10.1103/physreva.108.012409 · Cited by 60
Groppe, S., & Groppe, J. (2021) · International Database Engineering and Applications Symposium (IDEAS) · doi:10.1145/3472163.3472164 · Cited by 46
“runtime of 4 · √ N basic steps and claimed based on a result in [3] that up to a multiplicative constant among all possible quantum algorithms the optimality of his algorithm can be proven.”
BackgroundIntroduction to Quantum-Resistant Blockchain
Unogwu, O. J., Doshi, R., Hiran, K. K., & Mijwil, M. M. (2022) · Advances in data mining and database management book series · doi:10.4018/978-1-6684-5072-7.ch002 · Cited by 33
Buniy, R. V., Hsu, S. D. H., & Zee, A. (2005) · Physics Letters B · doi:10.1016/j.physletb.2005.09.084 · Cited by 36
Generalizing cryptosystems based on the subset sum problem
Kate, A., & Goldberg, I. (2011) · International Journal of Information Security · doi:10.1007/s10207-011-0129-2 · Cited by 30
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
Aaronson, S., Ben-David, S., Kothari, R., Rao, S., & Tal, A. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451047 · Cited by 91
“(This can also be proved directly using the lower bound method in [14].”
BackgroundMethodQCB: Efficient Quantum-Secure Authenticated Encryption
Bhaumik, R., Bonnetain, X., Chailloux, A., Leurent, G., Naya‐Plasencia, M., Schrottenloher, A., & Seurin, Y. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92062-3_23 · Cited by 37
“Theorem 1 (Adapted from [6], Theorem 3.”
MethodElectric-Circuit Realization of Fast Quantum Search
Pan, N., Chen, T., Sun, H., & Zhang, X. (2021) · Research · doi:10.34133/2021/9793071 · Cited by 34
On the Feasibility of Unclonable Encryption, and More
Ananth, P., Kaleoglu, F., Li, X., Liu, Q., & Zhandry, M. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15979-4_8 · Cited by 55
Bounds on the Power of Constant-Depth Quantum Circuits
Fenner, S., Green, F., Homer, S. T., & Zhang, Y. (2005) · Lecture notes in computer science · doi:10.1007/11537311_5 · Cited by 31
Adiabatic quantum search algorithm for structured problems
Roland, J., & Cerf, N. J. (2003) · Physical Review A · doi:10.1103/physreva.68.062312 · Cited by 34
The Multiplicative Quantum Adversary
Špalek, R. (2008) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2008.9 · Cited by 42
Quantum Computing and Phase Transitions in Combinatorial Search
Hogg, T. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.204 · Cited by 34
A New Approach for Algebraically Homomorphic Encryption.
Armknecht, F., & Sadeghi, A. (2008) · MADOC (University of Mannheim) · Cited by 29
Quantum versus classical learnability
Servedio, R. A., & Gortler, S. J. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2001.933881 · Cited by 45
“For example, a well-known result due to Deutsch and Jozsa [17] shows that exponentially fewer queries are required in the quantum model in order to determine with certainty whether a black-box oracle computes a constant Boolean function or a function which is balanced between outputs 0 and1:More recently, several rese…”
BackgroundMethodResultInfluentialSzegedy’s quantum walk with queries
Santos, R. A. M. (2016) · Quantum Information Processing · doi:10.1007/s11128-016-1427-4 · Cited by 31
“This algorithm is optimal [17].”
Optimization of partial search
Korepin, V. E. (2005) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/38/44/l02 · Cited by 31
Quantum Search on Structured Problems
Grover, L. K. (1999) · Chaos Solitons & Fractals · doi:10.1016/s0960-0779(98)00217-3 · Cited by 34
Power of Quantum Computation with Few Clean Qubits
Fujii, K., Kobayashi, H., Morimae, T., Nishimura, H., Tamate, S., & Tani, S. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2016.13 · Cited by 26
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.