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
QNCf0) 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
SU(2n) on
n qubits. (i) Random Pauli Rotation: choose an
n-qubit Pauli operator
P and an angle
θ∈[0,2π), both uniformly at random, and apply
eiθP. (ii) Brickwork Random Unitary Circuit: choose
n−1 unitaries
Ui uniformly at random from
SU(4) (including central phases of the parent group) independently, and apply
U2j−1 on two qubits
2j−1,2j and then
U2j on two qubits
2j,2j+1. Importantly, the gap bounds are independent of
n and apply for all finite dimensional unitary representations of
SU(2n) uniformly.
Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary
t-designs after
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
O(2cn) 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.
Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth
ω(p−1logn), and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on
n qubits, initialized in an arbitrary product state, with nearest-neighbor gates in
O(1) spatial dimensions and interspersed depolarizing noise of any constant strength
p. Our first result is that when the depth exceeds a threshold
d∗=Θ(p−1logn), the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its
n-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth
Θ~(p−1): after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds
Θ~(p−1).