Studying the complexity of states sampled from various ensembles is a central component of quantum information theory. In this work we establish the average-case hardness of learning, in the statistical query model, the Born distributions of states sampled uniformly from the compact symmetric spaces of type AI, AII, and DIII. These ensembles correspond in various senses to the so called circular and (fermionic) Gaussian ensembles. This finding complements analogous recent results for states sampled from the classical compact groups. On the technical side, we employ a somewhat unconventional approach to integrating over the compact groups which may be of some independent interest. For example, our approach allows us to exactly evaluate the total variation distances between the output distributions of Haar random unitary and orthogonal circuits and the constant distribution, which were previously known only approximately.
Studying the complexity of states sampled from various ensembles is a central component of quantum information theory. In this work we establish the average-case hardness of learning, in the statistical query model, the Born distributions of states sampled uniformly from the compact symmetric spaces of type AI, AII, and DIII. These ensembles correspond in various senses to the so called circular and (fermionic) Gaussian ensembles. This finding complements analogous recent results for states sampled from the classical compact groups. On the technical side, we employ a somewhat unconventional approach to integrating over the compact groups which may be of some independent interest. For example, our approach allows us to exactly evaluate the total variation distances between the output distributions of Haar random unitary and orthogonal circuits and the constant distribution, which were previously known only approximately.
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.
In open quantum systems, a basic question at the interface of quantum information, statistical physics, and many-body dynamics is how well can one infer the structure of noise and dissipation generators from finite-time measurement statistics alone. Motivated by this question, we study the learnability and cryptographic applications of random open-system dynamics generated by Lindblad-Gorini-Kossakowski-Sudarshan (GKSL) master equations. Working in the affine hull of the GKSL cone, we introduce physically motivated ensembles of random local Lindbladians via a linear parametrisation around a reference generator. On top of this geometric structure, we extend statistical query (SQ) and quantum-process statistical query (QPStat) frameworks to the open-system setting and prove exponential (in the parameter dimension M) lower bounds on the number of queries required to learn random Lindbladian dynamics. In particular, we establish average-case SQ-hardness for learning output distributions in total variation distance and average-case QPStat-hardness for learning Lindbladian channels in diamond norm. To support these results physically, we derive a linear-response expression for the ensemble-averaged total variation distance and verify the required nonvanishing scaling in a random local amplitude-damping chain. Finally, we design two Lindbladian physically unclonable function (Lindbladian-PUF) protocols based on random Lindbladian ensembles with distribution-level and tomography-based verification, thereby providing open-system examples where learning hardness can be translated into cryptographic security guarantees.
Abstract Understanding the complexity of quantum states and circuits is a central challenge in quantum information science, with broad implications in many-body physics, high-energy physics and quantum learning theory. A common way to model the behavior of typical states and circuits involves sampling unitary transformations from the Haar measure on the unitary group. In this work, we depart from this standard approach and instead study structured unitaries drawn from other compact connected groups, namely the symplectic and special orthogonal groups. By leveraging the concentration of measure phenomenon, we establish two main results. We show that random quantum states generated using symplectic or orthogonal unitaries typically exhibit an exponentially large strong state complexity, and are nearly orthogonal to one another. Similar behavior is observed for designs over these groups. Additionally, we demonstrate the average-case hardness of learning circuits composed of gates drawn from such classical groups of unitaries. Taken together, our results demonstrate that structured subgroups can exhibit a complexity comparable to that of the full unitary group.
Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms. For example, it can obstruct constant-time Langevin dynamics and message-passing in random k-SAT and max-cut instances. We provide an analogous framework for average-case quantum complexity showing that a natural family of quantum algorithms (e.g., Lindbladian evolution) fails for natural Hamiltonian ensembles (e.g., random 3-local Hamiltonians). Specifically, we prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling, which we define by a Lipschitz temperature dependence in quantum Wasserstein complexity. Our proof relies on showing that such algorithms fail to capture a structural phase transition in the Gibbs state, where glassiness causes the Gibbs state to decompose into clusters extensively separated in quantum Wasserstein distance. This yields average-case lower bounds for constant-time local Lindbladian evolution and shallow variational circuits. Unlike mixing time lower bounds, our results hold even when dynamics are initialized from the maximally mixed state. We apply these lower bounds to non-commuting, non-stoquastic Hamiltonians by showing a glass transition via the replica trick. We find that the ensemble of all 3-local Pauli strings with independent Gaussian coefficients is average-case hard, while providing analytical evidence that the general p-local Pauli ensemble is non-glassy for sufficiently large constant p, in contrast to its classical (Ising p-spin, always glassy) and fermionic (SYK, never glassy) counterparts.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown η-particle n-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlogn); here we improve this to O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable h, we prove a sample complexity bound of O(η∥h0∥22), where h0 is the traceless component of h; the associated classical post-processing scales as O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.
Motivated by work on quantum black-box query complexity, we consider quantum versions of two well-studied models of learning Boolean functions: Angluin's (1988) model of exact learning from membership queries and Valiant's (1984) Probably Approximately Correct (PAC) model of learning from random examples. For each of these two learning models we establish a polynomial relationship between the number of quantum versus classical queries required for learning. Our results provide an interesting contrast to known results which show that testing black-box functions for various properties can require exponentially more classical queries than quantum queries. We also show that under a widely held computational hardness assumption there is a class of Boolean functions which is polynomial-time learnable in the quantum version but not the classical version of each learning model; thus while quantum and classical learning are equally powerful from an information theory perspective, they are different when viewed from a computational complexity perspective.