Quantum machine learning: hype check

Put two hyped words next to each other and you get a headline that writes itself. “Quantum machine learning” is that headline. Quantum computers will train models exponentially faster. Quantum neural networks will find patterns classical ones can’t. Stuff like that.

I’ve spent the last couple of months learning quantum computing on my own and writing it up as I go: what a qubit is, Grover, Shor, error correction, and how I’d learn all of it again. I also spend a lot of time on the machine learning side. So at some point I had to actually sit down and ask the obvious question. When people say quantum computers will speed up machine learning, what exactly is the claim, and how much of it holds up?

Three different things called “QML”

The phrase covers at least three pretty different ideas, and a lot of the confusion comes from mixing them up.

1. Fault-tolerant linear algebra speedups. Machine learning is mostly linear algebra: solving systems of equations, finding the main directions in a big matrix, stuff like that. In 2008, Aram Harrow, Avinatan Hassidim, and Seth Lloyd posted an algorithm, now called HHL, that “solves” a linear system Ax = b in time that grows like poly(log N, kappa) instead of roughly N.¹ That’s an exponential speedup on paper. A whole wave of quantum ML algorithms for clustering, support vector machines, recommendation systems, and more was built on top of HHL or ideas like it.

2. Variational models on near-term hardware. This is the “quantum neural network” idea. You build a circuit with tunable rotation angles, feed in data, measure something, and train the angles with gradient descent, the same way you’d train weights in a regular network. A close cousin is the quantum kernel: use a circuit to map each data point to a quantum state, then use the overlap between states as a similarity measure inside a classical support vector machine.

3. Learning from quantum data. Here the input isn’t a spreadsheet. It’s a quantum state coming out of a physical experiment, like a molecule or a quantum sensor, and the quantum computer processes it directly instead of measuring it first.

These have very different track records. The first has a theory problem. The second has a training problem. The third has some of the clearest evidence for a quantum advantage. Let me go through them.

Reading the fine print on HHL

In 2015, Scott Aaronson wrote a short piece in Nature Physics called “Read the fine print.”² It’s about three pages, it’s very readable, and it helped me understand what those headlines leave out.

His point is that HHL does solve Ax = b in logarithmic time, but only with four caveats, and each one can quietly kill the speedup.

Loading the input. The vector b has to become a quantum state whose amplitudes are b’s entries. If you have a million numbers sitting in ordinary memory, you need some way to load them into a quantum computer fast. The usual answer is a “quantum RAM,” a memory that can be read in superposition. Nobody has built a large one. And Aaronson points out that if preparing the state takes n^c steps for any constant c, “the exponential speedup of HHL vanishes in the very first step.”²

Applying the matrix. The algorithm has to apply an operation built from A many times. That’s cheap if A is sparse (only a few nonzero entries per row) or has some other special structure. For a general dense matrix it isn’t.

Conditioning. The running time grows with the condition number kappa, which is the ratio between its largest and smallest singular values (or absolute eigenvalues for a Hermitian matrix). Roughly, it measures how close the matrix is to being impossible to invert. If kappa grows polynomially with the problem size, the speedup is gone again.

The output. This is the one people skip most often. What HHL hands back at the end is a quantum state |x>, with x’s entries stored in the amplitudes. You never get the list of numbers itself. And as I wrote in the qubit post, you can’t just read amplitudes. You measure and get one outcome. You can estimate some summary statistics of x, like an inner product with another vector. Recovering the full vector takes at least linear output work. Estimating an individual entry can also be costly, depending on its size and the precision required.

Put it together and Aaronson’s honest summary is that HHL prepares a quantum state related to the solution, in time roughly log(n) * kappa * s / epsilon (with s the sparsity and epsilon the error), assuming you can load b and apply A fast.² That’s still a real and interesting algorithm. It’s just a different thing from “solves linear equations exponentially faster.”

