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 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 to a state and uses the overlap 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 numbers as amplitudes takes about 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 5 qubits. For random inputs the plate histograms the kernel . Its mean falls as : 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 . 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.
And one to work out. With per-qubit mean kernel 0.703, what is the mean kernel for 10 qubits?
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).