For a random set S⊂U(d) of quantum gates we provide bounds on the probability that S forms a δ -approximate t -design. In particular we have found that for S drawn from an exact t -design the probability that it forms a δ -approximate t -design satisfies the inequality P(δ≥x)≤2Dte−|S|xarctanh(x)(1−x2)|S|/2=O(2Dt(e−x21−x2)|S|) , where Dt is a sum over dimensions of unique irreducible representations appearing in the decomposition of U↦U⊗t⊗U¯⊗t . We use our results to show that to obtain a δ -approximate t -design with probability P one needs O(δ−2(tlog(d)−log(1−P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S . Our results are valid for both symmetric and non-symmetric sets of gates.
For a random set S⊂U(d) of quantum gates we provide bounds on the probability that S forms a δ -approximate t -design. In particular we have found that for S drawn from an exact t -design the probability that it forms a δ -approximate t -design satisfies the inequality P(δ≥x)≤2Dte−|S|xarctanh(x)(1−x2)|S|/2=O(2Dt(e−x21−x2)|S|) , where Dt is a sum over dimensions of unique irreducible representations appearing in the decomposition of U↦U⊗t⊗U¯⊗t . We use our results to show that to obtain a δ -approximate t -design with probability P one needs O(δ−2(tlog(d)−log(1−P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S . Our results are valid for both symmetric and non-symmetric sets of gates.
For a Haar random set S⊂U(d) of quantum gates we consider the uniform measure νS whose support is given by S. The measure νS can be regarded as a δ(νS,t)-approximate t-design, t∈Z+. We propose a random matrix model that aims to describe the probability distribution of δ(νS,t) for any t. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by t. We prove that, the operator norm of this matrix, δ(t), is the random variable to which ∣S∣δ(νS,t) converges in distribution when the number of elements in S grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities P(δ(t)>2+ε), for any ε>0. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 1 there is t∈Z+ such that supk∈Z+δ(k)=δ(t). Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of S. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities P(Sδ(νS,t)>2+ε) are bounded from above by the tail probabilities P(δ(t)>2+ε) of our random matrix model. In particular our conjecture implies that a Haar random set S⊂U(d) satisfies the spectral gap conjecture with the probability 1.
For a Haar random setS⊂U(d)of quantum gates we consider the uniform measureνSwhose support is given byS. The measureνScan be regarded as aδ(νS,t)-approximatet-design,t∈Z+. We propose a random matrix model that aims to describe the probability distribution ofδ(νS,t)for anyt. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined byt. We prove that, the operator norm of this matrix,δ(t), is the random variable to which∣S∣δ(νS,t)converges in distribution when the number of elements inSgrows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilitiesP(δ(t)>2+ϵ), for anyϵ>0. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 1 there ist∈Z+such thatsupk∈Z+δ(k)=δ(t). Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality ofS. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilitiesP(Sδ(νS,t)>2+ϵ)are bounded from above by the tail probabilitiesP(δ(t)>2+ϵ)of our random matrix model. In particular our conjecture implies that a Haar random setS⊂U(d)satisfies the spectral gap conjecture with the probability 1.
Epsilon-nets and approximate unitaryt-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, forddimensional Hilbert space, unitaries constituting$\delta −approximatet−expandersform\epsilon −netsfort\simeq \frac {d^{5/2}}{ \epsilon }and\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}.Wealsoshowthatforarbitraryt,\epsilon −netscanbeusedtoconstruct\delta −approximateunitaryt−designsfor\delta \simeq \epsilon t,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitarytdesignnecessarytoobtainan\epsilon −netmustgrowatleastasfastas\frac {1}{ \epsilon }(forfixeddimension)andnotslowerthand^{2}(forfixed\epsilon ).Thisshowsnearoptimalityofourresultconnectingt−designsand\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.
We establish a relationship between the notion of universal quantum gates and the notion of unitary t-designs. We show that a set of qudit gates $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if S forms a $\ensuremath{\delta}$-approximate t(d)-design, where $\ensuremath{\delta}<1, t(2)=6$, and t(d)=4 for $d\ensuremath{\ge}3$. Moreover, we argue that from the application point of view sets S with the $\ensuremath{\delta}$ close to 1 should be regarded as nonuniversal. We also provide a second, more algebraic, criterion for the universality verification. It says that $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if the matrices that commute with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}\mathcal{S}}$ commute also with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}U(d)}$, where t(2)=3, and t(d)=2 for $d\ensuremath{\ge}3$. Finally, we show that the complexity of checking this algebraic criterion scales polynomially with the dimension d.
In this work, we study distributions of unitaries generated by random quantum circuits containing only symmetry-respecting gates. We develop a unified approach applicable to all symmetry groups and obtain an equation that determines the exact design properties of such distributions. It has been recently shown that the locality of gates imposes various constraints on realizable unitaries, which in general, significantly depend on the symmetry under consideration. These constraints typically include restrictions on the relative phases between sectors with inequivalent irreducible representations of the symmetry. We call a set of symmetric gates semi-universal if they realize all unitaries that respect the symmetry, up to such restrictions. For instance, while 2-qubit gates are semi-universal for Z2, U(1), and SU(2) symmetries in qubit systems, SU(d) symmetry with d≥3 requires 3-qudit gates for semi-universality. Failure of semi-universality precludes the distribution generated by the random circuits from being even a 2-design for the Haar distribution over symmetry-respecting unitaries. On the other hand, when semi-universality holds, under mild conditions, satisfied by U(1) and SU(2) for example, the distribution becomes a t-design for t growing polynomially with the number of qudits, where the degree is determined by the locality of gates. More generally, we present a simple linear equation that determines the maximum integer tmax for which the uniform distribution of unitaries generated by the circuits is a t-design for all t≤tmax. Notably, for U(1), SU(2) and cyclic groups, we determine the exact value of tmax as a function of the number of qubits and locality of the gates, and for SU(d), we determine the exact value of tmax for up to 4-qudit gates.
Unitary T-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. Until now, the most efficient construction of unitary T-designs for n-qudit systems has been via random local quantum circuits, which have been shown to converge to approximate T-designs in the diamond norm using O(T5+o(1)n2) quantum gates. In this work, we provide a new construction of T-designs via random matrix theory using O~(T2n2) quantum gates. Our construction leverages two key ideas. First, in the spirit of central limit theorems, we approximate the Gaussian Unitary Ensemble (GUE) by an i.i.d. sum of random Hermitian matrices. Second, we show that the product of just two exponentiated GUE matrices is already approximately Haar random. Thus, multiplying two exponentiated sums over rather simple random matrices yields a unitary T-design, via Hamiltonian simulation. A central feature of our proof is a new connection between the polynomial method in quantum query complexity and the large-dimension (N) expansion in random matrix theory. In particular, we show that the polynomial method provides exponentially improved bounds on the high moments of certain random matrix ensembles, without requiring intricate Weingarten calculations. In doing so, we define and solve a new type of moment problem on the unit circle, asking whether a finite number of equally weighted points, corresponding to eigenvalues of unitary matrices, can reproduce a given set of moments.