Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group $G$ possessing an invariant state $G^{\otimes k} \lvertΨ\rangle= \lvertΨ\rangle$ , a lower bound on the diamond distance between the $k$ \textsuperscript{th} moment operator of any ensemble of elements of $G$ , and that of the Haar measure over $G$ . We then use this bound to prove that for many groups of interest, no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$ -design over $G$ . More generally, on a $D$ -dimensional lattice, our results imply that such group designs require depths scaling at least as $n^{1/D}$ . Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$ -designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth $8$ -designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over $G$ using any circuit comprised of a sublinear number of gates generated by Pauli strings.Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group $G$ possessing an invariant state $G^{\otimes k} \lvertΨ\rangle= \lvertΨ\rangle$, a lower bound on the diamond distance between the $k$\textsuperscript{th} moment operator of any ensemble of elements of $G$, and that of the Haar measure over $G$. We then use this bound to prove that for many groups of interest, no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$-design over $G$. More generally, on a $D$-dimensional lattice, our results imply that such group designs require depths scaling at least as $n^{1/D}$. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth $8$-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over $G$ using any circuit comprised of a sublinear number of gates generated by Pauli strings.

arXiv:2506.16005Jun 19, 20251 citation

The Complexity of Approximate Counting (Preliminary Version)

Larry J. Stockmeyer

Jan 1, 198312 citations

Quantum Circuits with Unbounded Fan-out

Peter Høyer, Robert Špalek

We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by $\mathrm{QNC}_{\mathrm{f}}^0$ ) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by $\mathrm{QNC}_{\mathrm{f}}^0$) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.

arXiv:quant-ph/0208043Theory of ComputingJan 1, 200590 citations

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$ -qubit Pauli operator $P$ and an angle $θ\in [0,2π)$ , both uniformly at random, and apply $e^{\mathrm i θP}$ . (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ (including central phases of the parent group) independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$ . Importantly, the gap bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary $t$ -designs after $\mathcal{O}(nt)$ steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be $\mathcal{O}(2^{cn})$ for some $c < 1$ . Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal $t$ -designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for $t=2$ .We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$-qubit Pauli operator $P$ and an angle $θ\in [0,2π)$, both uniformly at random, and apply $e^{\mathrm i θP}$. (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ (including central phases of the parent group) independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the gap bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary $t$-designs after $\mathcal{O}(nt)$ steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be $\mathcal{O}(2^{cn})$ for some $c < 1$. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal $t$-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for $t=2$.

quant-pharXiv:2607.20919Jul 24, 20260 citations

G

possessing an invariant state

G^{\otimes k} \lvertΨ\rangle= \lvertΨ\rangle

, a lower bound on the diamond distance between the

k

\textsuperscript{th} moment operator of any ensemble of elements of

G

, and that of the Haar measure over

G

. We then use this bound to prove that for many groups of interest, no subset of

G

consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate

k

-design over

G

. More generally, on a

D

-dimensional lattice, our results imply that such group designs require depths scaling at least as

n^{1/D}

. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from

k

-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth

8

-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over

G

using any circuit comprised of a sublinear number of gates generated by Pauli strings.

We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by

\mathrm{QNC}_{\mathrm{f}}^0

) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups

\mathsf{SU}(2^n)

n

qubits. (i) Random Pauli Rotation: choose an

n

-qubit Pauli operator

P

and an angle

θ\in [0,2π)

, both uniformly at random, and apply

e^{\mathrm i θP}

. (ii) Brickwork Random Unitary Circuit: choose

n-1

unitaries

U_{i}

uniformly at random from

\mathsf{SU}(4)

(including central phases of the parent group) independently, and apply

U_{2j-1}

on two qubits

2j-1, 2j

and then

U_{2j}

on two qubits

2j, 2j+1

. Importantly, the gap bounds are independent of

n

and apply for all finite dimensional unitary representations of

\mathsf{SU}(2^n)

uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary

t

-designs after

\mathcal{O}(nt)

steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be

\mathcal{O}(2^{cn})

for some

c < 1

. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal

t

-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for

t=2