PaperlayerView exact revision on arXiv

Source-linked AI summary

Gate count estimates for performing quantum chemistry on small quantum computers

Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, Matthias Troyer

arXiv:1312.1695v3quant-phphysics.chem-ph

TL;DR

The paper asks whether small quantum computers can perform quantum chemistry beyond classical reach, and analyzes QFCI resource requirements for molecular ground-state energies. Using state preparation, Trotterized evolution, and phase estimation, it finds that gate demands grow far more severely than qubit demands, motivating algorithmic improvements.

  • Problem

    The paper examines whether small quantum computers can address electronic-structure problems beyond the reach of classical algorithms.

  • Method

    The paper analyzes QFCI at the circuit-element level, validates it against water’s FCI calculation, and estimates qubit, gate, and depth requirements.

  • Results

    The QFCI resource scaling is O(N^9) for serial gates and O(N^8) with parallel execution.

  • Takeaways & Limitations

    The paper concludes that useful quantum chemistry on small quantum computers will require drastic algorithmic improvements because the polynomial scaling and prefactors are very large.

Abstract

from arXiv · show

As quantum computing technology improves and quantum computers with a small but non-trivial number of N > 100 qubits appear feasible in the near future the question of possible applications of small quantum computers gains importance. One frequently mentioned application is Feynman's original proposal of simulating quantum systems, and in particular the electronic structure of molecules and materials. In this paper, we analyze the computational requirements for one of the standard algorithms to perform quantum chemistry on a quantum computer. We focus on the quantum resources required to find the ground state of a molecule twice as large as what current classical computers can solve exactly. We find that while such a problem requires about a ten-fold increase in the number of qubits over current technology, the required increase in the number of gates that can be coherently executed is many orders of magnitude larger. This suggests that for quantum computation to become useful for quantum chemistry problems, drastic algorithmic improvements will be needed.

I. INTRODUCTION

Quantum chemistry is a natural test of whether small quantum computers can address problems beyond classical reach. The paper evaluates the resources needed for such calculations and establishes scaling and baseline costs.

  • Motivation: Small quantum computers are motivated by the prospect of solving problems for which classical computers lack sufficient resources.Existing demonstrations, including factoring 15 and calculating a simple molecular energy, remain accessible to classical computers.
  • Classical boundary: Exact classical algorithms reach approximately N = 50 spin orbitals, while approximate methods are beginning to reach chemical accuracy for up to N = 70 spin orbitals.A useful quantum chemistry application therefore needs to target systems at least beyond the approximately N = 50 exact-classical threshold.
  • Application opportunity: Electronic structure may offer exponential speedups with fewer necessary qubits than factoring large integers, making it a candidate application for limited quantum hardware.Quantum chemistry also has potential technological benefits, including improved catalysts for industrial processes such as nitrogen fixation.
  • Paper scope: The paper focuses on measuring molecular electronic ground-state energies, using QFCI and comparing a water calculation with standard FCI.The water benchmark uses 10 electrons and 14 spin-orbitals in an STO-3G basis, and the study counts qubits, circuit elements, and circuit depth.
  • Resource scaling: O(N^9) serial and O(N^8) parallel gate scaling is derived by analyzing time-step errors and gate counts.Water is used to determine prefactors and establish a baseline for larger molecules.

II. THE COULOMB HAMILTONIAN IN QUANTUM CHEMISTRY

The electronic structure problem is formulated by fixing nuclear positions, choosing a single-particle basis, and expressing the molecular Hamiltonian in second-quantized form. The target quantities are the ground-state energy and wave function, with chemical accuracy requiring very fine energy resolution.

  • Problem formulation: The Born-Oppenheimer approximation fixes nuclear positions and reduces the molecular problem to the low-lying spectrum of electronic degrees of freedom.Full configuration interaction then requires selecting a single-particle orbital basis, such as STO-3G.
  • Basis and Hamiltonian: The chosen basis determines the number of orbitals included in the full configuration interaction calculation.Molecular orbitals are obtained through a Hartree-Fock calculation before rewriting the Hamiltonian in second-quantized form.
  • Target quantities: The paper targets the ground-state energy E0 and ground-state wave function |ψ0⟩ of the second-quantized Hamiltonian.The Hamiltonian is expressed using creation and annihilation operators for N spin orbitals.
  • Accuracy requirement: Chemical accuracy of approximately 1 milli-Hartree requires resolving molecular energy scales of roughly 100–1000 Hartree to one part in a million.These energy scales are set by atomic core energies for small molecules.
  • Classical methods: Classical treatments include exact FCI and systematically improvable approximate methods such as tensor networks, quantum Monte Carlo, and coupled cluster.The passage identifies these methods as current approaches to the electronic structure problem.

