Low-depth fermion routing without ancillas

• URL: http://arxiv.org/abs/2510.05099v2
• Date: Tue, 28 Oct 2025 17:11:46 GMT
• Title: Low-depth fermion routing without ancillas
• Authors: Nathan Constantinides, Jeffery Yu, Dhruv Devulapalli, Ali Fahimniya, Luke Schaeffer, Andrew M. Childs, Michael J. Gullans, Alexander Schuckert, Alexey V. Gorshkov,
• Abstract summary: 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.
• Score: 32.445850550281726
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\Theta(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.

Related papers

• Understanding the Mixture-of-Experts with Nadaraya-Watson Kernel [87.60286115014833]
  Mixture-of-Experts (MoE) has become a cornerstone in recent state-of-the-art large language models (LLMs)<n>Traditionally, MoE relies on $mathrmSoftmax$ as the router score function to aggregate expert output.<n>We propose the textbfzero-additional-cost Kernel Router with Normalization (KERN) as an alternative to $mathrmSoftmax$.
  arXiv  Detail & Related papers  (2025-09-30T08:04:02Z)
• Quantum Routing and Entanglement Dynamics Through Bottlenecks [1.1936126505067601]
  We consider the entanglement dynamics and routing between two regions only connected through an intermediate "bottleneck" region with few qubits.<n>We show an upper bound on the average amount of bipartite entanglement between $L$ and $C,R$ that can be generated in time $t$ by such architecture-respecting Hamiltonians.<n>We also show that, in systems of free particles, we can route optimally on the star graph in time $Theta(sqrtN)$ using Hamiltonian quantum routing.
  arXiv  Detail & Related papers  (2025-05-22T17:33:11Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  Dicke states represent an important class of entangled quantum states with broad applications in quantum computing.<n>We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints.
  arXiv  Detail & Related papers  (2025-05-21T11:55:17Z)
• Fault-tolerant fermionic quantum computing [39.58317527488534]
  We introduce fermionic fault-tolerant quantum computing, a framework which removes this overhead altogether.<n>We show how our framework can be implemented in neutral atoms, overcoming the apparent inability of neutral atoms to implement non-number-conserving gates.
  arXiv  Detail & Related papers  (2024-11-13T19:00:02Z)
• Succinct Fermion Data Structures [0.0]
  Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. We present two new second-quantized fermion encodings of $F$ fermions in $M$ modes.
  arXiv  Detail & Related papers  (2024-10-05T03:16:36Z)
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit [3.629687485125086]
  We explore the important task of applying a phase $exp(i,f(x))$ to a computational basis state $left| x right>$.<n>The closely related task of rotating a target qubit by an angle depending on $f(x)$ is also studied.<n>We find that strategies prioritising execution speed can achieve circuit depth as low as $O(logn+logS)$ for a register of $n$ qubits and a piecewise approximation of $S$ sections.
  arXiv  Detail & Related papers  (2024-09-06T19:57:13Z)
• Hybrid Oscillator-Qubit Quantum Processors: Simulating Fermions, Bosons, and Gauge Fields [31.51988323782987]
  We develop a hybrid oscillator-qubit processor framework for quantum simulation of strongly correlated fermions and bosons. This framework gives exact decompositions of particle interactions as well as approximate methods based on the Baker-Campbell Hausdorff formulas. While our work focusses on an implementation in superconducting hardware, our framework can also be used in trapped ion, and neutral atom hardware.
  arXiv  Detail & Related papers  (2024-09-05T17:58:20Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Does qubit connectivity impact quantum circuit complexity? [5.908927557774895]
  Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. In this paper, we show that all $n$-qubit unitary operations can be implemented by quantum circuits of $O(4n)$ depth and $O(4n)$ size.
  arXiv  Detail & Related papers  (2022-11-10T08:38:29Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Logical fermions for fault-tolerant quantum simulation [0.0]
  We show how to absorb fermionic quantum simulation's expensive fermion-to-qubit mapping overhead into the overhead already incurred by surface-code-based fault-tolerant quantum computing. Our approach encodes Dirac fermions, a key data type for simulation applications, directly into logical Majorana fermions.
  arXiv  Detail & Related papers  (2021-10-19T21:55:49Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  We show that feedforward ReLU neural networks can memorization any $N$ points that satisfy a mild separability assumption. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.
  arXiv  Detail & Related papers  (2021-10-07T05:25:23Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)

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.