Source Count: 15 | Weighted Score: 39 | Source Confidence: [4/5] | Primary Tier: 1 | Last Updated: April 16, 2026
Keywords: quantum computing, qubit, quantum gate, superposition, entanglement, quantum supremacy, Shor's algorithm, quantum error correction, topological qubit, superconducting qubit
Category Tags: information theory and computation
Cross-References: ZA_5_01 — Entropy & Information · V_4_21 — Cryptography · ZD_1_04 — Coding Theory

QUICK SUMMARY

Quantum computing harnesses quantum mechanical phenomena — superposition, entanglement, and interference — to perform computations fundamentally impossible for classical machines. First proposed by Richard Feynman in 1981 for simulating quantum systems and formalized by David Deutsch in 1985, the field achieved a major milestone when Google's 53-qubit Sycamore processor demonstrated "quantum supremacy" in 2019, performing a specific computation in 200 seconds that would take the most powerful classical supercomputer an estimated 10,000 years. Quantum algorithms including Peter Shor's factoring algorithm (1994) and Lov Grover's search algorithm (1996) offer exponential and quadratic speedups respectively. However, practical quantum advantage for useful real-world problems remains limited by decoherence, error rates, and the small number of logical qubits achievable with current technology.

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

1.1 Qubit Superposition and Entanglement

• Evidence: Unlike classical bits which exist as 0 or 1, quantum bits (qubits) can exist in superposition — a coherent combination of |0⟩ and |1⟩ states described by $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ where $|\alpha|^2 + |\beta|^2 = 1$. Multiple qubits can be entangled, creating correlations with no classical analogue, confirmed experimentally from Alain Aspect's 1982 Bell test experiments through modern loophole-free tests. An $n$-qubit register can represent $2^n$ states simultaneously, enabling quantum parallelism.
• Primary Source: Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000. ISBN: 978-0-521-63503-5

1.2 Shor's Algorithm and Cryptographic Implications

• Evidence: Peter Shor published a quantum algorithm in 1994 for integer factorization in polynomial time — $O((\log N)^3)$ — compared to the best known classical algorithms which are sub-exponential. This threatens RSA and other public-key cryptosystems whose security relies on the computational hardness of factoring large semiprimes. A sufficiently large quantum computer (~4,000 error-corrected logical qubits for 2048-bit RSA) would break current internet encryption. This has motivated the NIST Post-Quantum Cryptography standardization project, which selected four quantum-resistant algorithms in 2022. KEY FINDING
• Primary Source: Shor, Peter W. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134. IEEE, 1994. DOI: 10.1109/SFCS.1994.365700

1.3 Google's Quantum Supremacy Demonstration

• Evidence: In October 2019, a Google team led by John Martinis demonstrated quantum supremacy using their 53-qubit Sycamore processor, performing random circuit sampling in 200 seconds — a task estimated to take IBM's Summit supercomputer approximately 10,000 years. The result was published in Nature and immediately contested by IBM, who showed optimized classical algorithms could reduce the classical time to 2.5 days. Nevertheless, the experiment demonstrated quantum computational advantage for at least one specific task. KEY FINDING
• Primary Source: Arute, Frank, Kunal Arya, Ryan Babbush, et al. "Quantum Supremacy Using a Programmable Superconducting Processor." Nature 574 (2019): 505–510. DOI: 10.1038/s41586-019-1666-5

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

2.1 Quantum Error Correction Progress

• Evidence: Quantum decoherence — the loss of quantum information due to environmental interaction — remains the fundamental obstacle. The threshold theorem, proven by Dorit Aharonov and Michael Ben-Or (1997), guarantees that arbitrarily long quantum computations are possible if error rates fall below a threshold (~0.01–1% per gate, depending on architecture). Surface codes, developed by Alexei Kitaev, can encode one logical qubit in ~1,000–10,000 physical qubits with error rates below threshold. Google demonstrated in 2023 that increasing surface code distance reduces logical error rates — the first experimental proof of below-threshold scaling. However, the overhead remains enormous.
• Primary Source: Google Quantum AI. "Suppressing Quantum Errors by Scaling a Surface Code Logical Qubit." Nature 614 (2023): 676–681. DOI: 10.1038/s41586-022-05434-1

2.2 Competing Physical Platforms

• Evidence: Multiple qubit technologies compete: superconducting qubits (IBM, Google) offer the fastest gates (~20 ns) but shortest coherence times (~100 μs); trapped ions (IonQ, Honeywell/Quantinuum) offer highest fidelity (>99.9% per gate) but slower operations; photonic qubits (Xanadu, PsiQuantum) operate at room temperature but face lossy circuits; neutral atoms (QuEra) enable large-scale arrays; and topological qubits (Microsoft) promise inherent error protection but remain undemonstrated at scale. No clear winner has emerged — different architectures may suit different applications.

2.3 Near-Term Quantum Advantage: Chemistry and Optimization

• Evidence: Alán Aspuru-Guzik and colleagues proposed that quantum simulation of molecular systems could achieve practical advantage with hundreds of error-corrected qubits. Applications include designing catalysts for nitrogen fixation, modeling drug-protein binding, and optimizing battery materials. However, claims of broad quantum advantage for optimization problems (QAOA, quantum annealing) remain contested — Scott Aaronson and others note that classical heuristics often match or exceed quantum algorithms for practically-sized instances.

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

3.1 Million-Qubit Fault-Tolerant Computers

• Evidence: John Preskill coined the term NISQ (Noisy Intermediate-Scale Quantum) in 2018 to describe current devices with 50–1,000 qubits and high error rates. The transition to fault-tolerant quantum computing (FTQC) — estimated to require millions of physical qubits — remains a major engineering challenge. Industry roadmaps (IBM's 100,000-qubit target by 2033, Google's long-term plan) project FTQC within 10–20 years, but these timelines are inherently uncertain. Some physicists argue fundamental decoherence limits may prevent practical scaling.

