On the average-case complexity of learning states from the circular and Gaussian ensembles Maxwell West 1,2 Abstract . 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 circular and (fermionic) Gaussian ensembles. These ensembles of states are induced variously by the uniform measures on the compact symmetric spaces of type AI, AII, and DIII. 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. 1. Introduction Random ensembles of quantum states are ubiquitous in quantum computation and information [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] , as well as physics more generally [ 9 , 10 , 11 , 12 , 13 ] . While uniformly random states have in particular found numerous uses, bespoke applications are occasionally afforded by states generated by acting on a reference state with a unitary sampled uniformly from a strict subgroup of the full unitary group [ 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 ] , or indeed from a subset which lacks a group structure [ 25 ] . For example, in the presence of various symmetries, sampling from a well-chosen such subset can lead to more efficient protocols for benchmarking [ 14 ] and tomography [ 15 , 16 , 18 , 19 , 17 ] . Applications aside, the study of the properties of states sampled from various distributions under various assumptions is naturally of considerable intrinsic interest. Suppose for example that one has access to a state \ket{\psi} in some fixed basis \{\ket{\x}\}_{\bm{x}} . As such access allows one to sample from the Born probability distribution P_{\psi}(\bm{x})=\absolutevalue{\braket{\x}{\psi}}^{2} , one approach is to phrase questions about states drawn from an ensemble \mathcal{E} in terms of the distributions P_{\psi} for \ket{\psi}\sim\mathcal{E} . For instance, for a given \mathcal{E} , what do these distributions look like? How difficult is it to classically sample from them? If \ket{\psi} , \ket{\varphi}\sim\mathcal{E} , how (on average over \mathcal{E} , say) do P_{\psi} and P_{\varphi} compare? Amongst such questions, in this work we ask: What is the complexity of learning the Born distributions of states sampled uniformly from the circular and fermionic Gaussian ensembles? As it currently stands the question is somewhat ill-posed – what do we mean by “complexity”, for example? Here we will focus on sample-complexity in the statistical query model [ 26 , 6 , 24 ] . Concretely, this means that we have an (unknown) state sampled from a (known) distribution, consider an observer with the ability to query the expectation value of observables diagonal in a certain (fixed) basis, and ask how many such queries they need to make in order to learn an accurate model of the underlying state. Our question is inspired by recent works which have answered the analogous question for several different ensembles of states. First, Ref. [ 6 ] established the difficulty of, in the average-case, learning (within the statistical query model) both states drawn from the Haar measure on the full unitary group, and states produced by random brickwork quantum circuits of various depths. Subsequently, Ref. [ 27 ] found (via a rather different information-theoretic argument) that learning Born distributions resulting from matchgate circuits is also hard. More recently, Ref. [ 24 ] similarly found that the state distributions induced by sampling randomly from the Haar measures on the orthogonal and (unitary) symplectic groups are also average-case difficult to learn. Our specific choice of ensembles joins the examples previously considered in this context [ 6 , 27 , 24 ] in being physically motivated as well as reasonably amenable to analytic characterisation. Namely, we recall that the three circular ensembles (unitary, orthogonal and symplectic) were introduced by Dyson in 1962 [ 9 , 10 ] to describe the energy levels of complex quantum systems under various symmetry constraints. As by Wigner’s theorem a symmetry of a quantum mechanical system may always be represented by a unitary (possibly) multiplied by an anti-unitary operator that squares to \pm\mathds{1} , a short list of possibilities arises. First, and simplest of all, the case when there is no anti-unitary symmetry is assigned to the circular unitary ensemble , which is simply given by the usual Haar measure on the unitary group, and has therefore for our purposes been dealt with already in Ref. [ 6 ] . In the case of an anti-unitary symmetry with T^{2}=\mathds{1} , one has the circular orthogonal ensemble , a random element of which may be represented as U^{\mathsf{T}}U , with U itself Haar random on the unitary group. Finally, in the case of an anti-unitary symmetry with T^{2}=-\mathds{1} , one identifies the relevant matrix ensemble as the circular symplectic ensemble , a random element from which has the form JU^{\mathsf{T}}J^{\mathsf{T}}U , with U Haar random on the unitary group and J the symplectic form. The later two (which we would like to emphasise are, despite their names, not the Haar measures on the orthogonal and (unitary) symplectic groups) may also be recognised to be the uniform measures on the so-called compact symmetric spaces of types AI and AII, respectively (more details on the compact symmetric spaces may be found in Section 2.3 ). We will additionally consider the ensemble of states generated by sampling randomly from the (so-called) symmetric space of type DIII, which corresponds to the uniform measure on the manifold of fermionic Gaussian states [ 28 ] ; operationally, here one samples JO^{\mathsf{T}}JO , where O is drawn from the Haar measure on the orthogonal group 1 1 1 The manifold of bosonic Gaussian states (the symmetric space CI [ 28 ] ), on the other hand, is non-compact and so does not support a uniform probability measure; we do not consider it here . Having introduced the ensembles we will consider, we can state our main result: Theorem 1 . (Informal). The output distributions of circuits drawn from the circular and fermionic Gaussian ensembles are average-case hard to learn. This result is similar to the findings of Refs. [ 6 , 24 ] , where the difficulty of the same task was established for the ensembles under consideration in those works. While the informal statement of Theorem 1 is perhaps not particularly surprising (for example, the dimension of AI as a manifold is only lower by a constant factor than that of the full unitary group), we emphasise that, quantitatively, the difficulty of the learning task is quite extreme. For example, in all of our examples we will find that even given inverse-exponentially accurate statistical queries, learning so much as a doubly-exponentially (in the logarithm of the dimension of the Hilbert space) small fraction of the possible Born distributions can take doubly-exponentially many such queries. The structure of the rest of this work is as follows: In Section 2 we review some background knowledge necessary to understand our results, briefly covering the framework of statistical query learning and some elementary aspects of the theory of integration on compact groups and symmetric spaces. Our approach to the latter is somewhat atypical for a work in quantum information theory in that, foreshadowing our later need to integrate non-polynomial functions of the matrix elements of our ensembles, we (largely) avoid the use of Weingarten calculus [ 29 , 30 , 31 , 32 , 33 ] . Instead, we present an elementary treatment based on random variables from the beta and gamma distributions. In Section 3 we apply the methods of Section 2 to calculate the exact total variation distances between the Born distributions of Haar random unitary and orthogonal states and the constant distribution, for finite system dimension d (to avoid dealing with annoying special cases we assume throughout that d\geq 4 ). This improves somewhat over calculations in Refs. [ 6 ] and [ 24 ] , where those quantities were respectively approximated to an additive precision of \mathcal{O}(1/\sqrt{d}) . In Section 4 we give our main technical contribution, a proof of Theorem 1 (formal), a precise formalisation of Theorem 1 (informal). Finally, we conclude in Section 5 with some general discussion. 2. Preliminaries 2.1. Statistical query learning As forewarned, our results are phrased within the framework of statistical query learning ; we now briefly review the aspects necessary to understand the paper. We largely follow, though abridge, the treatment of Ref. [ 6 ] (to which the interested reader is referred for further details). Statistical query learning is concerned with the learning of distributions via access to the expectation values of functions on their support (as opposed, say, to access to samples from the distribution itself). Concretely, for a distribution P on a set \mathcal{X} and a tolerance \tau\geqslant 0 , the statistical query oracle \mathsf{Stat}_{\tau}^{P} is a function (1) \mathsf{Stat}_{\tau}^{P}:(\varphi:\mathcal{X}\to[-1,1])\mapsto v such that \absolutevalue{\expect_{x\sim P}\varphi(x)-v}_{x\sim P}\varphi(x)-v\leq\tau . That is, one gives the oracle a bounded function \varphi , and the oracle returns its average over the distribution, up to an additive tolerance \tau . Naturally, one is interested in the number of queries to \mathsf{Stat}_{\tau}^{P} necessary to identify P (perhaps given, say, that P belongs to some set \mathcal{D} of distributions on \mathcal{X} ). Formally, given some fixed values of \tau,\varepsilon , we will consider the problem of \varepsilon -learning \mathcal{D} to be that of, given access to the \mathsf{Stat}_{\tau}^{P} corresponding to some unknown P\in\mathcal{D} , outputting a function Q that is \varepsilon -close to P in total variation distance , where (2) {\rm d}_{\rm TV}(P,Q):=\frac{1}{2}\sum_{x\in\mathcal{X}}\left|P(x)-Q(x)\right|. We will be interested in the (deterministic 2 2 2 As opposed to the situation where the learning algorithm itself may employ randomness ) average-case complexity of the above problem, over some fraction of \mathcal{D} . That is, given a measure \mu on the set \mathcal{D} of distributions and a success fraction \beta , the deterministic average-case query complexity is the minimum number of queries q that a learning algorithm \mathcal{A} needs to make in order to ensure (3) \Pr_{P\sim\mu}[\mathcal{A}\ \varepsilon\text{-learns $P$ from $q$ ($\tau$-accurate) queries}]\geq\beta. We will make crucial use of the following somewhat formidable-looking lemma from Ref. [ 6 ] : Lemma 1 . [Lemma 1 of Ref. [ 6 ] ] Suppose there is a deterministic algorithm \mathcal{A} that \varepsilon -learns a fraction \beta of \mathcal{D} with respect to \mu from q many \tau -accurate statistical queries. Then for any Q , (4) q+1\geq\frac{\beta-\Pr_{P\sim\mu}[{\rm d}_{\rm TV}(P,Q)\leq\varepsilon+\tau]}{\displaystyle{\max_{\varphi\,:\,\mathcal{X}\to[-1,1]}}\Pr_{P\sim\mu}\left[\Big\lvert\expect_{\bm{x}\sim P}[\varphi(\bm{x})]-\expect_{\bm{x}\sim Q}[\varphi(\bm{x})]\Big\rvert>\tau\right]} Let us try to understand a little of what is going on here. First of all, we will only ever take Q to be the constant distribution \mathcal{C} on the set \mathcal{X}=\{0,1\}^{n} of computational basis output strings of n -qubit systems, i.e. \mathcal{C}(\bm{x})=1/d\ \forall\bm{x}\in\mathcal{X} , with d=2^{n} . There are then two quantities that we are interested in calculating. The first is the size (5) \mathfrak{u}:=\Pr_{P\sim\mu}[{\rm d}_{\rm TV}(P,\mathcal{C})\leq\varepsilon+\tau]=\mathcal{B}_{\varepsilon+\tau}^{\rm TVD}(\mathcal{C}) of the (\varepsilon+\tau) -ball (with respect to the TVD) around the constant distribution. The fact that something like this term should appear and lower the sample complexity is reasonably intuitive; indeed, any distribution that is \varepsilon -close to \mathcal{C} can be “learnt” simply by outputting \mathcal{C} without taking any samples. The second quantity we should like to calculate, the denominator of the right hand side of Eq. ( 4 ), is the fraction of the distributions that can be distinguished from Q via querying their oracle on some (fixed) observable \varphi ; again taking Q to be the uniform distribution on \{0,1\}^{n} we denote it (6) \mathfrak{f}:=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{P\sim\mu}\left[\left\lvert\expect_{\bm{x}\sim P}[\varphi(\bm{x})]-\frac{1}{d}\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\right\rvert>\tau\right]. As in Refs. [ 6 , 24 ] , we will in our applications fairly straightforwardly bound \mathfrak{f} by means of the Weingarten calculus combined with a concentration of measure argument. The calculation of \mathfrak{u} will prove somewhat more challenging, involving as we shall see the expectation of a non-polynomial function of the matrix elements of our ensemble; nonetheless, we will be able to evaluate it by utilising the techniques of Section 2.2 and 2.3 . Having calculated the average value, we will again proceed by a concentration of measure argument (Section 2.4 ). This will culminate in the following formalisation of Theorem 1 : Theorem 1 . (Formal). Let \tau>2/(d-1),\,\varepsilon\leq\xi_{0}-10/d-\tau . Set \xi=\xi_{0}-10/d-\varepsilon-\tau . Any algorithm that succeeds in \varepsilon -learning a \beta fraction of the output distributions of quantum circuits sampled uniformly from the uniform measures on AI, AII, or DIII requires at least q many \tau -accurate statistical queries, with (7) q+1\geq\frac{\beta-2\exp\left[-(d-2)\xi^{2}/96\right]}{2\exp[-(d-2)(\tau-2/(d-1))^{2}/384]} where (for AI, AII and DIII respectively) we take the values \xi_{0}=1/e,\,1/e,\,\sqrt{2/(\pi e)} . Note, as in Ref. [ 6 ] , that taking \tau,\xi\sim 2^{-n/4} and \beta\sim\exp(-2^{0.49 n}) cause the left-hand side of Eq. ( 7 ) to be doubly-exponentially large in n ; that is, learning a doubly-exponentially small fraction of the output distributions takes doubly-exponentially many inverse-exponentially accurate statistical queries. Interestingly, this argument is dramatically sensitive to the precise details of how accurate the oracle is (i.e. how small \tau is). For example, increasing the sensitivity merely from \tau\sim 2^{-n/4} to \tau\sim 2^{-n/2} weakens the bound of Eq. ( 7 ) all the way from being doubly-exponential in n to being trivial. 2.2. Sampling randomly from the classical compact groups In this section, we briefly recall some properties of matrices sampled from the uniform (Haar) measure 3 3 3 The existence and uniqueness of which we shall take for granted \mu_{G} on the classical compact groups, G\in\{\mathbb{U},\,\mathbb{O},\,\mathbb{SP}\} . Many more details may be found in e.g. Refs. [ 34 , 35 , 30 , 29 ] . Our starting point is the well-known fact that an individual column u of a Haar random matrix sampled from \mu_{\mathbb{U}},\ \mu_{\mathbb{O}},\ \mu_{\mathbb{SP}} is distributed like a normalised vector of i.i.d standard normal random variables over the real, complex, and quaternionic numbers respectively: (8) g=(g_{1},\dots,g_{d})\ \text{i.i.d.},\qquad\begin{cases}g_{j}\sim\mathcal{N}_{\mathbb{R}}(0,1)&(\mathbb{O}(d)),\\ g_{j}\sim\mathcal{N}_{\mathbb{C}}(0,1)&(\mathbb{U}(d)),\\ g_{j}\sim\mathcal{N}_{\mathbb{H}}(0,1)&(\mathbb{SP}(d/2))\end{cases}\qquad u=\dfrac{g}{\|g\|_{2}}. We will also require the joint distribution of two rows; operationally this is given by the Gram-Schmidt procedure: one (i) draws two rows g_{1},g_{2} from the appropriate normal distribution in Eq. ( 8 ) (ii) normalises the first to obtain a=g_{1}/\|g_{1}\| (iii) orthogonalises g_{2} with respect to a , h_{2}=g_{2}-\innerproduct{a}{g_2}a (iv) sets b=h_{2}/\|h_{2}\| . Then a,b are distributed as two rows of a Haar random distribution from the corresponding G [ 34 ] . Now, while the constraints of unitarity imply that the distribution of a given element of a Haar-random matrix is not independent of any of the other elements, simple expressions for the distribution of its magnitude do exist. To see them, we first recall the definitions and a few properties of some common distributions: Firstly, we recall that the gamma distribution 4 4 4 Note that {\rm Gamma}(-,-) denotes the so-defined gamma distribution , and \Gamma(-) the factorial-generalising gamma function {\rm Gamma}(k,\theta) has density x^{k-1}e^{-x/\theta}/(\Gamma(k)\theta^{k}) on (0,\infty) . Recall that if X_{i}\sim\mathcal{N}_{\mathbb{R}}(0,k) then \sum_{i=1}^{N}X_{i}^{2}\sim{\rm Gamma}(N/2,2k) ; it then follows from the above discussion that that distribution appears in our context as (9) |g_{j}|^{2}\sim\begin{cases}{\rm Gamma}(1,1),&(\mathbb{U}(d))\\ {\rm Gamma}\big(\frac{1}{2},2\big),&(\mathbb{O}(d))\end{cases}\ ,\qquad\sum_{k=1}^{d}|g_{k}|^{2}\sim\begin{cases}{\rm Gamma}(d,1),&(\mathbb{U}(d))\\ {\rm Gamma}\big(\frac{d}{2},2\big),&(\mathbb{O}(d))\end{cases} Secondly, the beta distribution {\rm Beta}(a,b) has density x^{a-1}(1-x)^{b-1}/B(a,b) , where B(a,b)=\Gamma(a)\Gamma(b)/\Gamma(a+b) . Importantly for us, if X\sim{\rm Gamma}(\alpha,\vartheta) and Y\sim{\rm Gamma}(\beta,\vartheta) are independent, then X/(X+Y)\sim{\rm Beta}(\alpha,\beta) . As (in the above notation) \absolutevalue{g_i}^{2} and \sum_{j\neq i}\absolutevalue{g_j}^{2} are independent, it follows that [ 5 ] (10) |U_{ij}|^{2}\sim\begin{cases}{\rm Beta}(1,d-1),&(\mathbb{U}(d))\\ {\rm Beta}\big(\frac{1}{2},\frac{d-1}{2}\big),&(\mathbb{O}(d))\end{cases}\ . Let us use the above formulation to calculate the distribution of the magnitude squared of the (real) dot product of the column of a Haar random unitary with itself (a quantity we will in any event be later in need of) Lemma 2 . Let a be a column of a d\times d Haar random unitary. Then \absolutevalue{a^\mst a}^{2}\sim{\rm Beta}(1,\frac{d-1}{2}) Proof. Let g=x+iy with x,y\in\mathbb{R}^{d} independent and having i.i.d. entries drawn from \mathcal{N}_{\mathbb{R}}(0,1/2) . Set a=g/\|g\| , so that a is distributed like a column of a Haar random unitary. We introduce the auxiliary quantities A=\|x\|^{2},\,B=\|y\|^{2},\,R=A+B=\|g\|^{2},\,C=x\cdot y,\,D=A/R. Then g^{\mathsf{T}}g=(x+iy)^{\mathsf{T}}(x+iy)=(A-B)+2iC, so that (11) |g^{\mathsf{T}}g|^{2}=(A-B)^{2}+4C^{2}=R^{2}-4(AB-C^{2})\quad\Longrightarrow\quad S:=|a^{\mathsf{T}}a|^{2}\,=\,1-\frac{4(AB-C^{2})}{R^{2}}, which we note en passant is 1-4\det(M)/(\tr[M]^{2}) , where M=\begin{pmatrix}A&C\\ C&B\end{pmatrix} . Let us move to spherical coordinates, writing x=r_{1}u , y=r_{2}v with r_{1},r_{2}>0 and u,v\in\mathbb{S}^{d-1} . Then (12) dx\,dy=r_{1}^{d-1}r_{2}^{d-1}\,dr_{1}\,dr_{2}\,d\omega(u)\,d\omega(v) and x,y have joint density \propto e^{-R} (independent of u,v ). Now, let z:=u\cdot v=\cos\theta . The surface element on \mathbb{S}^{d-1} is (\sin\theta)^{d-2}d\theta d\Omega , and since dz/d\theta=-\sin\theta , the marginal of z is (13) f_{Z}(z)\ \propto\ (1-z^{2})^{\frac{d-3}{2}},\qquad-12/(d+1),\,\varepsilon\leq 1/e-5/d-\tau . Set \xi=1/e-5/d-\varepsilon-\tau . Any algorithm that succeeds in \varepsilon -learning a \beta fraction of the output distributions of quantum circuits sampled uniformly from the circular orthogonal ensemble requires at least q many \tau -accurate statistical queries, with (77) q+1\geq\frac{\beta-2\exp\left[-(d-2)\xi^{2}/96\right]}{2\exp[-(d-2)(\tau-2/(d+1))^{2}/384]} From the discussion of Section 2.1 it is clear that in proving Theorem 2 there are two primary subtasks: namely, understanding the two main expressions that appear on the right hand side of Eq. ( 4 ). We begin with: Lemma 9 . (78) \Pr_{U\sim\mu_{\rm AI}}\left[\absolutevalue{{\rm d}_{\rm TV }(P_U,\mcc)-\frac{1}{e}}\geq\xi+\frac{5}{d}\right]\leq 2e^{-(d-2)\xi^{2}/96} Proof. Consider S=U^{\mathsf{T}}U , a random unitary drawn from \mu_{\rm AI} . Write the 0 th and x th columns of U as a,b\in\mathbb{C}^{d} so that (79) S_{x0}=\sum_{j=0}^{d-1}U_{jx}U_{j0}=a^{\mathsf{T}}b. We treat the diagonal x=0 and off–diagonal x\neq 0 cases separately, starting with the diagonal, in which instance we are concerned with S_{00}=a^{\mathsf{T}}a . Put T:=|a^{\mathsf{T}}a|^{2}\sim{\rm Beta}\left(1,\frac{d-1}{2}\right) , with density f_{T}(t)=\frac{d-1}{2}(1-t)^{(d-3)/2} . We then have (80) \displaystyle\expect_{T\sim{\rm Beta}\left(1,\frac{d-1}{2}\right)}|dT-1| \displaystyle=\int_{0}^{1/d}(1-dt)f_{T}(t)\,{\rm d}t+\int_{1/d}^{1}(dt-1)f_{T}(t)\,{\rm d}t (81) \displaystyle=\frac{4(d-1)}{d+1}\left(1-\frac{1}{d}\right)^{\frac{d-1}{2}}-\frac{d-1}{d+1} (82) \displaystyle\overset{d\to\infty}{\to}\frac{4}{\sqrt{e}}-1 Now we turn to the off-diagonal terms, i.e., letting x\neq 0 . We condition on a . Since (recalling Section 2.2 ) b is uniform on the (d-1) -dimensional complex unit sphere in the subspace a^{\perp} , the scalar (83) W:=a^{\mathsf{T}}b=\langle\overline{a},\,b\rangle is the projection of b onto the direction of \overline{a} within a^{\perp} . Let (84) R^{2}:=\|P_{a^{\perp}}\overline{a}\|^{2}=1-|a^{\mathsf{T}}a|^{2}=1-T. Now, as we have (essentially) seen before, for complex spherical b in dimension d-1 , the squared projection onto any fixed unit direction has a {\rm Beta}(1,d-2) law. Hence, with X\sim{\rm Beta}(1,d-2) independent of a , and defining Z:=(1-T)\,X , we want (85) \mathbb{E}_{Z}\,|dZ-1|=\mathbb{E}_{T}\left[\ \mathbb{E}_{X}\,\big|\,cX-1\,\big|\ \right] with c:=d(1-T) . We begin with the inner expectation value, over X\sim{\rm Beta}(1,d-2) . Its density is (d-2)(1-x)^{d-3} on [0,1] . Splitting the integral at x=1/c gives, for any c\geq 0 , (86) \displaystyle\expect_{X\sim{\rm Beta}(1,d-2)}|cX-1| \displaystyle=\int_{0}^{1/c}(1-cx)\,(d-2)(1-x)^{d-3}\,{\rm d}x+\int_{1/c}^{1}(cx-1)\,(d-2)(1-x)^{d-3}\,{\rm d}x (87) \displaystyle=\begin{cases}\displaystyle 1-\frac{c}{d-1},&01.\end{cases} It remains to average over T , where we recall T\sim{\rm Beta}\bigl(1,\frac{d-1}{2}\bigr) , so that Y:=1-T has density g(y)=\frac{d-1}{2}\,y^{(d-3)/2} on [0,1] and c=dY . Decomposing the average into c\leq 1 (i.e. Y\leq 1/d ) and c>1 (i.e. Y>1/d ) we conclude that for x\neq 0 (88) \displaystyle\expect_{U\sim{\mathbb{U}(d)}}\left|\,\lvert\langle x|U^{\mathsf{T}}U|0\rangle\rvert^{2}-\frac{1}{d}\right| \displaystyle=\int_{0}^{1/d}\left(1-\frac{dy}{d-1}\right)g(y)\,{\rm d}y+\int_{1/d}^{1}\left(1-\frac{dy}{d-1}+\frac{2(dy-1)}{d-1}\left(1-\frac{1}{dy}\right)^{d-2}\right)g(y)\,{\rm d}y. (89) \displaystyle=\frac{1}{d+1}+\frac{(d-1)^{d}}{d^{\frac{d+1}{2}}}\;{}_{2}F_{1}\left(d,\frac{d-1}{2},\,d+1,\,-(d-1)\right) where we have introduced the peculiarly denoted hypergeometric function {}_{2}F_{1} , defined by (90) _{2}F_{1}(a,b;c;z)=\sum_{n=0}^{\infty}\frac{(a)_{n}(b)_{n}}{(c)_{n}}\frac{z^{n}}{n!};\qquad(q)_{n}=\begin{cases}1;&n=0\\ q(q+1)\cdots(q+n-1);&n>0\end{cases} when \absolutevalue{z}<1 and by analytic continuation elsewhere. We conclude (91) \displaystyle\expect_{U\sim\mu_{\rm AI}}\,{\rm d}_{\rm TV}(P_{U},\mathcal{C}) \displaystyle=\frac{1}{2d}\left(\frac{4(d-1)}{d+1}\left(1-\frac{1}{d}\right)^{\frac{d-1}{2}}+\frac{(d-1)^{d+1}}{d^{\frac{d+1}{2}}}\;{}_{2}F_{1}\left(d,\frac{d-1}{2},\,d+1,\,-(d-1)\right)\right) (92) \displaystyle\in\left[\frac{1}{e}-\frac{5}{d},\frac{1}{e}+\frac{5}{d}\right] where the detailed calculations leading to the asymptotics in Eq. ( 92 ) may be found in Lemma 15 . Now, we would like to know the probability that a given U\sim{\rm AI} deviates from this average by a given amount. First, note that the function f:\mathbb{U}(d)\to\mathbb{R},\ f(U)={\rm d}_{\rm TV}(P_{U},\mathcal{C}) is 1-Lipschitz continuous (Lemmas 22 of Ref. [ 6 ] and 1 of Ref. [ 24 ] ), from which we conclude from Lemma 7 that, for any \xi>0 , (93) \Pr_{U\sim\mu_{\rm AI}}\left[\absolutevalue{{\rm d}_{\rm TV }(P_U,\mcc)-\frac{1}{e}}\geq\xi+\frac{5}{d}\right]\leq 2e^{-(d-2)\xi^{2}/96} ∎ Next we come to the calculation of Eq. ( 6 ); in the AI case we have Lemma 10 . (94) \mathfrak{f}_{\rm AI}\leq 2e^{-(d-2)(\tau-2/(d+1))^{2}/384} Proof. With \Phi=\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\outerproduct{\x}{\x} and \overline{\varphi}=(1/d)\tr\Phi we have: (95) \displaystyle\mathfrak{f}_{\rm AI} \displaystyle=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{V\sim\mu_{\rm AI}}\left[\left\lvert\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\lvert\langle\bm{x}|V|0\rangle\rvert^{2}-\overline{\varphi}\right\rvert>\tau\right] (96) \displaystyle=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{V\sim\mu_{\rm AI}}\left[\left\lvert\langle 0|V^{\dagger}\Phi V|0\rangle-\overline{\varphi}\right\rvert>\tau\right] Now, by Lemma 3 , (97) \expect_{V\sim\mu_{\rm AI}}V^{\dagger}\Phi V=\frac{\tr[\Phi]\mathds{1}+\Phi^{\mathsf{T}}}{d+1}, so that the average value of the quantity inside the absolute value on the right hand side of Eq. ( 96 ) is bounded as (98) -\frac{2}{d+1}\leq\expect_{V\sim\mu_{\rm AI}}\langle 0|V^{\dagger}\Phi V|0\rangle-\overline{\varphi}\leq\frac{2}{d+1} where we have recalled that |\varphi(\bm{x})|\leq 1 for all \bm{x} . It then follows from Lemmas 7 and 8 that, for \tau>2/(d+1) , (99) \mathfrak{f}_{\rm AI}\leq 2e^{-(d-2)(\tau-2/(d+1))^{2}/384} ∎ Combining the results of Lemmas 9 and 10 immediately yields Theorem 2 . 4.2. AII The goal of this subsection is to prove Theorem 3 : Theorem 3 . Let \tau>2/(d-1),\,\varepsilon\leq 1/e-5/d-\tau . Set \xi=1/e-5/d-\varepsilon-\tau . Any algorithm that succeeds in \varepsilon -learning a \beta fraction of the output distributions of quantum circuits sampled uniformly from the circular symplectic ensemble requires at least q many \tau -accurate statistical queries, with (100) q+1\geq\frac{\beta-2\exp\left[-(d-2)\xi^{2}/96\right]}{2\exp[-(d-2)(\tau-2/(d-1))^{2}/384]} As we shall see, the overall structure will be essentially identical to that of the AI case, with just some minor differences emerging in the calculations. We begin with: Lemma 11 . (101) \Pr_{U\sim\mu_{\rm AII}}\left[\absolutevalue{{\rm d}_{\rm TV }(P_U,\mcc)-\frac{1}{e}}\geq\xi+\frac{5}{d}\right]\leq 2e^{-(d-2)\xi^{2}/96} Proof. Consider S:=JU^{\mathsf{T}}JU , a random matrix sampled from \mu_{\rm AII} . Write u_{j} for the j th column of U and for each index x let x^{\prime} denote its “ J -partner”, i.e. the unique index such that e_{x}^{\mathsf{T}}J=s_{x}\,e_{x^{\prime}}^{\mathsf{T}} with s_{x}\in\{\pm 1\} . Up to an irrelevant sign, we then have (102) S_{x0}=u_{x^{\prime}}^{\mathsf{T}}Ju_{0}. We note that in the special case x=0^{\prime} the skew-symmetry of J forces S_{0^{\prime}0}=0 . Now, fix x\neq 0^{\prime} and condition on u_{0} . The remaining columns of U form a random orthonormal basis of u_{0}^{\perp} . In particular, u_{x^{\prime}} is uniform on the complex unit sphere in u_{0}^{\perp} , which has complex dimension d-1 . Importantly, \overline{Ju_{0}} is also in the subspace u_{0}^{\perp} , so that (103) \absolutevalue{S_{x0}}^{2}=\absolutevalue{u_{x'}^\mst J u_0}^{2}=\absolutevalue{\braket{u_{x'}}{\overline{J u_0}}}^{2} is the squared overlap between a fixed unit vector and a random unit vector in a (d-1) -dimensional complex vector space, which we have seen to be distributed as \mathrm{Beta}(1,\,d-2) ; as this conditional law does not depend on u_{0} , the unconditional distribution is the same, and we conclude \absolutevalue{S_{x0}}^{2}\sim\mathrm{Beta}\bigl(1,d-2) for all x\neq 0^{\prime} . So, let X\sim\mathrm{Beta}(1,d-2) , so f(x)=(d-2)(1-x)^{d-3} on [0,1] ; we have (104) \displaystyle\expect_{X\sim\mathrm{Beta}(1,d-2)}\bigl|dX-1\bigr| \displaystyle=(d-2)\int_{0}^{1/d}(1-dx)(1-x)^{d-3}\,{\rm d}x+(d-2)\int_{1/d}^{1}(dx-1)(1-x)^{d-3}\,{\rm d}x (105) \displaystyle=-\frac{1}{d-1}+2\left(1-\frac{1}{d}\right)^{d-2} So that (106) \displaystyle\expect_{S\sim\mu_{\rm AII}}\Bigl|\,d\,|\langle x|S|0\rangle|^{2}-1\,\Bigr| \displaystyle=\begin{cases}1,&x=0^{\prime}\\ \displaystyle 2\left(1-\frac{1}{d}\right)^{d-2}-\frac{1}{d-1},&x\neq 0^{\prime}\end{cases} (107) \displaystyle\overset{d\to\infty}{\to}\begin{cases}1,&x=0^{\prime}\\ 2/e,&x\neq 0^{\prime}\end{cases} We conclude (108) \displaystyle\expect_{U\sim\mu_{\rm AII}}\,{\rm d}_{\rm TV}(P_{U},\mathcal{C}) \displaystyle=\frac{1}{2d}\left(1+(d-1)\left(2\left(1-\frac{1}{d}\right)^{d-2}-\frac{1}{d-1}\right)\right) (109) \displaystyle=\left(1-\frac{1}{d}\right)^{d-1} (110) \displaystyle\in\left[\frac{1}{e}-\frac{5}{d},\frac{1}{e}+\frac{5}{d}\right] where the (elementary) details of the final bound are given in the proof of Lemma 16 . By identical reasoning to that employed in the proof of Lemma 9 , we conclude that (111) \Pr_{U\sim\mu_{\rm AII}}\left[\absolutevalue{{\rm d}_{\rm TV }(P_U,\mcc)-\frac{1}{e}}\geq\xi+\frac{5}{d}\right]\leq 2e^{-(d-2)\xi^{2}/96} ∎ Next we have the calculation of Eq. ( 6 ); in the AII case we find Lemma 12 . (112) \mathfrak{f}_{\rm AII}\leq 2e^{-(d-2)(\tau-2/(d-1))^{2}/384} Proof. With \Phi=\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\outerproduct{\x}{\x} and \overline{\varphi}=(1/d)\tr\Phi we have: (113) \displaystyle\mathfrak{f}_{\rm AII} \displaystyle=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{V\sim\mu_{\rm AII}}\left[\left\lvert\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\lvert\langle\bm{x}|V|0\rangle\rvert^{2}-\overline{\varphi}\right\rvert>\tau\right] (114) \displaystyle=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{V\sim\mu_{\rm AII}}\left[\left\lvert\langle 0|V^{\dagger}\Phi V|0\rangle-\overline{\varphi}\right\rvert>\tau\right] Now, by Lemma 4 , (115) \expect_{V\sim\mu_{\rm AII}}V^{\dagger}\Phi V=\frac{\tr[\Phi]\mathds{1}+J\Phi^{\mathsf{T}}J}{d-1}, so that the average value of the quantity inside the absolute value on the right hand side of Eq. ( 114 ) is bounded as (116) -\frac{2}{d-1}\leq\expect_{V\sim\mu_{\rm AII}}\langle 0|V^{\dagger}\Phi V|0\rangle-\overline{\varphi}\leq\frac{2}{d-1} where we have recalled that |\varphi(\bm{x})|\leq 1 for all \bm{x} . It then follows from Lemmas 7 and 8 that, for \tau>2/(d-1) , (117) \mathfrak{f}_{\rm AII}\leq 2e^{-(d-2)(\tau-2/(d-1))^{2}/384} ∎ Combining the results of Lemmas 11 and 12 immediately yields Theorem 3 . 4.3. DIII The goal of this subsection is to prove Theorem 4 : Theorem 4 . Let \tau>2/(d-1),\,\varepsilon\leq\sqrt{2/(\pi e)}-10/d-\tau . Set \xi=\sqrt{2/(\pi e)}-10/d-\varepsilon-\tau . Any algorithm that succeeds in \varepsilon -learning a \beta fraction of the output distributions of quantum circuits sampled uniformly from \mu_{\rm DIII} requires at least q many \tau -accurate statistical queries, with (118) q+1\geq\frac{\beta-2\exp\left[-(d-2)\xi^{2}/96\right]}{2\exp[-(d-2)(\tau-2/(d-1))^{2}/384]} The overall structure will be essentially identical to that of the AI and AII cases, with just some minor differences emerging in the calculations. We begin with: Lemma 13 . (119) \Pr_{U\sim\mu_{\rm DIII}}\left[\absolutevalue{{\rm d}_{\rm TV}(P_U,\mcc)-\sqrt\frac{2}{\pi e}}\geq\xi+\frac{10}{d}\right]\leq 2e^{-(d-2)\xi^{2}/96}. Proof. Consider S=JV^{\mathsf{T}}JV , a random matrix from \mu_{\rm DIII} . We denote the columns of V\sim\mu_{\mathbb{O}(d)} by v_{0},\dots,v_{d-1} and recall that for each index x there is a partner x^{\prime} with Je_{x}=\pm e_{x^{\prime}} ; we then have (up to an irrelevant sign) (120) S_{x0}=v_{x^{\prime}}^{\mathsf{T}}Jv_{0}. Note that by skew-symmetry S_{0^{\prime}0}=0 . If x\neq 0^{\prime} , then (conditioning on v_{0} ) the column v_{x^{\prime}} is uniform on the real unit sphere in v_{0}^{\perp}\cong\mathbb{R}^{d-1} . Because J is orthogonal and v_{0}^{\mathsf{T}}Jv_{0}=0 , we have Jv_{0}\in v_{0}^{\perp} and \|Jv_{0}\|=1 , so v_{x^{\prime}}^{\mathsf{T}}Jv_{0} is the first coordinate of a uniform vector on S^{d-2} in \mathbb{R}^{d-1} , whence \absolutevalue{S_{x0}}^{2}\sim\mathrm{Beta}\Bigl(\frac{1}{2},\frac{d-2}{2}\Bigr) for (x\neq 0^{\prime}) . Now, with X\sim\mathrm{Beta}(\frac{1}{2},\frac{d-2}{2}) and B_{z}(a,b)=\int_{0}^{z}u^{a-1}(1-u)^{b-1}{\rm d}u the incomplete Beta function , symbolic integration yields (121) \displaystyle\expect_{X\sim\mathrm{Beta}(\frac{1}{2},\frac{d-2}{2})}\bigl|dX-1\bigr| \displaystyle=\int_{0}^{1/d}(1-dx)\left(\frac{x^{-1/2}(1-x)^{\frac{d-4}{2}}}{B\left(\frac{1}{2},\frac{d-2}{2}\right)}\right){\rm d}x+\int_{1/d}^{1}(dx-1)\left(\frac{x^{-1/2}(1-x)^{\frac{d-4}{2}}}{B\left(\frac{1}{2},\frac{d-2}{2}\right)}\right){\rm d}x (122) \displaystyle=-\frac{1}{d-1}+\frac{2}{B(\frac{d-2}{2},\frac{1}{2})}\left(\frac{2}{\sqrt{d}}\left(1-\frac{1}{d}\right)^{\frac{d-2}{2}}+B_{1-1/d}\left(\frac{d-2}{2},\frac{3}{2}\right)\right) so that (123) \displaystyle\expect_{U\sim\mu_{\rm DIII}}\,{\rm d}_{\rm TV}(P_{U},\mathcal{C}) \displaystyle=\frac{1}{2d}\left(1+(d-1)\left(-\frac{1}{d-1}+\frac{2}{B(\frac{d-2}{2},\frac{1}{2})}\left(\frac{2}{\sqrt{d}}\left(1-\frac{1}{d}\right)^{\frac{d-2}{2}}+B_{1-1/d}\left(\frac{d-2}{2},\frac{3}{2}\right)\right)\right)\right) (124) \displaystyle=\frac{(d-1)}{dB(\frac{d-2}{2},\frac{1}{2})}\left(\frac{2}{\sqrt{d}}\left(1-\frac{1}{d}\right)^{\frac{d-2}{2}}+B_{1-1/d}\left(\frac{d-2}{2},\frac{3}{2}\right)\right) (125) \displaystyle\in\left[\sqrt{\frac{2}{\pi e}}-\frac{10}{d},\sqrt{\frac{2}{\pi e}}+\frac{5}{d}\right] where the detailed justification of the final line comes in Lemma 17 . We conclude that (126) \Pr_{U\sim\mu_{\rm DIII}}\left[\absolutevalue{{\rm d}_{\rm TV}(P_U,\mcc)-\sqrt\frac{2}{\pi e}}\geq\xi+\frac{10}{d}\right]\leq 2e^{-(d-2)\xi^{2}/96}. ∎ Next we have the calculation of Eq. ( 6 ); in the DIII case we find Lemma 14 . (127) \mathfrak{f}_{\rm DIII}\leq 2e^{-(d-2)(\tau-2/(d-1))^{2}/384} Proof. With \Phi=\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\outerproduct{\x}{\x} and \overline{\varphi}=(1/d)\tr\Phi we have: (128) \displaystyle\mathfrak{f}_{\rm DIII} \displaystyle=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{V\sim\mu_{\rm DIII}}\left[\left\lvert\sum_{\bm{x}\in\{0,1\}^{n}}\varphi(\bm{x})\lvert\langle\bm{x}|V|0\rangle\rvert^{2}-\overline{\varphi}\right\rvert>\tau\right] (129) \displaystyle=\max_{\varphi\,:\,\{0,1\}^{n}\to[-1,1]}\Pr_{V\sim\mu_{\rm DIII}}\left[\left\lvert\langle 0|V^{\dagger}\Phi V|0\rangle-\overline{\varphi}\right\rvert>\tau\right] Now, by Lemma 5 , (130) \expect_{V\sim\mu_{\rm DIII}}V^{\dagger}\Phi V=\frac{\tr[\Phi]\mathds{1}+J\Phi^{\mathsf{T}}J}{d-1}, so that the average value of the quantity inside the absolute value on the right hand side of Eq. ( 129 ) is bounded as (131) -\frac{2}{d-1}\leq\expect_{V\sim\mu_{\rm DIII}}\langle 0|V^{\dagger}\Phi V|0\rangle-\overline{\varphi}\leq\frac{2}{d-1} where we have recalled that |\varphi(\bm{x})|\leq 1 for all \bm{x} . It then follows from Lemmas 7 and 8 that, for \tau>2/(d-1) , (132) \mathfrak{f}_{\rm DIII}\leq 2e^{-(d-2)(\tau-2/(d-1))^{2}/384} ∎ Combining the results of Lemmas 13 and 14 immediately yields Theorem 4 ; combining Theorems 2 , 3 and 4 yields Theorem 1 . 5. Discussion In this work we have continued the recent trend [ 6 , 27 , 24 ] of establishing the hardness of learning within the statistical query model Born distributions of states resulting from various natural unitary ensembles. As in those works, we have found learning our target ensembles to be intractable, further highlighting the difficulty of the general problem. Similarly to Refs. [ 6 , 24 ] we have primarily relied upon a concentration of measure argument stemming from Levy’s Lemma, albeit combined with a slightly atypical approach to carrying out the corresponding integrations; in particular, our conclusions have turned out to be reasonably insensitive the differences between our considered ensembles. We note that although the conclusions of Refs. [ 6 , 27 , 24 ] all mirror closely those of this work, the techniques employed in Ref. [ 27 ] to establish the difficulty of learning free-fermionic (matchgate) distributions are very different from those employed in the other three papers. Indeed, their proof proceeds by a reduction to a parity-learning problem which is known to be hard. To see the correspondence between the matchgate case and our DIII analysis, we recall that a pure d -mode fermionic Gaussian state may be equivalently parametrised as V=O^{\mathsf{T}}JO , where O\in\mathbb{SO}(2d) and J is a (reference) complex structure [ 28 ] , or as a matchgate circuit acting on a reference state \ket{0} . In either case there is a redundancy of description given by a stabiliser subgroup isomorphic to \mathbb{U}(n) ; for example in the former case any V^{\prime} related to V by the transformation O\mapsto O^{\prime}O , where O^{\prime} is an orthogonal matrix which commutes with J , evidently leaves the Gaussian state unchanged. As (up to the unimportant linear action of another factor of J ), O^{\mathsf{T}}JO was exactly the quantity we considered in our DIII analysis, we see therefore the correspondence with the learning free fermionic states problem of Ref. [ 27 ] ; our result is then an (average-case) analogue of their result which relies only on carrying out conceptually straightforward (if admittedly somewhat tedious) calculations. 6.