Learnability of Quantum Computer Distributions

Apart from supervised learning, an important research focus in Machine Learning (ML) is unsupervised learning, including generative modeling paradigms. There, a type of oracle access to an unknown target distribution is given, usually (but not always) in the form of an unlabeled dataset, and the learning algorithm returns output, an approximate generator for that target distribution. Typical examples of such generative modeling are generative adversarial networks (GANs), variational auto-encoders and normalizing flows. At the same time, the development of quantum equivalent models and algorithms for generative modelling, such as quantum circuit Born machines (QCBMs), quantum GANs and quantum Hamiltonian-based models, have also been proposed and implemented within the field of Quantum Machine Learning (QML).

In this work, the authors study the learnability of the output distributions of local quantum circuits within the Probably Approximately Correct (PAC) framework for probabilistic modelling. The problem of density modelling has also been studied, in addition to providing results for generative modelling. The objective is to generate new samples from a target distribution i.e. an efficient generator, and to output with high probability a sufficiently accurate algorithm for evaluating the probabilities of events with respect to the target distribution i.e. an efficient evaluator. Both of these probabilistic modelling problems are studied with respect to two different models of access to the unknown target distribution. The first model is called the sample model where the learner has access to a sample oracle which provides samples from the unknown target distribution. The second model is a statistical query (SQ) model, which is a strict restriction of the sample model. In this case, the learners only have access to the approximate averaged statistical properties of the unknown target distribution instead of samples from the target distribution.

The work provides a query complexity lower bound for SQ-learning the output distributions of local Clifford circuits, in particular how it scales with respect to the circuit depth d. With respect to linear depth, the lower bound is exponential, while a super-polynomial lower bound is achieved at sub-linear circuit depths. In case of sufficiently highly unstructured problems like the SQ model, it is difficult to estimate the original target distribution, given the statistical averages of the sampled data, even for classical algorithms. This is also in accordance with the results in the case of output distributions of local Clifford circuits, as the distributions cannot be sample efficiently PAC learned in the SQ model. However, for the sample model, there might be an underlying data structure to the model that can be easily learnt, which can be exploited, allowing such model to be sample and computationally efficient. Due to the fact that the class of distributions generated by local Clifford circuits saturates at some circuit depth, it is shown that output distributions of local Clifford circuits of any depth are computationally efficiently PAC learnable in the sample model. Furthermore, a tradeoff is established between circuit depth and query complexity, i.e. if the circuit depth is less than the number of qubits, there exists some difficulty in implementing some global Clifford unitaries.

The work also shows that learning to sample from the output distribution of a quantum circuit given SQ oracle access to the distribution can be hard, even when such sampling can be done classically in an efficient manner when given a circuit description. However, there exist computational problems which are hard in the sample model yet easy in the SQ model, implying that hardness in SQ model cannot be correlated with that of the sample model. Also, the concept class of Born distributions corresponding to local Clifford circuits is both sample- and time- efficiently PAC learnable in the sample model by a classical learning algorithm despite being hard in the SQ model.

Overall, this work provides insights on PAC learnability of the Born distributions associated with local quantum circuits. The main results establish the hardness of learning the output distributions of super-logarithmic depth Clifford circuits, however a potential next step is to explore whether the output distributions of logarithmic depth Clifford circuits are efficiently SQ-learnable. This can be done by examining the tightness of the query complexity lower bounds. In the same direction, learnability of free-fermion distributions and match-gate circuits can be explored by exploiting the proposed algorithms. Moreover, another interesting direction to explore is the average case PAC learnability of local quantum circuit output distributions i.e. whether a randomly drawn distribution from the concept class will be efficiently PAC learnable, if all distributions in the concept class are efficiently learnable. Finally, improving the robustness of learnability results with respect to noise can enhance the efficiency of the learning algorithms.