He also makes a second point that I think is even more important. Once you add all those restrictions, the task you’re comparing against is no longer “solve any linear system.” It’s “estimate certain statistics of the solution, for special systems, with the input already in a convenient form.” And for that narrower task, it’s much less obvious that a clever classical algorithm can’t do the same thing. He gives an example from a 2013 quantum classification algorithm: once you spell out the conditions under which it works, a classical random sampling algorithm does the same job and is at most quadratically slower.²

That hint turned out to be a preview.

Dequantization: when the classical side catches up

In 2016, Kerenidis and Prakash published a quantum algorithm for recommendation systems, the “users who liked this also liked” problem behind Netflix and Amazon.³ It ran in time polylogarithmic in the size of the preference matrix, and unlike a lot of HHL-style proposals, it seemed to dodge most of the fine print. For a while it was considered one of the best candidates for an exponential quantum speedup on a practical machine learning problem.

Then in 2018, Ewin Tang, an 18-year-old undergraduate at UT Austin, found a classical algorithm that does essentially the same thing.⁴ Her algorithm runs in time O(poly(k) log(mn)) for a rank-k approximation of an m x n matrix. That’s only polynomially slower than the quantum one, which means the exponential gap was gone. The best detail in this story is that, according to Quanta, the project came out of Aaronson’s course, and he had challenged her to prove that no fast classical algorithm existed.⁵ She went the other way.

The trick is basically to give the classical algorithm the same deal the quantum one gets. The quantum algorithm assumes the data sits in a structure that lets you prepare states quickly. Tang’s classical algorithm assumes the data sits in a structure that lets you sample entries with probability proportional to their size squared. With that kind of sampling access, you can do a surprising amount of low-rank linear algebra without ever touching the whole matrix.

This idea got a name, dequantization, and it spread. In 2020, Chia, Gilyén, Li, Lin, Tang, and Wang built a general framework that dequantizes a whole family of quantum ML algorithms working on low-rank matrices, and argued that in the quantum RAM input model, this kind of quantum algorithm gives no exponential speedup for low-rank problems.⁶

I want to be careful here. Dequantization doesn’t kill everything. The classical algorithms are often slower by a large polynomial, and they only apply when the matrix is low-rank or close to it. For high-rank, sparse, well-conditioned problems, HHL-style speedups can survive. But those aren’t the problems most ML headlines were about. The lesson underneath is this: a lot of the “exponential speedup” was coming from the input assumption, not from the quantum part.

Barren plateaus: the training problem

So the fault-tolerant algorithms have a theory problem. What about the near-term variational models, the quantum neural networks?

Their main problem was named in 2018 by McClean and colleagues at Google: barren plateaus.⁷ If you build a variational circuit with randomly initialized parameters, and the circuit is expressive enough to look roughly random, then the gradient of your loss is almost always tiny. More precisely, the probability that a gradient is nonzero to any fixed precision shrinks exponentially with the number of qubits.

If you’ve trained a normal neural network, think of vanishing gradients, but worse. You don’t just get slow learning. You need exponentially many measurements to even tell which direction is downhill, because each gradient estimate comes from repeated noisy measurements of a quantum state. So the cost of training blows up exactly as the model gets big enough to be interesting.

People have spent years looking for circuit designs that avoid barren plateaus: shallow circuits, local cost functions, structure that matches the problem. In a 2025 perspective in Nature Communications, Cerezo and a long list of coauthors asked whether the same structure that lets you avoid barren plateaus also lets you simulate the model classically.⁸ Their argument is that for many of the commonly used models with provably trainable landscapes, the answer looks like yes, at least after collecting some data from the quantum device. They’re careful to list caveats, but the tension is real. If your model is trainable because it lives in a small, well-behaved corner of the huge quantum state space, a classical computer may be able to live in that same corner.

So the variational approach is squeezed from both sides. Too random, and you can’t train it. Structured enough to train, and you might not need a quantum computer.

