A quantum algorithm is a recipe of gates that uses interference to find an answer with fewer steps than any known classical method, for certain problems. The gain is rarely universal: some algorithms are exponentially faster, others only quadratically, and many problems gain nothing. Knowing which is the skill.
Key concepts
- Oracle problems: Deutsch-Jozsa, Bernstein-Vazirani and Simon show speed-ups in a clean model where a black box is queried.
- Quantum Fourier transform: a fast change of basis that exposes periodicity; it is the heart of Shor's algorithm.
- Shor's algorithm: finds the period behind integer factoring and discrete logarithms, which threatens some public-key cryptography.
- Grover's search: a quadratic speed-up for unstructured search, by repeatedly amplifying the marked item.
- Variational and simulation methods: quantum simulation of physical systems, and hybrid loops that tune circuit parameters classically.
Vocabulary
- Query complexity: the number of calls to an oracle an algorithm needs.
- Amplitude amplification: the generalisation of Grover's idea to raise the probability of good outcomes.
- BQP: the problems a quantum computer solves in polynomial time with small error.
- Post-quantum cryptography: classical schemes designed to resist known quantum attacks.
What to study, in order
- Quantum circuits and measurement, and the linear algebra they use.
- Implement Deutsch-Jozsa and Bernstein-Vazirani in a simulator and see why interference gives the answer.
- Work through Grover's search on four and eight items, and count the iterations.
- Learn the quantum Fourier transform, then phase estimation.
- Follow Shor's algorithm: the classical reduction to period finding, then the quantum step.
Related tags
#quantum-computing #complexity #cryptography #algorithms #linear-algebra