Grover and Shor assume a beautifully behaved quantum computer that does not exist yet.
So people invented a different style for the machines we do have: keep the quantum bit tiny, and let an ordinary computer do the hard thinking.
The loop
An ordinary computer suggests some settings — think dials on a mixing desk. A very short quantum circuit runs with those settings. You measure, and get back a score.
The ordinary computer looks at the score, nudges the dials, and goes round again. And again. Until the score stops improving.
The quantum computer is never doing the clever part. It is only being asked "how good is this?" — and because each run is short, it finishes before the qubits forget.
VQE: chemistry
The most convincing near-term use of quantum computing, and this is the method.
Every molecule has a lowest-energy arrangement, and knowing it tells you how the molecule behaves — whether a drug binds, whether a battery material works. Working it out on an ordinary computer gets impossible fast, because molecules are quantum things and quantum things are exactly what ordinary computers struggle with.
VQE tries an arrangement, measures its energy, and lets the optimiser hunt downhill. There is a helpful guarantee: your answer is always an overestimate, so getting a lower number always means genuine progress.
QAOA: planning problems
Same loop, aimed at puzzles like "split this network into two halves with as few connections cut as possible".
It has a nice theoretical property: run it for long enough and it provably finds the best answer. The trouble is that "long enough" is far longer than today's machines can manage.
Two problems that will not go away
The dials stop responding. On bigger circuits the score becomes almost completely flat, so nudging a dial changes nothing measurable and the optimiser has no idea which way to go. This has a name — barren plateaus — and it has its own lesson in the QML track.
Measuring is slow. To get ten times more precise you need a hundred times more runs. Chemistry needs a lot of precision. The sums add up alarmingly.
Worth remembering
- A short quantum circuit scores an answer; an ordinary computer tunes the dials.
- VQE hunts for a molecule's lowest energy, and is the strongest near-term case.
- QAOA targets planning problems but has never beaten a good conventional solver.
- Flat scores and slow measuring are the two obstacles nobody has solved.