Quantum algorithms that actually touch learning

Two speedup families, and only one of them is dramatic

The Fourier-sampling family — Shor's factoring and discrete-log algorithms, and the hidden subgroup problem behind them — gives superpolynomial separations on tightly structured problems. Nothing in supervised learning has that structure. The amplitude-amplification family, headed by Grover search, is generic but quadratic, and a quadratic gain has to survive the constant factors of error-corrected gate synthesis before it means anything. Every honest resource estimate for Grover-type speedups shows the crossover pushed far out by those constants, which is why the interesting proposals cluster around a third family: simulating quantum systems, where the machine does what it is natively built to do.

HHL and the fine print

Harrow, Hassidim and Lloyd's quantum linear-systems algorithm is the load-bearing citation in most quantum machine learning pitches, and its caveats have been public since Aaronson's Read the fine print commentary in Nature Physics. The algorithm needs the matrix sparse and well conditioned, needs the right-hand side loaded into amplitudes efficiently, and returns a quantum state whose entries you cannot read out wholesale. Four conditions, any one of which can swallow the exponential. Regression on a dense design matrix satisfies none of them comfortably, and the runtime dependence on the condition number is not a footnote — it is the whole margin.

Dequantisation keeps eating the soft claims

The sharpest correction came from Ewin Tang's quantum-inspired classical algorithm for recommendation systems, which removed an exponential separation by giving the classical algorithm the same sample-and-query access the quantum one had assumed. A stream of dequantisation results followed for low-rank linear algebra, principal component analysis and related tasks. The methodological lesson for anyone reading a new paper: check whether the classical baseline was granted the same access model. If it was not, the comparison is between a quantum algorithm with a generous oracle and a classical algorithm forced to read its input from disk.

Variational circuits: expressive, trainable, rarely both

Variational quantum eigensolvers, following Peruzzo and colleagues, and the quantum approximate optimisation algorithm of Farhi, Goldstone and Gutmann put a parameterised circuit in a classical optimisation loop. It is a natural fit for shallow hardware, and it inherits a hard obstruction: McClean and colleagues showed that gradients of random deep parameterised circuits concentrate exponentially in the number of qubits, so the cost landscape flattens. Structured ansätze, local cost functions and careful initialisation mitigate it; none of them makes it go away. Add the sampling cost — expectation values need many shots per parameter update — and the classical optimiser is often the cheaper half of the loop.

Kernels with a proof behind them

Quantum kernel methods, set out by Havlíček and colleagues, replace the feature map rather than the model, estimating inner products between states prepared from classical inputs. This is the corner of quantum machine learning with a genuine rigorous result: Liu, Arunachalam and Temme constructed a classification problem, built on the discrete logarithm, with a provable quantum advantage for a kernel method. Read it for what it is — an existence proof that quantum feature maps can help on problems with cryptographic structure, not evidence that they help on images or text.

Learning from experiments, not from datasets

The most robust separations arrive when the data is itself quantum. Huang and colleagues, publishing in Science, demonstrated exponential advantages in sample complexity for learning properties of physical systems when a quantum memory can hold the experimental output coherently. Pair that with classical shadows for efficient property estimation and you have a research direction where the quantum register is the sensor, not the accelerator. It matters for materials characterisation and for calibrating the machines themselves; it does not shorten a language model training run.

What survives for AGI-scale training

Frontier model training is backpropagation over dense tensors at enormous scale, bandwidth-bound as much as arithmetic-bound. There is no quantum primitive that returns a full classical weight update faster than a classical one, and the register cannot hold parameter counts of that order in any read-writable sense. What plausibly survives: combinatorial subproblems in architecture and scheduling, sampling from structured distributions, simulation of quantum systems whose outputs feed scientific models, and — furthest out — inference on small components where a quadratic gain is worth the interconnect.