Quantum supremacy denotes a performance improvement on a computational task over available classical approaches; the treatment frames this benefit as quantum advantage. It matters only for specific problems where quantum resources improve speed, scalability, or feasibility. section 1.0 section 1.1
The practical mental model is a probability distribution over possible outcomes. Quantum computation changes outcome probabilities in parallel, then measurement samples an outcome; repeating the computation reveals the distribution. section 1.3 section 1.6
Quantum advantage is associated with several reusable computational patterns:
- Quantum parallelism changes pairs of amplitudes simultaneously, using a butterfly-style computational pattern. section 1.6
- Measurement selects outcomes according to their probabilities rather than exposing every possible state directly. section 1.3
- Entanglement enables conditional transformations by linking qubit states that cannot always be described independently. section 1.3
- Useful targets include sampling probability distributions, searching for optimal values, estimating outcome probabilities, and simulating physical processes. section 1.3 section 1.6
Figure 1.1 Comparison of the increase in computational complexity relative to the input size for computing (fast) Fourier transforms with classical and quantum computers
Compare how computational complexity grows with input size for classical fast Fourier transforms and quantum Fourier transforms. section 1.0
