We propose several algorithms for learning unitary operators from quantum statistical queries with respect to their Choi-Jamiolkowski state. Quantum statistical queries capture the capabilities of a learner with limited quantum resources, which receives as input only noisy estimates of expected values of measurements. Our approach leverages quantum statistical queries to estimate the Fourier mass of a unitary on a subset of Pauli strings, generalizing previous techniques developed for uniform quantum examples. Specifically, we show that the celebrated quantum Goldreich-Levin algorithm can be implemented with quantum statistical queries, whereas the prior version of the algorithm involves oracle access to the unitary and its inverse. As an application, we prove that quantum Boolean functions with constant total influence or with constant degree are efficiently learnable in our model. Moreover, we prove that O(logn) -juntas are efficiently learnable and constant-depth circuits are learnable query-efficiently with quantum statistical queries. On the other hand, all previous algorithms for these tasks demand significantly greater resources, such as oracle access to the unitary or direct access to the Choi-Jamiolkowski state. We also demonstrate that, despite these positive results, quantum statistical queries lead to an exponentially larger query complexity for certain tasks, compared to separable measurements to the Choi-Jamiolkowski state. In particular, we show an exponential lower bound for learning a class of phase-oracle unitaries and a double exponential lower bound for testing the unitarity of channels. Taken together, our results indicate that quantum statistical queries offer a unified framework for various unitary learning tasks, with potential applications in quantum machine learning, many-body physics and benchmarking of near-term devices.
In this work, we initiate the study of learning quantum processes from quantum statistical queries. We focus on two fundamental learning tasks in this new access model: shadow tomography of quantum processes and process tomography with respect to diamond distance. For the former, we present an efficient average-case algorithm along with a nearly matching lower bound with respect to the number of observables to be predicted. For the latter, we present average-case query complexity lower bounds for learning classes of unitaries. We obtain an exponential lower bound for learning unitary 2-designs and a doubly exponential lower bound for Haar-random unitaries. Finally, we demonstrate the practical relevance of our access model by applying our learning algorithm to attack an authentication protocol using Classical-Readout Quantum Physically Unclonable Functions, partially addressing an important open question in quantum hardware security.
We study the problem of learning nearly
(s,ε)-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most
s components with at most
ε residual mass in Pauli
ℓ1-norm. This class generalizes well-studied families, including sparse unitaries, quantum
k-juntas,
2k-Pauli dimensional channels, and compositions of depth
O(loglogn) circuits with near-Clifford circuits.
Given query access to an unknown nearly sparse unitary
U, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to
U. We design a learning algorithm achieving this guarantee using
O~(s6/ε4) forward queries to
U, and running time polynomial in relevant parameters.
A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary
U, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold
θ, extending existing sparse recovery techniques to general unitaries.
We also study the broader class of unitaries with bounded Pauli
ℓ1-norm. For that class, we prove an exponential query lower bound
Ω(2n/2). We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli
ℓ1-norm uniformly bounded by
L1 are learnable with
O~(L18/ε16).
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.
In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on n qubits of depth d , we show three main results:– At super logarithmic circuit depth d=ω(log(n)) , any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance.– There exists a d=O(n) , such that any learning algorithm requires Ω(2n) queries to achieve a O(2−n) probability of success over the randomly drawn instance.– At infinite circuit depth d→∞ , any learning algorithm requires 22Ω(n) many queries to achieve a 2−2Ω(n) probability of success over the randomly drawn instance.As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability 1−O(2−n) , which confirms a variant of a conjecture by Aaronson and Chen.
This work considers a variation on the problem of learning shallow quantum circuits. Given query access to the circuit, as well as knowledge of its gate layout, we consider the task of learning the specific gates used in the circuit, producing an operationally-equivalent circuit matching this structure. Building on recent work for learning Haar random brickwork circuits, we identify a meta-algorithmic framework for learning broad classes of circuits based on iterative local gate inversions at the front and back of the circuit. We apply these techniques to study random, all-to-all, two-local circuits, and provide analytical and numerical evidence that this ensemble undergoes a sharp learnability transition at depth
d∗∼log2n+log2log2n in the large size limit, based on an analysis of lightcone growth. These results have implications for recently proposed quantum cryptographic schemes based on the difficulty of circuit learning, though there are important distinctions with respect to our setting that suggest avenues for future study.