Quantum computing — when and how it all started, and how it is slowly conquering the Turing world.
Quantum theory turned out to be one of the best descriptions of how the universe actually works, and that success pushed researchers to revisit every discipline from this stranger, richer point of view. It wasn't until the 1980s, though, that quantum information became a field of its own.
A very short history
In 1979 Paul Benioff argued that a computing machine with quantum behaviour could be built, soon followed by Yuri Manin's book Computable and Non-Computable. Then, in 1981, Richard Feynman gave his now-famous talk "Simulating Physics with Computers", where he made the case that a fundamentally quantum-mechanical nature should not be simulated by a classical computer, and sketched the features a useful quantum computer would need. It is hard to read that talk and not be struck by how far ahead Feynman was seeing.
With that push from Feynman, Manin, and Benioff, people went looking for algorithms that could run on such machines. In 1985 David Deutsch showed the kind of advantage these machines might hold over classical ones, later generalising it with Richard Jozsa.
That early advantage softened once you allowed small errors in the classical computation — the problem could then be solved in roughly linear time. So in 1993 Bernstein and Vazirani produced a problem with a clean separation between classical and quantum computation even when small errors were allowed, and along the way described a quantum version of the Fourier transform. Shortly after, Simon's problem gave a quantum computer a linear-time solution to something that costs a classical computer exponential time, and Seth Lloyd laid out how such a machine might physically be built.
Then came Peter Shor. He combined the existing ideas into a factoring algorithm and published it in 1994 — and because factoring underpins RSA cryptography, that single result lit a fire under the whole field. Suddenly everyone was hunting for more quantum algorithms.
Fast-forward about twenty years and a new subfield appears with a name fancier than almost anything before it: Quantum Machine Learning. Plenty of groundwork had been laid since the mid-90s, but the term itself shows up in Lloyd, Mohseni, and Rebentrost's "Quantum Principal Component Analysis". Interest has climbed steadily since 2013, and QML is now its own corner of quantum computing.
Four approaches to quantum machine learning
Aimeur, Brassard, and Gambs proposed a clean way to organise the field. Split on two questions: is the data generated by a classical (C) or quantum (Q) system, and is the learning device classical (C) or quantum (Q)? That gives four boxes.
CC — classical data, classical device
The conventional setting, but with methods borrowed from quantum information — for example tensor-network approaches, and the broader family of "quantum-inspired" models with varying degrees of grounding in real quantum theory.
QC — quantum data, classical device
Here machine learning helps quantum computing. Think of characterising the internal state of a quantum device with as few measurements as possible and analysing that data with ordinary ML, or discriminating between quantum states a source emits and between transformations an apparatus performs.
CQ — classical data, quantum device
This is the most heavily studied box, and the focus of this series. The aim is a speed-up on ML tasks by running quantum versions of learning algorithms on classical data — which first has to be encoded into the quantum computer, an active research problem in its own right. The strategies range from translating familiar ML models into quantum algorithms all the way to genuinely new models born from how quantum computers work. I'll mostly stay with supervised learning here, with the occasional detour into unsupervised ideas (quantum GANs, autoencoders, Boltzmann machines, and more).
QQ — quantum data, quantum device
Quantum data processed on a quantum device. Two flavours: measurements of a physical quantum experiment fed to a separate quantum learner, or a quantum device that simulates a system and hands its state straight to a quantum algorithm running on the same hardware — immediate access to the state, exponential speed-up by design. It's fascinating and largely open territory, mostly out of scope for this series.
That's the map. By way of a sign-off, Dunjko, Taylor, and Briegel make a lovely point about the fully-quantum corner: once the interaction itself can be quantum, even the question of what it means "to learn" gets slippery — agent and environment can end up entangled. (See their 2016 "Quantum-Enhanced Machine Learning".)