Curator's Take
This article tackles a fundamental question about quantum circuit complexity that directly impacts how we design quantum algorithms for real hardware with geometric constraints. The researchers prove that imposing 2D nearest-neighbor connectivity restrictions on quantum circuits doesn't fundamentally limit their computational power, though it requires quadratically more gates - a crucial finding for understanding the tradeoffs between theoretical quantum algorithms and their implementation on actual quantum chips with limited qubit connectivity. Perhaps most intriguingly, their results on 1D quantum circuits reveal stark limitations, showing that extremely constrained geometries can dramatically increase the circuit depth needed for basic computations like parity, which has important implications for quantum algorithms designed for linear qubit arrays or quantum processors with severe connectivity limitations. This work provides essential theoretical foundations for understanding how the physical layout of qubits affects computational complexity, helping bridge the gap between abstract quantum algorithm design and practical quantum computer architectures.
— Mark Eatherly
Summary
The computational complexity of $\mathsf{QAC}^0$, which are constant-depth, polynomial-size 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}^0$ circuits, where all the generalized Toffoli gates act on nearest neighbor qubits. We show that any $\mathsf{QAC}^0$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}^0$ circuit, i.e., a $\mathsf{2D\text{-}QAC}^{0}$ circuit, with a quadratic size blow-up. This implies that $\mathsf{QAC}^0 = \mathsf{2D\text{-}QAC}^{0}$. We further show that if there existed a $\mathsf{QAC}^0$ circuit that computes Parity with a bounded constant error, then for any $\varepsilon > 0$, there would exist a $\mathsf{2D\text{-}QAC}^{0}$ circuit that exactly computes Parity, with a very "thin" width $n^\varepsilon$. We further study the computational power of $\mathsf{1D\text{-}QAC}^{0} $ circuits, i.e., one-dimensional $\mathsf{QAC}^0$ circuits, which are the "thinnest" $\mathsf{2D\text{-}QAC}^{0}$ circuits. We prove a nearly logarithmic depth lower bound on $\mathsf{1D\text{-}QAC}^{0} $ circuits to compute the Parity function, even if allowing an unlimited number of ancilla. Furthermore, if the inputs are encoded in contiguous qubits, we prove that it requires a nearly linear depth $\mathsf{1D\text{-}QAC}^{0} $ circuit to compute the Parity function. This lower bound is almost tight. The results are proved via the combination of the restriction argument and the light-cone argument. These results may provide a new angle for studying the computational power of $\mathsf{QAC}^0$ circuits and for resolving the long-standing open problem of whether Parity is in $\mathsf{QAC}^0$.