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.
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.
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of probability distributions or quantum states produced by shallow circuits. Specifically, we show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors (LWE) problem, and thus believed to be intractable even for efficient quantum computation. This illustrates that quantum circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that this problem for log-depth circuits is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. Finally, we discuss potential future applications of our work for quantum gravity research by relating our results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.
Abstract The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state. The creation complexity of quantum states is closely related to the complexity of quantum circuits, which is crucial in developing efficient quantum algorithms that can outperform classical algorithms. A major question unanswered so far is what quantum states can be created with a number of elementary gates that scales polynomially with the number of qubits. In this work, it is first shown that for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is polynomial. Then, it is shown that it is possible for a large class of quantum states with polynomial creation complexity to have common coefficient features such that, given any candidate quantum state, an efficient coefficient sampling procedure can be designed to determine if the state belongs to the class or not with arbitrarily high success probability. Consequently, partial knowledge of a quantum state's creation complexity is obtained, which can be useful for designing quantum circuits and algorithms involving such a state.