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 1,001–1,100 of 1,466
Hasija, T., Ramkumar, K. R., Singh, B., Kaur, A., & Mittal, S. K. (2025) · Recent Advances in Computer Science and Communications · doi:10.2174/0126662558331360240924004351 · Cited by 2
End-to-end quantum algorithm for topology optimization in structural mechanics
Hölscher, L., Ahrend, O., Karch, L., L'Estocq, C., Marfany, M. A., Stollenwerk, T., Wilhelm, F. K., & Kowalski, J. (2026) · Quantum Science and Technology · doi:10.1088/2058-9565/ae4cfe · Cited by 7
Photonic variational quantum eigensolver for NISQ-compatible quantum technology
Hu, K.-M., Namkung, M., & Lim, H. (2025) · Nano Convergence · doi:10.1186/s40580-025-00525-x · Cited by 4
The Exponential Speedup Algorithm: O(logN) Amplitude Amplification via Geometric Series
Liu, Y. (2026) · Journal of Quantum Information Science · doi:10.4236/jqis.2026.161005 · Cited by 2
Optimality of Quantum Adiabatic Search Algorithm and Its Circuit Model
Sun, J., Zhang, Z., & Lu, S. (2026) · Quantum Reports · doi:10.3390/quantum8020028 · Cited by 2
“Addressing this may re-https quire revisiting lower-bound results from [49] and employing adiabatic-to-query simulation techniques [50].”
Copy-Protection from Unclonable Puncturable Obfuscation, Revisited
Ananth, P., Behera, A., Huang, Z., Kitagawa, F., & Yamakawa, T. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-25291-3_19 · Cited by 2
Classical and quantum satisfiability
de Araújo, A., & Finger, M. (2012) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.81.6 · Cited by 2
Comparative Analysis of Elliptic Curve and Lattice Based Cryptography
Davenport, A., & Shetty, S. S. (2021) · Annual Modeling and Simulation Conference (ANNSIM) · doi:10.23919/annsim52504.2021.9552144 · Cited by 2
Schuld, M., & Petruccione, F. (2018) · Quantum science and technology · doi:10.1007/978-3-319-96424-9_4 · Cited by 2
Phase matching in quantum search algorithm
Chowdhury, S. R., Baruah, S., & Dikshit, B. (2023) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/acba41 · Cited by 4
Passwords and Cryptwords: The Final Limits on Lengths
Clark, M. M., & Seamons, K. E. (2022) · New Security Paradigms Workshop · doi:10.1145/3584318.3584324 · Cited by 4
“proved [10] that a quantum computer can at best half the key space for brute force key searching.”
BackgroundN-partite Entanglement Measures of GHZ States in a Non-inertial Frame
Rueda-Paz, J., Manríquez-Zepeda, J. L., López-García, M. D. L., & Ávila, M. (2023) · International Journal of Theoretical Physics · doi:10.1007/s10773-023-05378-w · Cited by 2
Efficient Quantum Circuit Encoding of Object Information in 2D Ray Casting
Lee, S., Jeong, S., & Seo, J. (2024) · International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC) · doi:10.1109/itc-cscc62988.2024.10628280 · Cited by 3
“Interest in quantum computing remains strong due to the significant time-saving benefits for some problems provided by quantum parallelism and the superposition of states [6], [9].”
BackgroundDefine, refined and re-defined concepts of quantum machine learning : A review
Chavan, S., & Mulay, P. (2024) · Journal of Information and Optimization Sciences · doi:10.47974/jios-1320 · Cited by 3
Generalized Hybrid Search with Applications to Blockchains and Hash Function Security
Cojocaru, A., Garay, J. A., & Song, F. (2024) · Lecture notes in computer science · doi:10.1007/978-981-96-0947-5_3 · Cited by 2
Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits
Younes, A. (2017) · Emergence, complexity and computation · doi:10.1007/978-3-319-67997-6_5 · Cited by 2
A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
Wu, W., & Zhang, H. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2175-z · Cited by 2
Computation in a general physical setting
Lee, C. M. (2021) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ac2007 · Cited by 2
“In quantum computing, oracles are a vital component of many of the known computational speed-ups over classical computing [47, 48, 49].”
BackgroundKendon, V. M. (2011) · Springer eBooks · doi:10.1007/978-1-4614-1800-9_148 · Cited by 2
Constant-time quantum search with a many-body quantum system
DalFavero, B., Meill, A., Meyer, D., Wong, T. G., & Wrubel, J. (2024) · Physical Review A · doi:10.1103/physreva.110.052411 · Cited by 2
“Bennett, Bernstein, Brassard, and Vazi-rani [2] showed that a quantum computer needs at least Ω( √ N ) steps to perform the search, and thus Grover’s algorithm is optimal.”
BackgroundImproved Quantum Lifting by Coherent Measure-and-Reprogram
Cojocaru, A., Garay, J. A., Liu, Q., & Song, F. (2024) · Lecture notes in computer science · doi:10.1007/978-981-96-0947-5_6 · Cited by 2
“Therefore we have 𝜖 ≤ (2 𝑞 + 1) 2 /𝑁 , which immediately reproduces the tight bound for the famous Grover’s search problem [BBBV97].”
A Survey of Quantum Algorithms for Computer Science
Kumar, A. H., Singh, A. J., & Kumar, S. (2025) · Communications in computer and information science · doi:10.1007/978-3-031-86069-0_29 · Cited by 2
Noise-tolerant public-key quantum money from a classical oracle
Yuen, P. (2025) · Quantum · doi:10.22331/q-2025-04-07-1691 · Cited by 4
“Is it possible to make any of these schemes noise-tolerant?”
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
Buhrman, H., Helsen, J., & Weggemans, J. R. (2025) · Quantum · doi:10.22331/q-2025-07-11-1791 · Cited by 15
Finding stable models via quantum computation.
Meyer, D., Pommersheim, J., & Remmel, J. B. (2004) · Non-Monotonic Reasoning · Cited by 5
A Formal Technique for Reducing Software Testing Time Complexity
Baig, M. M., & Khan, A. A. (2009) · Springer eBooks · doi:10.1007/978-90-481-3658-2_34 · Cited by 2
Relativized Worlds without Worst-Case to Average-Case Reductions for NP
Watson, T. W. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_56 · Cited by 2
Study of a Quantum Framework for Search Based Software Engineering
Wu, N., Song, F., & Li, X. (2013) · International Journal of Theoretical Physics · doi:10.1007/s10773-013-1544-0 · Cited by 2
Can quantum entanglement detection schemes improve search?
Tarrataca, L., & Wichert, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-011-0231-4 · Cited by 3
“√ Unfortunately, it was proved that the search problem cannot be solved under Ω( N ) time [3] using standard quantum computation approaches.”
BackgroundExplicit relation between all lower bound techniques for quantum query complexity
Magnin, L., & Roland, J. (2013) · International Journal of Quantum Information · doi:10.1142/s0219749913500597 · Cited by 2
Theory of quantum computation and philosophy of mathematics. Part I
Wójtowicz, K. (2010) · Logic and Logical Philosophy · doi:10.12775/llp.2009.016 · Cited by 2
“This problem becomes interesting, when 6 In the case of a NP-complete problem (where 2n data have to be examined), the lower bound of the unstructured search is O(2n/2), as was proved in [Bennett et al., 1997].”
BackgroundOn the Cryptographic Long Term Security
Poulakis, D. (2013) · Cited by 2
Brief History of Quantum Cryptography: A Personal Perspective (Invited Paper)
Brassard, G. (2005) · Cited by 2
Self-citationCoherent Computing with Injection-Locked Laser Network
Utsunomiya, S., Wen, K., Takata, K., Tamate, S., & Yamamoto, Y. (2015) · Lecture notes in physics · doi:10.1007/978-4-431-55756-2_10 · Cited by 2
Hayles, N. K. (2015) · Science Fiction Studies · doi:10.5621/sciefictstud.42.1.0056 · Cited by 3
Failures Guide Probabilistic Search for a Hard-to-Find Test
Venkatasubramanian, M., & Agrawal, V. D. (2016) · IEEE North Atlantic Test Workshop (NATW) · doi:10.1109/natw.2016.18 · Cited by 2
“While classical algorithms can have complexity ranging from O(N ) to O(logN ), the complexity of Grover’s algorithm is shown to be O( √ N ) [4], [6].”
BackgroundQuantum Identification of Boolean Oracles
Ambainis, A., Iwama, K., Kawachi, A., Raymond, R., & Yamashita, S. (2006) · Springer eBooks · doi:10.1007/11683858_1 · Cited by 8
Grover's Quantum Search Algorithm and Mixed States
Kenigsberg, D., & Biham, E. (2001) · Cited by 2
Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
Yuge, T. (2018) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.87.124002 · Cited by 2
Quantum Algorithms: Application Perspective
Wong, R., & Bhatia, A. S. (2021) · Advances in information security, privacy, and ethics book series · doi:10.4018/978-1-7998-6677-0.ch005 · Cited by 2
Phase shift and multi-controlled Z-type gates
Novikov, A., & Zainulin, R. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04005-1 · Cited by 2
“[9] have shown that asymptotically no quantum algorithm can solve the search problem in less than a number of steps proportional to ( √ N ), so Grover’s algorithm appeared to be asymptotically optimal.”
BackgroundApplication of the Variational Quantum Eigensolver to the Ultimate Pit Problem
Hindy, Y., Pointing, J., Tolunay, M., Venkatarao, S., Motta, M., & Latone, J. A. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00083 · Cited by 2
“It is not yet known if a quantum algorithm can provide computational advantage in a combinatorial optimization problem, especially with the limitations of contemporary hardware [8]–[13].”
BackgroundQuantum dueling: an efficient solution for combinatorial optimization
Tang, L., Wang, H., Li, Z., Tang, H., Zhang, C., & Li, S. (2024) · Physica Scripta · doi:10.1088/1402-4896/ad2e55 · Cited by 3
Quantum CCA-Secure PKE, Revisited
Alamati, N., & Maram, V. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-57728-4_7 · Cited by 2
Quantum Speed-Ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching
Jin, C., & Nogler, J. (2024) · ACM Transactions on Algorithms · doi:10.1145/3672395 · Cited by 8
“+ 𝜏 )) .”
Yamakami, T. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45833-6_25 · Cited by 4
Ulyanoy, S. V., Antoni, G. D., Yamafuji, K., Fukuda, T., Rizzotto, G., & Kurawaki, I. (2002) · International Symposium on Micro-NanoMechatronics and Human Science · doi:10.1109/mhs.1998.745785 · Cited by 3
Quantum Algorithms without Initializing the Auxiliary Qubits
Chi, D. P., Kim, J. S., & Lee, S. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.080504 · Cited by 4
Evolutionary Algorithms for Quantum Computers
Johannsen, D., Kurur, P. P., & Lengler, J. (2013) · Algorithmica · doi:10.1007/s00453-013-9784-1 · Cited by 2
“This is similar to other general settings like unordered search [6, 26] or query complexity of local search on a graph [1], in which it is proven or conjectured that quantum computers can give at most a quadratic speedup.”
BackgroundCryptography from tensor problems
Schulman, L. J. (2012) · CaltechAUTHORS (California Institute of Technology) · Cited by 7
Advances in quantum computational learning theory
Servedio, R. A., & Atıcı, A. (2006) · Cited by 2
Novel Scheme based on Ping-pong Effect for Predictive Fast Handovers for Mobile IPv6
Wang, H., Jia, Z., & Zhao, H. (2007) · ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD) · doi:10.1109/snpd.2007.438 · Cited by 2
Key Establishment à la Merkle in a Quantum World
Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., & Salvail, L. (2019) · Journal of Cryptology · doi:10.1007/s00145-019-09317-z · Cited by 10
Self-citationTulsi, A. (2016) · Quantum Information Processing · doi:10.1007/s11128-016-1322-z · Cited by 2
“ust be satisfied whi ch demands that in one time step, we can implement only one local operator coupling only neighboring vertices. The famous Grover’s algorithm is optimal for general search problems [1,2,3,4] but it becomes inefficient for QSS. However, it can be generalize d to get efficient QSS algorithms. First effic…”
Massar, S., & Sántha, M. (2021) · Quantum Information Processing · doi:10.1007/s11128-020-02959-0 · Cited by 2
Quantum time-space tradeoffs for sorting
Klauck, H. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780551.780553 · Cited by 2
Sun, X. (2016) · Scientia Sinica Informationis · doi:10.1360/n112016-00084 · Cited by 4
Raffaelli, F., Denman, R., Collins, R. B., Faugère, J., Martino, G. D., Shaw, C., Kennard, J., Sibson, P., Perret, L., & Erven, C. (2019) · Advanced Optical Technologies · doi:10.1515/aot-2020-0021 · Cited by 2
“[37]), giving con fi dence in the existence of cryptographically interesting problems that are hard to solve in the quantum setting.”
BackgroundOptimal fixed-point quantum search in an interacting Ising spin system
Sombillo, N. I., Banzon, R. S., & Villagonzalo, C. D. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03023-1 · Cited by 2
Analysis of Neural Network Predictions for Entanglement Self-Catalysis
Acácio, T. M., & Duarte, C. (2022) · Brazilian Journal of Physics · doi:10.1007/s13538-022-01191-8 · Cited by 2
“However, more than a mathematical object, entanglement has assumed over the past decades a key role in quantum computation [9], quantum communication [10, 11], quantum cryptography [12, 13] and more recently in quantum networks [14].”
BackgroundQuantum counterfactuality with identical particles
Rao, V. N., Banerjee, A., & Srikanth, R. (2023) · Communications in Theoretical Physics · doi:10.1088/1572-9494/acb9fd · Cited by 2
“By contrast, the single-photon interference that leads to IFM-by-proxy is not expected to give a greater-than-quadratic speedup, as in Grover search [47], since it can be described by first-quantization principles.”
How Many Query Superpositions Are Needed to Learn?
Castro, J. (2006) · Lecture notes in computer science · doi:10.1007/11894841_10 · Cited by 3
“3 in [9] states (see first line in the last paragraph of the proof) that ‖|E〉‖(2) = 2 ∑ [q]∈G w[q](|φ〉), that is a better characterization than the inequality given by Lemma 4.”
BackgroundMethodInfluentialQuantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties
Spakowski, H., Thakur, M., & Tripathi, R. S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-24597-1_32 · Cited by 2
The Structure of Promises in Quantum SpeedupsPreprint
Ben-David, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.3323 · Cited by 2
“the n-bit OR function. It’s not hard to see that R(f) = (n). On the other hand, it has been shown that Q(f) = ( p n) (the upper bound follows from Grover search [7], and the lower bound was shown in [4]). While the quantum query complexity is asymptotically faster than the classical query complexity, the gap is polyno…”
BackgroundQuantum Algorithms: Database Search and its VariationsPreprint
Patel, A. D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.2058 · Cited by 2
“On the other hand, the optimality of Grover’s algorithm is a consequence of unitarity [6, 7].”
BackgroundQuantum Algorithms for Finding Claws, Collisions and TrianglesPreprint
Buhrman, H., Dürr, C., & Hyer, P. (2000) · arXiv (Cornell University) · Cited by 2
Quantum Evaluation of Multi-Valued Boolean FunctionsPreprint
Iwama, K., Kawachi, A., Masuda, H., Putra, R. H., & Yamashita, S. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0304131 · Cited by 2
“It is well-known that the query complexity for the EQ-oracle is Θ( √ N )[3, 5, 6, 7, 9, 13], while only O (1) for the IP-oracle[2, 8].”
BackgroundMethodQuantum Algorithm for Commutativity Testing of a Matrix SetPreprint
Itakura, Y. K. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0509206 · Cited by 4
“,...,xn) ∈{0,1}n, is there isuch that xi = 1? This lower bound is useful in later sections when we reduce from this search problem to the problems of our interest. This lower bound was first proven in [BBBV97] using a “hybrid argument”. Theorem 2.4.3 [Amb03] The query complexity of a search on unstructured database of…”
MethodInfluentialvan Dam, W. K. (2002) · UvA-DARE (University of Amsterdam) · Cited by 3
QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES
Nishimura, H. (2003) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054103002059 · Cited by 3
Diagonalization of diffusion matrix in Grover's algorithm
Kwek, L. C., Oh, C. H., Singh, K., & Wang, X. (2000) · Physics Letters A · doi:10.1016/s0375-9601(00)00084-0 · Cited by 2
Quantum lower bound for sortingPreprint
Shi, Y. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0009091 · Cited by 3
Quantum query complexity and distributed computing
Röhrig, H. (2004) · UvA-DARE (University of Amsterdam) · Cited by 2
The quantum complexity of set membership
Radhakrishnan, J., Sen, P., & Venkatesh, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892143 · Cited by 5
Oracles with CostsPreprint
Kimmel, S., Lin, C. Y.-Y., & Lin, H.-H. (2015) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2015.1 · Cited by 4
“When discussing lower bounds on the cost of STO, we will often refer to the SEARCH problem.”
MethodInfluentialNewman, I., Buhrman, H., Fortnow, L., & Röhrig, H. (2001) · UvA-DARE (University of Amsterdam) · Cited by 2
The non-injective hidden shift problem
Gharibi, M. (2012) · UWSpace (University of Waterloo) · Cited by 2
Quantum‐Resistant Cryptography
Grimes, R. A. (2019) · Wiley eBooks · doi:10.1002/9781119618232.ch6 · Cited by 2
Physics and Metaphysics Look at Computation
Svozil, K. (2006) · De Gruyter eBooks · doi:10.1515/9783110325461.491 · Cited by 2
Quantum Communication-Query TradeoffsPreprint
Hoza, W. M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.07768 · Cited by 3
“Z|loglog|X| , whereas in actual fact, QOIP(f) might be much larger. For example, QOIP(EQ) ≥ Ω( p |X|); this is the familiar fact that Grover’s algorithm [Gro96] is optimal, proven by Bennett et al. [BBBV97]. 1.2 Proof overview Theorem 1 generalizes the technique used by Cleve et al. [CDNT13] to prove that Q∗cc(IP) ≥ Ω…”
MethodInfluentialQuantum Computing, Quantum Games and Geometric Algebra
Chappell, J. M. (2011) · Adelaide Research & Scholarship (AR&S) (University of Adelaide) · Cited by 4
Early days following Grover's quantum search algorithmPreprint
Song, F. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.01236 · Cited by 5
“sically culminated the early stage of developments related to quantum search. As to the optimality of Grover’s search algorithm, an early manuscript in 1994 by Bennett, Bernstein,Brassardand Vazirani [BBBV97]actually precededGrover’spaper. Theysystematically studied the strengths and limits of quantum algorithms. In p…”
BackgroundMethodInfluentialA Counterexample to the Generalized Linial-Nisan ConjecturePreprint
Aaronson, S. (2011) · arXiv (Cornell University) · Cited by 2
Classical lower bounds from quantum upper boundsPreprint
Ben-David, S., Bouland, A., Garg, A., & Kothari, R. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.06256 · Cited by 2
“Therefore even a quantum algorithm for this query problem would require Ω( √ n) queries by the lower bound for Grover search [42].”
Quantum Algorithms and Complexity for Continuous Problems
(2011) · Springer eBooks · doi:10.1007/springerreference_60596 · Cited by 2
Quantum speedups need structurePreprint
Keller, N., & Klein, O. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.03748 · Cited by 2
“, xN ) contains a non-zero element xi over a classical algorithm cannot be exceeded (see [10]).”
BackgroundHybrid Decision Trees: Longer Quantum Time is Strictly More PowerfulPreprint
Sun, X., & Zheng, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.13091 · Cited by 10
“es in T to violate the statement. Next, we need to determine β(v) i for every vand i. The intuition about β(v) i makes one think of query magnitude, a notion that is first introduced by Bennett et al. [BBBV97]. Suppose we have a classical decision tree Aand the input yis determined. It is easy to define πA i (y) as the…”
Ahlswede, R. (2006) · Lecture notes in computer science · doi:10.1007/11889342_1 · Cited by 2
Patel, A. D., & Grover, L. K. (2016) · Springer eBooks · doi:10.1007/978-1-4939-2864-4_317 · Cited by 3
Grover, L. K., & Reichardt, B. W. (2008) · Springer eBooks · doi:10.1007/978-0-387-30162-4_317 · Cited by 2
(2014) · Elsevier eBooks · doi:10.1016/b978-0-12-800953-6.00020-7 · Cited by 2
Tripartite entanglement and matrix inversion quantum algorithmPreprint
Hwang, M.-R., Kim, M., Jung, E., Woo, C.-Y., & Park, D. (2022) · Research Square · doi:10.21203/rs.3.rs-2287755/v1 · Cited by 3
Quantum Algorithms and Complexity for Continuous Problems
Papageorgiou, A., & Traub, J. F. (2009) · Springer eBooks · doi:10.1007/978-0-387-30440-3_424 · Cited by 2
“The quantum model of computation is discussed in detail in [6, 7, 8, 17, 27, 48] and we summarize it here as it applies to continuous problems.”
BackgroundQuantum Algorithms for Solving the Traveling Salesman ProblemPreprint
Klug, F. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4836033 · Cited by 2
Collision Finding with Many Classical or Quantum Processors
Jeffery, S. (2011) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 2
Finding spin-glass ground states using quantum walks [dataset]
Callison, A. (2019) · Durham Research Online (Durham University) · doi:10.15128/r21544bp097 · Cited by 7
Searching for an Efficient System of Equations Defining the AES Sbox for the QUBO Problem
Burek, E., Mańk, K., & Wroński, M. (2023) · Journal of Telecommunications and Information Technology · doi:10.26636/jtit.2023.4.1340 · Cited by 1
An Efficient Quantum cryptanalysis of lightweight hash function - PHOTON-Beetle
Allu, S. N., Tentu, A. N., & Kancharla, G. R. (2023) · International Conference on Automation, Computing and Renewable Systems (ICACRS) · doi:10.1109/icacrs58579.2023.10404523 · Cited by 1
“In 1997 [20], Bennett, Bernstein, Brassard, and Vazirani verified that given a search space N , the number of queries needed to be O ( √ N ) .”
BackgroundImplementing Post-Quantum Cryptography Algorithm in Blockchain
Preethi, P., Ulla, M. M., Sapna, R., & Mohan, K. G. (2023) · International Conference on New Frontiers in Communication, Automation, Management and Security (ICCAMS) · doi:10.1109/iccams60113.2023.10525729 · Cited by 4
“These attacks impact the most public-key algorithms, including RSA (Rivest, Shamir, Adleman) [3], ECDSA (Elliptic Curve Digital Signature Algorithm) [4], [5], ECDH (Elliptic Curve Diffie-Hellman) [16] or DSA (Digital Signature Algorithm) [7].”
BackgroundQuantized Markov Chain Couplings that Prepare Qsamples
Temme, K., & Wocjan, P. (2025) · Quantum · doi:10.22331/q-2025-12-18-1951 · Cited by 6
“Note that this result is different from Szegedy walks [2], which are unitaries that permit the reflection about the qsample when combined with phase estimation.”
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.