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

• URL: http://arxiv.org/abs/2605.26041v1
• Date: Mon, 25 May 2026 17:07:47 GMT
• Title: Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
• Abstract summary: Simulating fermionic systems on qubit hardware involves many nonlocal interactions.<n>Recent works reduce this Jordan-Wigner routing overhead to polylogarithmic depth under all-to-all connectivity.<n>We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal $O(sqrtN)$ depth.
• Score: 1.0712892191688657
• License: http://creativecommons.org/licenses/by/4.0/
• 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 Jordan-Wigner routing overhead to polylogarithmic depth under all-to-all connectivity, but degrade to $O(\sqrt{N}\,\mathrm{polylog}\,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, mid-circuit measurements, or classical feedforward. 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 the fermionic fast Fourier transform and Trotter simulation of sparse SYK model demonstrate consistent reduction in depth, spacetime volume, and infidelity for system sizes $N \gtrsim 100$ in the early fault-tolerant regime.

Related papers

• Flash EQ-Linear: Accelerating Equivariant Linear Layers via Group-wise Discrete Fourier Transform [65.89510337046077]
  Equivariant networks embed geometric symmetries as structural priors through weight sharing.<n>Existing implementations unroll the structured weights into dense matrices and dispatch them to generic dense kernels.<n>This is the first time equivariant networks strictly dominate their non-equivariant counterparts along all three axes simultaneously.
  arXiv  Detail & Related papers  (2026-07-23T12:45:21Z)
• Offline Channel-Independent QAOA Angles for RIS Power Aggregation: Unit-Circle Phase Dictionaries and Infinite-Size Spin-Glass Limits [0.0]
  We introduce a $2M$-phase $$ dictionary for optimizing power on reconfigurable surfaces.<n>We observe performance reaching a near-optimal multi-start single-flip local-search reference for $N!le!16$ under order-2 modeling.<n>The approach suggests a route to near-optimal large-$N$ performance on future fault-tolerant (FTQ) quantum computers.
  arXiv  Detail & Related papers  (2026-06-23T13:07:10Z)
• Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids [12.16068230936605]
  Diagonal unitaries are a resource-intensive class of quantum operations.<n>We address synthesis and compilation jointly.<n>We show that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality.
  arXiv  Detail & Related papers  (2026-06-16T06:51:26Z)
• Fermion lattices can be simulated by same-size qubit lattices with $\mathcal{O}(1)$ interaction overhead [0.0]
  Local interactions among electrons underlie many complex properties of correlated materials.<n>We show how to simulate all geometrically local interactions on an $N$-site two-dimensional fermion lattice with no overhead in the number of interactions and no space overhead.
  arXiv  Detail & Related papers  (2026-05-12T18:00:04Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
  arXiv  Detail & Related papers  (2025-11-11T15:38:57Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Low-depth fermion routing without ancillas [32.445850550281726]
  We show that fermion routing can be performed in depth $O(log2 N)$ emph without ancillas, measurements, or feedforward.<n>We construct efficient mappings with $O(log2 N)$ depth between all product-preserving ternary tree fermionic encodings.
  arXiv  Detail & Related papers  (2025-10-06T17:59:13Z)
• Optimizing digital quantum simulation of open quantum lattice models [3.761360709981958]
  We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment.<n>We develop near-optimal algorithms that attain a simulation error $delta$ in the system-state with $mathcalO(Nt(Nt/delta)o(1))$ gates, $mathcalO(t(Nt/delta)o(1))$ ancillas.
  arXiv  Detail & Related papers  (2025-09-02T12:44:57Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  We develop and analyze DASHA: a new family of methods for noneps distributed optimization problems. Unlike MARINA, the new methods DASHA, DASHA-MVR send compressed vectors only and never synchronize the nodes, which makes them more practical for learning.
  arXiv  Detail & Related papers  (2022-02-02T20:10:40Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.