Skip to content

References: Quantum Algorithms and Their Real-World Limits

  1. Shor's algorithm - Wikipedia - Details the quantum factoring algorithm, its polynomial runtime, and resource requirements, central to this chapter's analysis of the gap between theoretical promise and practical feasibility.

  2. Grover's algorithm - Wikipedia - Explains the quadratic speedup for unstructured search and its optimality proof, relevant to this chapter's discussion of why quadratic speedups rarely translate to practical commercial advantage.

  3. Quantum supremacy - Wikipedia - Covers the concept of quantum computational supremacy, Google's Sycamore experiment, and subsequent classical challenges, directly supporting this chapter's analysis of contrived benchmarks.

  4. Quantum Computing Since Democritus (2013) - Scott Aaronson - Cambridge University Press - Provides rigorous yet accessible analysis of quantum computational complexity, the limits of quantum speedups, and why quantum computers likely cannot solve NP-complete problems efficiently.

  5. The Theory of Quantum Information (2018) - John Watrous - Cambridge University Press - Graduate-level treatment of quantum algorithms and computational complexity, including formal proofs of the limitations of quantum computing discussed in this chapter.

  6. Quantum Computing in the NISQ Era and Beyond - John Preskill, arXiv (2018) - Coined the term NISQ (Noisy Intermediate-Scale Quantum), framing the gap between current quantum hardware capabilities and fault-tolerant requirements that this chapter examines.

  7. Strong Quantum Computational Advantage Using a Superconducting Quantum Processor - Wu et al., Science (2021) - Reports the Jiuzhang and Zuchongzhi supremacy experiments from China, key examples in this chapter's discussion of how supremacy claims are evaluated and challenged.

  8. Quantum Computational Advantage via 60-Qubit 24-Cycle Random Circuit Sampling - Google Quantum AI, arXiv (2021) - Follow-up to the original Sycamore experiment, relevant to this chapter's analysis of how classical simulation improvements continually erode quantum supremacy claims.

  9. How Much Structure Is Needed for Huge Quantum Speedups? - Scott Aaronson, arXiv (2022) - Examines which problem structures enable exponential quantum speedups and why most practical problems lack this structure, directly supporting this chapter's narrow applicability argument.

  10. Evidence for the Utility of Quantum Computing Before Fault Tolerance - IBM, Nature (2023) - IBM's claim of quantum utility on a 127-qubit processor, a key case study in this chapter's discussion of how "utility" claims differ from genuine practical advantage.