On the Computational Power of Geometrically Local QAC circuits

Abstract

The computational power of $\mathsf{QAC}$, which are constant-depth quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local $\mathsf{QAC}$ circuits, where the qubits are arranged in a high-dimensional grid, and all the generalized Toffoli gates act on contiguous qubits along one direction. We prove that $2D\text{-}\mathsf{QAC}$ circuits are universal: any $\mathsf{QAC}$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}$ circuit. Therefore, we focus on the computational power of $2D\text{-}\mathsf{QAC}$ circuits with grid width $w$. We prove that $\mathsf{PARITY}$ computation has a tight width--depth tradeoff of $w=n^{\Theta (1/d)}$ in the constant-depth regime if the circuit allows arbitrary ancilla. Moreover, for polynomial-size circuits, a width lower bound of $n^{\omega (1/d)}$ for $\mathsf{PARITY}$ would imply $\mathsf{PARITY}\notin {\mathsf{QAC}}^0$. We also establish Fourier tail and sensitivity bounds, together with tight width lower bounds and tight depth lower bounds in $1D\text{-}\mathsf{QAC}$ circuits for $\mathsf{MAJORITY}$ and $\mathsf{MOD}$ computation. Our main tool is \emph{local measurement variance}, the maximum variance of normalized sums of observables on separated regions. We use a hybrid argument to show that each layer of a ${2D\text{-}\mathsf{QAC}}^0$ circuit increases this variance by at most a factor depending only on its width, yielding a variance bound for every ${2D\text{-}\mathsf{QAC}}^0$ state. The high local measurement variance of cat and Dicke states then gives the width lower bounds.