Shadows of quantum machine learning

Abstract

Quantum machine learning is often highlighted as one of the most promising practical applications for which quantum computers could provide a computational advantage. However, a major obstacle to the widespread use of quantum machine learning models in practice is that these models, even once trained, still require access to a quantum computer in order to be evaluated on new data. To solve this issue, we introduce a class of quantum models where quantum resources are only required during training, while the deployment of the trained model is classical. Specifically, the training phase of our models ends with the generation of a 'shadow model' from which the classical deployment becomes possible. We prove that: (i) this class of models is universal for classically-deployed quantum machine learning; (ii) it does have restricted learning capacities compared to 'fully quantum' models, but nonetheless (iii) it achieves a provable learning advantage over fully classical learners, contingent on widely believed assumptions in complexity theory. These results provide compelling evidence that quantum machine learning can confer learning advantages across a substantially broader range of scenarios, where quantum computers are exclusively employed during the training phase. By enabling classical deployment, our approach facilitates the implementation of quantum machine learning models in various practical contexts.

Fig. 1. Quantum and shadow models.

(left) Conventional quantum models can be expressed as inner products between a data-encoding quantum state ρ(x) and a parametrized observable O(θ). The resulting linear model $f_{\mathit{\theta }}\left(\mathit{x}\right)=\mathrm{Tr}\left[\rho \left(\mathit{x}\right)O\left(\mathit{\theta }\right)\right]$ naturally corresponds to a quantum computation, depicted here. (middle) We define flipped models $f_{\mathit{\theta }}\left(\mathit{x}\right)=\mathrm{Tr}\left[\rho \left(\mathit{\theta }\right)O\left(\mathit{x}\right)\right]$ as quantum linear models where the role of the quantum state ρ(θ) and the observable O(x) is flipped compared to conventional models. (right) Flipped models are associated to natural shadow models: one can use techniques from shadow tomography to construct a classical representation $\widehat{\rho }\left(\mathit{\theta }\right)$ of the parametrized state ρ(θ) (during the shadowing phase), such that, for encoding observables O(x) that are classically representable (e.g., linear combinations of Pauli observables), $\widehat{\rho }\left(\mathit{\theta }\right)$ can be used by a classical algorithm to evaluate the model f_θ(x) on new input data (during the evaluation phase). More generally, a shadow model is defined by (i) a shadowing phase where a (bit-string) advice ω(θ) is generated by the evaluation of multiple quantum circuits W₁(θ), …, W_M(θ), and (ii) an evaluation phase where this advice is used by a classical algorithm $\mathcal{A}$, along with new input data x to evaluate their labels ${\tilde{f}}_{\mathit{\theta }}\left(\mathit{x}\right)$. In the Section “General shadow models”, we show that under this general definition, all shadow models are shadows of flipped models.

Fig. 2. Separations between classical, shadow, and quantum models.

Under the assumption that the discrete cube root (DCR) cannot be computed classically in polynomial time, we have a separation between shadow models (captured by the class BPP/qgenpoly) and classical models (in BPP). Under the assumption that there exist functions that can be computed in quantum polynomial time but not in classical polynomial time with the help of advice (i.e., BQP ⊄ P/poly), we have a separation between quantum models (universal for BQP) and shadow models (BPP/qgenpoly). A candidate function for this separation is the discrete logarithm (DLP).