Does a quantum computer try all solutions at once?
Not in the popular sense: a function can act on a superposition of all inputs, but measurement yields one random result; advantage requires engineered interference.
The common phrase “a quantum computer tries every possibility at once” is misleading. It is true that applying an oracle $U_f$ to the superposition $\frac{1}{\sqrt{2^n}}\sum_x|x\rangle$ produces $\frac{1}{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle$ in a single step, which is called Quantum Parallelism. But measuring this state gives a single random pair $(x,f(x))$, which is what could be obtained classically by trying a random input.
The real advantage comes from interference: successful algorithms (Deutsch–Jozsa, Simon, Shor, Grover) arrange the gates so that amplitudes interfere constructively at useful answers and destructively elsewhere, and then extract a global property of the function (a period, an order, a marked item) rather than its full table of values. That is why there is no fast quantum algorithm for every problem.
Related topics
References
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
- John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com