What has actually run on hardware

This is the part I most wanted to get right, because “demonstrated” gets used loosely.

The most cited early experiment is Havlíček et al., published in Nature in 2019 by a team at IBM.⁹ It introduced the quantum kernel and variational classifier approaches I described above, and it ran them on a superconducting processor. The device had five qubits, and the experiment used two of them. The training and test data were artificially generated so they could be separated by the specific feature map the authors chose. I don’t say this to dunk on the paper. It was a proof of concept, and it says so. But it’s a long way from “quantum computers classify data better,” which is how it sometimes gets described.

The question I care about is whether these models beat good classical baselines on real tasks. In 2024, Bowles, Ahmed, and Schuld at Xanadu did a large benchmark study to check exactly that.¹⁰ They took 12 popular quantum ML models and tested them on 6 binary classification tasks, 160 datasets in total. The finding was that out-of-the-box classical models generally outperformed the quantum classifiers. Even more telling, removing entanglement from the quantum models often gave the same or better results. That suggests the “quantum” part wasn’t what was doing the work on these tasks.

That study ran on simulators, because the models were small enough to simulate, and that’s the point. These small simulations do not establish an advantage over the best classical methods.

The experiment I find most convincing goes in a different direction. In 2022, Huang and colleagues, a group from Google, Caltech, and elsewhere, published “Quantum advantage in learning from experiments” in Science.¹¹ Their input was quantum states from a physical system, fed into a quantum memory and processed by a quantum computer. On up to 40 superconducting qubits, they showed that for certain tasks, the quantum approach could learn from exponentially fewer experiments than any approach that measures each state first and processes the results classically. That’s a provable separation, and they demonstrated it on real hardware.

It’s a real result. It’s also about learning properties of quantum systems, which is a narrower thing than speeding up the machine learning most people mean when they say “machine learning.”

What’s actually proven

So what’s on solid ground? My summary of the literature, as of right now:

• Quantum data, quantum advantage. When the input is itself quantum, there are provable and demonstrated advantages.¹¹ This is the strongest case.
• Classical data, artificial problems. In 2021, Liu, Arunachalam, and Temme proved a rigorous speedup for a quantum kernel method on classical data.¹² But the dataset is constructed from the discrete logarithm problem, the same kind of number theory Shor’s algorithm attacks, and the classifier needs a fault-tolerant quantum computer. It’s an existence proof that quantum kernels can help in principle. It isn’t a problem anyone was trying to solve with ML.
• Quadratic speedups via Grover-style search. Lots of ML subroutines can get a square-root speedup, the same kind of speedup Grover’s algorithm gives. But a 2021 analysis by Babbush and colleagues argued that quadratic speedups won’t give a real runtime advantage on early fault-tolerant machines, because the error correction overhead is so large that the quantum computer’s slow clock eats the gain.¹³ Given what I learned writing the error correction post, that makes sense to me.
• Exponential speedups on practical classical-data ML. As far as I can tell, nothing here has survived both the fine print and dequantization. I could be missing something, and I’d love to be corrected.

What would make this exciting

The possibility of a quantum computer helping us learn something we couldn’t otherwise learn is exciting. I just want to understand where that advantage would come from. For ordinary classical data, loading the input, training the model, and comparing it with a strong classical method are all part of the question.

Schuld and Killoran argue for looking beyond beating classical models as the field’s only goal, and for understanding what quantum models are actually useful for.¹⁴ That makes me more curious about problems involving quantum data. If the thing we want to study is already quantum, perhaps that gives us a better reason to use a quantum model in the first place.

I’d want to see a useful task where the full comparison holds up, including the costs that are easy to leave out of a headline. In the meantime, a small simulated kernel experiment could help make the question concrete. Comparing it with a tuned classical SVM, then removing the entangling gates, would let me see what those gates contribute in that example. It wouldn’t establish a practical advantage, but it could make the next result I read easier to understand.

Sources