Shadows of quantum machine learning

Quantum machine learning (QML) holds immense potential, particularly using parametrized quantum circuits (PQCs). PQCs have shown promising results in various learning tasks, both in simulations and on real quantum hardware. Some studies suggest QML models can solve problems intractable for classical algorithms, based on cryptographic assumptions. However, a significant hurdle to practical QML implementation is the need for quantum computer access for both model training and deployment phases. This restricts widespread adoption since trained models often need broad deployment. The solution proposed is to develop shadow models; a shadowing phase is inserted between training and deployment using a quantum computer to extract information on the quantum model, then a classical computer evaluates the model on new data during the deployment phase. Previous research explored classical surrogates or shadow models through trigonometric polynomials but raised concerns that classically deployable quantum models might lack quantum advantage. This paper addresses this issue by investigating whether shadow models can achieve quantum advantages over classical models and determining if quantum models exist that are not efficiently shadowable.

Early works utilized PQCs in machine learning, demonstrating good performance. These studies showed promise in solving certain learning tasks intractable for classical algorithms, particularly in predicting ground state properties of quantum systems. However, a significant limitation highlighted in this paper is the reliance on quantum computers for both training and deployment phases of these models. Previous attempts at resolving this limitation involved generating shadow models—classical representations of quantum models—to enable classical evaluation. However, existing approaches, using trigonometric polynomial representations, suggested that classically deployable quantum models may not offer quantum advantage, prompting the research questions addressed in this paper.

The paper introduces 'flipped models' as a core component of their shadow model approach. Flipped models are quantum linear models where the roles of the quantum state and observable are reversed compared to conventional quantum models. This reversal allows for straightforward use of shadow tomography techniques to generate classical representations (shadows) of the quantum state during the shadowing phase. The authors show that shadow models, under their general definition, are shadows of flipped models. The performance of flipped shadow models depends on the number of measurements and the complexity of estimating expectation values of observables. Efficient shadowing procedures can be designed leveraging properties of the quantum states, such as low-bond-dimension matrix product state representations. The paper analyzes the computational capabilities of shadow models. They demonstrate that under widely-believed cryptographic assumptions, certain learning tasks exist where shadow models exhibit a provable quantum advantage over fully classical models. They prove this by considering a variant of the discrete cube root learning task, which is believed to be classically hard but efficiently solvable quantumly using Shor's algorithm. A flipped model is defined using this task that allows for efficient classical evaluation after a quantum shadowing phase, thus proving the quantum advantage. The paper then investigates the limits of shadowability by defining general shadow models and introducing the complexity class BPP/q-poly (Bounded-error Probabilistic Polynomial-time with quantum-generated advice). They establish the existence of quantum models not efficiently shadowable under assumptions like BQP ≠ P/poly. The paper also investigates the limitations of the Fourier shadowing approach, showing its exponential sample complexity in high-dimensional input spaces.

The paper's key findings are: (i) A novel class of QML models, called 'flipped models,' are introduced, where the roles of quantum states and observables are reversed compared to conventional QML models, enabling efficient shadowing. (ii) A general definition of shadow models is proposed, encompassing existing methods and clarifying the role of quantum resources. (iii) Under this general definition, all shadow models are proven to be shadows of flipped models. (iv) Shadow models are proven to achieve a provable quantum advantage over classical models for specific learning tasks under widely believed complexity-theoretic assumptions, specifically a variant of the discrete cube root problem. (v) It's established that there exist quantum models that are not efficiently shadowable under assumptions such as BQP ≠ P/poly, implying that the shadowing approach cannot encompass all QML models. (vi) The Fourier approach to constructing shadow models is shown to suffer from exponential sample complexity in high-dimensional input spaces.

The results provide strong evidence that QML can offer learning advantages even in scenarios with limited quantum computing access. The ability to classically deploy trained models drastically increases the practical applicability of QML across various fields. The introduced 'flipped models' provide a practical approach for building classically deployable QML models, and the proof of quantum advantage in specific tasks highlights the potential for real-world impact. The limitations identified regarding the non-shadowability of some quantum models underscore the need for further research into more general shadowing techniques. The finding regarding the limitations of the Fourier shadowing approach directs attention towards alternative approaches suitable for high-dimensional data.

This paper successfully demonstrates the potential for quantum advantage in classically-deployable QML models. The introduction of flipped models and the rigorous analysis of shadowability provide a valuable framework for future research. Future work could focus on developing more efficient shadowing techniques applicable to a broader class of QML models and exploring the practical applications of these models in diverse domains. Investigating the limitations of shadowability further, particularly concerning high-dimensional data, is also a crucial next step.

The demonstrated quantum advantage is contingent upon widely believed but unproven complexity-theoretic assumptions. The paper focuses primarily on specific learning tasks; the generalizability of the findings to other tasks needs further investigation. The efficiency of the proposed shadowing techniques may vary depending on the specific properties of the quantum models and the chosen shadowing protocol. The exponential sample complexity limitation of Fourier shadowing suggests a need for alternative methods in high-dimensional settings.