124
Part Three · B · Algorithms

Quantum machine learning: kernels, QNNs, data loading, provable separations

In ordinary machine learning, more expressive models usually do better if you have enough data. Quantum machine learning (QML) inherited that intuition, and spent several years learning where it fails. A quantum feature map can place data in a space of 2n2^n dimensions, but in so vast a space every data point looks almost the same as every other. The rigorous successes turned out to lie somewhere else: learning about quantum systems from quantum data.

On the plate: how similar two data points look to a quantum model, as qubits are added.

Quantum kernels and neural networks

A quantum kernel maps each input xx to a state ∣ϕ(x)⟩|\phi(x)\rangle and uses the overlap k(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2k(x,x') = |\langle\phi(x)|\phi(x')\rangle|^2 as a similarity measure in a support-vector machine. A quantum neural network is a variational circuit (Chapter 122) whose output is a prediction. Both need classical data loaded into the circuit. Loading NN numbers as amplitudes takes about NN gates (Chapter 120); loading them as rotation angles is cheap but uses one parameter per number. Established

Kernel concentration

Encode each feature as a rotation angle on its own qubit, with n=n = 5 qubits. For random inputs the plate histograms the kernel k=∏icos⁡2((xi−xi′)/2)k = \prod_i\cos^2\big((x_i - x_i')/2\big). Its mean falls as 0.703n0.703^n: 0.029 at 10 qubits, about 10⁻³ at 20. Every pair looks equally unlike every other, so estimating the kernel to useful relative precision takes exponentially many shots. Supriyo Thanasilp and colleagues showed in 2024 that this exponential concentration afflicts expressive embeddings, global measurements, entanglement and noise alike. Established

Where advantage is real

Yunchao Liu, Srinivasan Arunachalam and Kristan Temme proved in 2021 a quantum kernel advantage for a classification task built on the discrete logarithm, the problem Shor’s algorithm solves; it is rigorous but contrived. The stronger results concern quantum data. Hsin-Yuan Huang, Richard Kueng and John Preskill introduced classical shadows in 2020: measure each copy of a state in a random basis, and estimate many properties from the record. Try a single-qubit state with 100 snapshots, then . Each snapshot reports ±1 in a random Pauli basis; tripling it gives an unbiased estimate, and the error falls as 3/N\sqrt{3/N}. In 2022 Huang and colleagues showed on Google’s processor that learning from quantum data held in quantum memory needs exponentially fewer experiments than any measure-first strategy, for certain tasks. Established for quantum data in those settings; Speculative for advantage on classical data.

What you now have

Quantum kernels and neural networks, the data-loading cost, exponential kernel concentration, the discrete-log separation, classical shadows, and the experimental quantum-data advantage.

· · ·

Three questions to carry with you.

What is kernel concentration?tap
Kernel values for different inputs collapse toward a single value exponentially in n, so they carry no usable information.
What does a classical shadow store?tap
The random basis and outcome of each measured copy, enough to estimate many observables later.
Where is QML advantage best established?tap
Learning about quantum systems from quantum data, with quantum memory.

And one to work out. With per-qubit mean kernel 0.703, what is the mean kernel for 10 qubits?

k̄ ≈

Sources: Y. Liu, S. Arunachalam and K. Temme, Nat. Phys. 17, 1013 (2021). H.-Y. Huang, R. Kueng and J. Preskill, Nat. Phys. 16, 1050 (2020). H.-Y. Huang et al., Science 376, 1182 (2022). S. Thanasilp et al., Nat. Commun. 15, 5200 (2024). M. Schuld and F. Petruccione, Machine Learning with Quantum Computers (Springer, 2021). Checked by code: per-qubit mean ½ + ½(2/π)² = 0.7026; sampled means 0.172 (5 qubits), 0.029 (10), 9 × 10⁻⁴ (20).

Next · Chapter 125
Quantum optimization and annealing

Nature finds the lowest valley if you go slowly enough. How slow is slow enough?

Turn the page