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,101–1,200 of 1,466
Quantum Communication Advantage in TFNP
Göös, M., Gur, T., Jain, S., & Li, J. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718155 · Cited by 1
“TFNP problems. introduced a new total NP search problem that exhibits an exponential holds over the uniform distribution, a question raised by Aaronson variant of their problem, called Bipartite NullCodeword , and obtain the any total NP search problem.”
Sun, J., Zhang, Z., & Lu, S. (2026) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/ae7758 · Cited by 1
The Single-Rotation Quantum Search Algorithm: Amplitude Amplification with One Oracle Call
Liu, Y. (2026) · Journal of Quantum Information Science · doi:10.4236/jqis.2026.162006 · Cited by 1
Grover’s Algorithm for Unstructured Search
Marquezino, F. D. L., Portugal, R., & Lavor, C. (2019) · SpringerBriefs in computer science · doi:10.1007/978-3-030-19066-8_3 · Cited by 3
Hull, I., Sattath, O., Diamanti, E., & Wendin, G. P. (2024) · Contributions to economics · doi:10.1007/978-3-031-50780-9_3 · Cited by 2
On the number of solutions to a random instance of the permuted kernel problem
Sanna, C. (2024) · Journal of Complexity · doi:10.1016/j.jco.2024.101898 · Cited by 1
Post-Quantum Cryptography: Effects of Quantum Computing on Modern Cryptograph
Yang, D. (2024) · International journal of high school research · doi:10.36838/v6i6.3 · Cited by 3
A Simplified Quantum Approach Using Grover's Algorithm for Solving the Vertex Cover Problem
Cherif, M. Y., Chaari, W. L., & Driss, O. B. (2024) · IEEE/ACS International Conference on Computer Systems and Applications (AICCSA) · doi:10.1109/aiccsa63423.2024.10912613 · Cited by 1
Grover Adaptive Search With Spin Variables
Fujiwara, S., & Ishikawa, N. (2025) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2025.3595910 · Cited by 1
“In addition, by optimizing algorithm parameters, query complexity can be further reduced [24], [25], although it has been proven that it is impossible to be reduced below o ( √ 2 n ) [26].”
Multiplayer conflict avoidance through entangled quantum walks
Shiratori, H., Yamagami, T., Segawa, E., Mihana, T., Röhm, A., & Horisaki, R. (2025) · Physical Review A · doi:10.1103/zxx8-j2d4 · Cited by 1
“Famously, Grover’s algorithm can extract an item from a randomly ordered list of N items with only O ( √ N ) iterations [3], beating the fastest classical search algorithm [4].”
Quantum Algorithms for Hopcroft's problem
Andrejevs, V., Belovs, A., & Vihrovs, J. (2026) · ACM Transactions on Quantum Computing · doi:10.1145/3787461 · Cited by 4
“Finally, quite often the quantum query complexity of a problem matches its time complexity, like in Unstructured Search [Gro96; BBBV97], Element Distinctness [Amb07; Amb05; Kut05], Closest Pair [Aar+20], Claw Finding [Tan09; Zha05], just to name a few.”
Griset, R., Lavdas, I., & Jarkovský, J. G. (2025) · Journal of quantum computing · doi:10.32604/jqc.2025.066064 · Cited by 2
“Under standard complexity-theoretic assumptions, Grover’s algorithm is considered optimal for unstructured search [8].”
Creemers, S., & Armas, L. F. P. (2025) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2024.0561 · Cited by 1
Van der Waals Ferroelectric CuInP 2 S 6 ‐based Multi‐slope In‐memory Probabilistic Computing
Kim, C., Kim, N., Kang, S., Park, C. Y., Lee, S., Jang, C., Park, J., Chul, J. B., & Lee, S. (2026) · Advanced Materials · doi:10.1002/adma.202518284 · Cited by 1
Quantum Truncated Differential Attacks Using Convolutions
Pichollet-Mugnier, A., & Schrottenloher, A. (2026) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2026.i1.148-188 · Cited by 2
“As an example, Grover’s algorithm [Gro96] is known to solve black-box search problems with a quadratic speedup over classical exhaustive search, but this is optimal [BBBV97].”
Iterative Matrix Product State Simulation for Scalable Grover’s Algorithm
Sam, M. I., Kuo, T.-L., & Li, T.-Y. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11461240 · Cited by 3
“√ Bennett et al. [2] established the Ω( N ) lower bound for any quantum search, proving Grover’s optimality within quantum mechanics.”
QERA: A QUANTUM ECONOMIC RISK ASSESSMENT FRAMEWORK FOR BLOCKCHAIN CRYPTOGRAPHIC INFRASTRUCTURE
Pillai, B., Rao, A. S., Madineni, N., Karaca, Y., & Chang, E. J. (2026) · Fractals · doi:10.1142/s0218348x26400645 · Cited by 1
Klug, F. (2026) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2026.131649 · Cited by 1
Srivats, B. G. (2026) · Next research. · doi:10.1016/j.nexres.2026.101888 · Cited by 2
Racing a quantum computer through Minkowski spacetime
Biamonte, J. (2010) · Journal of Physics Conference Series · doi:10.1088/1742-6596/229/1/012020 · Cited by 1
Quantum Computation Relative to Oracles
Tamon, C., & Yamakami, T. (2001) · Springer eBooks · doi:10.1007/978-1-4471-0313-4_20 · Cited by 1
“[10, 3] bsǫ (M, A, x) ≤ 8T (x)(2)/ǫ(2), where T (x) is the running time of M with A on x.”
BackgroundMethodChallenges of adiabatic quantum evaluation of NAND trees
Tarrataca, L. D. T. J. (2015) · Quantum Information Processing · doi:10.1007/s11128-015-1137-3 · Cited by 1
“√ This is optimal since there is a known lower bound of Ω( N ) [6].”
BackgroundQuantum Mechanical Search and Harmonic Perturbation
Jiang, J.-H. R., Chiou, D.-W., & Wu, C.-E. R. (2007) · Quantum Information Processing · doi:10.1007/s11128-007-0062-5 · Cited by 1
Entropy of a needle in a haystack
Fang, Y., Kwek, L. C., Choo, K. W., Kaszlikowski, D., & Oh, C. H. (2006) · Laser Physics · doi:10.1134/s1054660x06020332 · Cited by 1
Walsh transforms and efficient quantum algorithms
Mihara, T. (2000) · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · doi:10.1002/(sici)1520-6440(200008)83:8<71::aid-ecjc8>3.0.co;2-c · Cited by 3
Geometric Analysis of Grover’s Search Algorithmin the Presence of Perturbation
Jin, W. (2014) · Brazilian Journal of Physics · doi:10.1007/s13538-014-0176-z · Cited by 1
A Quantum Processing Framework for Quantum Algorithms
Aghaei, M. R. S., & Zukarnain, Z. A. (2012) · Majlesi Journal of Electrical Engineering · Cited by 1
How significant are the known collision and element distinctness quantum algorithms
Groverand, L., & Rudolph, T. (2003) · INFORMS journal on computing · Cited by 1
Kendon, V. M. (2018) · Springer eBooks · doi:10.1007/978-1-4939-6883-1_429 · Cited by 1
Reus, B. (2016) · Undergraduate topics in computer science · doi:10.1007/978-3-319-27889-6_23 · Cited by 1
\({\ell_0}\) Optimization with Robust Non-Oracular Quantum Search
Zhang, T., & Yuan, K. (2023) · Technologies · doi:10.3390/technologies11050148 · Cited by 1
Perspective on photonic neuromorphic computing
Goi, E., & Gu, M. (2024) · Elsevier eBooks · doi:10.1016/b978-0-323-98829-2.00009-8 · Cited by 1
Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
Khadiev, K. R., & Serov, D. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-63742-1_10 · Cited by 1
“√ This claim contradicts the lower bound for unstructured search [12] that is Ω ( n ) in the quantum case, and Ω ( n ) in the classical case.”
BackgroundQuantum computation by cooling
Cho, J. (2024) · Journal of the Korean Physical Society · doi:10.1007/s40042-024-01137-0 · Cited by 2
Oracle separations for non-adaptive collapse-free quantum computing
Hepp, H., da Silva, M. V. G., & Zatesko, L. M. (2025) · Theoretical Computer Science · doi:10.1016/j.tcs.2025.115078 · Cited by 1
“There is an oracle A for which Our proof for Theorem 1 follows the structure of the proof by Fortnow and Rogers for BQP , but using properties for naCQP shown by Aaronson et al. combined with a technical lemma by Bennet et al. [3].”
InfluentialKim, J., Choi, H., & Woo, J. (2025) · IEEE International Reliability Physics Symposium proceedings · doi:10.1109/irps48204.2025.10983490 · Cited by 1
“Quantum computing, leveraging qubits, has demonstrated exceptional capabilities in efficiently exploring solution through quantum superposition [3, 4].”
Uncloneable Quantum States Are Necessary as Proofs and Advice
Chatterjee, R., Kundu, S., & Podder, S. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718226 · Cited by 6
Chicano, F., Dahi, Z. A., & Luque, G. (2025) · Genetic and Evolutionary Computation Conference Companion (GECCO Companion) · doi:10.1145/3712255.3734319 · Cited by 2
Quantum Attacks on ECDLP-Based Cryptosystems
Yan, S. Y. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7722-9_4 · Cited by 1
Revisiting a limit on efficient quantum computation
Purewal, T. S. (2006) · ACM Southeast Regional Conference (ACMSE) · doi:10.1145/1185448.1185502 · Cited by 1
Uyanık, K., & Turgut, S. (2013) · Quantum Information Processing · doi:10.1007/s11128-013-0606-9 · Cited by 1
“This result is compatible with the bounds given for the Grover algorithm [7–9, 15 ], Choi and Braunstein’s”
BackgroundResultOhya, M., & Volovich, I. V. (2011) · Theoretical and mathematical physics · doi:10.1007/978-94-007-0171-7_14 · Cited by 1
Collision Finding with Many Classical or Quantum Processors
Jeery, S. (2011) · Cited by 2
Classical and Quantum Computation
Yan, S. Y. (2015) · Springer eBooks · doi:10.1007/978-3-319-25823-2_2 · Cited by 1
Nan, W. U., XiangDong, L. I., & Song, F. (2015) · Scientia Sinica Informationis · doi:10.1360/n112013-00192 · Cited by 1
“1997 年 , Bennett 等 [12] 证明了 Grover 算法对非结构 ( 随机 ) 空间的搜 索的时间复杂度达到了下限 Ω( √ N ), 即在量子设备上进行搜索的最优算法可以获得与经典算法相比 的平方根加速效果 .”
Quasiadiabatic Grover search via the Wentzel-Kramers-Brillouin approximation
Muthukrishnan, S., & Lidar, D. A. (2017) · Physical Review A · doi:10.1103/physreva.96.012329 · Cited by 1
Schöning, U., & Pruim, R. J. (1998) · Springer eBooks · doi:10.1007/978-3-642-60322-8_27 · Cited by 1
Amplitude Amplification for Operator Identification and Randomized Classes
Bera, D. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-94776-1_48 · Cited by 4
“The current methods for improving success probability of bounded-error nonquery quantum algorithms are parallel repetitions [12] that have the same complexity as classical methods.”
MethodThe Research of Grover’s Quantum Search Algorithm with Use of Quantum Circuits QX2 and QX4
Liber, A., & Nita, L. (2018) · Advances in intelligent systems and computing · doi:10.1007/978-3-319-99981-4_14 · Cited by 2
Multiobjective Optimization Grover Adaptive Search
Barán, B., & Villagra, M. (2018) · Studies in computational intelligence · doi:10.1007/978-3-319-99648-6_11 · Cited by 2
Several Remarks on Grover's Quantum Search Algorithm with a Single Marked Element
Han, Q., Han, Y., Lu, Z., & Kou, Y. (2021) · Scholars Journal of Physics Mathematics and Statistics · doi:10.36347/sjpms.2021.v08i03.002 · Cited by 1
“In [1, 5, 6], the evolution operator and the initial condition of Grover's algorithm have real entries, this means that the entire evolution takes place in a real vector subspace of the Hilbert space N 2 H , the key of the algorithm is the product operator U of two reflection operators f R and D R .”
BackgroundInfluentialSmall Circuits Imply Efficient Arthur-Merlin Protocols
Ezra, M., & Rothblum, R. D. (2022) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2022.67 · Cited by 3
Geometry and causal flux in multi-loop Feynman diagrams
Sborlini, G. F. R. (2022) · Suplemento de la Revista Mexicana de Física · doi:10.31349/suplrevmexfis.3.020703 · Cited by 1
“In particular, we relied on Grover’s search algorithm [51, 52, 53] to test the causal flow conditions simultaneously for all the configurations.”
MethodA Simple Heuristic for Expressing a Truth Table as a Quadratic Pseudo-Boolean Function
Pakin, S. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00039 · Cited by 3
Theory of Quantum Computation and Philosophy of Mathematics. Part II
Wójtowicz, K. (2018) · Logic and Logical Philosophy · doi:10.12775/llp.2018.006 · Cited by 1
Quantum Attacks on IFP-Based Cryptosystems
Yan, S. Y. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7722-9_2 · Cited by 1
Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
Creiner, A., & Jackson, S. (2023) · Mathematical logic quarterly · doi:10.1002/malq.202200068 · Cited by 1
Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP‐Hard
Wang, L. (2024) · IET Information Security · doi:10.1049/2024/3219604 · Cited by 1
Avances de la computación cuántica en México
Palacios-Razo, L., & Sun, G.-H. (2024) · PÄDI Boletín Científico de Ciencias Básicas e Ingenierías del ICBI · doi:10.29057/icbi.v12i23.11467 · Cited by 1
Miao, X. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0607144 · Cited by 6
“computational science and can be used to solve the NP-hard problems. It has been shown that the square speedup for the standard quantum search algorithm [7] is optimal in a pure-state quantum system [15]. The first attempt to break through the quantum-searching square speedup limit was carried out in a nuclear magnetic…”
Quantum money and scalable 21-cm cosmology
Farhi, E., Tegmark, M., & Lutomirski, A. (2011) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1
Experimental realization of quantum key distribution.
Kabeya, M. (2009) · Cited by 1
Cryptography Based on Quadratic Forms: Complexity Considerations
Hartung, R. J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-540-88353-1_5 · Cited by 1
“This is taken as a hint that this type of primitives may still be secure in the (still hypothetical) age of quantum computers because cryptographic schemes based on NP-hard problems seem to withstand attacks by quantum computers (see [ 3 ]).”
BackgroundBinary Subdivision for Quantum SearchPreprint
Zakaria, M. N. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1101.4703 · Cited by 1
“e method proposed in this paper, however, should be easier to understand and implement. 3. While it has been proven before that a black-box quantum query algorithm cannot solve NP problems in o(2n/2) [1], the approach in this paper incorporates non-unitary model, and hence it does not violate the result in [1]. 8 4. T…”
MethodQubit Logic, Algebra and Geometry
Havel, T. F. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45410-1_14 · Cited by 1
“Such operations, generally some form of Fourier transformation, have been discovered for only a very few problems to date, and in particular, quantum computers are unlikely to be a panacea for NP-complete problems [ 20 ].”
BackgroundEntanglement in systems of oscillators and quantum computationsPreprint
Ozhigov, Y. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.0747 · Cited by 1
“k: |kc|=ωif λkΨfΨphot k Here the phase of λk does not influence to the entanglement if we use (2).”
BackgroundRoland, J., & Cerf, N. J. (2004) · Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · Cited by 1
NP in BQP with NonlinearityPreprint
Gossett, P. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9804025 · Cited by 1
“Introduction Despite a series of successes for isolated problems (the Deutsch-Jozsa algorithm [1], Simon’s problem [2], discrete log and factorization [3]), a number of recent papers [4,5,6,7,8,9] have cast doubt that quantum computers are capable of solving NP-complete problems in polynomial time…”
BackgroundFeynman Path Integral Approach on Superconducting Qubits and Readout ProcessPreprint
Rad, A. I., Zandi, H., & Fardmanesh, M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1403.5762 · Cited by 1
Oblivious Transfer à la Merkle
Brassard, G., Salvail, L., & Tapp, A. (2009) · International Conference on Quantum, Nano and Micro Technologies (ICQNM) · doi:10.1109/icqnm.2009.28 · Cited by 1
“Moreover, this algorithm is optimal in the sense that no quantum algorithm could expect to succeed with o( √ N ) queries [4].”
BackgroundSelf-citationQuantum Algorithms and Complexity for Continuous Problems
Papageorgiou, A., & Traub, J. F. (2013) · Springer eBooks · doi:10.1007/978-3-642-27737-5_424-3 · Cited by 2
Investigations in Quantum Computing: Causality and Graph Isomorphism
Beckman, D. (2004) · CaltechTHESIS (California Institute of Technology) · doi:10.7907/s1r0-0v87 · Cited by 1
On the Power of Quantum Multi-Prover Interactive Proof SystemsPreprint
Kobayashi, H., & Matsumoto, K. (2001) · arXiv (Cornell University) · Cited by 1
Haverkort, H. J., & Toma, L. (2016) · Springer eBooks · doi:10.1007/978-1-4939-2864-4_585 · Cited by 4
Conclusive exclusion of quantum states and aspects of thermo-majorization
Perry, C. (2016) · UCL Discovery (University College London) · Cited by 2
Complexity analysis and semantics for quantum computation
Kashefi, E. (2003) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 4
Post-Quantum Elliptic Curve Cryptography
Soukharev, V. (2016) · UWSpace (University of Waterloo) · Cited by 1
Universal Test for Quantum One-Way Permutations
Kawachi, A., Kobayashi, H., Koshiba, T., & Putra, R. H. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28629-5_66 · Cited by 1
Computational Space, Time and Quantum Mechanics
Nicolaidis, M. (2010) · IGI Global eBooks · doi:10.4018/978-1-61692-014-2.ch016 · Cited by 2
Computationally secure uncloneable encryption scheme
Ma, Z., Lü, X., & Feng, D. (2005) · International Symposium on Communications and Information Technologies · doi:10.1109/iscit.2004.1413855 · Cited by 1
St-Jules, M. (2016) · uO Research (University of Ottawa) · doi:10.20381/ruor-329 · Cited by 5
An upper bound on the rate of information transfer by Grover's oracle
Arıkan, E. (2005) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2005.07.031 · Cited by 1
Signature Schemes in the Quantum Random-Oracle Model
Eaton, E. (2017) · UWSpace (University of Waterloo) · Cited by 1
Quantum walk on two-dimensional torus and grid
Komeili, M. (2018) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/31963 · Cited by 1
Knot theory and quantum computingPreprint
Gaudreau, R., & Ledvinka, D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.03186 · Cited by 1
“More discussion of the limitations of the quantum circuit model can be found in [5].”
BackgroundOn the physical limit of quantum computingPreprint
Ozhigov, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.05426 · Cited by 1
Quantum Computation Relative to OraclesPreprint
Tamon, C., & Yamakami, T. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0010002 · Cited by 1
“[10, 3] bsǫ (M, A, x) ≤ 8T (x)(2)/ǫ(2), where T (x) is the running time of M with A on x.”
BackgroundMethodOne Complexity Theorist's View of Quantum ComputingPreprint
Fortnow, L. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0003035 · Cited by 2
“Bennett, Bernstein, Brassard and Vazirani [BBBV97] show an interesting way to get around this problem: Compute whether the quantum machine accepts.”
BackgroundInfluentialMassively Parallel Algorithms for String Matching with Wildcards.Preprint
Hajiaghayi, M., Saleh, H., Seddighin, S., & Sun, X. (2019) · arXiv (Cornell University) · Cited by 1
An Economic Model for Quantum Key-Recovery Attacks against Ideal CiphersPreprint
Harsha, B., & Blocki, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.05911 · Cited by 3
Quantum comparator circuit on superconducting quantum computer
Benchasattabuse, N. (2019) · Chula Digiverse · doi:10.58837/chula.the.2019.156 · Cited by 1
Signcryption in a Quantum WorldPreprint
Puria, S. K. P. (2021) · IACR Cryptology ePrint Archive · Cited by 1
Quantum Request-Answer Game with Buffer Model for Online AlgorithmsPreprint
Khadiev, K. R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.12321 · Cited by 1
“Due to [43], the randomized query complexity of unstructed search among mk/2 is Ω(mk).”
Post-Quantum Key Exchange Protocols
Li, X., Leung, L., Kwan, A. C. T., Zhang, X., Kahanda, D., & Anshel, M. (2006) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1
Quantum computations (course of lectures)Preprint
Ozhigov, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.08047 · Cited by 1
Kendon, V. M. (2017) · Springer eBooks · doi:10.1007/978-3-642-27737-5_429-4 · Cited by 1
Kendon, V. M. (2015) · Springer eBooks · doi:10.1007/978-3-642-27737-5_429-3 · Cited by 1
Discrete logarithm and Diffie-Hellman problems in identity black-box groupsPreprint
Ivanyos, G., Joux, A., & Sántha, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.01662 · Cited by 1
“[8] have shown that Ω( √ N) queries are also necessary.”
BackgroundHybrid hypercomputing: towards a unification of quantum and classical computationPreprint
Horsman, D. C., & Munro, W. J. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0908.2181 · Cited by 1
Chen, H. (2023) · OSF Preprints (OSF Preprints) · doi:10.31219/osf.io/nsuf5 · Cited by 1
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.