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,401–1,466 of 1,466
A Pedagogical Introduction to the Deutsch and Deutsch-Jozsa AlgorithmsPreprint
Guchhait, A. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5372952
A Collapse-free Quantum Algorithm for a Problem in QSZK
Hepp, H., da Silva, M. V. G., & Zatesko, L. M. (2025) · Anais do Encontro de Teoria da Computação (ETC) · doi:10.5753/etc.2025.9268
Wang, C., Lin, Y., & Cheng, L. (2025) · IEEE Transactions on Learning Technologies · doi:10.1109/tlt.2025.3604522 · Cited by 1
“This approach is known as the quantum-logic design approach [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11].”
Quantum CCA-Secure PKE, Revisited
Alamati, N., & Maram, V. (2025) · Journal of Cryptology · doi:10.1007/s00145-025-09555-4
“We note that one might use other well-known techniques (for example, the Gentle Measurement Lemma; see [BBC + 21, Theorem 1], an adaptation of [BBBV97, Theorem 3.3]) to show the indistinguishability of the quantum decryption oracles G and H in the overview above.”
InfluentialQuantum search for gravitational wave of massive black hole binaries
郭, F. L. 福. G., & He, J. (2025) · Physical review. D/Physical review. D. · doi:10.1103/3n8r-7dm7 · Cited by 1
“By encoding a large template space into quantum states and applying amplitude amplification techniques, quantum matched filtering may improve search efficiency.”
On the query complexity of unitary channel certification
Jeon, S., & Oh, C. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01135-5 · Cited by 7
“A well-known solution to this is Grover’s algorithm, which achieves a quadratic speedup over the brute-force approach in a basis-search problem [34, 35].”
Benincasa-Dowker-Glaser causal set actions by quantum counting
Adamson, S. A., & Wallden, P. (2026) · Physical Review Research · doi:10.1103/qdst-yrh6
“Moreover, this quantum speedup is asymptotically tight [34].”
Quantum algorithm for binary vector encoding and retrieval utilizing the permutation trick
Wichert, A. (2026) · Quantum Machine Intelligence · doi:10.1007/s42484-026-00454-w
“4.”
Krishnakumar, R. (2025) · Springer eBooks · doi:10.1007/978-3-031-90727-2_10
Hunt, E., Nguyen, H., Tukkugudam, D. S., Horton, D., & Nguyen, T. N. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00036
Computational Complexity Bounds for Maxwell's Demon: From Landauer's Principle to Quantum AdvantagePreprint
Enriquez, R. P. H. (2025) · SSRN Electronic Journal · doi:10.21203/rs.3.rs-8271063/v1
Hybrid-Query Bounds with Partial Input Control Framework and Application to Tight M-eTCR
Hülsing, A., Kudinov, M., & Majenz, C. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-5125-5_9
Barhoush, M., Nishimaki, R., & Yamakawa, T. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-5125-5_17 · Cited by 6
Symmetry operations and critical behavior in classical to quantum stochastic processes
Cabrera, G. M., Biswas, S., & Gorin, T. (2025) · Physical review. E · doi:10.1103/sxv8-vv6r
The complexity of parameters for probabilistic and quantum computation
Breutzmann, J. M. (1996) · Iowa State University Digital Repository (Iowa State University) · doi:10.31274/rtd-180813-10541
“The second is from Bennett, Bernstein, Brassard and Vazirani [9].”
BackgroundMethodInfluentialQuantum algorithms for searching, resampling, and hidden shift problems
Ozols, M. (2012) · UWSpace (University of Waterloo)
On the Exploration of Post-Quantum Algorithms on COTS-Based Avionic Architectures
Hamel, J., de Magalhães, F. G., & Nicolescu, G. (2025) · IEEE Interregional NEWCAS Conference (NEWCAS) · doi:10.1109/newcas64648.2025.11107112
Lee, D., & Lee, S. (2026) · Scientific Reports · doi:10.1038/s41598-025-30625-x
A Quantum Global Optimization Algorithm: Application to the Knapsack ProblemPreprint
Cherif, M. Y., Chaari, W. L., & Driss, O. B. (2026) · Research Square · doi:10.21203/rs.3.rs-8555103/v1
Measuring Less to Learn More: Quadratic Speedup in Learning Nonlinear Properties of Quantum States
Zhang, Y., Wu, Y., Zhou, Y., & Yuan, X. (2026) · Physical Review Letters · doi:10.1103/cllg-15kd · Cited by 13
Quantum interference conventions: Overlap determinability and the unified no-superposition principle
Bang, J., Cho, K., & Yee, K. H. (2026) · Physical Review A · doi:10.1103/s3mc-38zd · Cited by 3
“…algorithm finds w using O ( √ N ) oracle calls, where N := 2 n [1], and the Bennett-Bernstein-Brassard-Vazirani hybrid argument shows that this scaling is optimal for quantum theory: i.e., any algorithm using unitary dynamics and Born-rule measurement requires Ω( √ N ) queries [25] (see also Ref.”
Connecting Quantum Computing with Classical Stochastic Simulation
Blanchet, J., Squillante, M. S., Szegedy, M., & Wang, G. (2025) · Winter Simulation Conference · doi:10.1109/wsc68292.2025.11339097 · Cited by 2
“This running time is known to be of optimal order (Bennett et al. 1997), with even the constant factor being optimal (Zalka 1999), in stark contrast to the best possible classical algorithm, which requires at least Ω ( N ) operations in the worst case to find ω with high probability.”
Coherence dynamics in conditional quantum search with bi-quadratic speed-up
Rastegin, A. E. (2026) · Chinese Journal of Physics · doi:10.1016/j.cjph.2026.02.005
Markov chain decision-making with quantum-assisted entropy kernels
Peretz, O., & Koren, M. (2026) · Discover Quantum Science · doi:10.1007/s44464-026-00010-2
“By exploiting superposition, interference, and controlled entanglement, quantum computing operates in Hilbert spaces whose effective dimensionality surpasses classical representations [5, 38, 45].”
A Survey of Quantum Computing: Foundations, Challenges, and Emerging DirectionsPreprint
Hassan, M. R., Mahmoud, T. M., & Kaabouch, N. (2026) · doi:10.36227/techrxiv.177223090.01125198/v1
Wang, C., Lin, Y., Ou, C., & Shih, J.-D. (2025) · Quantum Information and Computation · doi:10.2478/qic-2025-0037
“Nowadays, the design of quantum algorithms is divided into two categories: the quantum-logic algorithm de-sign approach [1,2,4,6–11] and the quantum QUBO algorithm design approach [12–17].”
Authentication and encryption protocols : design, attacks and algorithmic improvements
Maimuţ, D. (2015) · theses.fr (ABES) · doi:10.70675/a4c4e8d2z5e4cz4eafzbf6bzfb9b77e3cfb7 · Cited by 1
Classical and quantum cryptanalysis for Euclidean lattices and subset sums
Shen, Y. (2021) · theses.fr (ABES) · doi:10.70675/c36a63dbz469ez406azba4fza2fd2c7ca09b
Secret-key cryptography and impact of a quantum attacker on the telecommunication world
Frixons, P. (2022) · theses.fr (ABES) · doi:10.70675/816f8235z99bfz4cb9zbe68z075dcc32e303
Performance evaluation and control improvements for solving optimization problems on NISQ platforms
Gilbert, V. (2024) · theses.fr (ABES) · doi:10.70675/81f9c638z5867z40e4zaed8ze9824ff5a163 · Cited by 1
Complex quantum Networks for machine learning protocols
Henaff, J. (2024) · theses.fr (ABES) · doi:10.70675/9cf94ee2z8367z4741zb21bz2eb55cf23f29
SiO x ‐Based Probabilistic Bits Enabling Invertible Logic Gate for Cryptographic Applications
Kim, J., Choi, H., & Woo, J. (2026) · Advanced Intelligent Systems · doi:10.1002/aisy.70365
Grover Quantum Algorithm: Applications and Limits
Hill, D. R. C. (2026) · Encyclopedia · doi:10.3390/encyclopedia6040089
“The BBBV theorem [10] (named after Charles Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani) establishes a fundamental lower bound in quantum computing ( Ω ( √ N) in asymptotic notation); thus, Grover’s algorithm is likely optimal for an unstructured search.”
Algorithmic Approaches to Consciousness, and Why They Are Incomplete
Edwards, D. J. (2026) · Springer eBooks · doi:10.1007/978-3-032-15628-0_2
How to Prove Post-quantum Security for Succinct Non-interactive Reductions
Chiesa, A., Di, Z., Hu, Z., & Zheng, Y. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-25336-1_14
Monogamous entanglement cheats at the price of complexity
Corbeel, A., & Verlinde, E. (2026) · International Journal of Modern Physics D · doi:10.1142/s021827182640002x
QRAP: A Quantum Resource Allocation Platform for Adaptive Scheduling Under Topology Constraints
Guo, S., Liu, Z., & Qu, Z. (2026) · Software Practice and Experience · doi:10.1002/spe.70080
Quantum-Resistant Authenticated Encryption Variants of GCM
Fischlin, M., & Schmalz, T. (2026) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.a66che8nm2-x
“However, Bennett et al. [BBBV97] showed that these changes can be neglected, as long as the total query magnitude on the modified inputs is small (see also, e.g., [BDF + 11; BBC + 21]).”
InfluentialAdditive Resource Scaling in Quantum Circuits for Search in Cryptanalysis
Lavagna, L., Vittori, G., Rosato, A., & Panella, M. (2026) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas66217.2026.11562218
“…in this case we do not need an explicit formula since (even for states outside the action of Π S ) Grover’s bound in the form of a ‘rank budget’ [20] shows the existence of a projector Π T on H T such that, starting from any branch a and any workspace state, the algorithm can concentrate…”
Grover’s Model with Single Oracle Call and Log(N) Different Diffusion Calls
Liu, Y. (2026) · Journal of Quantum Information Science · doi:10.4236/jqis.2026.162009
Khadiev, K. R. (2021) · doi:10.55056/ceur-ws.org/vol-2850/paper1.pdf
“Due to [43], the randomized query complexity of unstructed search among mk/2 is Ω(mk).”
The societal and technological impact of Quantum Computers
Beressova, A., Alimov, A., Taipov, A., Moldabek, B., & Galizhan, N. (2026) · Journal of Emerging Technologies and Computing · doi:10.47344/mps66a79
Kulkarni, P. P., & Alam, A. (2026) · Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data) · doi:10.1145/3811628.3811832
Oracle problems as communication tasks and optimization of quantum algorithms
Te’eni, A., Schwartzman-Nowik, Z., Nowakowski, M. L., Horodecki, P., & Cohen, E. (2026) · Physical Review Research · doi:10.1103/5qsb-5jy5 · Cited by 1
“Indeed, it is sometimes possible to prove not only upper bounds on the query complexity of a given problem, but also lower bounds [5–10], which are usually difficult to obtain in both classical and quantum complexity theory.”
BackgroundCounting Random Oracles for the Polynomial-Time Hierarchy and Quantum Complexity Classes
Hitchcock, J. M., Sekoni, A., & Shafei, H. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-31348-5_22
Cuomo, M. T., Tortora, D., Prete, S. D., Loia, F., & Papa, A. (2026) · De Gruyter eBooks · doi:10.1515/9783111593814-021
Generation of Probabilistic Bits by Exploiting Orthogonal Spin Currents in Magnetic Trilayers
Han, D., Shin, C., Kim, S.-J., Jang, Y., Koh, D., Kim, T., Jung, J., Baek, G., Kang, M., Kim, E., et al. (2026) · Advanced Science · doi:10.1002/advs.202524371
Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search
Anonymous, An, D., Hu, J., & Wen, Z. (2026) · Physical Review A · doi:10.1103/7k6t-m463 · Cited by 2
“Classically, this problem is inherently inefficient, as guaranteeing success requires Ω( N/M ) queries [7].”
Chakraborty, A., Banik, M., & de Wolf, R. (2026) · Research Square · doi:10.21203/rs.3.rs-10587821/v1 · Cited by 4
Taherdoost, H. (2026) · Cryptography · doi:10.3390/cryptography10040053
“It is shown to be best for random search [56], and the speedup is linear rather than exponential.”
Unclonable Encryption in the Haar Random Oracle Model
Bartusek, J., & Goldin, E. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35409-9_11
A Bi-directional multi-solution scalable Grover search Algorithm
Konar, D., Hafeez, Z., & Aggarwal, V. (2026) · Quantum Information Processing · doi:10.1007/s11128-026-05328-5
“GS technique is known for its ability to locate an item in an unstructured list with high probability using only O ( √ N ) [1, 8] evaluations, a substantial improvement over classical systems.”
Petkova, E. (2026) · Proceedings of the International Conference on Secure Systems Design and Technology Development · doi:10.68302/std2026.vol1.222
VERIFYING ASPECTS AN "BRUTE FORCE" ATTACK ON 256 - AES ENCRYPTED VOICE STREAM
Petkova, E., & Angelov, M. (2026) · Proceedings of the International Conference on Secure Systems Design and Technology Development · doi:10.68302/std2026.vol1.223
EQuADiSE: Efficient Quantum-Safe Adaptive Distributed Symmetric-Key Encryption
Sinha, S., Patranabis, S., & Mukhopadhyay, D. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-38695-3_28
Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search
Ziatdinov, M., Levkovich-Maslyuk, F., & Pothos, E. M. (2026) · Entropy · doi:10.3390/e28101060
“One of the fundamental quantum algorithms–Grover’s algorithm–solves the un-structured search problem with O ( √ N / M ) query complexity, providing a quadratic speedup over the classical lower bound of Ω ( N / M ) , where M is the number of solutions to f ( x ) = 1 (marked items) [1,9,15].”
Seyidova, M. (2026) · Luminis Applied Science and Engineering · doi:10.69760/lumin.2026003004
Akhtar, M. A. K. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.7543198
Learning Shallow Quantum Circuits
Huang, H.-Y., Liu, Y., Broughton, M., Kim, I., Anshu, A., Landau, Z. A., & McClean, J. R. (2026) · SIAM Journal on Computing · doi:10.1137/24m1689946
A Survey on Security Reductions in Post-Quantum Cryptography
Attema, T., Cramer, R., Fehr, S., Huang, Y., de Kock, B., & Sotáková, J. (2026) · IACR Communications in Cryptology · doi:10.62056/a0zo-49p1
Tomography-free quantum diagnostics of dissipative quantum chaosPreprint
Wakaura, H., & Tanimae, T. (2026) · Research Square · doi:10.21203/rs.3.rs-11442426/v1
How to Define Expected Quantum Polynomial-Time Zero Knowledge Simulation
Lai, Z., Spooner, N., & Tromanhauser, M. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-43624-5_9
Study on quantum-inspired optimization approaches for flow shop scheduling problems
Xin, W. (2012) · Institutional Repositories DataBase (IRDB)
Physical systems for the solution of hard computational problems
Mattsson, P. (2003)
(1998) · doi:10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
Self-citation
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.