III. QUANTUM FULL CONFIGURATION INTERACTION ALGORITHM

The QFCI procedure prepares an approximate molecular ground state, evolves it with a Trotterized Hamiltonian, and uses quantum phase estimation to measure its energy. Resource requirements depend on gate cost, total evolution time, and Trotter-step size.

  • III. QUANTUM FULL CONFIGURATION INTERACTION ALGORITHM: For small molecules, the algorithm initializes qubits in a Hartree-Fock state with sufficiently high overlap with the ground state.For larger molecules, adiabatic evolution from the Hartree-Fock Hamiltonian toward the full Coulomb Hamiltonian can improve state preparation.
  • III. QUANTUM FULL CONFIGURATION INTERACTION ALGORITHM: Quantum phase estimation converts energy eigenstate components into binary-encoded energies and can collapse the prepared state to the ground state.The ground-state outcome occurs with probability proportional to the squared overlap with the ground-state wave function.
  • III. QUANTUM FULL CONFIGURATION INTERACTION ALGORITHM: The required evolution time is T = π/ϵ for absolute energy error ϵ, while total effort combines gates per Trotter step, evolution time, and the number of steps.For 1 milli-Hartree accuracy, the paper states T ≈ 6000 Eh^-1 and extrapolates water costs to classically intractable systems.
  • III. QUANTUM FULL CONFIGURATION INTERACTION ALGORITHM: Time evolution exp(−iHt) is implemented with one- and two-qubit gates, generally using a Trotter decomposition when no special structure enables more efficient evolution.Hamiltonian terms must be represented so each exp(−i∆thk) can be decomposed into standard gates.
  • III. QUANTUM FULL CONFIGURATION INTERACTION ALGORITHM: Higher-order Trotter decompositions reduce time-step error but increase the gate count per step, creating a resource trade-off.The effective Hamiltonian viewpoint treats time-step error as evolution under Heff = ln U(∆t)/(−i∆t).

IV. RESULTS – WATER

The water-molecule simulation validates QFCI against exact results and quantifies the Trotter-step, gate-count, and parallel-depth requirements for chemical accuracy.

  • Simulation setup: The simulation uses a minimal STO-3G basis with ten electrons in fourteen spin-orbitals, initialized from Hartree-Fock orbitals and validated against FCI.The implementation uses LIQUi|⟩ for circuit simulation.
  • Energy landscape: The calculated water-molecule energy is mapped over bond length and bond angle using the STO-3G basis.
  • Trotter accuracy: A Trotter time step of 0.01 E_h^-1 is required to achieve chemical accuracy.For most Hamiltonian-term orderings, first-order Trotter error behaves as O(∆t^2).
  • Trotter accuracy: Higher-order Trotter decomposition can reduce the number of steps, but its larger per-step gate overhead creates a trade-off.A fourth-order decomposition would permit ∆t = 0.1 E_h^-1 and reduce Trotter steps ten-fold based on error scaling, while increasing gates per step by a larger factor.
  • Resource estimation: The resource estimate counts circuit elements and parallel depth, including separate rotation counts and possible simultaneous execution on disjoint qubits.Jordan-Wigner strings increase off-diagonal-term gate counts by a factor of N, although proposed methods may improve this overhead.
  • Resource estimation: Approximately 6 · 10^5 Trotter steps and 10^10 serial gates are needed for chemical accuracy; parallel execution gives a factor-of-three speedup.For water, one Trotter step contains 20,494 sequential gates or 6,438 parallel gates.

V. SCALING TO LARGER MOLECULES

The paper extrapolates gate and Trotter-step requirements from water-molecule simulations to larger molecules, finding steep overall scaling and a sequential cost of approximately O(N^9).

  • Scaling quantities: The extrapolation tracks Ng, the gates required for one Trotter step, and ∆t, the Trotter time step.These quantities determine the circuit requirements for larger molecules.
  • Gate-count scaling: O(N^5) gate scaling is expected from O(N^4) Hamiltonian terms and roughly N gates per Jordan-Wigner-transformed term.This estimate assumes all gates have roughly equal cost; rotations scale at most as O(N^4).
  • Trotter-step scaling: The measured Trotter-step scaling is 1/∆t ∼ m, with fitted exponents 1.27 or 1.08 depending on the electron-to-orbital ratio.The empirical scaling is closer to m than the theoretical m^3/2 expectation.
  • Overall scaling: O(N^9) total scaling is found for sequential operation, better than the O(N^11) scaling from the most general bounds.The Fe2S2 example uses 112 spin orbitals, about eight times the H2O basis.

