Understanding the difficulty of identifying quantum states remains a fundamental challenge in theoretical physics. Maxwell West and colleagues demonstrate the average‑case hardness of learning the probability distributions—known as Born distributions—of states drawn from the circular and Gaussian ensembles. These ensembles represent a broad class of quantum states arising from compact symmetric spaces, extending previous work on classical systems. This research is significant because it establishes a clear computational lower bound for distinguishing between different quantum states, offering insights into the limits of quantum information processing. Moreover, the novel mathematical techniques developed—particularly a new approach to integration over compact groups—provide precise calculations of key quantities previously known only approximately.

The work establishes the average‑case hardness of learning the Born distributions of states uniformly sampled from the circular and fermionic Gaussian ensembles, a significant advancement in understanding the limits of quantum‑state characterisation. Researchers proved this hardness within the statistical query model, a framework for assessing learning complexity based on the number of expectation‑value queries required to accurately model an unknown state. This finding extends analogous recent results concerning states sampled from classical compact groups, solidifying a growing understanding of computational limitations in quantum systems.

The team achieved this breakthrough by employing an unconventional approach to integration over compact groups, a technique that may prove valuable in other contexts. This novel mathematical treatment allowed for the exact evaluation of total‑variation distances between the output distributions of Haar‑random unitary and orthogonal circuits and the constant distribution—quantities previously known only through approximations. Specifically, the research focuses on ensembles induced by uniform measures on compact symmetric spaces of types AI, AII, and DIII, providing a rigorous mathematical foundation for assessing their inherent complexity. The ability to precisely quantify these distances represents a substantial technical achievement, offering new insights into the behaviour of random quantum circuits.

These ensembles—circular unitary, orthogonal, and symplectic, alongside the fermionic Gaussian—are deeply rooted in both physics and mathematics. The circular ensembles were originally introduced to describe energy levels in complex quantum systems exhibiting various symmetry constraints, while the fermionic Gaussian ensemble arises in the study of many‑body physics. By demonstrating the average‑case hardness of learning their associated Born distributions, the study reveals fundamental limits on how efficiently these states can be distinguished or reconstructed from limited data. The researchers formally state that learning these distributions requires a number of queries that scales doubly‑exponentially with the logarithm of the Hilbert space dimension, even with highly accurate queries.

Experiments show that even inverse‑exponentially accurate statistical queries are insufficient to learn a small fraction of the possible Born distributions in a reasonable number of steps. This extreme difficulty underscores the inherent complexity of these quantum states and has implications for applications such as benchmarking and quantum tomography. The work opens avenues for further investigation into the relationship between symmetry, ensemble structure, and the computational cost of learning quantum states, potentially guiding the development of more efficient quantum algorithms and characterisation techniques. This research establishes a firm theoretical basis for understanding the challenges associated with processing information encoded in these fundamental quantum ensembles.

---

Learning Born Distributions via Statistical Query Models

The study rigorously investigates the average‑case hardness of learning Born distributions originating from states sampled across circular and Gaussian ensembles, employing the statistical query model as its foundational framework. Researchers engineered a novel approach to integration over compact groups, circumventing the need for Weingarten calculus and instead utilising elementary techniques based on beta and gamma distributions. This methodological innovation allowed for the precise calculation of total‑variation distances between the output distributions of Haar‑random unitary and orthogonal circuits and the constant distribution, improving upon previous approximations with an additive precision of (O(1/\sqrt{d})). Experiments focused on calculating these distances for finite system dimensions, specifically assuming (d \ge 4) to avoid problematic special cases.

The team developed a formal proof of a central theorem, establishing a precise formalisation of an earlier informal proposition regarding the complexity of learning these distributions. Central to the work is the statistical query learning framework, where algorithms learn distributions by accessing expectation values of functions rather than direct sampling. Scientists defined the statistical query oracle, Stat(P_{\tau}), which returns the average of a function over a distribution (P), accurate to within a tolerance (\tau). The research harnessed Lemma 1 from a prior publication to establish a relationship between the number of queries required for learning and the probability of distinguishing distributions.

Calculations centred on determining two key quantities: the size of the ((\varepsilon+\tau))-ball around the constant distribution and the maximum fraction of distributions distinguishable from the constant distribution via querying their oracle. The approach enables precise evaluation of these quantities, utilising concentration‑of‑measure arguments and the techniques developed for integrating over compact groups, ultimately demonstrating the computational complexity of learning states from the specified ensembles. This method achieves a level of accuracy previously unattainable, providing a more definitive understanding of the inherent difficulty of this learning problem.

---

Born Distribution Learning Hardness for Gaussian Ensembles

Scientists have established the average‑case hardness of learning the Born distributions of states sampled uniformly from the circular and fermionic Gaussian ensembles, building upon recent advances in understanding quantum‑state complexity. The research focuses on ensembles induced by uniform measures on compact symmetric spaces of types AI, AII, and DIII, complementing analogous findings for states originating from classical compact groups. This work employs a novel approach to integrating over compact groups, offering a potentially valuable technique for future investigations within quantum information theory. Experiments reveal the ability to precisely evaluate total‑variation distances between output distributions of Haar‑random unitary and orthogonal circuits and the constant distribution, a feat previously achieved only through approximation.

The team measured the complexity of learning these distributions within the statistical query model, assessing the number of queries needed to accurately model underlying states. This investigation addresses a fundamental question in quantum information: how difficult is it to classically sample from the Born distributions generated by states drawn from specific ensembles? Results demonstrate that determining the complexity of learning states from the circular and fermionic Gaussian ensembles presents a significant computational challenge, furthering understanding of the inherent difficulty in characterising quantum systems. The study builds on prior work establishing the difficulty of learning states from the Haar measure on the unitary group and those produced by random brickwork quantum circuits.

Measurements confirm that the circular ensembles—unitary, orthogonal, and symplectic—introduced by Dyson in 1962 accurately describe energy levels in complex quantum systems subject to varying symmetry constraints. Specifically, the research details how the circular orthogonal and symplectic ensembles relate to uniform measures on compact symmetric spaces of types AI and AII, respectively. Furthermore, scientists explored the ensemble of states generated by sampling randomly from the symmetric space of type DIII, corresponding to the uniform measure on the manifold of fermionic Gaussian states. The breakthrough delivers a precise method for evaluating total‑variation distances, previously known only approximately, between the output distributions of random quantum circuits and a constant distribution. This advancement stems from the unconventional integration approach developed for compact groups, potentially offering broader applications within the field. Data show a clear path toward quantifying the difficulty of learning the Born distributions of states, providing a foundation for future research into the complexity of quantum‑state characterisation and its implications for quantum computation and information processing.

---

Conclusions

This work establishes the average‑case hardness of learning Born distributions of quantum states drawn from the circular and Gaussian ensembles, building upon existing results for classical compact groups. Researchers demonstrated this intractability within the statistical query model, confirming the inherent difficulty of distinguishing these ensembles from random noise. The findings contribute to a growing understanding of the complexity associated with characterising states generated by natural unitary transformations. The technical approach employed offers a novel method for integration over compact groups, allowing for precise calculations of total‑variation distances between output distributions of random quantum circuits and a uniform distribution. While the conclusions align with previous studies utilising concentration‑of‑measure arguments, this research presents a distinct analytical pathway. The authors acknowledge limitations stemming from the computational intensity of the calculations and suggest that future work could explore extending these techniques to other relevant quantum ensembles.

---

More information

On the average‑case complexity of learning states from the circular and Gaussian ensembles – arXiv: 2601.10197