Source-linked AI summary
Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, Hartmut Neven
TL;DR
High-accuracy molecular simulation with plane waves can demand far more orbitals than Gaussian bases, while prior plane-wave algorithms scale poorly with basis size. The paper uses first-quantized interaction-picture simulation in the kinetic operator’s rotating frame and reports gate complexity eO(N^1/3η^8/3), compared with prior eO(N^8/3/η^2/3) scaling. It concludes that the lower basis-size scaling can overcome the plane-wave resolution burden and may support explicit quantum treatment of nuclei.
Problem
Plane waves require roughly a hundred times more orbitals than Gaussians for chemical-reaction-rate accuracy, while the prior plane-wave algorithm described here has gate complexity eO(N^8/3/η^2/3).
Source: §I · p. 1Method
The algorithm uses first-quantized momentum-space simulation in the kinetic operator’s rotating frame, applying interaction-picture techniques to the potential.
Source: §I · p. 1Results
The algorithm has gate complexity eO(N^1/3η^8/3), compared with prior plane-wave complexity eO(N^8/3/η^2/3).
Source: §I · p. 1Takeaways & Limitations
The low scaling dependence on N allows the method to overcome the plane-wave resolution difference and may support explicit quantum treatment of nuclei.
Source: §III · p. 6
Abstract
from arXiv · showhide
We present a quantum algorithm for simulating quantum chemistry with gate complexity $\tilde{O}(N^{1/3} \eta^{8/3})$ where $\eta$ is the number of electrons and $N$ is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity $\tilde{O}(N^{8/3} /\eta^{2/3})$. We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when $N \gg \eta$, as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation.
I. INTRODUCTION
Plane waves restore structure that enables more efficient simulation, but their resolution requirements make high-accuracy molecular simulations costly. This work introduces a first-quantized algorithm with sublinear scaling in the number of plane-wave orbitals.
I. INTRODUCTION
- Quantum simulation for chemistry builds on earlier quantum-simulation proposals, fermion-simulation algorithms [3], and a proposal to prepare molecular ground states.Source: §I · p. 1
- With volume proportional to η, prior plane-wave algorithms scale as O(N^10/3/η^1/3 + N^8/3/η^2/3) and eO(N^8/3/η^2/3), respectively.The volume assumption is motivated by constant electron density in condensed-phase systems and molecular wavefunctions that decay exponentially outside a volume proportional to η.Source: §I · p. 1
- The algorithm achieves gate complexity eO(N^1/3η^8/3) using first quantization and interaction-picture simulation in the kinetic operator’s rotating frame.Its sublinear dependence on N addresses the cost of using many plane waves to suppress discretization error.Source: §I · p. 1
- For molecules, plane waves require roughly a hundred times more orbitals than Gaussians for chemical-reaction-rate accuracy, making the corresponding qubit requirement impractical in most contexts.Discretization error decreases asymptotically as O(1/N) for both bases, but their constant factors differ substantially.Source: §I · p. 1
A. Encoding Quantum Simulations of Electronic Structure in Momentum Space First Quantization
The section encodes η electrons in first quantization using registers for plane-wave orbitals, with antisymmetry enforced in the wavefunction. It constructs the Hamiltonian in a Galerkin plane-wave basis and compares the approach with earlier first- and second-quantized methods.
A. Encoding Quantum Simulations of Electronic Structure in Momentum Space First Quantization
- The method represents η particles with η registers of log N qubits each and uses plane waves in three dimensions, with spin ignored for simplicity.The plane-wave indices lie in G = [−N^1/3/2, N^1/3/2]^3 ⊂ Z^3; each orbital has wavenumber k_p = 2πp/Ω^1/3.Source: A. Encoding Quantum Simulations of… · p. 2
- Antisymmetry is imposed explicitly in the wavefunction: swapping any two electron registers changes its sign, and an initial state can be antisymmetrized with O(η log η log N) gates.Hamiltonian evolution preserves antisymmetry when it is present initially because fermionic Hamiltonians commute with the electron permutation operator.Source: A. Encoding Quantum Simulations of… · p. 2
- First-quantized real-space grids require finite-difference methods that lack the variational basis-error bounds guaranteed by Galerkin discretization.The cited work also reports that maintaining constant precision for certain states can sometimes require inverse grid spacing to grow exponentially with particle number.Source: A. Encoding Quantum Simulations of… · p. 2
- Earlier Gaussian-basis configuration-interaction algorithms used O(η log N) spatial complexity, while the more efficient had eO(η^2N^3) gate complexity.The paper reports its eO(η^8/3N^1/3) gate complexity as a substantial improvement over that method.Source: A. Encoding Quantum Simulations of… · p. 2
- The plane-wave Galerkin formulation gives H = T + U + V, where T is kinetic energy, U is the external potential, and V is the two-body Coulomb interaction.The stated Hamiltonian uses a cubic cell with periodic boundaries, and the approach extends to other lattice geometries and reduced periodicity.Source: A. Encoding Quantum Simulations of… · p. 2
B. Simulating Chemistry in the Interaction Picture
The algorithm applies interaction-picture simulation with the kinetic operator as the rotating-frame term and the potential as the simulated term. This choice exploits their norm relationship in first-quantized momentum space and yields sublinear gate scaling in basis size.
B. Simulating Chemistry in the Interaction Picture
- The interaction picture simulates H = A + B in A’s rotating frame so that the large norm of A does not enter complexity in the usual way.The approximation uses time-ordered products interleaving B with evolution under A, implemented through linear combinations of unitaries.Source: B. Simulating Chemistry in the… · pp. 2–3
- For error ǫ, the method uses O(λt) time segments and truncation order K = O(log(λt/ǫ)/log log(λt/ǫ)).The gate complexity also carries a multiplicative factor log(t∥A∥/ǫλ) for preparing time ancillas.Source: B. Simulating Chemistry in the… · p. 3
- When N ≫ η, first-quantized momentum space has ∥U + V∥ ≪ ∥T∥, so the algorithm chooses A = T and B = U + V.This reverses the norm relationship described for the second-quantized setting in [10].Source: B. Simulating Chemistry in the… · p. 3
- The potential terms are expressed as unitaries with Boolean masks preventing contributions when momentum shifts leave the orbital set G.For example, an out-of-range shift in the nuclear term is interpreted as a Boolean value of 1, suppressing that contribution.Source: B. Simulating Chemistry in the… · p. 3
- With molecular volume scaling Ω ∝ η, the potential’s unitary-weight sum is λ = O(η^5/3N^1/3).The paper relates this scaling to the maximum possible potential energy in the basis and the minimum electron separation proportional to (Ω/N)^1/3.Source: B. Simulating Chemistry in the… · p. 3
C. Performing Simulation in the Kinetic Frame
The kinetic-frame simulation implements kinetic evolution and the potential terms through select and prepare operations. Its total gate complexity is dominated by kinetic evolution, with the nuclear-data access cost depending on the arrangement of nuclei.
C. Performing Simulation in the Kinetic Frame
- The potential select operation applies momentum transfers to selected electron registers for the two-electron term, or applies a nuclear phase and momentum transfer for the nuclear term.Both implementations iterate through the electron registers; the nuclear phase uses kν·Rℓ.Source: C. Performing Simulation in the… · p. 4
- Finite position precision contributes O(δR N^1/3 Z/η) error to U/λ, and the text cancels Z and η using charge neutrality.The stated precision scaling is log(1/δR) = O(log(ηNt/ε)).Source: C. Performing Simulation in the… · p. 4
- The prepare operation weights the U and V terms and prepares uniform electron-index superpositions, while nuclear-charge superpositions use weights √ζℓ.The nuclear-charge database has access complexity O(L), with regular arrays allowing logarithmic complexity in L.Source: C. Performing Simulation in the… · p. 4
- For a regular nuclear array, the stated overall complexity is O(log(ηNt/ε) log N); a full nuclear database adds O(L log(ηNt/ε)).Source: C. Performing Simulation in the… · p. 4
- The total gate complexity is Õ(η^8/3 N^1/3 t), with O(η log^2 N) kinetic evolution dominating each segment.The number of segments is Õ(λt), with λ = O(η^5/3 N^1/3).Source: C. Performing Simulation in the… · p. 4
D. Preparing the Momentum State
The momentum state is prepared using nested cubes and an approximation that weights momenta inversely with their magnitude. A single amplitude-amplification step brings success close to one, while the preparation procedure retains logarithmic cost in N.
D. Preparing the Momentum State
- Nested cubes of successively doubled size organize momentum values, with cube weights accounting for variation in 1/∥kν∥ between cubes.Within each cube, 1/∥kν∥ varies little, supporting a large success amplitude.Source: D. Preparing the Momentum State · p. 5
- The integer encoding represents zero twice, so the minus-zero case is flagged as a failure to keep all remaining values equally weighted.Source: D. Preparing the Momentum State · p. 5
- For large M, the construction gives amplitudes proportional to 1/∥ν∥; finite-M error is controlled through the squared-amplitude error and δ = O(1/M).The text sets log M = O(log(ηNt/ε)).Source: D. Preparing the Momentum State · pp. 5–6
- A single amplitude-amplification step brings state-preparation success close to 1, although it triples the state-preparation complexity.The reported failure probability after one step is not total algorithm failure; the identity can be applied instead, with its known contribution subtracted from eigenvalue estimates.Source: D. Preparing the Momentum State · p. 6
- The preparation’s most costly step is the inequality test, but its O(log(1/δ) log N) cost leaves the prepare operation negligible relative to other steps.The other listed state-preparation steps have logarithmic cost in N or 1/δ.Source: D. Preparing the Momentum State · p. 6
III. CONCLUSION
For a 54-electron FeMoco estimate, the paper compares its plane-wave scaling with a prior algorithm and projects substantially lower scaling at the stated resolution. The authors argue that this low dependence on basis size can support higher-resolution chemistry simulations, including explicit quantum treatment of nuclei.
III. CONCLUSION
- The authors expect low N scaling to overcome the plane-wave resolution gap and allow explicit quantum treatment of nuclei with enough momentum-transfer range.They state that precision may otherwise be limited by relativistic effects and the Born-Oppenheimer approximation.Source: §III · p. 6
- The prior O(N^3) algorithm's fewer than 10^9 T gates applied to 100 plane-wave spin-orbitals, which the paper says is insufficient resolution for FeMoco.Source: §III · p. 7
- At 10^6 plane-wave spin-orbitals for 54 electrons, η^8/3N^1/3 is about 4×10^6, versus about 7×10^14 for N^8/3/η^2/3.The authors describe this as a back-of-the-envelope estimate and note that significant logarithmic and constant factors remain.Source: §III · p. 7
- At that resolution, the algorithm requires roughly 10^3 logical qubits, encodable in roughly 10^6 physical qubits under the stated architecture assumptions.The paper says further work is needed to determine precise gate counts.Source: §III · p. 7