Understanding inherent bottlenecks to efficient algorithm design lies at the heart of computer science. This question is significant both in the classical computing domain as well as in the emerging context of quantum computing. In this thesis, my goal is to characterize bottlenecks in designing efficient algorithms through the lens of a parameter called concentration of functions, starting with the domain of quantum information. My primary focus is probabilistically approximately correct (PAC) learning. I chose this domain since it allows us to approach the important subject of supervised learning in a rigorous and principled manner. For PAC learning, I propose a quantum algorithm to learn the class of concentrated Boolean functions with complexity $ O(\frac{M}{\epsilon^2})$ which offers an advantage over the best known classical PAC algorithms with complexity $\tilde{O}(n^2M)$ , where M denotes the number of the concentration terms. I also show a lower bound $\Omega(M)$ to PAC learn this class of functions in distribution-independent settings. All this work is done in the context of the standard query model for PAC learning where the complexity measure is the number of queries, dubbed query complexity. I extend this work to include the learning model where functions are learned without any error, which is often called exact learning, and prove a query complexity lower bound of $\Omega(\frac{\epsilon \log M}{n} 2^n)$ in exact learning the class of concentrated Boolean functions. In the next part of the thesis, I focus my work on classical algorithms and explore a combinatorial counterpart of concentration called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel algorithm in polynomial time using a quasi-polynomial number of processors for the Graph Isomorphism problem. My work builds on Babai’s celebrated quasi-polynomial algorithm and is work-preserving. The idea behind the parallelization explores the symmetry of the input structure for easier parallelization.Understanding inherent bottlenecks to efficient algorithm design lies at the heart of computer science. This question is significant both in the classical computing domain as well as in the emerging context of quantum computing. In this thesis, my goal is to characterize bottlenecks in designing efficient algorithms through the lens of a parameter called concentration of functions, starting with the domain of quantum information. My primary focus is probabilistically approximately correct (PAC) learning. I chose this domain since it allows us to approach the important subject of supervised learning in a rigorous and principled manner. For PAC learning, I propose a quantum algorithm to learn the class of concentrated Boolean functions with complexity $ O(\frac{M}{\epsilon^2})$ which offers an advantage over the best known classical PAC algorithms with complexity $\tilde{O}(n^2M)$, where M denotes the number of the concentration terms. I also show a lower bound $\Omega(M)$ to PAC learn this class of functions in distribution-independent settings. All this work is done in the context of the standard query model for PAC learning where the complexity measure is the number of queries, dubbed query complexity. I extend this work to include the learning model where functions are learned without any error, which is often called exact learning, and prove a query complexity lower bound of $\Omega(\frac{\epsilon \log M}{n} 2^n)$ in exact learning the class of concentrated Boolean functions. In the next part of the thesis, I focus my work on classical algorithms and explore a combinatorial counterpart of concentration called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel algorithm in polynomial time using a quasi-polynomial number of processors for the Graph Isomorphism problem. My work builds on Babai’s celebrated quasi-polynomial algorithm and is work-preserving. The idea behind the parallelization explores the symmetry of the input structure for easier parallelization.

Aug 1, 20210 citations

Supervised Learning with Quantum Computers

Maria Schuld, Francesco Petruccione

Quantum science and technologyJan 1, 2018707 citations

Learning with Quantum Examples: Multiclass, Online, and Smoothed Settings

Preetham Mohan

As quantum computing progresses toward fault-tolerant architectures, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory, and in particular learning from quantum examples, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e., worst-case) PAC learning, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast, under the uniform distribution, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together, these results reveal a striking dichotomy. However, this understanding has largely been developed in the context of learning Boolean functions in the batch setting, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning, online learning, and smoothed learning. In the multiclass PAC setting, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes, finding that quantum examples continue to yield no distribution-independent separation from classical examples, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon, we develop a smoothed learning framework that constrains distributions to be smooth, interpolating between the concentrated-distribution regime, in which no quantum advantage exists, and the uniform-distribution regime, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions, we establish the robustness of quantum Fourier sampling throughout a nontrivial near-uniform regime in the batch setting and observe that these guarantees extend naturally to the online setting. We further analyze several approaches to recovering the target function once its Fourier support has been identified and, based on these observations, formulate conjectures supporting the persistence of the unbounded quantum advantage throughout this regime. Together, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting, showing that quantum-classical separations depend on the interplay between hypothesis class structure, distributional assumptions, and the degree of adversarial control permitted in the learning process.As quantum computing progresses toward fault-tolerant architectures, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory, and in particular learning from quantum examples, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e., worst-case) PAC learning, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast, under the uniform distribution, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together, these results reveal a striking dichotomy. However, this understanding has largely been developed in the context of learning Boolean functions in the batch setting, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning, online learning, and smoothed learning. In the multiclass PAC setting, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes, finding that quantum examples continue to yield no distribution-independent separation from classical examples, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon, we develop a smoothed learning framework that constrains distributions to be smooth, interpolating between the concentrated-distribution regime, in which no quantum advantage exists, and the uniform-distribution regime, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions, we establish the robustness of quantum Fourier sampling throughout a nontrivial near-uniform regime in the batch setting and observe that these guarantees extend naturally to the online setting. We further analyze several approaches to recovering the target function once its Fourier support has been identified and, based on these observations, formulate conjectures supporting the persistence of the unbounded quantum advantage throughout this regime. Together, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting, showing that quantum-classical separations depend on the interplay between hypothesis class structure, distributional assumptions, and the degree of adversarial control permitted in the learning process.

Jan 1, 20260 citations

\tilde{O}(n^2M)

, where M denotes the number of the concentration terms. I also show a lower bound

\Omega(M)

to PAC learn this class of functions in distribution-independent settings. All this work is done in the context of the standard query model for PAC learning where the complexity measure is the number of queries, dubbed query complexity. I extend this work to include the learning model where functions are learned without any error, which is often called exact learning, and prove a query complexity lower bound of

\Omega(\frac{\epsilon \log M}{n} 2^n)

in exact learning the class of concentrated Boolean functions. In the next part of the thesis, I focus my work on classical algorithms and explore a combinatorial counterpart of concentration called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel algorithm in polynomial time using a quasi-polynomial number of processors for the Graph Isomorphism problem. My work builds on Babai’s celebrated quasi-polynomial algorithm and is work-preserving. The idea behind the parallelization explores the symmetry of the input structure for easier parallelization.