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
Items 1,301–1,400 of 1,465
Hidden symmetry detection on a quantum computer
Schützhold, R., & Unruh, W. G. (2007) · Quantum Information and Computation · doi:10.26421/qic7.1-2-4
The quantum adversary method and classical formula size lower boundsPreprint
Laplante, S., Lee, T., & Szegedy, M. (2005) · arXiv (Cornell University)
Preliminary study for developing instantaneous quantum computing algorithms (IQCA)
Amoroso, R. L. (2019) · Journal of Physics Conference Series · doi:10.1088/1742-6596/1251/1/012005
“This implies subquadratic speedups for many other basic problems [49].”
BackgroundMethodDilawar, N., Nadeem, S., Arooj, S., Rizwan, M., & Ahmad, F. (2018) · ICST Transactions on Scalable Information Systems · doi:10.4108/eai.13-7-2018.159794
“Each memory location can have values 0, and both 0 and 1 at a same time [7].”
BackgroundPerformance Analysis and Parameter Optimization of the Optimal Fixed-Point Quantum Search
Bao, T.-Y., & Huang, D. (2019) · Applied Sciences · doi:10.3390/app9173584
Xu, C. (2019) · Berkeley Scientific Journal · doi:10.5070/bs3232045346
Security Analysis of Quantum Obfuscation
Shang, T., & Liu, J. (2020) · Springer eBooks · doi:10.1007/978-981-15-3386-0_12
The Crown Jewels of Quantum Algorithms
Bera, R. K. (2020) · Undergraduate lecture notes in physics · doi:10.1007/978-981-15-2471-4_10
Tetrapartite Entanglement of GHZ State in Noninertial Frames
钟, 海. (2020) · Pure Mathematics · doi:10.12677/pm.2020.104033
Cryptographic Hardness based on the Decoding of Reed-Solomon Codes.Preprint
Kiayias, A., & Yung, M. M. (2007) · IACR Cryptology ePrint Archive
A study of one-turn quantum refereed games
Ghosh, S. (2020) · UWSpace (University of Waterloo)
Quantum Computers for Next Generation
Telkar, N., Naik, P., Mabali, A., Girish, S. H., Gurusiddeshwar, S. H., & Balikai, S. (2020) · International Journal of Scientific Research in Computer Science Engineering and Information Technology · doi:10.32628/cseit2063118
On the Theory of Modern Quantum Algorithms.Preprint
Biamonte, J. (2020) · arXiv (Cornell University)
Eight Oxford Questions: Quantum Mechanics Under a New Light
Ares, N., Pearson, A., & Briggs, G. A. D. (2020) · Fundamental theories of physics · doi:10.1007/978-3-030-46777-7_25 · Cited by 1
“In particular, when the internal entanglement of a system becomes sufficiently high, our ability to simulate the system with anything other than a quantum computer falls away, due to the apparent difference between the computational complexity classes P and BQP [125].”
BackgroundFlores, A. A. O. (2020) · Revista de la Escuela de Física · doi:10.5377/ref.v8i1.10085
Quantum Computing and Programming
Bassoli, R., Boche, H., Deppe, C., Ferrara, R., Fitzek, F. H. P., Janßen, G., & Saeedinaeeni, S. (2020) · Foundations in signal processing, communications and networking · doi:10.1007/978-3-030-62938-0_3
A Note About Claw Function with a Small RangePreprint
Ambainis, A., Balodis, K., & Iraids, J. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2021.6
ABOUT QUANTUM COMPUTER AND QUANTUM MEDICINE
Борисевич, М. Н., & Kozlovsky, V. I. (2021) · Vestnik of Vitebsk State Medical University · doi:10.22263/2312-4156.2021.2.18
Quantum-resistant digital signatures schemes for low-power IoTPreprint
Hattenbach, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.11710 · Cited by 1
“It was also shown, that something similar to grovers algorithm but with exponential speedup is impossible [6].”
Multiplicative inverse with quantum search algorithm under π/18 phase rotation
Yang, Y.-F., Duan, L., Qiu, T., & Xie, X.-M. (2021) · The European Physical Journal Plus · doi:10.1140/epjp/s13360-021-01704-5
Towards Quantum Resistant Key Agreement Schemes Using Unpredictability
Elhao, A., Megahed, M. H., & Elsamahy, E. A. (2021) · International Conference on Electronics, Computers and Artificial Intelligence (ECAI) · doi:10.1109/ecai52376.2021.9515012 · Cited by 1
Parallel Quantum Pebbling: Analyzing the Post-Quantum Security of iMHFs.Preprint
Blocki, J., & Lee, S. (2021) · arXiv (Cornell University)
Lower bounds on quantum query complexity for symmetric functionsPreprint
Mittal, R., Nair, S. S., & Patro, S. (2021) · arXiv (Cornell University) · Cited by 2
Abnormal Quantum State Search Based on Parallel Phase Comparison
Xu, G., Xu, X., & Wang, X. (2021) · Parallel Processing Letters · doi:10.1142/s0129626421500225
Quantum Heaviside Eigen SolverPreprint
Sun, Z.-Z., & Su, G. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.08288
“Luckily we can use either the full-blown quantum counting [5, 6] or a trial-anderror scheme where iterates are applied by an exponentially increasing number of times [5, 7] without losing the quadratic speedup from quantum search algorithm.”
MethodOn the power of "modal quantum" computation.Preprint
de Beaudrap, N. (2014) · arXiv (Cornell University)
Zhang, J., & Zhang, Z. (2020) · Springer eBooks · doi:10.1007/978-981-15-8427-5_1
Meter, R. V. (2014) · Wiley eBooks · doi:10.1002/9781118648919.biblio
Imre, S., & Balázs, F. (2004) · Wiley eBooks · doi:10.1002/9780470869048.refs
Babu, H. M. H. (2020) · Wiley eBooks · doi:10.1002/9781119679455.biblio
Imre, S., & Gyöngyösi, L. (2012) · Wiley eBooks · doi:10.1002/9781118337462.refs
Quantum Algorithms and Complexity for Continuous Problems
Papageorgiou, A., & Traub, J. F. (2011) · Springer eBooks · doi:10.1007/978-1-4614-1800-9_145
(2011) · Elsevier eBooks · doi:10.1016/b978-0-12-383874-2.00009-6
Quantum Computing Approach for Alignment-Free Sequence Search and Classification
Kotamarti, R. M., Thornton, M. A., & Dunham, M. H. (2013) · IGI Global eBooks · doi:10.4018/978-1-4666-3604-0.ch090
Kempe, J., & Vidick, T. (2010) · Lecture notes in physics · doi:10.1007/978-3-642-11914-9_10 · Cited by 4
“Moreover, a matching lower bound was proved in [10], showing that Grover’s algorithm is essentially optimal, and also showing that quantum algorithms cannot solve NP-complete problems efficiently in a black-box setting, i.”
BackgroundJiao, L., Shang, R., Liu, F., & Zhang, W. (2020) · Elsevier eBooks · doi:10.1016/b978-0-12-819795-0.00001-3
Braunstein, S. L. (2003) · Wiley eBooks · doi:10.1002/3527600434.eap585
Ahlswede, R. (2005) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2005.07.077
Kendon, V. M. (2009) · Springer eBooks · doi:10.1007/978-0-387-30440-3_429
Yan, S. Y. (2018) · Springer eBooks · doi:10.1007/978-3-319-72536-9_3
Yan, S. Y. (2015) · Springer eBooks · doi:10.1007/978-3-319-25823-2_1
Grover, L. K., & Patel, A. D. (2015) · Springer eBooks · doi:10.1007/978-3-642-27848-8_317-2 · Cited by 1
Minoli, D. (2005) · Wiley eBooks · doi:10.1002/0471736600.refs
Quantum Algorithm for Finding Triangles
Richter, P. C. (2008) · Springer eBooks · doi:10.1007/978-0-387-30162-4_308
Huang, W. (2022) · Research Square · doi:10.21203/rs.3.rs-2200915/v1
Quantum algorithm for search of largest square on two dimensional map
Khadiev, K. R., & Remidovskii, V. (2022) · Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications" · doi:10.20948/dms-2022-25
Quantum algorithm for search of longest segment of elements satisfying a predicate
Khadiev, K. R., & Bikmullin, T. E. (2022) · Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications" · doi:10.20948/dms-2022-24
Quantencomputing und Programmierung
Bassoli, R., Boche, H., Deppe, C., Ferrara, R., Fitzek, F. H. P., Janßen, G., & Saeedinaeeni, S. (2023) · Springer eBooks · doi:10.1007/978-3-031-26326-2_3
Arenstein, L. S. (2022) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/d.45.2022.tde-19062023-143615 · Cited by 1
Developments in Post‐Quantum Cryptography
Sarkar, S., Kumar, S. S., Bose, A., & Mukherjee, T. (2023) · Wiley eBooks · doi:10.1002/9781119879831.ch5
An Approach to the Classification of Finite Semifields by Quantum Computing
Cáceres, J. M. H., & Rúa, I. F. (2023) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-031-32707-0_16
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0006
Microwave resonators for superconducting devices
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0013
(2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.002.0003
The rotating wave approximation
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0001
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0004
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0007
Quantum simulation of Hamiltonian eigenstates
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0012
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0002
Quantum simulation of Hamiltonian dynamics
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0011
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0009
The molecular Hamiltonian in second quantization
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0004
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0005
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0008
Oblivious amplitude amplification lemma
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0005
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0006
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0003
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0001
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0014
(2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.002.0005
(2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.002.0004
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0010
An equilibrium thermodynamics analysis of quantum thermal searchPreprint
Review, B. (2023) · OSF Preprints (OSF Preprints) · doi:10.31219/osf.io/mxv9y
(2023) · SciPost Physics · doi:10.21468/scipost.report.8094
A Grover-like Quantum Algorithm for Minimum Distance Decoding of Linear Block Codes
Kim, G., & Oh, J. (2023) · International Conference on Information and Communication Technology Convergence (ICTC) · doi:10.1109/ictc58733.2023.10393803
Digital Signatures and Quantum Computing
Andrade, F., & Almeida, J. B. (2024) · Law, governance and technology series · doi:10.1007/978-3-031-41820-4_12
Underlying theory for quantum computing
Giardina, C. R. (2024) · Elsevier eBooks · doi:10.1016/b978-0-443-13697-9.00006-0
Hull, I., Sattath, O., Diamanti, E., & Wendin, G. P. (2024) · Contributions to economics · doi:10.1007/978-3-031-50780-9_4
Physics for secure and efficient societies
Barbato, F. C. T., Barthélemy, M., Beck, C., Biamonte, J., Cirac, J. I., Malz, D., Marino, A., Seskir, Z. C., & Ventura‐Traveset, J. (2024) · Institute of Physics eBooks · doi:10.1088/978-0-7503-6342-6ch7 · Cited by 1
Quantum thermal search: computing ground states via quantum mixing thermal operations
Kim, M. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04413-x
Oracle Quantum Algorithms: An OverviewPreprint
da Silva, R. P. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4862127 · Cited by 1
The serial and/or parallel execution of Grover's algorithmPreprint
Creemers, S. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4889509
Quantum Key Distribution Protocols
Sihare, S. R. (2024) · Advances in systems analysis, software engineering, and high performance computing book series · doi:10.4018/978-1-7998-9522-0.ch003
Shang, T. (2024) · Springer eBooks · doi:10.1007/978-981-97-6722-9_2
Quantum Acceleration of Black-Box Pseudo-Boolean Optimization Algorithms
Ajimakin, A. D., & Devi, V. S. (2024) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2024.3485194
“Both versions are suboptimal for the N EEDLE problem, known to be optimally solvable in O ( √ 2 n ) [6] by the Grover’s algorithm [1].”
Shallow-Depth Quantum Circuit for Unstructured Database Search
Zhan, J. (2024) · Quantum Reports · doi:10.3390/quantum6040037
Ding, X., & Clark, B. K. (2024) · Physical Review A · doi:10.1103/physreva.110.062403
Chen, Z. Y. (2024) · Applied and Computational Engineering · doi:10.54254/2755-2721/2024.melb18296
Creiner, A. (2022) · University of North Texas Digital Library (University of North Texas) · doi:10.12794/metadc1987243
Observer-Dependence in P vs NP
Nye, L. (2025) · Journal of Modern Physics · doi:10.4236/jmp.2025.161002
Alagh, A., Wason, R., & Arora, P. (2024) · IEEE Delhi Section Conference (DELCON) · doi:10.1109/delcon64804.2024.10867251
“The rise in quantum computing is a threat to traditional cryptographic systems, their data as well as communications across the Internet[5].”
Influence of IQT on research in ICT, part 2
Suszyński, P., Dubiński, J., Ignaciuk, A., Jimenez-Soler, P., Pituła, E. W., Wójtowicz, P., & Romaniuk, R. S. (2025) · International Journal of Electronics and Telecommunications · doi:10.24425/ijet.2025.153566
“The fact that the Grover speedup, which is just quadratic, is the best achievable one for oracle lookups [3] serves as a reminder to tread carefully.”
Dang, V. T., & Volkov, A. (2024) · Telecom IT · doi:10.31854/2307-1303-2024-12-3-29-51
On Quantum Money and Evasive Obfuscation
Zhandry, M. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-91131-6_7
“The following result is paraphrased from [BBBV97]: Lemma 3 ([BBBV97] Theorems 3.1 and 3.3) .”
InfluentialAHP-Based Approach in Quantum Computing Difficulties in the Software Sector
Habboo, A. F. H. (2025) · Journal of Information Systems Engineering & Management · doi:10.52783/jisem.v10i21s.7224
Квантовые алгоритмы и угрозы кибербезопасности
Kozachok, A. V., Тарасенко, С. І., & Kozachok, A. V. (2025) · Modelirovanie, optimizaciâ i informacionnye tehnologii. · doi:10.26102/2310-6018/2025.49.2.019
Singh, K., Virender, V., Singh, G., Pombeiro, A. J. L., & Mohan, B. (2025) · Wiley eBooks · doi:10.1002/9781394248605.ch5
The Fundamental Theorem for Eco-Environmental Surface Modelling
Yu, G., Zhao, N., Shi, W., & Fan, Z. (2025) · Springer eBooks · doi:10.1007/978-981-96-1977-1_2
Resource-efficient quantum data representation based on Grover’s algorithm
Ji, J., & Bae, J. (2025) · International Journal of Quantum Information · doi:10.1142/s0219749925500182
A Pedagogical Introduction to the Deutsch and Deutsch-Jozsa AlgorithmsPreprint
Guchhait, A. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5372952
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.