Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.
Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.
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.
Symmetry underlies many of the most effective classical and quantum learning algorithms, yet whether quantum learners can gain a fundamental advantage under symmetry-imposed structures remains an open question. Based on evidence that classical statistical query ($\SQ$) frameworks have revealed exponential query complexity in learning symmetric function classes, we ask: can quantum learning algorithms exploit the problem symmetry better? In this work, we investigate the potential benefits of symmetry within the quantum statistical query ($\QSQ$) model, which is a natural quantum analog of classical $\SQ$. Our results uncover three distinct phenomena: (i) we obtain an exponential separation between $\QSQ$ and $\SQ$ on a permutation-invariant function class; (ii) we establish query complexity lower bounds for $\QSQ$ learning that match, up to constant factors, the corresponding classical $\SQ$ lower bounds for most commonly studied symmetries; however, the potential advantages may occur under highly skewed orbit distributions; and (iii) we further identify a tolerance-based separation exists, where quantum learners succeed at noise levels that render classical $\SQ$ algorithms ineffective. Together, these findings provide insight into when symmetry can enable quantum advantage in learning.
It has been shown that the apparent advantage of some quantum machine learning algorithms may be efficiently replicated using classical algorithms with suitable data access -- a process known as dequantization. Existing works on dequantization compare quantum algorithms which take copies of an n-qubit quantum state ∣x⟩=∑ixi∣i⟩ as input to classical algorithms which have sample and query (SQ) access to the vector x. In this note, we prove that classical algorithms with SQ access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs. Because classical algorithms are a subset of quantum algorithms, this demonstrates that SQ access can sometimes be significantly more powerful than quantum state inputs. Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs. If we compare quantum algorithms with quantum state inputs to classical algorithms with access to measurement data on quantum states, the landscape of quantum advantage can be dramatically different. We remark that when the quantum states are constructed from exponential-size classical data, comparing SQ access and quantum state inputs is appropriate since both require exponential time to prepare.
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.
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.
The astounding acceleration in Artificial Intelligence and Quantum Computing advances naturally gives rise to a line of research, which unrolls the potential advantages of quantum computing on classical Machine Learning tasks, known as Quantum Machine Learning or Quantum Machine Intelligence. The typical objectives are either (1) exploring the potential quantum advantages on classical learning tasks or (2) levering well-established classical ML algorithms to tackle quantum-related problems on Noisy Intermediate-Scale Quantum (NISQ) devices. Along the second research direction, we study Quantum Neural Networks (QNNs) to accomplish the purpose of Bayesian learning. By observing a wide range of studies on QNNs, in which the sole training method is based on frequentist training, we find that Bayesian learning benefits QNNs from two aspects. First, Bayesian-trained models enjoy a high level of generalization due to the prior and posterior distribution usage compared to frequentist training, which will be justified by this paper’s theoretical study of model capacity. Second, Bayesian Inference offers epistemic uncertainty estimation, which merits the decision-making process. It is worth mentioning that frequentist-trained QNNs generally lack this desirable property. Under the Bayesian training procedure, our derived models can be considered a new class of QNNs (called BayesianQNNs) which possesses both desirable properties of Bayesian Inference while maintaining comparable predictive performance as frequentist counterparts. The proposed Bayesian Quantum Neural Networks is justified by empirical evidence from numerical experiments.