Does a Quantum Computer Try Every Answer at Once?
In short: Quantum computers can compute in superposition but extract only limited information, so their best search beats classical search by a real but proven-bounded square-root margin, not by trying every answer at once.
A 1:23 short film in the series “From Fingers to Qubits”, narrated by intellect_voice_01.
Sources used in this film: Purdue University (CS 593/MA 592 Intro to Quantum Computing, Spring 2024 lecture notes, Lecture 6.1), “6.1.pdf”; University of Cambridge, Department of Applied Mathematics and Theoretical Physics (DAMTP): lecture notes by Richard Jozsa, Michaelmas term 2021, “D27L.pdf”; TED Conferences, LLC (TEDxDresden talk page), “What quantum computing isn't | Scott Aaronson | TEDxDresden”; Shtetl-Optimized, the blog of Scott Aaronson, “The Orion Quantum Computer Anti-Hype FAQ”; Computer History Museum, “Computer History Museum”; Stanford Encyclopedia of Philosophy, “The Church-Turing Thesis”; Los Alamos National Laboratory (Los Alamos Science, Number 27, 2002), “Richard Feynman on Quantum Physics and Computer Simulation”; International Journal of Theoretical Physics (Plenum Publishing Corporation), Feynman's 1982 paper, hosted in a Princeton University Computer Science course archive, “Simulating physics with computers”; The Royal Society (Proceedings of the Royal Society of London A: Mathematical and Physical Sciences), page captured by the Internet Archive Wayback Machine, “Quantum theory, the Church–Turing principle and the universal quantum computer | Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences”; David Deutsch, Proceedings of the Royal Society of London A (1985); LaTeX version edited by Wim van Dam at the Centre for Quantum Computation, Oxford (1999), hosted by Southern Methodist University, “deutsch85.dvi”; arXiv (Cornell University); preprint by Christof Zalka, published in Physical Review A, “Grover's quantum searching algorithm is optimal”; National Institute of Standards and Technology (NIST), U.S. Department of Commerce, “Quantum Computing Explained”.
Sources used in this film
- Purdue University (CS 593/MA 592 Intro to Quantum Computing, Spring 2024 lecture notes, Lecture 6.1) — 6.1.pdf · View →
- University of Cambridge, Department of Applied Mathematics and Theoretical Physics (DAMTP): lecture notes by Richard Jozsa, Michaelmas term 2021 — D27L.pdf · View →
- TED Conferences, LLC (TEDxDresden talk page) — What quantum computing isn't | Scott Aaronson | TEDxDresden · View →
- Shtetl-Optimized, the blog of Scott Aaronson — The Orion Quantum Computer Anti-Hype FAQ · View →
- Computer History Museum — Computer History Museum · View →
- Stanford Encyclopedia of Philosophy — The Church-Turing Thesis · View →
- Los Alamos National Laboratory (Los Alamos Science, Number 27, 2002) — Richard Feynman on Quantum Physics and Computer Simulation · View →
- International Journal of Theoretical Physics (Plenum Publishing Corporation), Feynman's 1982 paper, hosted in a Princeton University Computer Science course archive — Simulating physics with computers · View →
- The Royal Society (Proceedings of the Royal Society of London A: Mathematical and Physical Sciences), page captured by the Internet Archive Wayback Machine — Quantum theory, the Church–Turing principle and the universal quantum computer | Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · View →
- David Deutsch, Proceedings of the Royal Society of London A (1985); LaTeX version edited by Wim van Dam at the Centre for Quantum Computation, Oxford (1999), hosted by Southern Methodist University — deutsch85.dvi · View →
- arXiv (Cornell University); preprint by Christof Zalka, published in Physical Review A — Grover's quantum searching algorithm is optimal · View →
- National Institute of Standards and Technology (NIST), U.S. Department of Commerce — Quantum Computing Explained · View →
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Purdue University (CS 593/MA 592 Intro to Quantum Computing, Spring 2024 lecture notes, Lecture 6.1): 6.1.pdf
- Also: University of Cambridge, Department of Applied Mathematics and Theoretical Physics (DAMTP): lecture notes by Richard Joz: D27L.pdf
- Also: TED Conferences, LLC (TEDxDresden talk page): What quantum computing isn't | Scott Aaronson | TEDxDresden
- Also: Shtetl-Optimized, the blog of Scott Aaronson: The Orion Quantum Computer Anti-Hype FAQ
- Also: Computer History Museum: How Do Digital Computers “Think”? - CHM Revolution
- Also: Stanford Encyclopedia of Philosophy: The Church-Turing Thesis
- Also: Los Alamos National Laboratory (Los Alamos Science, Number 27, 2002): Richard Feynman on Quantum Physics and Computer Simulation
- Also: International Journal of Theoretical Physics (Plenum Publishing Corporation), Feynman's 1982 paper, hosted in a Princeto: Simulating physics with computers
- Also: The Royal Society (Proceedings of the Royal Society of London A: Mathematical and Physical Sciences), page captured by t: Quantum theory, the Church–Turing principle and the universal quantum computer | Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences
- Also: David Deutsch, Proceedings of the Royal Society of London A (1985); LaTeX version edited by Wim van Dam at the Centre fo: deutsch85.dvi
- Also: arXiv (Cornell University); preprint by Christof Zalka, published in Physical Review A: Grover's quantum searching algorithm is optimal
- Also: National Institute of Standards and Technology (NIST), U.S. Department of Commerce: Quantum Computing Explained
To cite this card, link to https://intellectplus.co.uk/app/does-a-quantum-computer-try-every-answer-at-once.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Science · Latest · A–Z · All topics
