Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.26041

Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas

Dantong Li, Shifan Xu, Yongshan Ding

quant-phSubmitted May 25, 2026• Announced May 26, 2026• 0 citations• Revised Sep 8, 2026 (v2)
v1 · May 25, 2026v2 · Sep 8, 2026
arXivHTMLPDF

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(\sqrt{N}\log 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(\sqrt{N})$ depth with $O(N\sqrt{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 $Ω(\sqrt{N})$ lower bound, which holds even when $O(N)$ ancillas and classical feedforward are permitted. We further construct an $O(\sqrt{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.

Comments
24 pages, 14 figures

Related papers

Fermion lattices can be simulated by same-size qubit lattices with $\mathcal{O}(1)$ interaction overhead

Gregor Aigner, Berend Klaver, Martin Lanthaler +1 more

Local interactions among electrons underlie many complex properties of correlated materials. While the Jordan-Wigner transformation can preserve this locality along one spatial dimension, interactions along the remaining dimensions typically incur substantial overhead. We show how to simulate all geometrically local interactions on an $N$-site two-dimensional fermion lattice with no asymptotic overhead in the number of interactions and no space overhead. The primary overhead of our method is circuit depth, which on a qubit lattice matches that of fermionic swap networks, scaling as $\mathcal{O}(\sqrt{N})$, but reduces to $\mathcal{O}(\log N)$ on reconfigurable qubit arrays and to $\mathcal{O}(1)$ in lattice-surgery-based surface-code architectures. This is enabled by dynamically reorienting the Jordan-Wigner transformation to switch the lattice dimension along which locality is preserved. Furthermore, we study fermion routing, as required for the simulation of non-local interactions. When using qubit lattices, we reach resource scaling that asymptotically matches that of qubit routing, whilst on fully connected qubit devices, a depth scaling arbitrarily close to $\mathcal{O}(\log N)$ is reached. This allows the fermionic fast Fourier transform to be implemented on qubit lattices with asymptotically optimal resource scaling under these locality constraints. Notably, all of our constructions naturally extend to $d$-dimensional lattices. Beyond scaling improvements, we show explicit examples of our method, including Fermi-Hubbard-model simulations of the square-, Lieb- and kagome lattice and the fermionic fast Fourier transform.

quant-pharXiv:2605.12600•May 14, 2026•0 citations

Low-depth fermion routing without ancillas

Nathan Constantinides, Jeffery Yu, Dhruv Devulapalli +6 more

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.

arXiv:2510.05099•Oct 6, 2025•0 citations

Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids

Chengzhuo Xu, Xiao Chen, Zhihao Liu +1 more

Diagonal unitaries are a fundamental but resource-intensive class of quantum operations, arising as the phase separators of QAOA and the time-evolution blocks of Hamiltonian simulation. Under all-to-all connectivity their optimal depth is established, but on nearest-neighbor hardware general-purpose compilers fall back on heuristic search, which yields no analyzable cost bound and becomes intractable at the very sizes where depth is the bottleneck. We address synthesis and compilation jointly. On the synthesis side, we develop a Gray-Path Framework (GPF) that realizes any $n$-qubit diagonal unitary in asymptotically optimal $R_z$ and CNOT depth $O(2^n/n)$ without ancillas. Our main result is that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality: routing adds depth $Θ(2^n/n)$ and gate count $Θ(2^n)$. Because GPF fixes its entire interaction structure in advance, routing reduces to scheduling a known sequence, with no heuristic search. We give the construction both with and without ancillas: the ancilla-free, cost-optimized layout is a two-row grid, and a $2k$-row layout introduces a space--time tradeoff that cuts depth by $1/k$ while remaining asymptotically optimal for the enlarged register; both are deterministic and analyzed in closed form. The same complexity is also attained on a linear nearest-neighbor chain, so the preservation is topology-independent, holding on any architecture that contains such a chain. All routing bounds are closed-form, giving the concrete resource estimates that heuristic compilers cannot provide at scale.

quant-pharXiv:2606.17589•Jun 17, 2026•0 citations

Efficient Simulation of Sparse, Non-Local Fermion Models

Reinis Irmejs, J. Ignacio Cirac

Efficient simulation of interacting fermionic systems is a key application of near-term quantum computers, but is hindered by the overhead required to encode fermionic operators on qubit hardware. Here, we consider models with $N$ fermionic modes in which each participates in at most a constant number $d$ of interactions and study the circuit depth required to implement the Trotterized time evolution on qubit hardware with all-to-all connectivity. We introduce an encoding that augments each physical fermionic mode with a small number of auxiliary fermions, enabling the removal of Jordan--Wigner strings. Although the preparation of the auxiliary fermion state incurs an initial overhead, this state remains invariant under time evolution. As a result, long-time evolution can be implemented with asymptotically optimal circuit depth, reducing a previously multiplicative $O(\log N)$ overhead to an additive overhead. Our results thus establish that the simulation of sparse fermionic models on qubit hardware matches the performance achievable on ideal fermionic hardware up to constant factors and $O(dN)$ ancillary qubits.

quant-pharXiv:2512.15843•Dec 18, 2025•0 citations

Nearest-neighbour gates are all you need: High-rate quantum low-density parity-check codes on a planar grid

Boren Gu, Tamas Noszko, Vincent Steffan +4 more

High-performance quantum low-density parity-check codes promise substantial reductions in the overhead of fault-tolerant quantum computation, but most constructions require long-range connectivity or qubit shuttling, both of which are difficult to realise in superconducting architectures. Here we introduce a family of quantum low-density parity-check codes that, for the first time, combines planar open-boundary layouts, finite-size advantages over surface codes, and syndrome extraction using only nearest-neighbour gates on a planar grid of qubits with either square or hexagonal connectivity. The resulting circuits achieve optimal constant-depth stabiliser measurement, independent of code size, and naturally remove leakage from the system by exchanging the roles of check and data qubits at each syndrome extraction round. We find finite-size instances such as a [[323,14,15]] code, whose code-efficiency ratio is nearly an order of magnitude larger than that of rotated surface-code patches. At around 40 circuit qubits per logical qubit, the best directional tile-code layouts reduce the per-logical per-round logical error rate by a factor of 100 relative to rotated surface-code memories. These results show that the advantages of quantum low-density parity-check codes can survive compilation into strictly planar nearest-neighbour circuits, bringing low-overhead fault-tolerant memories closer to near-term hardware.

quant-pharXiv:2606.19482•Jun 19, 2026•0 citations

Hardware-Aware Fermion-to-Qubit Mappings for Simulating the 2D Hubbard Model on Heavy-Hexagon Quantum Processors

Alessio Esposito, Andrea Giachero, Zoltàn Zimboràs +1 more

Quantum simulation of strongly correlated fermionic systems is among the most promising near- term applications of quantum computing, but its practical efficiency depends critically on the choice of fermion-to-qubit mapping and on the connectivity of the underlying hardware. In this work we address this problem in the context of the two-dimensional Hubbard model, simulated on IBM superconducting quantum processors with heavy-hexagon connectivity. We numerically benchmark the Jordan-Wigner, Bravyi-Kitaev, and Bonsai transformations, evaluating their Pauli weight and SWAP overhead across seven heavy-hexagon chips of increasing size. We show that, while the Bravyi-Kitaev mapping initially exhibits a lower Pauli weight, this advantage is eliminated once routing costs are taken into account, confirming the Bonsai mapping as the most hardware-efficient baseline transformation for this architecture. We then use the Bonsai mapping to construct the qubit Hamiltonian of the 2D spinful Fermi-Hubbard model, introducing a simulated annealing algorithm that optimizes the assignment of Majorana strings to lattice sites, reducing the cost function by nearly 50% percent. Finally, we simulate on quantum hardware the time evolution of fermionic states up to 6x6 lattices, confirming the viability of the Bonsai encoding for hardware-aware large-scale two-dimensional simulations.

quant-pharXiv:2608.25024•Aug 27, 2026•0 citations
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)O(\sqrt{N}\log N)O(N​logN) for NNN fermionic modes on 2D nearest-neighbor architectures. We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal O(N)O(\sqrt{N})O(N​) depth with O(NN)O(N\sqrt{N})O(NN​) nearest-neighbor gates and no ancilla qubits, measurements, or classical feedforward. For N=L2N=L^2N=L2 modes, the CNOT depth is at most 10L+1210L+1210L+12. This matches the Ω(N)Ω(\sqrt{N})Ω(N​) lower bound, which holds even when O(N)O(N)O(N) ancillas and classical feedforward are permitted. We further construct an O(N)O(\sqrt{N})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=6L=6L=6 (N=36N=36N=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.
Fermion lattices can be simulated by same-size qubit lattices with O(1)\mathcal{O}(1)O(1) interaction overhead
Local interactions among electrons underlie many complex properties of correlated materials. While the Jordan-Wigner transformation can preserve this locality along one spatial dimension, interactions along the remaining dimensions typically incur substantial overhead. We show how to simulate all geometrically local interactions on an NNN-site two-dimensional fermion lattice with no asymptotic overhead in the number of interactions and no space overhead. The primary overhead of our method is circuit depth, which on a qubit lattice matches that of fermionic swap networks, scaling as O(N)\mathcal{O}(\sqrt{N})O(N​), but reduces to O(log⁡N)\mathcal{O}(\log N)O(logN) on reconfigurable qubit arrays and to O(1)\mathcal{O}(1)O(1) in lattice-surgery-based surface-code architectures. This is enabled by dynamically reorienting the Jordan-Wigner transformation to switch the lattice dimension along which locality is preserved. Furthermore, we study fermion routing, as required for the simulation of non-local interactions. When using qubit lattices, we reach resource scaling that asymptotically matches that of qubit routing, whilst on fully connected qubit devices, a depth scaling arbitrarily close to O(log⁡N)\mathcal{O}(\log N)O(logN) is reached. This allows the fermionic fast Fourier transform to be implemented on qubit lattices with asymptotically optimal resource scaling under these locality constraints. Notably, all of our constructions naturally extend to ddd-dimensional lattices. Beyond scaling improvements, we show explicit examples of our method, including Fermi-Hubbard-model simulations of the square-, Lieb- and kagome lattice and the fermionic fast Fourier transform.
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)O(N)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)O(\log N)O(logN) by decomposing general fermion routing into O(log⁡N)O(\log N)O(logN) interleave permutations of depth O(1)O(1)O(1), using Θ(N)Θ(N)Θ(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⁡2N)O(\log^2 N)O(log2N) \emph{without} ancillas, measurements, or feedforward. Secondly, we construct efficient mappings with O(log⁡2N)O(\log^2 N)O(log2N) 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.
Diagonal unitaries are a fundamental but resource-intensive class of quantum operations, arising as the phase separators of QAOA and the time-evolution blocks of Hamiltonian simulation. Under all-to-all connectivity their optimal depth is established, but on nearest-neighbor hardware general-purpose compilers fall back on heuristic search, which yields no analyzable cost bound and becomes intractable at the very sizes where depth is the bottleneck. We address synthesis and compilation jointly. On the synthesis side, we develop a Gray-Path Framework (GPF) that realizes any nnn-qubit diagonal unitary in asymptotically optimal RzR_zRz​ and CNOT depth O(2n/n)O(2^n/n)O(2n/n) without ancillas. Our main result is that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality: routing adds depth Θ(2n/n)Θ(2^n/n)Θ(2n/n) and gate count Θ(2n)Θ(2^n)Θ(2n). Because GPF fixes its entire interaction structure in advance, routing reduces to scheduling a known sequence, with no heuristic search. We give the construction both with and without ancillas: the ancilla-free, cost-optimized layout is a two-row grid, and a 2k2k2k-row layout introduces a space--time tradeoff that cuts depth by 1/k1/k1/k while remaining asymptotically optimal for the enlarged register; both are deterministic and analyzed in closed form. The same complexity is also attained on a linear nearest-neighbor chain, so the preservation is topology-independent, holding on any architecture that contains such a chain. All routing bounds are closed-form, giving the concrete resource estimates that heuristic compilers cannot provide at scale.
Efficient simulation of interacting fermionic systems is a key application of near-term quantum computers, but is hindered by the overhead required to encode fermionic operators on qubit hardware. Here, we consider models with NNN fermionic modes in which each participates in at most a constant number ddd of interactions and study the circuit depth required to implement the Trotterized time evolution on qubit hardware with all-to-all connectivity. We introduce an encoding that augments each physical fermionic mode with a small number of auxiliary fermions, enabling the removal of Jordan--Wigner strings. Although the preparation of the auxiliary fermion state incurs an initial overhead, this state remains invariant under time evolution. As a result, long-time evolution can be implemented with asymptotically optimal circuit depth, reducing a previously multiplicative O(log⁡N)O(\log N)O(logN) overhead to an additive overhead. Our results thus establish that the simulation of sparse fermionic models on qubit hardware matches the performance achievable on ideal fermionic hardware up to constant factors and O(dN)O(dN)O(dN) ancillary qubits.
High-performance quantum low-density parity-check codes promise substantial reductions in the overhead of fault-tolerant quantum computation, but most constructions require long-range connectivity or qubit shuttling, both of which are difficult to realise in superconducting architectures. Here we introduce a family of quantum low-density parity-check codes that, for the first time, combines planar open-boundary layouts, finite-size advantages over surface codes, and syndrome extraction using only nearest-neighbour gates on a planar grid of qubits with either square or hexagonal connectivity. The resulting circuits achieve optimal constant-depth stabiliser measurement, independent of code size, and naturally remove leakage from the system by exchanging the roles of check and data qubits at each syndrome extraction round. We find finite-size instances such as a [[323,14,15]] code, whose code-efficiency ratio is nearly an order of magnitude larger than that of rotated surface-code patches. At around 40 circuit qubits per logical qubit, the best directional tile-code layouts reduce the per-logical per-round logical error rate by a factor of 100 relative to rotated surface-code memories. These results show that the advantages of quantum low-density parity-check codes can survive compilation into strictly planar nearest-neighbour circuits, bringing low-overhead fault-tolerant memories closer to near-term hardware.
Quantum simulation of strongly correlated fermionic systems is among the most promising near- term applications of quantum computing, but its practical efficiency depends critically on the choice of fermion-to-qubit mapping and on the connectivity of the underlying hardware. In this work we address this problem in the context of the two-dimensional Hubbard model, simulated on IBM superconducting quantum processors with heavy-hexagon connectivity. We numerically benchmark the Jordan-Wigner, Bravyi-Kitaev, and Bonsai transformations, evaluating their Pauli weight and SWAP overhead across seven heavy-hexagon chips of increasing size. We show that, while the Bravyi-Kitaev mapping initially exhibits a lower Pauli weight, this advantage is eliminated once routing costs are taken into account, confirming the Bonsai mapping as the most hardware-efficient baseline transformation for this architecture. We then use the Bonsai mapping to construct the qubit Hamiltonian of the 2D spinful Fermi-Hubbard model, introducing a simulated annealing algorithm that optimizes the assignment of Majorana strings to lattice sites, reducing the cost function by nearly 50% percent. Finally, we simulate on quantum hardware the time evolution of fermionic states up to 6x6 lattices, confirming the viability of the Bonsai encoding for hardware-aware large-scale two-dimensional simulations.