Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that $$BQP$$ B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.
Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that BQP B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.
An overarching milestone of quantum machine learning (QML) is to demonstrate the advantage of QML over all possible classical learning methods in accelerating a common type of learning task, as represented by supervised learning from classical data. However, the provable advantages of QML in supervised learning have been known so far only for the learning tasks designed for using the advantage of specific quantum algorithms, i.e., Shor’s algorithms. Here, we explicitly construct an unprecedentedly broader family of supervised learning tasks with classical data to offer the provable advantage of QML based on general quantum computational advantages, progressing beyond Shor’s algorithms. Our learning task is feasibly achievable by executing a general class of functions that can be computed efficiently in polynomial time for a large fraction of inputs by arbitrary quantum algorithms, but not by any classical algorithm. We prove the hardness of achieving this learning task for any possible polynomial-time classical learning method. We also clarify protocols for preparing the classical data to demonstrate this learning task in experiments. These results provide a way to exploit a variety of quantum advantages in computing functions for the realization of provably advantageous QML.
Despite significant effort, the quantum machine learning community has only demonstrated quantum learning advantages for artificial cryptography-inspired datasets when dealing with classical data. In this paper we address the challenge of finding learning problems where quantum learning algorithms can achieve a provable exponential speedup over classical learning algorithms. We reflect on computational learning theory concepts related to this question and discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve. We examine existing learning problems with provable quantum speedups and find that they largely rely on the classical hardness of evaluating the function that generates the data, rather than identifying it. To address this, we present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data. Furthermore, we explore computational hardness assumptions that can be leveraged to prove quantum speedups in scenarios where data is quantum-generated, which implies likely quantum advantages in a plethora of more natural settings (e.g., in condensed matter and high energy physics). We also discuss the limitations of the classical shadow paradigm in the context of learning separations, and how physically-motivated settings such as characterizing phases of matter and Hamiltonian learning fit in the computational learning framework.
Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We provide evidence for these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP = BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.
One of the key challenges in quantum machine learning is finding relevant machine learning tasks with a provable quantum advantage. A natural candidate for this is learning unknown Hamiltonian dynamics. Here, we tackle the supervised learning version of this problem, where we are given random examples of the inputs to the dynamics as classical data, paired with the expectation values of some observable after the time evolution, as corresponding output labels. The task is to replicate the corresponding input-output function. We prove that this task can yield provable exponential classical-quantum learning advantages under common complexity assumptions in natural settings. To design our quantum learning algorithms, we introduce a new method, which we term \textit{\subroutine}~algorithm for parametrized circuit functions, and which may be of independent interest. Furthermore, we discuss the limitations of generalizing our method to arbitrary quantum dynamics while maintaining provable guarantees. We explain that significant generalizations are impossible under certain complexity-theoretic assumptions, but nonetheless, we provide a heuristic kernel method, where we trade-off provable correctness for broader applicability.
The most general examples of quantum learning advantages involve data labeled by cryptographic or intrinsically quantum functions, where classical learners are limited by the infeasibility of evaluating the labeling functions using polynomial-sized classical circuits. While broad in scope, such results reveal little about advantages arising from the learning process itself. In cryptographic settings, further insight is possible via random-generatability - the ability to classically generate labeled data - enabling hardness proofs for identification tasks, where the goal is to identify the labeling function from a dataset, even when evaluation is classically intractable. These tasks are particularly relevant in quantum contexts, including Hamiltonian learning and identifying physically meaningful order parameters. However, for quantum functions, random-generatability is conjectured not to hold, leaving no known identification advantages in genuinely quantum regimes. In this work, we give the first proofs of quantum identification learning advantages under standard complexity assumptions. We confirm that quantum-hard functions are not random-generatable unless BQP is contained in the second level of the polynomial hierarchy, ruling out cryptographic-style data generation strategies. We then introduce a new approach: we show that verifiable identification - solving the identification task for valid datasets while rejecting invalid ones - is classically hard for quantum labeling functions unless BQP is in the polynomial hierarchy. Finally, we show that, for a broad class of tasks, solving the identification problem implies verifiable identification in the polynomial hierarchy. This yields our main result: a natural class of quantum identification tasks solvable by quantum learners but hard for classical learners unless BQP is in the polynomial hierarchy.
All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.