Sublinear-depth Quantum Simulation of Electrons with Atomic Orbitals

Technical Summary: Sublinear-Depth Quantum Simulation of Electrons with Atomic Orbitals

Problem Statement
Simulating electronic structure in molecules and materials is a primary application for digital quantum computing. While the performance of quantum simulation algorithms regarding evolution time ($t$) and accuracy ($\epsilon$) is well-understood for both Trotter product formulas and qubitization frameworks, the scaling with system size ($N$) remains a challenge, particularly for systems with less structured interactions.

The standard approach for modeling electrons in molecules utilizes atomic orbitals, which offer a compact and flexible representation where atoms remain meaningful subunits. However, discretizing electronic degrees of freedom into atomic orbitals typically results in Hamiltonians with up to $O(N^4)$ interaction terms and little inherent structure. Previous attempts to simulate these models on quantum computers using direct implementation of all terms resulted in impractically large polynomial scaling (e.g., $O(N^{10})$). Even with improvements via Linear Combination of Unitaries (LCU) and Hamiltonian decomposition, previous results suggested that atomic orbitals were not competitive with plane-wave or real-space grid methods for large-scale simulations, which achieve gate complexities around $O(N^{5/3})$. Furthermore, many existing efficient methods rely on qubitization, which often incurs a query depth of $\Omega(\lambda t)$ where $\lambda \ge \|H\| = \Omega(N)$, preventing sublinear-depth simulation.

Methodology
This work proposes a Trotter-based quantum simulation algorithm for atomic orbitals that achieves state-of-the-art gate complexity with sublinear depth and no clean ancilla qubits. The methodology relies on three core technical pillars:

1. Rigorous Orbital Localization and Basis Construction:
   The authors formally define a notion of orbital localization satisfied by realistic many-atom systems. They address the challenge that standard atomic orbitals are not orthogonal and that converting them to an orthonormal basis (e.g., Hartree-Fock) often destroys spatial locality. The paper proves that Löwdin orthogonalization ($S^{-1/2}$) of an atomic-orbital set preserves the exponential decay properties required for localization, provided the system is in the thermodynamic limit (constant orbital resolution per atom, constant minimal inter-nuclear distance). This establishes that the resulting orthonormal basis remains an "atomic-orbital set" with well-defined decay parameters.

2. Hierarchical Hamiltonian Decomposition (Fast Multipole Method Inspired):
   Leveraging the exponential decay of orbital overlaps, the authors first truncate the Hamiltonian to a sparse graph where only $O(N)$ orbital pairs interact significantly. They then decompose the remaining long-range Coulomb interactions ($h_{long}$) using a strategy inspired by the classical Fast Multipole Method (FMM).

   • The system is partitioned hierarchically into boxes (levels $j$).
   • Interactions are split into short-range (handled directly) and long-range components.
   • Long-range interactions between spatially separated boxes are approximated via multipole expansions (spherical harmonics), resulting in a low-rank decomposition of the Hamiltonian terms.
   • This decomposition reduces the long-range interaction into a sum of rank-1 operators acting on disjoint sets of qubits.

3. Shallow Quantum Circuits for Trotter Steps:
   The algorithm implements each Trotter step by processing these decomposed terms:

   • Fermionic Permutations: To align interacting orbitals in the Jordan-Wigner encoding, fermionic permutations are applied. The algorithm utilizes the version that performs these permutations in $O(\log^2 N)$ depth without ancillas, ensuring no additional clean qubits are required (though $O(\log N)$ depth is possible with $\Theta(N)$ ancillas, the proposed method avoids this overhead).
   • Rank-1 ZZ-Interactions: The core innovation is a new quantum circuit for implementing the evolution of rank-1 ZZ-interactions ($e^{-i v w t}$). The authors demonstrate that such interactions can be implemented in polylogarithmic depth ($O(\text{polylog}(Nt/\epsilon))$) using shallow quantum Fourier arithmetic circuits and a small number of "dirty" ancilla qubits (which can be recycled from idle system qubits, requiring no net increase in clean qubit count).
   • Parallelization: By arranging the hierarchical decomposition such that interactions within a level can be parallelized into a constant number of layers, the total depth per Trotter stage is kept low.

Key Contributions and Results
The paper presents the following specific results:

• Theoretical Foundation: A proof that Löwdin orthogonalization preserves the exponential decay of atomic orbitals, justifying the use of localized orthonormal bases for quantum simulation in the thermodynamic limit.
• Algorithmic Efficiency: A Trotter-based simulation algorithm that implements a single Trotter step in depth $O(\text{polylog}(Nt/\epsilon))$.
• Complexity Bounds:
  • Gate Count: The total gate count scales as $N^{5/3 + o(1)}$ for 3D systems (and $N^{1+o(1)}$ for 1D, $N^{3/2+o(1)}$ for 2D). This matches the best-known scaling for any basis (previously only achieved by plane-wave methods).
  • Depth: The simulation depth scales sublinearly as $N^{2/3 + o(1)}$ for 3D systems.
  • Ancillas: The algorithm requires zero clean ancilla qubits, utilizing only "dirty" ancillas that are recycled from the system.
• Error Analysis: The authors bound the Trotter error using commutator structures, showing that the optimal Trotter order yields the stated gate and depth complexities.

Significance
The paper claims that this work resolves a long-standing inefficiency in quantum chemistry simulations. By combining rigorous orbital localization, FMM-inspired decomposition, and shallow arithmetic circuits, the authors demonstrate that atomic orbitals are competitive for large-scale quantum simulations, contrary to previous assumptions.

The significance lies in:

1. Breaking the Depth Barrier: Achieving sublinear depth ($N^{2/3}$) for atomic orbital simulations, whereas previous methods were limited by linear or higher depth scaling.
2. Resource Efficiency: Eliminating the need for clean ancilla qubits, which are a scarce resource in near-term and early fault-tolerant devices, by utilizing recycled "dirty" ancillas.
3. Paradigm Shift: Showing that Trotter-based methods, often viewed as less efficient than qubitization for certain metrics, can outperform qubitization in terms of depth and ancilla requirements when combined with advanced Hamiltonian decomposition techniques.

The authors note that while the asymptotic scaling is improved, the constant factors and logarithmic overheads mean the crossover point where this method outperforms others depends on specific system sizes and hardware constraints, which requires further study. They also clarify that their approach is distinct from restricting to low-energy subspaces, as it addresses the full electronic structure problem.