Quantum machine learning

Is quantum AI real, or mostly hype? Here's the one part of quantum machine learning that holds up.

What this Short covers:

1. Most AI comes down to matrix math: multiplying and solving huge grids of numbers.
2. HHL (Harrow, Hassidim, Lloyd, published 2009) is a quantum algorithm for linear systems that promised an exponential speedup for certain (sparse, well-conditioned) problems.
3. The fine print: loading classical data into qubits can cancel the speedup, and the answer comes out as a quantum state, so reading out the full result costs many repeats.
4. In 2018, Ewin Tang, then 18, published a classical algorithm that nearly matched the quantum recommendation algorithm (Kerenidis–Prakash), removing its exponential advantage.
5. Where quantum machine learning could really win: data that is already quantum, such as molecules and materials.

Fine print for the physics crowd: "grids of numbers" = matrices. HHL (Harrow, Hassidim, Lloyd) solves linear systems Ax = b; the exponential speedup needs a sparse, well-conditioned matrix, fast state preparation, and gives you a quantum state, not the full vector (arXiv Nov 2008, Phys. Rev. Lett. 2009). Ewin Tang's 2018 classical algorithm is only polynomially slower than the Kerenidis–Prakash quantum recommendation algorithm, so the exponential gap is gone, not the quantum algorithm itself. "Data that's already quantum" = learning from quantum systems, where an exponential advantage was proven (Huang et al., Science 2022); a practical win on real molecules is still ahead, hence "could".

1. HHL algorithmarxiv.org
2. Aaronson, "Read the fine print", Nature Physics (2015)nature.com
3. Tang, classical recommendation algorithm (2018)arxiv.org
4. Quanta Magazine on Tang's resultquantamagazine.org
5. Huang et al., quantum advantage in learning from experiments, Science (2022)arxiv.org
6. en.wikipedia.org
7. arxiv.org
8. arxiv.org