This dissertation investigates the fundamental computational capabilities of quantum algorithms with respect to combinatorial optimization and distribution learning. We establish rigorous quantum advantages over classical algorithms for such problems under both widely accepted cryptographic assumptions and unconditionally. First, we demonstrate a super-polynomial quantum advantage for approximating solutions to combinatorial optimization problems, explicitly constructing advantage-bearing instances of Integer Linear Programming. Our proofs build upon approximation hardness results that instantiate a connection between the representation-independent hardness of learning and approximation hardness, as captured by Occam’s razor within computational learning theory. We show that the instances we construct can be efficiently approximated by quantum algorithms utilizing Shor’s factoring algorithm, yet remain classically intractable unless standard cryptographic assumptions fail. Second, we fill a previously open gap by proving a super-polynomial quantum advantage for learning the density function of probability distributions, complementing prior results established for generative distribution learning. We show that the hardness of density modeling can be established under weaker cryptographic assumptions involving pseudorandom functions. The quantum advantage for density modeling fundamentally arises from Shor’s algorithm for computing discrete logarithms. Moreover, we explicitly articulate known connections between Boolean function learning hardness and distribution learning hardness using established constructions. Third, addressing practical constraints of near-term quantum devices, we establish an unconditional quantum advantage for generative distribution learning using shallow, constant-depth quantum circuits. We find that shallow quantum circuits pose a superior class of hypotheses compared to classical counterparts. This result underscores the potential of near-term quantum hardware by highlighting the unique computational capabilities enabled by quantum entanglement and non-local correlations, offered even by constrained devices. Collectively, these contributions deepen our understanding of quantum computational advantages for combinatorial optimization and distribution learning, clarifying their foundations and pointing toward promising avenues for future exploration.
This dissertation investigates the fundamental computational capabilities of quantum algorithms with respect to combinatorial optimization and distribution learning. We establish rigorous quantum advantages over classical algorithms for such problems under both widely accepted cryptographic assumptions and unconditionally. First, we demonstrate a super-polynomial quantum advantage for approximating solutions to combinatorial optimization problems, explicitly constructing advantage-bearing instances of Integer Linear Programming. Our proofs build upon approximation hardness results that instantiate a connection between the representation-independent hardness of learning and approximation hardness, as captured by Occam’s razor within computational learning theory. We show that the instances we construct can be efficiently approximated by quantum algorithms utilizing Shor’s factoring algorithm, yet remain classically intractable unless standard cryptographic assumptions fail. Second, we fill a previously open gap by proving a super-polynomial quantum advantage for learning the density function of probability distributions, complementing prior results established for generative distribution learning. We show that the hardness of density modeling can be established under weaker cryptographic assumptions involving pseudorandom functions. The quantum advantage for density modeling fundamentally arises from Shor’s algorithm for computing discrete logarithms. Moreover, we explicitly articulate known connections between Boolean function learning hardness and distribution learning hardness using established constructions. Third, addressing practical constraints of near-term quantum devices, we establish an unconditional quantum advantage for generative distribution learning using shallow, constant-depth quantum circuits. We find that shallow quantum circuits pose a superior class of hypotheses compared to classical counterparts. This result underscores the potential of near-term quantum hardware by highlighting the unique computational capabilities enabled by quantum entanglement and non-local correlations, offered even by constrained devices. Collectively, these contributions deepen our understanding of quantum computational advantages for combinatorial optimization and distribution learning, clarifying their foundations and pointing toward promising avenues for future exploration.
It is unclear to what extent quantum algorithms can outperform classical algorithms for problems of combinatorial optimization. In this work, by resorting to computational learning theory and cryptographic notions, we give a fully constructive proof that quantum computers feature a super-polynomial advantage over classical computers in approximating combinatorial optimization problems. Specifically, by building on seminal work by Kearns and Valiant, we provide special instances that are hard for classical computers to approximate up to polynomial factors. Simultaneously, we give a quantum algorithm that can efficiently approximate the optimal solution within a polynomial factor. The quantum advantage in this work is ultimately borrowed from Shor's quantum algorithm for factoring. We introduce an explicit and comprehensive end-to-end construction for the advantage bearing instances. For these instances, quantum computers have, in principle, the power to approximate combinatorial optimization solutions beyond the reach of classical efficient algorithms.
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.
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.
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.
In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp., AC0), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., AND,OR,NOT gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (RLWE) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for TC0; and if there exists no 2O(d1/η)-time quantum algorithm to solve RLWE with dimension d=O(polylogn) (for every constant η>2), then there exists no O(nlogνn)-time quantum learning algorithm for poly(n)-sized AC0 circuits (for a constant ν>0), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning TC20 in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the LWE problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class TC20, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.
Quantum computers were initially proposed to surpass the limitations of classical computers in simulating physical systems. Soon after, the field of quantum computing advanced through landmark discoveries of quantum algorithms, with some conjectured to provide exponential advantages over classical counterparts. These include Shor’s factoring algorithm, which has profound implications in cryptography. Additionally, moderate yet significant polynomial separations have further increased interest in the field. However, despite this progress, unconditional proofs confirming quantum superiority on the theoretical side remain elusive. At the same time, large, noise-resilient quantum computations on the experimental side, which could challenge the extended Church-Turing thesis by potentially breaking classical computational barriers, have yet to be achieved. Meanwhile, our understanding of the differences between classical and quantum mechanics has deepened. We now possess rigorous theoretical tools, such as Bell inequalities and nonlocal games, to describe behaviors unique to these theories. Moreover, the main loopholes for observing non-classical correlations have been closed experimentally, showing that correlations in the physical world exceed those predicted by classical mechanics. This thesis investigates computational complexity differences between quantum and classical models by studying shallow-depth circuits. The primary focus lies in identifying, elucidating, and proving computational quantum advantages. Additionally, the analysis delves into the bijection between these circuits and foundational non-local game constructions, exploring how quantum-classical deviations in multi-party correlation settings translate to computational advantages. A key question addressed is how to synthesize constant-depth quantum circuits for various problems to leverage quantum advantages. To this end, circuit synthesis techniques tailored to measurement-based quantum computation are developed, enabling simultaneously optimal quantum strategies for certain nonlocal games based on a particular bijection between this model and XOR non-local games. Building on this work, we confront a pivotal challenge: If a candidate quantum circuit potentially provides a computational advantage, how can we prove that no classical circuit surpasses it? This work presents new unconditional quantum-classical separations within shallow-depth settings, distinguishing for the first time constant-depth quantum circuits with one- and two-qubit gates from biased polynomial threshold circuits, which incorporate neural-network-type functionalities. These separations extend to prime-dimensional quantum systems, and we conjecture to have identified Razborov-Smolensky-type problems uniquely solvable by specific prime dimensions. The thesis also differentiates constant-depth quantum circuits with multi-qubit Toffoli gates from their classical counterparts, emphasizing the power of parallel quantum computation. Finally, verifying shallow-depth quantum computations is challenging due to conjectured exponential separations from classical computations, limiting correctness verification through simulation. While specific quantum algorithms within BQP have been addressed, we explore whether a quantum computer can reliably execute any instance from a fixed class of quantum circuits. Moving beyond heuristic-based solutions, we propose a benchmarking protocol that certifies, with exponentially high confidence, the execution of arbitrary circuits of specified dimensions, widths, and depths.