Source Count: 14 | Weighted Score: 40 | Source Confidence: [4/5] | Primary Tier: 1 | Last Updated: April 1, 2026
Keywords: quantum computing, quantum algorithm, Shor's algorithm, Grover's algorithm, quantum error correction, qubit, quantum supremacy, variational quantum eigensolver, NISQ, quantum gate, quantum circuit, quantum Fourier transform
Category Tags: quantum-computing, quantum-algorithms, computational-complexity, cryptography, quantum-error-correction, variational-methods
Cross-References: V_4_01 — Computer Science Foundations · ZA_5_01 — Quantum Technology Overview · V_4_13 — Cryptography History

QUICK SUMMARY

Quantum computing exploits the principles of quantum superposition, entanglement, and interference to perform computations that are intractable for classical computers. The field was conceptually launched by Richard Feynman (1982), who proposed that simulating quantum systems requires a quantum mechanical computer, and by David Deutsch (1985), who formalized the quantum Turing machine. The two most transformative quantum algorithms are Shor's algorithm (1994), which factors large integers in polynomial time — threatening RSA encryption — and Grover's algorithm (1996), which searches unsorted databases with quadratic speedup. In 2019, Google claimed quantum supremacy with its 53-qubit Sycamore processor, performing a specific sampling task in 200 seconds that would take the most powerful classical supercomputer approximately 10,000 years (though IBM disputed this estimate). The current era of Noisy Intermediate-Scale Quantum (NISQ) devices — processors with 50–1,000+ qubits but lacking full error correction — has driven development of hybrid classical-quantum algorithms such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA), which are designed to extract useful computation from imperfect hardware.

1. VERIFIED CLAIMS (Tier 1 — Peer-Reviewed / Established)

1.1 Shor's Algorithm: Polynomial-Time Integer Factoring

• Evidence: In 1994, Peter Shor (AT&T Bell Labs) published an algorithm that factors an n-bit integer in O(n³) time on a quantum computer — exponentially faster than the best known classical algorithm (the general number field sieve, which runs in sub-exponential time ~O(exp(n^{1/3}))). KEY FINDING Shor's algorithm uses the quantum Fourier transform (QFT) to efficiently find the period of modular exponentiation functions, then applies classical number theory (the reduction of factoring to period-finding, known since Euler) to extract prime factors. The security of RSA encryption — which relies on the classical intractability of factoring products of two large primes — would be broken by a sufficiently large, error-corrected quantum computer running Shor's algorithm. Current estimates suggest that breaking RSA-2048 would require a quantum computer with approximately 4,000 logical qubits (corresponding to millions of physical qubits with current error rates).
• Primary Source: Shor, Peter W. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." Proceedings of the 35th Annual Symposium on Foundations of Computer Science (1994): 124–134

1.2 Grover's Algorithm: Quadratic Search Speedup

