Source-linked AI summary
Exploiting locality in quantum computation for quantum chemistry
Jarrod R. McClean, Ryan Babbush, Peter J. Love, Alán Aspuru-Guzik
TL;DR
Classical quantum chemistry faces exponential Hilbert-space growth, while quantum algorithms offer polynomial-cost routes with substantial overhead. This paper combines physical locality, local basis sets, and Bravyi–Kitaev encoding to improve scaling, yielding more favorable estimates for phase estimation and practical alternatives for limited coherence.
Problem
Exact classical quantum-chemistry calculations become intractable with molecular size, while quantum algorithms retain substantial overhead.
Source: INTRODUCTION · p. 1Method
The paper incorporates local basis sets and physical interaction locality into quantum algorithms, using Bravyi–Kitaev encoding and analyzing phase estimation and Hamiltonian averaging.
Source: INTRODUCTION · p. 1, Hamiltonian averaging · p. 8, Estimates of qubit and coupler scaling · p. 12Results
Quantum phase estimation with first-order Suzuki–Trotter evolution is estimated to scale as O(M^5 log M), improving over prior O(M^8)-O(M^9) and O(M^5.5)-O(M^6.5) estimates.
Source: CONCLUSIONS · p. 13Takeaways & Limitations
Accounting for physical locality substantially improves the outlook for quantum chemistry on quantum computers.
Source: CONCLUSIONS · p. 13The reported bounds are worst-case, and further studies are needed to quantify performance beyond those bounds.
Source: Effect of truncation · p. 4, Quantum phase estimation · p. 8, Hamiltonian averaging · p. 9
Abstract
from arXiv · showhide
Accurate prediction of chemical and material properties from first principles quantum chemistry is a challenging task on traditional computers. Recent developments in quantum computation offer a route towards highly accurate solutions with polynomial cost, however this solution still carries a large overhead. In this perspective, we aim to bring together known results about the locality of physical interactions from quantum chemistry with ideas from quantum computation. We show that the utilization of spatial locality combined with the Bravyi-Kitaev transformation offers an improvement in the scaling of known quantum algorithms for quantum chemistry and provide numerical examples to help illustrate this point. We combine these developments to improve the outlook for the future of quantum chemistry on quantum computers.
INTRODUCTION
Quantum chemistry requires solving an electronic-structure problem whose exact classical treatment scales exponentially, motivating quantum-computational approaches. The paper reviews this problem and frames locality-aware quantum algorithms as a route toward improved scalability.
INTRODUCTION
- Exact classical solutions become intractable as molecular size grows because the Hilbert-space dimension increases exponentially.Source: INTRODUCTION · p. 1
- Quantum computation represents quantum systems directly, offering a potential route around classical storage requirements.Source: INTRODUCTION · p. 1
- Prior quantum-chemistry algorithms improved through circuit and realistic-error analyses, but their costs remained substantial [15] [16] [17].Source: INTRODUCTION · p. 1
- This paper combines local basis sets with quantum algorithms and analyzes quantum phase estimation and Hamiltonian averaging.Source: INTRODUCTION · p. 1
ELECTRONIC STRUCTURE PROBLEM
- Electronic-structure calculations target eigenstates and energies of a molecular Hamiltonian, with ground states often the primary focus.Source: ELECTRONIC STRUCTURE PROBLEM · p. 2
Second quantized Hamiltonian
- The second-quantized formulation encodes antisymmetry in operators over an orthogonal spin-orbital basis with M terms.Source: Second quantized Hamiltonian · p. 2
Spatial locality
Local Gaussian basis functions make electronic interactions decay with distance, reducing the number of significant Hamiltonian terms relative to the formal O(M^4) count. The resulting scaling depends on overlap decay, integral magnitudes, and nuclear-attraction contributions.
Spatial locality
- Locality reduces the number of non-negligible Hamiltonian terms from the formal O(M^4) count toward O(M^2) in suitable bases.Source: Spatial locality · p. 2
- Gaussian overlaps decay exponentially with center separation, creating a characteristic distance beyond which overlap and kinetic integrals can be neglected.Source: Spatial locality · p. 3
- Two-electron integrals are expected to show quadratic practical scaling, with further-distance interactions eventually yielding effectively linear significant-term counts.Source: Spatial locality · p. 3
- For fixed chemical composition, maximal overlap, kinetic, and two-electron integral magnitudes are independent of molecular size in standard atom-centered Gaussian bases.Source: Spatial locality · p. 3
- Nuclear-attraction integrals remain size dependent because each significant local term sums contributions from all nuclei.Source: Spatial locality · p. 4
- The nuclear-attraction bound scales as O(N_nuc^2/3), while atom-centered Gaussian bases contain a number of functions linear in nuclear count.Source: Spatial locality · p. 4
Effect of truncation
Integral truncation can preserve target energy accuracy when discarded terms are controlled by a precision-dependent threshold. The analysis uses perturbative or direct averaging bounds, while emphasizing that worst-case estimates may be pessimistic.
Effect of truncation
- A magnitude threshold δ can be chosen so discarded integrals preserve a desired energy precision ϵ for eigenvalue and averaged-energy estimates.Source: Effect of truncation · pp. 4–5
- Perturbation theory models truncation as a perturbation H_t = H + V and bounds eigenvalue changes from removed Hamiltonian terms.Source: Effect of truncation · p. 4
- The error bound is worst case and excludes cancellations between Hamiltonian terms, which numerical studies suggest can make it overly pessimistic [16].Source: Effect of truncation · p. 4
- Energy averaging requires a threshold whose worst-case accuracy condition matches the first-order eigenvalue-perturbation result.Source: Effect of truncation · p. 5
- Sorting integrals by magnitude and removing the largest set whose total magnitude remains below ϵ provides a practical truncation strategy.Source: Effect of truncation · p. 5
- For physical chemistry systems, removing terms around δ = 10^-10 or smaller is observed to retain qualitative and quantitative accuracy, with convergence testable for each system.Source: Effect of truncation · p. 5
Onset of favorable scaling
Numerical examples show that locality becomes advantageous beyond system-dependent length scales, especially in larger systems and compact local bases. Canonical molecular orbitals can remain sparser for the smallest molecules, so the crossover is basis dependent.
Onset of favorable scaling
- Larger, more diffuse basis sets exhibit locality effects at comparatively larger length scales, although the asymptotic scaling arguments remain general.Source: Onset of favorable scaling · p. 5
- Quantum simulation cannot directly use the bare nonorthogonal atomic-orbital basis, so the study uses Löwdin symmetric orthogonalization.Source: Onset of favorable scaling · p. 5
- Further basis developments, including jointly local occupied and virtual orbitals and multiresolution wavelets, could avoid costly exact orthogonalization transformations scaling as O(M^5).Source: Onset of favorable scaling · p. 5
- At δ = 10^-7, localized OAO bases save about 6×10^6 integrals over canonical MOs in hydrogen chains, with differences emerging near 10 Å.Source: Figure 1 · p. 5, Onset of favorable scaling · p. 6
- At 10 carbon atoms, localized alkane-chain bases save almost 10^8 integrals at truncation level 10^-7.Source: Onset of favorable scaling · p. 6
- Canonical molecular orbitals can be sparser for small molecules, but localized bases become more advantageous at medium-to-large sizes.Source: Onset of favorable scaling · p. 6
QUANTUM ENERGY ESTIMATION
Quantum energy estimation separates state preparation from energy estimation and compares quantum phase estimation with Hamiltonian averaging under an available eigenstate oracle. Locality and the Bravyi–Kitaev transformation reduce gate-count scaling, while Suzuki–Trotter error determines the required timestep.
Quantum phase estimation
- Quantum phase estimation evolves an approximate eigenstate under H and reads out the accumulated phase to obtain its eigenenergy.Its dominant cost is coherent system evolution.Source: Quantum phase estimation · pp. 6–7
- Bravyi–Kitaev encoding reduces transformation overhead to O(log M), giving O(M^2 log M) gates per Suzuki–Trotter timestep, or O(M log M) macroscopically.The comparison is against Jordan–Wigner overhead that scales with the number of qubits.Source: Quantum phase estimation · p. 7
- The timestep must keep Suzuki–Trotter bias below ϵ while total evolution time provides energy resolution better than ϵ.The analysis treats total time T as fixed for chemical precision ϵchem = 10^-3.Source: Quantum phase estimation · p. 7
- For a k’th-order Suzuki–Trotter propagator, the leading ground-state eigenvalue perturbation is O(∆t)^(k+1) for a non-degenerate system.The lower-order imaginary contribution vanishes for a real ground state, leaving the real term at order (∆t)^(k+1).Source: Quantum phase estimation · pp. 7–8
- The phase-estimation scaling is a worst-case bound that excludes possible cancellation between Hamiltonian terms.Numerical work suggests these bounds may be too pessimistic because average cancellation can occur.Source: Quantum phase estimation · p. 8
- O(M^5 log M) bounds quantum phase estimation in the large-size local-basis limit with Bravyi–Kitaev encoding.This uses quadratically scaling significant two-electron integrals and linearly scaling significant one-electron integrals.Source: Quantum phase estimation · pp. 7–8
Hamiltonian averaging
Hamiltonian averaging estimates an eigenenergy by independently measuring Pauli terms and averaging their coefficient-weighted outcomes. It requires only O(1) coherence after each state preparation but has an O(M^6) worst-case scaling under the stated locality assumptions.
Hamiltonian averaging
- Hamiltonian averaging obtains the energy from independent Pauli measurements of the transformed Hamiltonian on the supplied eigenstate.Measurement outcomes are weighted by the transformed Hamiltonian coefficients and averaged.Source: Hamiltonian averaging · p. 8
- The sample count is set by the variance required to achieve statistical accuracy ϵ, with each independent sample measuring all Nint quantities.The total cost counts state preparations and measurements.Source: Hamiltonian averaging · p. 9
- O(M^6) is the large-size Hamiltonian-averaging scaling in spin-orbital basis functions under the maximum-error assumptions.This is only marginally worse in integrals and precision than first-order Suzuki–Trotter phase estimation.Source: Hamiltonian averaging · p. 9
- Hamiltonian averaging needs only O(1) coherence time after each state preparation, making it suitable when coherence is limited and good eigenstate approximations are available.The paper notes that further studies are needed beyond worst-case bounds.Source: Hamiltonian averaging · p. 9
- Bravyi–Kitaev single-qubit measurement rotations scale as O(log M), compared with O(M) for Jordan–Wigner encoding.The estimate assumes these single-qubit rotations can be performed in parallel and therefore omits them from the cost.Source: Hamiltonian averaging · p. 9
USING IMPERFECT ORACLES
The section examines how imperfect trial states affect energy estimation, showing that Hamiltonian averaging has linear bias while QPE can remove bias only at potentially exponential repetition cost.
IMPERFECT ORACLES
- For N non-interacting two-level subsystems, Hamiltonian averaging produces an energy bias that grows linearly with system size N.The subsystem gap is denoted ω = (E_e − E_g).Source: USING IMPERFECT ORACLES · p. 10
- QPE removes the bias by projecting onto the exact ground state, but succeeds with probability proportional to the squared trial-state overlap.For product trial states, the relevant overlap probability is exponentially small in system size.Source: USING IMPERFECT ORACLES · p. 10
- The energy-bias distribution is analyzed by counting excited subsystems, yielding a binomial distribution that approaches a Gaussian for large N.The resulting probability of measuring bias below ϵ(M) is expressed using the error function.Source: USING IMPERFECT ORACLES · p. 10
- For any fixed imperfect subsystem guess with |∆| < 1, perfect bias removal by QPE has exponential cost in system size.The expected cost depends strongly on oracle quality and the fraction of bias removed.Source: Figure 3 · p. 10, USING IMPERFECT ORACLES · p. 11
- Improving |∆| as (1 − 1/(2N)) keeps |∆|2N at O(1), but preparing sufficiently accurate subsystem states may itself scale exponentially with precision and system size.Interacting subsystems are not expected to make this preparation problem easier, motivating variational, cooling, adiabatic, MCSCF, and UCC approaches [51].Source: USING IMPERFECT ORACLES · p. 11
ADIABATIC COMPUTATION
The adiabatic approach embeds molecular electronic-structure Hamiltonians into programmable 2-local systems using Bravyi–Kitaev mapping and perturbative gadgets. Its efficiency is supported by arguments and small-system studies concerning the minimum spectral gap.
ADIABATIC COMPUTATION
- Molecular Hamiltonians are mapped from second quantization to qubits with Bravyi–Kitaev, whereas Jordan–Wigner cannot scalably reduce them to 2-local interactions.Perturbative gadgets then produce a 2-local programmable system with restricted physical couplings.Source: ADIABATIC COMPUTATION · p. 11
- Adiabatic state preparation may be efficient if the excited-state gap shrinks only polynomially with the number of spin-orbitals.The argument relies on molecular ground-state stability and efficient simulation of the natural processes producing those states.Source: ADIABATIC COMPUTATION · p. 11
- For the studied small chemical systems, the minimum gap occurred at the end of evolution when initialization used a CAS ground state.The observed behavior and the HOMO–LUMO gap support the proposed gap-scaling hypothesis.Source: ADIABATIC COMPUTATION · p. 11
Resources for adiabatic quantum chemistry
The adiabatic formulation assumes experimentally viable problem Hamiltonians are 2-local and evaluates resources through qubits, couplings, field values, and perturbative-gadget accuracy.
Resources for adiabatic quantum chemistry
- Any 2-local Hamiltonian on n qubits is described using local fields and pairwise Pauli couplings, with resource demands determined by their nonzero terms.The analysis focuses on qubit couplings because local fields are comparatively straightforward to implement.Source: Resources for adiabatic quantum… · p. 11
- Perturbative gadget design trades effective-Hamiltonian error ϵ against coupling strength through the gadget spectral gap ∆.The gap is directly related to the largest Hamiltonian term.Source: Resources for adiabatic quantum… · p. 12
- A smaller gadget gap ∆ makes the Hamiltonian easier to implement but increases error in the effective Hamiltonian.Additional gadgets can enforce geometric or interaction constraints, generally requiring more ancilla qubits and stronger couplings.Source: Resources for adiabatic quantum… · p. 12
Estimates of qubit and coupler scaling
Bravyi–Kitaev provides logarithmic locality, enabling resource bounds for gadgetizing molecular Hamiltonians; under the stated worst-case assumptions, the resulting adiabatic construction has modest qubit and coupler requirements.
Estimates of qubit and coupler scaling
- Bravyi–Kitaev guarantees a logarithmic upper bound on Hamiltonian locality, with maximum locality O(log(M)) for M spin-orbitals.This bound is used to estimate the resources needed for 2-local gadgetization.Source: Estimates of qubit and coupler scaling · p. 12
- Using local bases and truncating small integrals can reduce the number of Bravyi–Kitaev terms relative to the general electronic-structure scaling.The transformation otherwise produces a number of terms scaling with the number of electronic integrals.Source: Estimates of qubit and coupler scaling · p. 12
- Bit-flip gadgets convert terms of logarithmic locality into ancilla systems, and the resulting ancilla count supplies an upper bound on total qubit requirements.Each ancilla system contains qubits matching the locality of its associated term.Source: Estimates of qubit and coupler scaling · p. 12
- The number of couplers is bounded by the fully connected ancilla systems required by the bit-flip gadgets.Under maximum-locality assumptions, the analysis concludes that the adiabatic approach has modest qubit and coupler requirements.Source: Estimates of qubit and coupler scaling · p. 12
Estimates of spectral gap scaling
Perturbative-gadget analysis bounds the spectral gap needed to reduce interaction locality, while revealing substantial implementation challenges for nontrivial molecular systems.
Spectral-gap bound
- The Bravyi–Kitaev transformation bounds interaction locality by k = O(log M), which determines the perturbative-gadget scaling of the required spectral gap.The analysis combines gadget parameters with the locality bound to derive the gap dependence.Source: Estimates of spectral gap scaling · p. 12
- The largest integral magnitude is bounded by γ ≤ |β_OEI|max M^2/3, supplying a further scale in the spectral-gap estimate.Source: Estimates of spectral gap scaling · p. 12
Limitations
- Because parallel gadgets cause cross-gadget contamination at high perturbative orders, the precise polynomial dependence of the gap on M^2 remains difficult to predict.The authors therefore report only a polynomial characterization without a precise exponent.Source: Estimates of spectral gap scaling · p. 12
Implementation implications
- The adiabatic approach requires coupler values spanning at least several orders of magnitude for non-trivial systems.This range is identified as the most significant implementation challenge for the adiabatic approach to quantum chemistry.Source: Estimates of spectral gap scaling · p. 12
Open questions
- Exact gadgets could eliminate the need for large spectral gaps, but known constructions fail for noncommuting terms in general.Exact reductions exist for selected Hamiltonian classes, including frustration-free constructions.Source: Estimates of spectral gap scaling · pp. 12–13
CONCLUSIONS
The conclusions assess locality-aware quantum chemistry across quantum phase estimation, Hamiltonian averaging, and adiabatic computation. Locality improves scaling and practical prospects, but the methods differ in coherence requirements and sensitivity to imperfect input states.
Quantum phase estimation
- Locality-aware first-order Suzuki–Trotter quantum phase estimation is expected to scale as O(M^5 log M), below earlier estimates of O(M^8)-O(M^9) and O(M^5.5)-O(M^6.5).The comparison is attributed to realistic physical locality rather than unphysical random integral distributions or too-small molecules.Source: CONCLUSIONS · p. 13
Hamiltonian averaging
- Hamiltonian averaging scales as O(M^6), adding overhead relative to quantum phase estimation but reducing coherence-time requirements and allowing all measurements in parallel.Source: CONCLUSIONS · p. 13
- Hamiltonian averaging returns the energy of the supplied state when oracle guesses are imperfect, whereas quantum phase estimation can remove this bias at a cost dependent on guess quality.Hamiltonian averaging can be combined with variational or adiabatic methods to improve the energy estimate.Source: CONCLUSIONS · p. 13
Adiabatic computation
- Adiabatic quantum computation has no known direct dependence on oracle guess quality and can provide state-oracle input for the other approaches.Source: CONCLUSIONS · p. 13
Overall conclusion
- Across these approaches, incorporating physical locality greatly improves the outlook for quantum chemistry on quantum computers.The authors argue that analyses should include locality because quantum chemistry targets physical systems rather than abstract constructs.Source: CONCLUSIONS · p. 13