Complexity 1

Abstract: Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using $\Theta(\log \log n)$-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of \emph{constant-time} quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class $\mathsf{QAC^0}$. Finally, our results suggest a new approach towards proving that PARITY is not computable in $\mathsf{QAC^0}$, a long-standing question in quantum complexity theory.

Abstract: Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between BQP and BPP. We build on a powerful technique to differentiate quantum and classical algorithms called the level-$\ell$ Fourier growth (the sum of absolute values of Fourier coefficients of sets of size $\ell$) and show that it can also be used to differentiate quantum algorithms based on the types of resources used. We show that noise acting on a quantum algorithm dampens its Fourier growth in ways intricately linked to the type of noise. Concretely, we study noisy models of quantum computation where highly mixed states are prevalent, namely: DQC_k algorithms, where k qubits are clean and the rest are maximally mixed, and 1/2-BQP algorithms, where the initial state is maximally mixed, but the algorithm is given knowledge of the initial state at the end of the computation. We establish upper bounds on the Fourier growth of DQC_k, 1/2-BQP and BQP algorithms and leverage the differences between these bounds to derive oracle separations between these models. In particular, we show that the 2-Forrelation and 3-Forrelation problems require $N^{\Omega(1)}$ queries in the DQC_1 and 1/2-BQP models respectively. Our results are proved using a new matrix decomposition lemma that might be of independent interest.

Abstract: All-to-all interactions arise naturally in many areas of theoretical physics and across diverse experimental quantum platforms, motivating a systematic study of their information-processing power. Assuming each pair of qubits interacts with $\mathcal{O}(1)$ strength, time-dependent all-to-all Hamiltonians can simulate arbitrary all-to-all quantum circuits, performing quantum computation in time proportional to the circuit depth. In this work, we show that this naive correspondence is far from optimal: all-to-all Hamiltonians can process information on much faster timescales. Our first main result establishes that any two-qubit gate can be simulated by all-to-all Hamiltonians on $N$ qubits in time $\mathrm{O}(1/N)$ (up to factor $N^{\delta}$ with an arbitrarily small constant $\delta>0$), with polynomially small error $1/\mathrm{poly}(N)$. Immediate consequences include: 1) Certain $\mathrm{O}(N)$-qubit unitaries, such as the multiply-controlled Toffoli gate, can be realized in $\mathrm{O}(1/N)$ time. 2) Globally entangled states such as the GHZ and W states of $\mathrm{O}(N)$ qubits can be prepared in $\mathrm{O}(1/N)$ time. 3) Any depth-$D$ circuit on $N_{\rm d}$ qubits can be simulated in arbitrarily short time $T=\mathrm{O}(DN_{\rm d}/N)$, inversely proportional to the space overhead $N/N_{\rm d}$. 4) The existing Lieb-Robinson bound for strong power-law interactions $H_{ij}\sim r_{ij}^{-\gamma}$ in spatial dimension $\mathsf{d}>\gamma$ is tight, requiring time $T=\Omega(N^{\frac{\gamma}{\mathsf{d}}-1})$ for information to propagate. Our second main result shows that any depth-$D$ quantum circuit can be simulated in time $T=\mathrm{O}(D/\sqrt{N})$ with constant space overhead, with error $1/\mathrm{poly}(N)$ for almost all inputs. This “optimistic” simulation may suffice for practical purposes: for instance, building on prior work, we demonstrate that Shor’s factoring algorithm can be implemented by $\mathrm{O}(\sqrt{N})$-time Hamiltonian evolution with constant space overhead. The techniques underlying our results depart fundamentally from the existing literature on parallelizing commuting gates: We rely crucially on non-commuting Hamiltonians and draw on diverse ideas from semiclassical quantum mechanics, (spin) squeezing, Mølmer–Sørensen gates, and spin-wave physics.