Quantum Machine Learning: Four Flavors

Why did dequantization sting? Because the Kerenidis–Prakash recommendation algorithm was a flagship: an exponential speedup for a genuinely practical problem, built on the same linear-algebra machinery as HHL. Tang's insight was that the speedup's fine print — the assumption that data arrives in a special quantum-friendly format — could be matched classically by an analogous classical data structure (sampling access). Once she showed the classical algorithm inherits the same advantage under comparable assumptions, the "exponential speedup" evaporated into a polynomial one. The reality check: a quantum ML speedup claim must specify its input model, or it is comparing a quantum athlete to a classical athlete with tied shoes.

The loading bottleneck deserves its full weight, because it is the central caveat of the entire CQ program. HHL solves \(Ax = b\) in time \(O(\log n)\) — but only if the vector \(b\) is already loaded as a quantum state \(|b\rangle\), and only if you are satisfied with a quantum state \(|x\rangle\) as the answer rather than all \(n\) classical numbers. Preparing \(|b\rangle\) from classical data costs \(O(n)\) in general; reading out all of \(x\) costs \(O(n)\) too. So the exponential speedup survives only for problems where the input is cheap to prepare and the output you need is some global property — an expectation value, not the full vector.

Quantum RAM (QRAM) is the theoretical escape hatch: a device that loads classical data into superposition in \(O(\log n)\) time. But no QRAM exists, and building one requires maintaining coherence across an enormous routing network — arguably as hard as building the quantum computer itself, with error-correction overhead on top. Most researchers treat QRAM as a placeholder for "someday, maybe," not a plan. Until the input problem is solved, CQ algorithms are speedups waiting for a data pipeline.

That is why QQ is conceptually the cleanest box: when the data-generating system is itself quantum — a collider, a quantum sensor network, a quantum simulation — there is nothing to load. The state arrives as a state. The ML principles (function approximation plus optimization, from the last lesson) carry over unchanged; only the substrate changes. The field's bet is that as quantum devices proliferate, quantum-native data will too — and QQ will inherit the earth. Honest summary for the whole 2×2: the physics is real, the speedups are conditional, and the conditions are the interesting part.