On the Computational Complexity of Geometrically Local QAC0 circuits
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911576609521664 |
|---|---|
| author | Dong, Yangjing Ou, Fengning Yao, Penghui |
| author_facet | Dong, Yangjing Ou, Fengning Yao, Penghui |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07178 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Computational Complexity of Geometrically Local QAC0 circuits Dong, Yangjing Ou, Fengning Yao, Penghui Quantum Physics 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$. |
| title | On the Computational Complexity of Geometrically Local QAC0 circuits |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.07178 |