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-19 · 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
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
“oblem. For such hard combinatorial search problems we probably can’t do much better than exhaustively searching for a solution. Quantum computers can speed up exhaustive search [6], but only modestly [7], so NP-hard problems are likely to be quantumly hard as well as classically hard. For a physicist seeking problems…”
BackgroundA 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
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
“However, since it is impossible to achieve a better-than-quadratic speedup in the Grover search problem without introducing an explicit dependence on the marked state (Bennett et al., 1997), this result is not conclusive in linking entanglement with enhanced computational efficiency.”
BackgroundMethodBernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Self-citationSteane, A. (1998) · Reports on Progress in Physics · doi:10.1088/0034-4885/61/2/002 · Cited by 1,391
Steane, A. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9708022 · Cited by 1,390
On 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
Self-citationQuantum random-walk search algorithm
Shenvi, N., Kempe, J., & Whaley, K. B. (2003) · Physical Review A · doi:10.1103/physreva.67.052307 · Cited by 1,150
The role of relative entropy in quantum information theory
Vedral, V. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.197 · Cited by 1,166
Two-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069
Report on Post-Quantum Cryptography
Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., & Smith-Tone, D. (2016) · doi:10.6028/nist.ir.8105 · Cited by 1,034
The Variational Quantum Eigensolver: A review of methods and best practices
Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G. H., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2022.08.003 · Cited by 1,031
Fault-tolerant quantum computation
Shor, P. W. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 892
“codes can also be used to reduce decoherenceand inaccuracyin quantum computation. Until now, the best estimate on the amount of inaccuracy required to permit t steps of quantum computation was O(1/t) [2]. We will show in this paper that quantum circuits can be made fault-tolerant, so that quantum computation can be ac…”
BackgroundMethod(1996) · Cited by 824
Stabilizer Codes and Quantum Error Correction
Gottesman, D. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9705052 · Cited by 753
“Contents”
AI for next generation computing: Emerging trends and future directions
Gill, S. S., Xu, M., Ottaviani, C., Patros, P., Bahsoon, R., Shaghaghi, A., Golec, M., Stankovski, V., Wu, H., Abraham, A., et al. (2022) · Internet of Things · doi:10.1016/j.iot.2022.100514 · Cited by 686
“For example, it is not expected that they can efficiently solve NP-hard ptimisation problems [155] and, coming to searching, the speed-up offered by quantum computers scales quadratically with respect o the time needed by a classical computer (Grover’s algorithm [156]).”
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 703
Spatial search by quantum walk
Childs, A. M., & Goldstone, J. (2004) · Physical Review A · doi:10.1103/physreva.70.022314 · Cited by 725
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Quantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639
Grover’s quantum searching algorithm is optimal
Zalka, C. (1999) · Physical Review A · doi:10.1103/physreva.60.2746 · Cited by 635
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632
Quantum Computers Can Search Rapidly by Using Almost Any Transformation
Grover, L. K. (1998) · Physical Review Letters · doi:10.1103/physrevlett.80.4329 · Cited by 616
“[ BBBV ] showed by using subtle arguments about unitary trans-”
BackgroundFernandez-Carames, T. M., & Fraga-Lamas, P. (2020) · IEEE Access · doi:10.1109/access.2020.2968985 · Cited by 607
“In contrast to public-key cryptosystems, traditional hash functions are considered to be able to withstand quantum attacks since it seems unlikely the development of quantum algorithms for NP-hard problems [38].”
BackgroundDefining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601
Dynamical memristors for higher-complexity neuromorphic computing
Kumar, S., Wang, X., Strachan, J. P., Yang, Y., & Lu, W. D. (2022) · Nature Reviews Materials · doi:10.1038/s41578-022-00434-z · Cited by 558
“Quantum computing hopes to achieve exponential advantages over classical computing in some areas through the use of quantum bits that could explore an exponentially large Hilbert space through super-position and novel compute operations enabled by entanglement 179,180 .”
BackgroundInformation and computation: Classical and quantum aspects
Galindo, A., & Martín-Delgado, M. A. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.347 · Cited by 552
Quantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
“As pointed out in [47,52], if that was not the case, the QRAM would violate the search lower bounds proved in [53].”
ResultFault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513
Random Oracles in a Quantum World
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_3 · Cited by 449
Quantum circuits with mixed states
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276708 · Cited by 428
“nsions of the classical models of Turing machines and circuits, that take into account the laws of quantum physics. Deutsch’s model, augmented with further work [3, 14], enabled a sequence of results [2, 13, 6] culminating with Shor’s polynomial quantum algorithm for factoring integers [12]. However, it seems that Deu…”
MethodInfluentialAn introduction to quantum computing for non-physicists
Rieffel, E., & Polak, W. (2000) · ACM Computing Surveys · doi:10.1145/367701.367709 · Cited by 407
“The second half of the October 1997 issue of the SIAM Journal of Computing contains six seminal articles on quantum computing, including four we have already cited [Bennett et al. 1997; Bernstein and Vazirani 1997; Shor 1997; Simon 1997].”
BackgroundMethodInfluentialQuantum Computers Can Search Arbitrarily Large Databases by a Single Query
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.4709 · Cited by 432
“to identify a marked item out of N possible items [ BBBV ] & [BBHT], it could not possibly solve an NP-complete”
BackgroundThe thermodynamic meaning of negative entropy
Rio, L. D., Åberg, J., Renner, R., Dahlsten, O., & Vedral, V. (2011) · Nature · doi:10.1038/nature10123 · Cited by 420
“In the following we explain the relation of our work to established results on reversible computation, in particular [2, 40, 41, 49, 50].”
Quantum vs. classical communication and computation
Buhrman, H., Cleve, R., & Wigderson, A. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276713 · Cited by 389
Analog analogue of a digital quantum computation
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.57.2403 · Cited by 384
“hows that this is not the case. We now show that our procedure for finding |wi, in a time which grows like N1/2/E, is optimally short. The proof we give here is the analog analogue of the oracle proof [3] which 3 can be used to show that the Grover algorithm is optimal for the problem it sets out to solve. Again we are…”
A quantum-inspired classical algorithm for recommendation systems
Tang, E. (2019) · Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing · doi:10.1145/3313276.3316310 · Cited by 360
“These state preparation assumptions are nontrivial: even given ability to query entries of a vector in superposition, preparing states corresponding to arbitrary length-n input vectors is known to take Ω(√n) time (a corollary of quantum search lower bounds [6]).”
BackgroundA Quantum Algorithm for Finding the Minimum
Durr, C., & Hoyer, P. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9607014 · Cited by 359
“Due to a general lower bound of [1], this is within a constant factor of the optimum.”
BackgroundQuantum speedup of Monte Carlo methods
Montanaro, A. (2015) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2015.0301 · Cited by 334
“algorithm estimates E[v(B)] up to additive error except with probability at most 3=10 + pˇ2 6 T p . Lemma18is reminiscent of the hybrid argument for proving lower bounds on quantum query complexity [8]: if the distributions D Aand D Bare close, and the amplitude amplication algorithm makes few queries, it cannot disti…”
BackgroundQuantum Lower Bounds by Quantum Arguments
Ambainis, A. (2002) · Journal of Computer and System Sciences · doi:10.1006/jcss.2002.1826 · Cited by 340
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
“plexity of the hidden shift problem may no longer be polynomial; for example, the hidden shift problem with f0(x)=δx,0 is equivalent to unstructured search, which has quantum query complexity Ω( √ N)(Bennett et al., 1997). 37 it is not clear how to do so efficiently. In fact, the Legendre sequence χ(x),χ(x+1),... has b…”
BackgroundFernandez-Carames, T. M. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2958788 · Cited by 317
“Pre-Quantum symmetric algorithms and hash functions seem to be still valid for the post-quantum era: it is considered unlikely that efficient quantum algorithms will be found for NP-hard problems [26].”
BackgroundA geometric approach to quantum circuit lower bounds
Nielsen, M. A. (2006) · Quantum Information and Computation · doi:10.26421/qic6.3-2 · Cited by 251
Quantum lower bounds for the collision and the element distinctness problems
Aaronson, S., & Shi, Y. (2004) · Journal of the ACM · doi:10.1145/1008731.1008735 · Cited by 328
Guest Column: NP-complete problems and physical reality
Aaronson, S. (2005) · ACM SIGACT News · doi:10.1145/1052796.1052804 · Cited by 227
“[17] C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani.”
InfluentialBrassard, G., HØyer, P., & Tapp, A. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055105 · Cited by 256
Self-citationQuantum computation and quantum information
Nagy, M., & Akl, S. G. (2006) · International Journal of Parallel, Emergent and Distributed Systems · doi:10.1080/17445760500355678 · Cited by 287
“For completely unstructured searches, Grover's algorithm is optimal [ 16 , 36 , 186 ].”
Quantum Machine Learning: What Quantum Computing Means to Data Mining
Wittek, P. (2014) · Cited by 483
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308
“69,70 9.”
BackgroundTannu, S. S., & Qureshi, M. K. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304007 · Cited by 306
Quantum Algorithm Implementations for Beginners
J., A., Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., Gunter, D., Karra, S., et al. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3517340 · Cited by 245
“It has also been shown [14] that Grover’s algorithm is optimal in the sense that no quantum Turing machine can do this in less than O( √ N ) operations.”
BackgroundMagniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269
“Under the Unique Games Conjecture [83, 84], it is strictly impossible to improve upon the guarantees of GW using either quantum or classical algorithms unless a quantum computer can solve NP-Hard problems in polynomial time, which is not believed to be the case [85], or if P = NP.”
BackgroundComplexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv (Cornell University) · doi:10.14288/1.0343134 · Cited by 54
Decoherence in quantum walks – a review
KENDON, V. (2007) · Mathematical Structures in Computer Science · doi:10.1017/s0960129507006354 · Cited by 252
Using quantum key distribution for cryptographic purposes: A survey
Alléaume, R., Branciard, C., Bouda, J., Debuisschert, T., Dianati, M., Gisin, N., Godfrey, M., Grangier, P., Länger, T., Lütkenhaus, N., et al. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.09.018 · Cited by 217
“There are even some indications leading to partially negatively answer to this question: as demonstrated in [119], oracle methods can be used to give evidence that the complexity class NP is not included in BQP (which contains the problems that can be considered as efficiently solvable on a quantum computer), somehow…”
MethodAdleman, L. M., DeMarrais, J., & Huang, M.-D. A. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293639 · Cited by 262
Efficient quantum algorithm for dissipative nonlinear differential equations
Liu, J.-P., Kolden, H. Ø., Krovi, H. K., Loureiro, N. F., Trivisa, K., & Childs, A. M. (2021) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2026805118 · Cited by 237
Sophisticated Quantum Search Without Entanglement
Meyer, D. A. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.2014 · Cited by 242
“Since implementing the g a -controlled- NOT ‘gate’ with a subcircuit of local gates would introduce entanglement at intermediate timesteps, however, one might conclude that counting queries (or, more generally, nonlocal function calls) is a poor way to study the power of quantum algorithms [27].”
BackgroundConstructing elliptic curve isogenies in quantum subexponential time
Childs, A. M., Jao, D., & Soukharev, V. (2010) · Cited by 239
How to Construct Quantum Random Functions
Zhandry, M. (2012) · 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.37 · Cited by 230
A framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276712 · Cited by 240
Complete 3-Qubit Grover search on a programmable quantum computer
Figgatt, C., Maslov, D., Landsman, K. A., Linke, N. M., Debnath, S., & Monroe, C. (2017) · Nature Communications · doi:10.1038/s41467-017-01904-7 · Cited by 235
Quantum Attacks on Bitcoin, and How to Protect Against Them
Aggarwal, D., Brennen, G., Lee, T., Santha, M., & Tomamichel, M. (2018) · Ledger · doi:10.5195/ledger.2018.127 · Cited by 231
BQP and the polynomial hierarchy
Aaronson, S. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806711 · Cited by 226
“[8] gave oracle evidence that NP 6⊂ BQP, and while no one regards such evidence as decisive, today it seems extremely unlikely that quantum computers can solve NP-complete problems in polynomial time.”
BackgroundFixed-Point Quantum Search with an Optimal Number of Queries
Yoder, T. J., Low, G. H., & Chuang, I. L. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.210501 · Cited by 223
Fast parallel circuits for the quantum Fourier transform
Cleve, R., & Watrous, J. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892140 · Cited by 215
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv · doi:10.48550/arxiv.1612.05903 · Cited by 218
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2004) · 45th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.54 · Cited by 216
Quantum speed-up for unsupervised learning
Aïmeur, E., Brassard, G., & Gambs, S. (2013) · Machine Learning · doi:10.1007/s10994-012-5316-5 · Cited by 214
“In particular, if finding the optimal solution for a particular clustering problem is NP-hard (Garey and Johnson 1979), it is generally believed that quantum computers would also be unable to solve the problem exactly in polynomial time (Bennett et al. 1997).”
BackgroundSelf-citationQuantum Simulations of Classical Random Walks and Undirected Graph Connectivity
Watrous, J. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1732 · Cited by 216
Grover, L. K. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.150501 · Cited by 210
“The original quantum search algorithm is known to be the best possible algorithm for exhaustive searching [6], [7] therefore no algorithm will be able to improve its performance.”
Quantum Charging Advantage Cannot Be Extensive without Global Operations
Gyhm, J.-Y., Šafránek, D., & Rosa, D. (2022) · Physical Review Letters · doi:10.1103/physrevlett.128.140501 · Cited by 207
Quantum Computational Complexity
Watrous, J. (2009) · Encyclopedia of Complexity and Systems Science · doi:10.1007/978-0-387-30440-3_428 · Cited by 189
“While there is little reason to hope that this containment holds, there is at the same time little evidence against it aside from the fact that it fails relative to an oracle [28].”
BackgroundMethodHow Powerful is Adiabatic Quantum Computation
van Dam, W., Mosca, M., & Vazirani, U. V. (2002) · CERN Document Server (European Organization for Nuclear Research) · Cited by 204
Self-citationChallenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
“Although, in general, this is the best that can be hoped for 228 , the advantage is often less pronounced in practical problem classes in which brute-force search is not the best classical algorithm.”
The Path to Scalable Distributed Quantum Computing
Van Meter, R., & Devitt, S. J. (2016) · Computer · doi:10.1109/mc.2016.291 · Cited by 199
“In the 1980s and 90s, a handful of algorithms were developed and the foundations of quantum computational complexity were laid, but the full range of capabilities and the process of creating new algorithms were poorly understood [1, 3, 4, 5, 6].”
BackgroundAmbainis, A. (2004) · ACM SIGACT News · doi:10.1145/992287.992296 · Cited by 191
A Lambda Calculus for Quantum Computation
van Tonder, A. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539703432165 · Cited by 197
“The subset of λ q not involving quantum operations consists of a set of reversible classical rewritings, which can be unitarily and efficiently implemented on a quantum Turing machine by [2, 38, 39].”
BackgroundMethodQuantum algorithms and the finite element method
Montanaro, A., & Pallister, S. (2016) · Physical Review A · doi:10.1103/physreva.93.032324 · Cited by 192
“We adapt a standard technique of Bennett et al. [6].”
MethodThe Evolution of Quantum Secure Direct Communication: On the Road to the Qinternet
Pan, D., Long, G.-L., Yin, L., Sheng, Y.-B., Ruan, D., Ng, S. X., Lu, J., & Hanzo, L. (2024) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2024.3367535 · Cited by 180
“However, Grover’s algorithm provides an improvement to this problem [25], although an exponential speed-up in the database search problem is infeasible even for Grover’s optimal algorithm [20], [26]–[28].”
Near-optimal ground state preparation
Lin, L., & Tong, Y. (2020) · Quantum · doi:10.22331/q-2020-12-14-372 · Cited by 187
Quantum Copy-Protection and Quantum Money
Aaronson, S. (2009) · 2009 24th Annual IEEE Conference on Computational Complexity · doi:10.1109/ccc.2009.42 · Cited by 177
“Furthermore, by the optimality of Grover’s algorithm [7], it is clear that any would-be counterfeiter needs Ω 2 n/ 2 queries to U to find the secret key s , even if given the public key e s .”
BackgroundMethodInfluentialFaster quantum-walk algorithm for the two-dimensional spatial search
Tulsi, A. (2008) · Physical Review A · doi:10.1103/physreva.78.012310 · Cited by 185
Quantum Walk Based Search Algorithms
Santha, M. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_3 · Cited by 177
“…algorithm is the following simple procedure that satisfies the conditions of Theorem 5, but with a slightly higher complexity, of the order of S + [10,36], that | ψ i − | φ i ≤ O ( i 2 − k ). constant when k This implies that | ψ k i−| φ k is an arbitrarily small is chosen to be O(log(1 / √ ε ))…”
MethodQuantum information and precision measurement
Childs, A. M., Preskill, J., & Renes, J. (2000) · Journal of Modern Optics · doi:10.1080/09500340008244034 · Cited by 183
“And as the Grover search algorithm can be seen to be optimal, in the sense that a marked state can be identified with high probability with the minimal number of oracle calls [14], so the driving term we have chosen is optimal in the sense that it enables us to identify the value of the classical parameter labeling th…”
BackgroundHow to Record Quantum Queries, and Applications to Quantum Indifferentiability
Zhandry, M. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-26951-7_9 · Cited by 172
The quantum query complexity of approximating the median and related statistics
Nayak, A., & Wu, F. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301349 · Cited by 177
“The first such step in the field of quantum computation was taken by Bennett et al. [2].”
BackgroundQuantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2002) · Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) · doi:10.1109/sfcs.1998.743485 · Cited by 179
How powerful is adiabatic quantum computation?
van Dam, W., Mosca, M., & Vazirani, U. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959902 · Cited by 175
“To reconcile this with the oracle results from [2], it is useful to recall that the Cook-Levin theorem, suitably formulated as saying that NP has a ‘localcheckability’ property, does not relativize [1] (see [14] for a brief discussion of this issue).”
BackgroundMethodResultSelf-citationLimit on the Speed of Quantum Computation in Determining Parity
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.5442 · Cited by 181
“In fact this √ N speedup can be shown to be optimal [4].”
BackgroundQuantum Algorithms for Some Hidden Shift Problems
van Dam, W., Hallgren, S., & Ip, L. (2006) · SIAM Journal on Computing · doi:10.1137/s009753970343141x · Cited by 126
A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model
Kiltz, E., Lyubashevsky, V., & Schaffner, C. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-78372-7_18 · Cited by 163
“Hence, adaptive reprogramming in the QROM is difficult (but not impossible e.g., [12,18,36]).”
Complexity Limitations on Quantum Computation
Fortnow, L., & Rogers, J. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1651 · Cited by 168
An improved quantum Fourier transform algorithm and applications
Hales, L., & Hallgren, S. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892139 · Cited by 162
“Moreover, to produce a superpositionj i such that kj i Fpj ik the largest transform can be taken to be a power of 2 with justO (n+ log(1= )) bits.”
Background
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.