Linear Complexity Fermionic Simulation on Quantum Devices with Hardware Connectivity Constraints
This work addresses the critical bottleneck of compiling fermionic Hamiltonians into efficient quantum circuits for near-term quantum devices, providing provably optimal scaling and substantial practical improvements.
Accordion is an end-to-end framework for simulating fermionic systems on quantum devices that co-designs fermion-to-qubit mapping with circuit synthesis and hardware routing. It achieves O(N^4) gate count and depth for full-rank all-to-all Hamiltonians, matching the information-theoretic lower bound, and reduces gate count by up to 79% and circuit depth by up to 77% on realistic hardware topologies.
Simulating fermionic systems on quantum hardware requires compiling fermionic Hamiltonians into executable quantum circuits. Existing approaches treat each compilation stage independently, applying heuristics with localized objectives that produce circuits with superquartic gate count and depth scaling and compilation times reaching several hours for large instances. We present Accordion, an end-to-end framework that co-designs the fermion-to-qubit mapping with circuit synthesis and hardware routing. Accordion fixes the Jordan Wigner mapping, which despite its higher Pauli weight produces Pauli operators with structural regularity that enables provably efficient circuit generation. For full-rank all-to-all electronic structure Hamiltonians, we prove O(N^4) gate count and circuit depth, matching the information-theoretic lower bound imposed by the Theta(N^4) second excitation terms. On linear, IBM heavy-hex, and square-grid architectures, Accordion reduces gate count by up to 79% and circuit depth by up to 77% relative to the best baseline.