A. Quantum hardware requirements for classically-intractable molecules

The hardware analysis compares the qubits and coherent gate operations needed for Fe2S2 with current technology, finding that gate capacity is the dominant obstacle.

  • Gate requirements: 1018 gates are obtained as an upper bound for simulating Fe2S2, versus a few hundred gate operations supported by current technology.The comparison implies an improvement of more than 15 orders of magnitude is necessary.
  • Qubit requirements: About 100 qubits are required for Fe2S2, while current technology operates on about a dozen qubits.The qubit shortfall is approximately one order of magnitude.
  • Projected hardware progress: A gate-doubling rate of every 18 months would still imply 75 years to simulate Fe2S2 with the analyzed QFCI algorithm.This assumption also uses a clock speed of 1 GHz.
  • Physical implementation: The estimates are expressed in logical qubits and gate operations with perfect coherence and fidelity, rather than physical hardware resources.Physical implementations require error correction and multiple physical operations per logical gate.
  • Control-speed boundary: Quantum-computer speed is bounded by classical-control speed, which the paper considers unlikely to exceed tens of gigahertz in the foreseeable future.This constrains how much faster gate execution can become through clock-speed improvements.

VI. CONCLUSIONS

The conclusions assess whether roughly 100-qubit quantum computers can address classically intractable quantum-chemistry problems and find that QFCI’s polynomial scaling remains practically prohibitive.

  • VI. CONCLUSIONS: A quantum computer with on the order of 100 qubits could represent molecular wave functions with up to 100 spin orbitals, but QFCI has very large polynomial scaling and prefactors.Under reasonable assumptions about quantum-computing improvements, the classically intractable regime remains intractable.
  • VI. CONCLUSIONS: The paper argues that useful electronic-structure simulation is unlikely to be achieved through hardware improvements alone under even optimistic assumptions.It emphasizes the necessity of algorithmic advances.

A. The Path Forward

The paper examines algorithmic routes beyond naive QFCI, including higher-order Trotterization, fewer Hamiltonian terms, and alternative bases or simulation algorithms.

  • A. The Path Forward: Alternative sparse-Hamiltonian algorithms have asymptotically better bounds than naive Trotterization, but differing constants and non-tight bounds leave their practical advantage uncertain.The paper discusses quantum-walk and sparse-Hamiltonian approaches as possible alternatives.
  • A. The Path Forward: The paper considers incremental reductions in the scaling factors as another route toward making a QFCI variant tractable.This possibility is presented alongside entirely new algorithms and alternative representations.
  • A. The Path Forward: Higher-order Trotter decompositions can reduce the theoretical dependence on Hamiltonian terms from m^(1+1/2k) to m, but may add substantial overhead.The paper notes possible combined savings of order N^2 if higher-order decompositions become as cheap as second-order ones.
  • A. The Path Forward: The authors identify the need for many time steps as a central problem in the current approach.Potential remedies include error extrapolation and cancellation in observables of interest.
  • A. The Path Forward: Reducing the number of Hamiltonian terms or using a local basis could change complete-algorithm scaling from O(N^9) to O(N^5).In a local basis, the number of terms often scales as N^2 instead of N^4.

Appendix A: Scaling of Trotter time step with molecule size

The appendix estimates how Trotter time-step requirements scale with molecule size by numerically evaluating Trotter errors for generic molecules. It uses these estimates to determine the number of steps needed for a target accuracy.

  • Method: Trotter time steps are estimated by diagonalizing the Trotterized time-evolution unitary and extracting energies from its eigenvalues.For timestep Δt, energies are estimated from log(λ_i)/(−iΔt), corresponding to the energies measured by quantum phase estimation.
  • Scope: N = 24 spin orbitals is approximately the largest size studied because classical scaling and unitary-based energy estimation impose substantial computational overhead.The simulations generate molecules up to N = 24 while varying electron counts and Trotter timesteps.
  • Method: The required Trotter-step count is obtained from the empirically estimated error ε(Δt) at target accuracy ε_t.Ground-state energies are evaluated for multiple Δt values, producing the error estimate used to determine the required number of steps.
  • Results: The resulting scaling of the Trotter number with molecule size is empirically confirmed.

