A Quantum Algorithm with Polylogarithmic Depth per Trotter Step for the Extended Hubbard Model

Technical Summary: Q2FMM for the Extended Hubbard Model

Problem Statement
The simulation of the extended Fermi-Hubbard model on a two-dimensional lattice is a central challenge in quantum computing, particularly for condensed matter physics and strongly correlated electronic structures. While local terms (hopping and on-site interactions) can be simulated efficiently with constant or low-depth circuits, the inclusion of long-range Coulomb interactions presents a significant bottleneck. These interactions generate $O(N^2)$ terms (where $N$ is the number of lattice sites), leading to deep quantum circuits. Standard approaches, such as fermionic SWAP networks, result in a circuit depth per Trotter step scaling as $O(N)$. Truncation strategies are often ineffective for Coulomb potentials due to their slow $1/r$ decay, which requires large cutoff radii to maintain accuracy.

Methodology: The Q2FMM Algorithm
The authors propose Q2FMM, a quantum algorithm inspired by the classical Fast Multipole Method (FMM) to simulate the time evolution of the extended Hubbard model within the Trotter product formula. The core methodology involves replacing direct site-site interactions with interactions between hierarchical, coarse-grained "boxes" across multiple length scales.

1. Hierarchical Structure: The algorithm organizes the 2D lattice into a quadtree structure. It distinguishes between "near-field" interactions (handled directly at the finest level) and "far-field" interactions (approximated via multipole expansions).
2. Multipole Expansions:
   • 0th-Order Q2FMM: Uses a simplified approximation where distant boxes interact based on their total occupation numbers ($N_A N_B$).
   • Higher-Order Q2FMM: Refines accuracy by retaining multipole coefficients ($M_{\ell m}$) rather than just total occupation numbers. This allows for a systematic trade-off between accuracy and computational cost via a truncation order $p$.
3. Quantum Circuit Design:
   • Compute Phase: The algorithm proceeds from the finest level (individual sites) to the coarsest level. At each level, it aggregates information from child boxes to parent boxes using quantum adders. For higher-order versions, this involves translating and summing multipole coefficients.
   • Phase Application: The interaction energy for box pairs is computed using quantum multipliers to calculate products of occupation numbers or multipole terms. The resulting phase is applied via single-qubit phase gates.
   • Uncompute Phase: To prevent the accumulation of garbage states and unwanted entanglement, the algorithm employs a reversible "uncompute" phase. This reverses the aggregation steps (decomposing parent information back into child information) after the phase has been imprinted, ensuring the system returns to a clean state while preserving the dynamical phase.
4. Optimizations: The paper discusses optional optimizations using COPY operations (Transversal CNOTs) to parallelize phase calculations and unbounded fan-out gates to reduce the depth of arithmetic circuits to $O(\log^* n)$, though the primary scaling analysis relies on standard reversible circuits.

Key Results and Complexity
The resulting quantum circuit achieves the following scaling properties per Trotter step and for total simulation time $t$ with target error $\epsilon$:

• Circuit Depth: The depth per Trotter step scales polylogarithmically with the system size $N$. Specifically, it scales as $O(\log N \cdot \log Q)$, where $Q$ is the number of electrons.
• Gate Complexity: The gate complexity per Trotter step scales quasi-linearly with system size, denoted as $\tilde{O}(N)$.
• Total Complexity: Accounting for the number of Trotter steps required to simulate time $t$ with error $\epsilon$, the total circuit depth scales as $\tilde{O}(N^{1/2} t^{3/2} / \epsilon^{1/2})$, and the total gate complexity scales as $\tilde{O}(N^{3/2} t^{3/2} / \epsilon^{1/2})$.
• Ancilla Qubits: The algorithm requires a number of ancilla qubits that scales quasi-linearly with the system size, $\tilde{O}(N)$.

Significance and Claims
The paper claims that Q2FMM offers a significant advantage over existing methods for simulating long-range interactions in large systems.

• Comparison with Interaction Picture: The authors compare Q2FMM to the interaction-picture method (Low and Wiebe, Ref. [82]), which has a gate complexity of $\tilde{O}(N^2 t)$. Q2FMM becomes advantageous in the large-system regime (large $N$), whereas the interaction-picture method is more favorable for long-time, high-precision simulations (large $t$, small $\epsilon$). The crossover point is estimated at $N \sim \tilde{O}(t/\epsilon)$.
• Hardware Suitability: The authors suggest that Q2FMM is particularly well-suited for two-dimensional neutral-atom quantum computers, which natively support atom shuttling and long-range entangling gates. It is also compatible with surface-code architectures where long-range operations can be realized in constant depth.
• Generality: While demonstrated on the extended Hubbard model, the framework is presented as applicable to other kernels (e.g., Yukawa, Helmholtz) and potentially to ab initio molecular Hamiltonians discretized on real-space grids.

Distinction from Related Work
The authors distinguish Q2FMM from recent FMM-based approaches for molecular Hamiltonians (e.g., Berry et al., Ref. [80]). In those works, the quantum state is in first quantization, requiring complex sorting of electrons into spatial boxes based on quantum position data. In contrast, Q2FMM operates on a lattice where qubits are pre-arranged by spatial position (second quantization), eliminating the need for quantum data movement based on position. Consequently, Q2FMM focuses on the efficient hierarchical reuse of intermediate results and the management of garbage states through uncomputing.