Low-depth fermion routing without ancillas
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917047427923968 |
|---|---|
| author | Constantinides, Nathan Yu, Jeffery Devulapalli, Dhruv Fahimniya, Ali Schaeffer, Luke Childs, Andrew M. Gullans, Michael J. Schuckert, Alexander Gorshkov, Alexey V. |
| author_facet | Constantinides, Nathan Yu, Jeffery Devulapalli, Dhruv Fahimniya, Ali Schaeffer, Luke Childs, Andrew M. Gullans, Michael J. Schuckert, Alexander Gorshkov, Alexey V. |
| contents | Routing is the task of permuting qubits in such a way that quantum operations can be parallelized maximally, given constraints on the hardware geometry. When simulating fermions in the Jordan-Wigner encoding with qubits, a one-dimensional nearest-neighbor-connected geometry is effectively imposed on the system, independently of the underlying hardware, which means that naively, an $O(N)$ depth routing overhead is incurred. Recently, Maskara et al. [arXiv:2509.08898] demonstrated that this routing overhead can be reduced to $O(\log N)$ by decomposing general fermion routing into $O(\log N)$ interleave permutations of depth $O(1)$, using $Θ(N)$ ancillary qubits and employing measurements and feedforward. Here, we exhibit an alternative construction that achieves the same asymptotic performance. We also generalize the result in two ways. Firstly, we show that fermion routing can be performed in depth $O(\log^2 N)$ \emph{without} ancillas, measurements, or feedforward. Secondly, we construct efficient mappings with $O(\log^2 N)$ depth between all product-preserving ternary tree fermionic encodings, thereby showing that fermion routing in any such encoding can be done efficiently. While these results assume all-to-all connectivity, they also imply upper bounds for fermion routing in devices with limited connectivity by multiplying the fermion routing depth by the worst-case qubit routing depth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05099 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Low-depth fermion routing without ancillas Constantinides, Nathan Yu, Jeffery Devulapalli, Dhruv Fahimniya, Ali Schaeffer, Luke Childs, Andrew M. Gullans, Michael J. Schuckert, Alexander Gorshkov, Alexey V. Quantum Physics Routing is the task of permuting qubits in such a way that quantum operations can be parallelized maximally, given constraints on the hardware geometry. When simulating fermions in the Jordan-Wigner encoding with qubits, a one-dimensional nearest-neighbor-connected geometry is effectively imposed on the system, independently of the underlying hardware, which means that naively, an $O(N)$ depth routing overhead is incurred. Recently, Maskara et al. [arXiv:2509.08898] demonstrated that this routing overhead can be reduced to $O(\log N)$ by decomposing general fermion routing into $O(\log N)$ interleave permutations of depth $O(1)$, using $Θ(N)$ ancillary qubits and employing measurements and feedforward. Here, we exhibit an alternative construction that achieves the same asymptotic performance. We also generalize the result in two ways. Firstly, we show that fermion routing can be performed in depth $O(\log^2 N)$ \emph{without} ancillas, measurements, or feedforward. Secondly, we construct efficient mappings with $O(\log^2 N)$ depth between all product-preserving ternary tree fermionic encodings, thereby showing that fermion routing in any such encoding can be done efficiently. While these results assume all-to-all connectivity, they also imply upper bounds for fermion routing in devices with limited connectivity by multiplying the fermion routing depth by the worst-case qubit routing depth. |
| title | Low-depth fermion routing without ancillas |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.05099 |