Appendix B: Improved Trotter-Suzuki Error Bounds and Ground State Energy Error

This appendix develops improved bounds for second-order Trotter-Suzuki errors and relates them to ground-state energy estimation. Exploiting the sparse commutation structure of quantum-chemistry Hamiltonians yields substantially better scaling than a naive series-expansion bound.

  • Trotter-Suzuki approximation: A second-order Trotter-Suzuki approximation symmetrically applies exponentials of Hamiltonian terms around the sequence midpoint.The displayed circuit implements the terms in forward and reverse order, with half timesteps at the sequence boundaries.
  • Naive bound: The usual bound gives error O((mΛΔt)^3), requiring a Trotter number scaling as m^3/2 for fixed evolution time and small error.Here m is the number of Hamiltonian terms and Λ bounds their norms.
  • Ground-state energy error: Ground-state energy error is obtained from the eigenvalue difference between exact and Trotterized evolution operators, rather than by accumulating phase-estimation evolution error linearly.For sufficiently short timesteps, the relevant eigenvalues lie near 1, allowing the energy error to be inferred directly.
  • Improved bound: K = O(N^3) and m = O(N^4) for the quantum-chemistry Hamiltonian, so O(N^5) Trotter steps suffice for small error.K counts the maximum number of terms that fail to commute with any given term; exploiting vanishing commutators improves the scaling.
  • Naive bound: The naive series-expansion proof is valid only when mΛΔt is sufficiently small.Its higher-order expansion parameter remains mΛΔt, limiting the range where the bound can be established.
  • Higher-order bounds: For sixth-order Trotter-Suzuki with K = N^3 and m = N^4, the required Trotter number is expected to be sublinear in m.This higher-order conclusion is stated as an expectation based on the proposed general error form.

Appendix C: Coalescing

The coalescing approach reduces gate counts by applying small Hamiltonian terms with larger Trotter steps and grouping similar near-identity operations. This saving trades against additional discretization error from reordering terms.

  • Conclusion: The paper concludes that algorithmic improvements are needed to make quantum chemistry practical on quantum computers.Coalescing is presented as one potential improvement, but its usefulness depends on the error-versus-gate-count trade-off.
  • Motivation: Small off-diagonal Hartree-Fock matrix elements can use larger Trotter timesteps, reducing the number of circuits applied.The approach targets terms whose coefficients are small in the Hartree-Fock basis.
  • Gate reduction: Grouping identical terms close to the identity allows them to be executed together, lowering the total gate count.The grouping is based on small Hamiltonian coefficients in the Hartree-Fock basis.
  • Trade-off: Changing the order of terms introduces additional discretization error and may require smaller Trotter steps to preserve total accuracy.The best balance depends sensitively on the distribution of Hamiltonian terms and is not analyzed in detail here.
  • Bucket construction: Hamiltonian terms are divided into magnitude-ordered buckets, with larger terms executed more frequently than later, smaller-term buckets.Each term belongs to exactly one bucket, and bucket 1 contains the largest terms.
  • Construction: The scheme approximates exp(−iHt) by recursively combining approximations for partial sums of bucketed Hamiltonian terms.The construction proceeds inductively from one bucket to the next, producing approximations V_a to the corresponding partial evolutions.
  • Trade-off: Interactions between buckets can weaken denominator-based error suppression, although small later-bucket terms can suppress these contributions.The interaction terms are at most second order in T_1 and at least first order in S_a.

Appendix D: Circuits

Appendix D presents circuit representations for Hamiltonian terms after mapping fermionic operators to Pauli-spin operations. The circuits use basis changes where needed and can be parameterized for larger molecules.

  • Jordan-Wigner transformation expresses fermionic operators using Pauli spin operators while preserving commutation relations by entangling spin-orbitals.
  • Hadamard and Y/Y† operations flip between σx or σy bases and the σz basis before and after propagator execution.
  • Figures 5–8 show circuits for the Hamiltonian terms, with θ set by term strengths computed using PyQuante and a Restricted Hartree-Fock model.
  • The displayed circuits can be parameterized to estimate expected resource usage for substantially larger molecules.
Loading 1312.1695v3…