Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
Abstract
Simulating fermionic systems on qubit hardware involves many nonlocal interactions, and efficient routing of these interactions is critical to the overall cost of fermionic simulation algorithms. Recent works reduce this routing overhead to polylogarithmic depth under all-to-all connectivity, but degrade to O(√Nlog N) for N fermionic modes on 2D nearest-neighbor architectures. We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal O(√N) depth with O(N√N) nearest-neighbor gates and no ancilla qubits, measurements, or classical feedforward. For N=L2 modes, the CNOT depth is at most 10L+12. This matches the Ω(√N) lower bound, which holds even when O(N) ancillas and classical feedforward are permitted. We further construct an O(√N)-depth transformation between the Jordan--Wigner, Bravyi--Kitaev, and Parity encodings on the 2D grid via a Hilbert-curve layout, extending our result to all three encodings. Benchmarks on a standalone fermionic permutation circuit, the fermionic fast Fourier transform, and Trotter simulation of a sparse SYK model demonstrate that the practical crossover is near the analytical depth-bound breakeven at L=6 (N=36), followed by consistent reductions in circuit depth and spacetime volume and higher estimated no-fault probability in the early fault-tolerant regime, growing with system size.
Related
- Asymptotically Optimal Mixed-State Cloning
- Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians
- Entangled measurements are necessary for optimal tomography of mixed fermionic Gaussian states and of bosonic Gaussian states near the vacuum
- Optimal testing of fermionic and bosonic Gaussian states
- Certifying fermionic Gaussian states (and a little more) with optimal precision dependence
BibTeX
@misc{li2026asymptotically,
title = {{Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas}},
author = {Dantong Li and Shifan Xu and Yongshan Ding},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.26041},
eprint = {2605.26041},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.26041},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
AU - Dantong Li
AU - Shifan Xu
AU - Yongshan Ding
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2605.26041
UR - https://arxiv.org/abs/2605.26041
AB - Simulating fermionic systems on qubit hardware involves many nonlocal interactions, and efficient routing of these interactions is critical to the overall cost of fermionic simulation algorithms. Recent works reduce this routing overhead to polylogarithmic depth under all-to-all connectivity, but degrade to O(√Nlog N) for N fermionic modes on 2D nearest-neighbor architectures. We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal O(√N) depth with O(N√N) nearest-neighbor gates and no ancilla qubits, measurements, or classical feedforward. For N=L^2 modes, the CNOT depth is at most 10L+12. This matches the Ω(√N) lower bound, which holds even when O(N) ancillas and classical feedforward are permitted. We further construct an O(√N)-depth transformation between the Jordan--Wigner, Bravyi--Kitaev, and Parity encodings on the 2D grid via a Hilbert-curve layout, extending our result to all three encodings. Benchmarks on a standalone fermionic permutation circuit, the fermionic fast Fourier transform, and Trotter simulation of a sparse SYK model demonstrate that the practical crossover is near the analytical depth-bound breakeven at L=6 (N=36), followed by consistent reductions in circuit depth and spacetime volume and higher estimated no-fault probability in the early fault-tolerant regime, growing with system size.
ER -