Abstract We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential gate complexity of state preparation, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.
Abstract We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential gate complexity of state preparation, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.
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.
We consider the tasks of learning quantum states, measurements and channels generated by continuous-variable (CV) quantum circuits. This family of circuits is suited to describe optical quantum technologies and in particular it includes state-of-the-art photonic processors capable of showing quantum advantage. We define classes of functions that map classical variables, encoded into the CV circuit parameters, to outcome probabilities evaluated on those circuits. We then establish efficient learnability guarantees for such classes, by computing bounds on their pseudo-dimension or covering numbers, showing that CV quantum circuits can be learned with a sample complexity that scales polynomially with the circuit's size, i.e., the number of modes. Our results show that CV circuits can be trained efficiently using a number of training samples that, unlike their finite-dimensional counterpart, does not scale with the circuit depth.
There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.
We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the problem of \emph{PAC learning quantum process}, and study its sample complexity. In the problem of PAC learning quantum process, we want to learn an ϵ-approximate of an unknown quantum process c∗ from a known finite concept class C with probability 1−δ using samples {(x1,c∗(x1)),(x2,c∗(x2)),…}, where {x1,x2,…} are computational basis states sampled from an unknown distribution D and {c∗(x1),c∗(x2),…} are the (possibly mixed) quantum states outputted by c∗. The special case of PAC-learning quantum process under constant input reduces to a natural problem which we named as approximate state discrimination, where we are given copies of an unknown quantum state c∗ from an known finite set C, and we want to learn with probability 1−δ an ϵ-approximate of c∗ with as few copies of c∗ as possible. We show that the problem of PAC learning quantum process can be solved with O(ϵ2log∣C∣+log(1/δ)) samples when the outputs are pure states and O(ϵ2log3∣C∣(log∣C∣+log(1/δ))) samples if the outputs can be mixed. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples and approximate state discrimination can be solved in polynomial samples even when concept class size ∣C∣ is exponential in the number of qubits, an exponentially improvement over a full state tomography.
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to withinexp(−Ω(mlogm))additive error is hard for any classical computer, wheremis the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNPreduction. In the recent experiments, the quantum circuit has n-qubits and the architecture is a two-dimensional grid of sizen×n[1]. Indeed for constant depth circuits approximating the output probabilities to within2−Ω(nlogn)is hard. For circuits of depthlognornfor which the anti-concentration property holds, approximating the output probabilities to within2−Ω(nlog2n)and2−Ω(n3/2logn)is hard respectively. We then show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including the trivial circuit with identity gates. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp–Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.
Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are PAC (probably approximately correct) learnable on a quantum computer via empirical risk minimization: to learn a quantum circuit with at most nc gates and each gate acting on a constant number of qubits, the sample complexity is bounded by O~(nc+1). In particular, we explicitly construct a family of variational quantum circuits with O(nc+1) elementary gates arranged in a fixed pattern, which can represent all physical quantum circuits consisting of at most nc elementary gates. Our results provide a valuable guide for quantum machine learning in both theory and experiment.