3.2 Quantum Internet and Distributed Quantum Computing

• Evidence: Quantum networks transmitting entangled photons over optical fiber have been demonstrated at distances up to 511 km (China, 2020) and via satellite (Micius experiment, Jian-Wei Pan, 2017). A full quantum internet would enable blind quantum computing, provably secure communication, and distributed quantum computation. However, quantum repeaters — essential for long-distance networks — remain in early experimental stages.

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

4.1 Quantum Computers Can Solve "Everything" Faster

• Evidence: The popular misconception that quantum computers speed up all computations is DEBUNKED. Quantum speedup requires specific algorithmic structure. Scott Aaronson emphasizes that quantum computers offer exponential advantage only for structurally compatible problems (factoring, quantum simulation, certain search problems). Many NP-complete problems are believed to remain hard even for quantum computers — the complexity class BQP (bounded-error quantum polynomial time) is not believed to contain NP.

Counter-Arguments & Criticisms

• Practical relevance: Gil Kalai argues that quantum error correction may face fundamental physical limits — correlated noise in many-qubit systems may prevent achieving the error thresholds required by the threshold theorem, making fault-tolerant quantum computing physically impossible.
• Commercial hype: Despite billions in investment, no quantum computer has yet solved a practical problem faster than a classical alternative. Sabine Hossenfelder and other skeptics argue the field promises transformative results that may be decades away or never materialize for most commercial applications.
• Post-quantum cryptography readiness: The cryptographic threat from quantum computers has motivated premature alarm — current quantum computers are orders of magnitude too small to break RSA. However, "harvest now, decrypt later" adversarial strategies justify proactive migration to post-quantum algorithms.

IMAGES

No images assigned yet.

BIBLIOGRAPHY

1. Nielsen, Michael A.; Isaac L | 2000 | ∅ | Quantum Computation and Quantum Information | ∅ | ∅ | Chuang | ∅ | isbn:9780521635035 | ∅ | ∅ | Cambridge: Cambridge University Press
2. 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 | ∅ | ∅ | ∅
3. Arute, Frank, Kunal Arya, Ryan Babbush, et al | 2019 | "Quantum Supremacy Using a Programmable Superconducting Processor" | Nature | ∅ | 574::505–510 | ∅ | ∅ | doi:10.1038/s41586-019-1666-5 | ∅ | ∅ | ∅
4. Google Quantum AI | 2023 | "Suppressing Quantum Errors by Scaling a Surface Code Logical Qubit" | Nature | ∅ | 614::676–681 | ∅ | ∅ | doi:10.1038/s41586-022-05434-1 | ∅ | ∅ | ∅
5. Feynman, Richard P | 1982 | "Simulating Physics with Computers" | International Journal of Theoretical Physics | ∅ | 7::467–488 | 21.6 | ∅ | doi:10.1007/BF02650179 | ∅ | ∅ | ∅
6. 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 | ∅ | ∅ | ∅
7. Preskill, John | 2018 | "Quantum Computing in the NISQ Era and Beyond" | Quantum | ∅ | 2::79 | ∅ | ∅ | doi:10.22331/q-2018-08-06-79 | ∅ | ∅ | ∅
8. Grover, Lov K. : 212 219 | 1996 | "A Fast Quantum Mechanical Algorithm for Database Search" | Proceedings of the 28th ACM Symposium on Theory of Computing | ∅ | ∅ | ∅ | ∅ | doi:10.1145/237814.237866 | ∅ | ∅ | ∅
9. Kitaev, Alexei. . )00018-0 | 2003 | "Fault-Tolerant Quantum Computation by Anyons" | Annals of Physics | ∅ | 303.1::2–30 | ∅ | ∅ | doi:10.1016/S0003-4916(02 | ∅ | ∅ | ∅
10. Aaronson, Scott | 2013 | ∅ | Quantum Computing Since Democritus | ∅ | ∅ | Cambridge: Cambridge University Press | ∅ | isbn:9780521199568 | ∅ | ∅ | ∅
11. Pan, Jian-Wei, et al | 2017 | "Satellite-Based Entanglement Distribution over 1200 Kilometers" | Science | ∅ | 356.6343::1140–1144 | ∅ | ∅ | doi:10.1126/science.aan3211 | ∅ | ∅ | ∅
12. Aspuru-Guzik, Alán, Anthony D | 2005 | "Simulated Quantum Computation of Molecular Energies" | Science | ∅ | 309.5741::1704–1707 | Dutoi, Peter J | ∅ | doi:10.1126/science.1113479 | ∅ | ∅ | Love, and Martin Head-Gordon
13. Kalai, Gil | 2020 | "The Argument Against Quantum Computers" | Quantum, Probability, and Logic | ∅ | ∅ | In , edited by Meir Hemmo and Orly Shenker, 399 422 | ∅ | isbn:9783030343156 | ∅ | ∅ | Cham: Springer
14. Aharonov, Dorit; Michael Ben-Or | 2008 | "Fault-Tolerant Quantum Computation with Constant Error Rate" | SIAM Journal on Computing | ∅ | 38.4::1207–1282 | ∅ | ∅ | doi:10.1137/S0097539799359385 | ∅ | ∅ | ∅
15. National Institute of Standards and Technology (corp.) | 2022 | "Post-Quantum Cryptography: Selected Algorithms " | ∅ | ∅ | ∅ | NIST IR 8413, 2022 | ∅ | ∅ | ∅ | ∅ | ∅

CROSS-REFERENCE INDEX

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