• Evidence: In 1996, Lov Grover (Bell Labs) published an algorithm for searching an unsorted database of N items in O(√N) quantum operations, compared to the classical O(N) requirement. Grover's algorithm uses amplitude amplification — repeated applications of an oracle function and a diffusion operator that progressively increase the probability amplitude of the target item while decreasing amplitudes of non-target items. Charles Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani (1997) proved that Grover's speedup is optimal — no quantum algorithm can search an unstructured database faster than O(√N). Applications extend beyond database search to constraint satisfaction, optimization, and cryptanalysis (Grover's algorithm effectively halves the security of symmetric encryption keys).
• Primary Source: Grover, Lov K. "A Fast Quantum Mechanical Algorithm for Database Search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996): 212–219

1.3 Quantum Error Correction

• Evidence: Quantum systems are inherently susceptible to decoherence (loss of quantum information to the environment) and gate errors (imprecise quantum operations). Peter Shor (1995) and independently Andrew Steane (1996) demonstrated that quantum error correction is possible — quantum information can be encoded redundantly across multiple physical qubits such that errors can be detected and corrected without destroying the encoded information. The surface code (proposed by Alexei Kitaev, 1997, and developed extensively by Robert Raussendorf and others) is currently the leading candidate for scalable error correction, requiring approximately 1,000–10,000 physical qubits per logical qubit depending on the physical error rate. KEY FINDING In 2023, Google demonstrated below-threshold error correction on its Sycamore processor, showing that larger surface codes produced lower logical error rates — a key milestone toward fault-tolerant quantum computing.
• Primary Source: Shor, Peter W. "Scheme for Reducing Decoherence in Quantum Computer Memory." Physical Review A 52.4 (1995): R2493–R2496

1.4 Google's Quantum Supremacy Claim (2019)

• Evidence: In October 2019, Google AI Quantum published in Nature that their 53-qubit Sycamore processor performed a specific random circuit sampling task in 200 seconds that they estimated would take the Summit supercomputer approximately 10,000 years classically. This constituted the first credible claim of quantum computational advantage (or "quantum supremacy," a term coined by John Preskill in 2012). IBM immediately disputed the 10,000-year estimate, arguing that with optimized classical algorithms and sufficient disk storage, Summit could complete the task in approximately 2.5 days. The task itself (random circuit sampling) has no practical application — it was chosen specifically to demonstrate quantum advantage.
• Primary Source: Arute, Frank, Kunal Arya, Ryan Babbush, et al. "Quantum Supremacy Using a Programmable Superconducting Processor." Nature 574.7779 (2019): 505–510

2. CREDIBLE CLAIMS (Tier 2 — Academic / Debated but Supported)

2.1 NISQ Algorithms: VQE and QAOA

• Evidence: The NISQ era (term coined by John Preskill, 2018) refers to quantum processors with 50–1,000+ qubits that are too noisy for full error correction but potentially useful for specific tasks. The Variational Quantum Eigensolver (VQE), proposed by Alberto Peruzzo and colleagues (2014), is a hybrid classical-quantum algorithm for finding ground-state energies of molecular systems: a parameterized quantum circuit prepares trial wavefunctions, which are measured to compute energy expectation values, and a classical optimizer iteratively adjusts circuit parameters to minimize energy. VQE has been demonstrated for small molecules (H₂, LiH, BeH₂) on real quantum hardware. The Quantum Approximate Optimization Algorithm (QAOA), proposed by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann (2014), targets combinatorial optimization problems using a similar variational approach.
• Primary Source: Peruzzo, Alberto, Jarrod McClean, Peter Shadbolt, et al. "A Variational Eigenvalue Solver on a Photonic Quantum Processor." Nature Communications 5 (2014): 4213

2.2 Quantum Machine Learning

• Evidence: Proposed quantum speedups for machine learning include the HHL algorithm (Aram Harrow, Avinatan Hassidim, and Seth Lloyd, 2009) for solving linear systems of equations exponentially faster than classical methods (under specific conditions), quantum kernel methods, and quantum neural networks. However, Scott Aaronson (2015) and others have cautioned that quantum machine learning speedups often require exponential-cost data loading steps ("the input problem") that negate the quantum advantage, and that practical quantum advantage for machine learning remains undemonstrated.

2.3 Quantum Simulation of Materials and Chemistry

• Evidence: Feynman's original vision (1982) — using quantum computers to simulate quantum systems — remains the most promising near-term application. Quantum simulation could revolutionize drug discovery (modeling protein-ligand interactions), materials science (high-temperature superconductors, catalyst design), and fundamental physics (lattice gauge theories). Matthias Troyer and colleagues at Microsoft Research have estimated that simulating the FeMo-cofactor of nitrogenase (relevant to nitrogen fixation and fertilizer chemistry) would require approximately 200 logical qubits with deep circuits — beyond current NISQ capabilities but within reach of early fault-tolerant machines.

3. SPECULATIVE CLAIMS (Tier 3 — Possible but Unverified)

3.1 Quantum Advantage for Practical Problems

• Evidence: Despite decades of theoretical development and recent hardware advances, no quantum computer has yet solved a practical problem faster than a classical computer. The 2019 Google experiment demonstrated quantum advantage only for an artificial benchmark. Whether NISQ devices can achieve practical advantage before fault-tolerant machines arrive — or whether the NISQ era will be a "valley of death" with impressive hardware but no useful algorithms — is the central open question. Gil Kalai (Hebrew University) has argued that quantum error correction may face fundamental physical barriers, though this remains a minority position.

3.2 Post-Quantum Cryptography Transition

• Evidence: The threat of Shor's algorithm to RSA and elliptic-curve cryptography has motivated the NIST Post-Quantum Cryptography Standardization process, which in 2022 selected four algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+) based on lattice problems and hash functions believed resistant to quantum attack. However, the timeline for when a cryptographically relevant quantum computer (CRQC) will exist ranges from estimates of 10–30+ years, and experts question whether it will ever be built at scale.

4. DUBIOUS CLAIMS (Tier 4 — No Credible Source / Contradicted by Evidence)

4.1 Quantum Computers "Try All Solutions Simultaneously"

• Evidence: DEBUNKED The popular explanation that quantum computers work by "trying all possible answers at once" due to superposition is fundamentally misleading. While a quantum computer with n qubits can exist in a superposition of 2ⁿ states, simply measuring the system collapses it to a single random outcome. Quantum algorithms achieve speedups through constructive and destructive interference — carefully designed sequences of operations that amplify the probability of correct answers and cancel incorrect ones. As Scott Aaronson has emphasized, "Quantum computers are not just classical computers that try exponentially many solutions in parallel."

Counter-Arguments & Criticisms

Gil Kalai (Hebrew University, 2019) has argued that quantum error correction faces fundamental obstacles related to correlated noise in many-qubit systems, and that fault-tolerant quantum computing may be impossible in practice. While this is a minority view contradicted by recent experimental progress (Google's below-threshold error correction, 2023), it highlights that the engineering challenges of building large-scale quantum computers remain formidable.

Mikhail Dyakonov (University of Montpellier, 2018) criticized the quantum computing field for overpromising, noting that the number of continuous parameters needed to describe the state of n qubits grows as 2ⁿ, and that controlling this exponentially large state space with the required precision may be fundamentally impractical. He likened quantum computing hype to nuclear fusion: "always 20 years away."

IMAGES

BIBLIOGRAPHY

1. Shor, Peter W. : 124 134 | 1994 | "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" | Proceedings of the 35th Annual Symposium on Foundations of Computer Science | ∅ | ∅ | ∅ | ∅ | doi:10.1109/SFCS.1994.365700 | ∅ | ∅ | ∅
2. Grover, Lov K. : 212 219 | 1996 | "A Fast Quantum Mechanical Algorithm for Database Search" | Proceedings of the 28th Annual ACM Symposium on Theory of Computing | ∅ | ∅ | ∅ | ∅ | doi:10.1145/237814.237866 | ∅ | ∅ | ∅
3. Shor, Peter W | 1995 | "Scheme for Reducing Decoherence in Quantum Computer Memory" | Physical Review A | ∅ | 52.4::R2493–R2496 | ∅ | ∅ | doi:10.1103/PhysRevA.52.R2493 | ∅ | ∅ | ∅
4. Arute, Frank, Kunal Arya, Ryan Babbush, et al | 2019 | "Quantum Supremacy Using a Programmable Superconducting Processor" | Nature | ∅ | 574.7779::505–510 | ∅ | ∅ | doi:10.1038/s41586-019-1666-5 | ∅ | ∅ | ∅
5. Peruzzo, Alberto, Jarrod McClean, Peter Shadbolt, et al | 2014 | "A Variational Eigenvalue Solver on a Photonic Quantum Processor" | Nature Communications | ∅ | 5::4213 | ∅ | ∅ | doi:10.1038/ncomms5213 | ∅ | ∅ | ∅
6. Preskill, John | 2018 | "Quantum Computing in the NISQ Era and Beyond" | Quantum | ∅ | 2::79 | ∅ | ∅ | doi:10.22331/q-2018-08-06-79 | ∅ | ∅ | ∅
7. Feynman, Richard P | 1982 | "Simulating Physics with Computers" | International Journal of Theoretical Physics | ∅ | 7::467–488 | 21.6 | ∅ | doi:10.1007/BF02650179 | ∅ | ∅ | ∅
8. Deutsch, David | 1985 | "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer" | Proceedings of the Royal Society of London A | ∅ | 400.1818::97–117 | ∅ | ∅ | doi:10.1098/rspa.1985.0070 | ∅ | ∅ | ∅
9. Nielsen, Michael A.; Isaac L | 2000 | ∅ | Quantum Computation and Quantum Information | ∅ | ∅ | Chuang | ∅ | isbn:9780521635035 | ∅ | ∅ | Cambridge: Cambridge University Press
10. Harrow, Aram W., Avinatan Hassidim; Seth Lloyd | 2009 | "Quantum Algorithm for Linear Systems of Equations" | Physical Review Letters | ∅ | 103.15::150502 | ∅ | ∅ | doi:10.1103/PhysRevLett.103.150502 | ∅ | ∅ | ∅
11. Kitaev, Alexei Yu. | 2003 | "Fault-Tolerant Quantum Computation by Anyons" | Annals of Physics | ∅ | 303.1::2–30 | ∅ | ∅ | doi:10.1016/S0003-4916(02)00018-0 | ∅ | ∅ | ∅
12. Aaronson, Scott | 2015 | "Read the Fine Print" | Nature Physics | ∅ | 11.4::291–293 | ∅ | ∅ | doi:10.1038/nphys3272 | ∅ | ∅ | ∅
13. Farhi, Edward, Jeffrey Goldstone; Sam Gutmann. arXiv preprint | 2014 | "A Quantum Approximate Optimization Algorithm" | ∅ | ∅ | ∅ | ∅ | ∅ | arxiv:1411.4028 | ∅ | ∅ | ∅
14. Bennett, Charles H., Ethan Bernstein, Gilles Brassard; Umesh Vazirani | 1997 | "Strengths and Weaknesses of Quantum Computing" | SIAM Journal on Computing | ∅ | 26.5::1510–1523 | ∅ | ∅ | doi:10.1137/S0097539796300933 | ∅ | ∅ | ∅

CROSS-REFERENCE INDEX

Generated from V4 expansion plan. Last Updated: April 1, 2026

Corrections

• 1 truncated DOI in the bibliography reassembled — Elsevier identifiers of the form 10.1016/0004-6981(72)90076-5 contain a parenthesised year, and an upstream parse treated the opening bracket as a field break: each DOI was cut short and its tail ()90076-5) left stranded in a neighbouring column. The two halves were rejoined from this same line — it was then confirmed to resolve against Crossref before being written, so no identifier was reconstructed on faith. Repaired: 10.1016/S0003-4916(02)00018-0. Corpus hygiene campaign, Phase 4, 2026-07-29.