arXiv_SI

# Is there evidence for exponential quantum advantage in quantum chemistry?

Seunghoon Lee  Division of Chemistry and Chemical Engineering, California
Institute of Technology, Pasadena, California 91125, USA  Joonho Lee
Department of Chemistry, Columbia University, New York, New York 10027, USA
Huanchen Zhai  Division of Chemistry and Chemical Engineering, California
Institute of Technology, Pasadena, California 91125, USA  Yu Tong  Department
of Mathematics, University of California, Berkeley, California 94720, USA
Alexander M. Dalzell  AWS Center for Quantum Computing, Pasadena, California
91125, USA  Ashutosh Kumar  Department of Chemistry, Virginia Tech,
Blacksburg, Virginia 24061, USA  Theoretical Division, Los Alamos National
Laboratory, Los Alamos, NM 87545, USA  Phillip Helms  Division of Chemistry
and Chemical Engineering, California Institute of Technology, Pasadena,
California 91125, USA  Johnnie Gray  Division of Chemistry and Chemical
Engineering, California Institute of Technology, Pasadena, California 91125,
USA  Zhi-Hao Cui  Division of Chemistry and Chemical Engineering, California
Institute of Technology, Pasadena, California 91125, USA  Wenyuan Liu
Division of Chemistry and Chemical Engineering, California Institute of
Technology, Pasadena, California 91125, USA  Michael Kastoryano  AWS Center
for Quantum Computing, Pasadena, California 91125, USA  Amazon Quantum
Solutions Lab, Seattle, Washington 98170, USA  Ryan Babbush  Google Quantum
AI, 340 Main Street, Venice, CA 90291, USA  John Preskill  Institute for
Quantum Information and Matter, California Institute of Technology, Pasadena,
California 91125, USA  AWS Center for Quantum Computing, Pasadena, California
91125, USA  David R. Reichman  Department of Chemistry, Columbia University,
New York, New York 10027, USA  Earl T. Campbell  Riverlane, Cambridge, UK
Edward F. Valeev  Department of Chemistry, Virginia Tech, Blacksburg, Virginia
24061, USA  Lin Lin  Department of Mathematics, University of California,
Berkeley, California 94720, USA  Computational Research Division, Lawrence
Berkeley National Laboratory, Berkeley, California 94720, USA  Garnet Kin-Lic
Chan<EMAIL_ADDRESS>Division of Chemistry and Chemical Engineering,
California Institute of Technology, Pasadena, California 91125, USA

###### Abstract

The idea to use quantum mechanical devices to simulate other quantum systems
is commonly ascribed to Feynman. Since the original suggestion, concrete
proposals have appeared for simulating molecular and materials chemistry
through quantum computation, as a potential “killer application” [1, 2, 3, 4,
5]. Indications of potential exponential quantum advantage in artificial tasks
[6, 7, 8, 9] have increased interest in this application, thus, it is critical
to understand the basis for potential exponential quantum advantage in quantum
chemistry. Here we gather the evidence for this case in the most common task
in quantum chemistry, namely, ground-state energy estimation. We conclude that
evidence for such an advantage across chemical space has yet to be found.
While quantum computers may still prove useful for quantum chemistry, it may
be prudent to assume exponential speedups are not generically available for
this problem.

##  1 Main

The most common task in quantum chemistry is computing the ground electronic
energy. The exponential quantum advantage hypothesis for this task is that for
a large set of relevant (“generic”) chemical problems, this may be completed
exponentially more quickly (as a function of system size) on a quantum versus
classical computer. Here we examine this hypothesis.

We proceed using numerical experiments supported by theoretical analysis.
Numerics is needed because while much theoretical analysis is known, its
relevance to problems of chemical interest is often unclear. To limit scope,
we focus on fault-tolerant quantum algorithms — the most advantageous setting
for quantum computing, not limited by noise or hardware. Rigorously, computing
the ground-state of even simple Hamiltonians can be exponentially hard on a
quantum computer [10]. However, such Hamiltonians might not be relevant to
generic chemistry, and thus the specific exponential quantum advantage (EQA)
hypothesis considered here, is that generic chemistry involves Hamiltonians
which are polynomially easy for quantum algorithms (with respect to ground-
state preparation) and simultaneously still exponentially hard classically,
even using the best classical heuristics. Numerically, we thus focus on the
evidence for quantum state preparation being exponentially easier than
classical heuristic solution in typical problems; and whether the cost of
classical heuristics in such problems scales exponentially with system size.

We stress that we do not attempt a rigorous proof or disproof of the EQA
hypothesis, or other classes of quantum advantage. Such proofs cannot be
obtained, not least because what is “generic” chemistry is not precisely
defined. Many components of the arguments in our work will not be strictly
new, and can be found individually in the body of knowledge of different
communities. However, here we will attempt a coherent examination of the
evidence for whether exponential quantum speedup for ground-state
determination in quantum chemistry should be considered likely in typical
cases of interest — or, instead, very fine-tuned.

##  2 Theoretical background

###  2.1 Statement of the problem

We compute the ground-state eigenvalue $E$ of the electronic Schrödinger
operator (Hamiltonian) of a chemical system discretized with a basis set, and
the problem size is the basis size $L$. We consider the case where increasing
$L$ corresponds to increasing physical system size (i.e. number of atoms) with
basis size proportional to system size (other scenarios are discussed in the
SI S1.1). The absolute ground-state energy $E$ increases with $L$, and in
physical problems we expect extensivity (i.e. $\lim_{L\to\infty}E(L)\propto L$
for a chemically uniform system); in this limit, the energy density
$\bar{E}=E/L$ may be the quantity of interest. Thus depending on the setting,
the relevant error can be $\epsilon$ (error in $E$) or $\bar{\epsilon}$ (error
in $\bar{E}$).

###  2.2 Fault tolerant quantum algorithms for ground-state quantum chemistry

Fault tolerant quantum algorithms are ones which employ deep circuits (e.g.
depth is a function of $1/\epsilon$). The most famous one in quantum chemistry
is quantum phase estimation (QPE) [11, 12]. We focus on QPE for simplicity;
qualitative features of the complexity remain similar in “post-QPE” algorithms
[13]. Phase estimation approximately measures the energy with approximate
projection onto an eigenstate. The cost has 3 components (i) preparing an
initial state $\Phi$, (ii) the phase estimation circuit, and (iii) the number
of repetitions (to produce the ground-state $\Psi_{0}$ rather than any
eigenstate). The cost to obtain $E$ to precision $\epsilon$ is

$\text{poly}{(}1/S)[\text{poly}{(}L)\text{poly}{(}1/\epsilon)+C]$ (1)

where $C$ corresponds to (i), $\text{poly}{(}L)\text{poly}{(}1/\epsilon)$
corresponds to (ii), and $\text{poly}{(}1/S)$ ($=1/S^{2}$ for QPE) with
$S=|\langle\Phi|\Psi_{0}\rangle|$ corresponds to (iii). We term $S$ overlap
and $S^{2}$ weight.

Motivated by the $\text{poly}{(}L)$ cost of (ii), and assuming an $\exp(L)$
cost for classical solution, it is often informally stated that QPE yields EQA
for the ground-state quantum chemistry task (see Sec. 6). However, the number
of repetitions ($\text{poly}{(}1/S)$) may also depend on $L$: this stems from
the quality of state preparation. For EQA, the cost arising from state
preparation must be exponentially less than the classical solution cost.

###  2.3 State preparation

####  2.3.1 Ansatz state preparation

We can prepare a state specified by an approximate classical ansatz. (We
assume once an ansatz solution is specified, it is easy to prepare on the
quantum device). Often, simple states, such as the Hartree-Fock or Kohn-Sham
ground-state (single Slater determinants) are considered in ansatz state
preparation, as they are hoped to have good overlap with $\Psi_{0}$ [14, 15];
the $\text{poly}{(}1/S)$ cost is then not further quantitatively considered.
But while good overlap with such simple states can be observed in small
molecules, EQA is an asymptotic statement, thus we should consider the limit
of large $L$.

The orthogonality catastrophe [16, 17] has previously been discussed in the
context of state preparation in the large $L$ limit [18]. For a set of $O(L)$
non-interacting subsystems, the global ground-state is the product of the
subsystem ground-states, thus if the local overlap between the approximate
classical ansatz and ground-state for each subsystem is $\sim s<1$, then the
global overlap is $s^{O(L)}$ i.e. it decreases exponentially. This is
sometimes viewed as an obstacle to ansatz state preparation, but in fact it
does not rule it out; we simply need to efficiently (here and elsewhere, we
use efficiently to mean in polynomial time) prepare states with a local
overlap that improves with $L$, such that the global overlap is
$1/\text{poly}{(}L)$ or better.

The relevant consideration for EQA however, is that if classical heuristics
can efficiently prepare states with such good overlap for large $L$ (for some
systems), they may also efficiently obtain the ground-state energy to the
desired precision. Establishing EQA additionally requires preparing states
with good overlap but which do not solve the problem, i.e. with poor energies.
Other combinations are problematic: for example, the ability to classically
prepare states with poor overlap but good energies suggests that it could be
efficient to classically solve for $E$.

####  2.3.2 Adiabatic state preparation (ASP)

Alternatively, we can evolve slowly from the ground-state of a solvable
initial Hamiltonian to that of the desired Hamiltonian [19, 20, 21, 12]. This
requires that the ground-state gap along the path be not too small; for paths
where the smallest minimum gap $\Delta_{\text{min}}\geq 1/\text{poly}{(}L)$
(which we will term “protected”), ASP plus QPE provides a polynomial cost
quantum algorithm. Since a protected gap is not guaranteed using an arbitrary
initial Hamiltonian and path, ASP is a heuristic quantum algorithm. Although
it is commonly conjectured that closing adiabatic gaps in physical problems
can be protected (e.g. at a critical point), it is not a generic property
(e.g. at certain first-order phase transitions that could arise between
competing phases). A problem that expresses the difficulty of finding a good
path is unstructured search, where $\Delta_{\text{min}}$ acquires a strong
dependence on the ground-state $\Upsilon_{0}$ of the initial Hamiltonian,
$\Delta_{\text{min}}\sim|\langle\Upsilon_{0}|\Psi_{0}\rangle|$ [22], yielding
exponential cost when using adiabatic algorithms. The key challenge for EQA is
whether interesting chemical problems allow for initial Hamiltonians and paths
with a protected gap to be easily found. If ASP is highly heuristic in typical
problems, requiring similar information as classical heuristics, it becomes
harder to reason about and argue for EQA.

###  2.4 The power of classical heuristics

“Exact” classical methods for ground state determination, such as exact
diagonalization, are exponentially expensive on a classical computer (see SI
S1.3). Thus the typical methods used in quantum chemistry are classical
heuristics, which come in a wide variety for different problems (see SI S1.2).
The critical questions for EQA are (i) do these heuristics require $\exp(L)$
cost for given $\epsilon$ or $\bar{\epsilon}$ in their application domain,
(ii) does the patchwork of heuristics cover chemical space, and (iii) if there
are gaps in coverage in practice, do we require classical methods of $\exp(L)$
cost to cover them?

EQA assumes exponential-scaling cost of classical heuristic algorithms for
given $\epsilon$ (or $\bar{\epsilon}$) across generic problems. We will
examine this assumption in our numerical experiments. However, as actually
employed in calculations, classical heuristics are often executed with
$\text{poly}{(}L)$ cost without necessarily achieving a specific accuracy,
complicating the comparison with rigorous quantum algorithms. Thus we will
also examine the empirical precision dependence of classical heuristics with
respect to $\epsilon$ or $\bar{\epsilon}$.

##  3 Numerical experiments

###  3.1 Fe-S clusters and metalloclusters of nitrogenase

Iron-sulfur (Fe-S) clusters are amongst the most common bioinorganic motifs in
Nature [23], and the Fe-S clusters of nitrogenase have become a poster child
problem for quantum chemistry on quantum devices [1, 24]. In the current
context, they provide a concrete setting to assess the EQA hypothesis, in
particular, the behaviour of quantum state preparation strategies.

Specifically, we consider iron-sulfur clusters containing 2, 4, 8 transition
metal atoms (the latter includes the famous FeMo-cofactor) in Figure 1. The 2,
4 metal clusters will be referred to as [2Fe-2S], [4Fe-4S] clusters, while the
8 metal clusters include the P-cluster (8Fe) and the FeMo-cofactor (7Fe, 1Mo).
We note that the P-cluster and FeMo-cofactor are the largest Fe-S clusters
found in Nature. We represent the electronic structure in active spaces with
Fe 3d/S 3p character constructed from Kohn-Sham orbitals. Within the
occupation number to qubit mapping, this corresponds to up to $40$ qubits
([2Fe-2S]), up to $72$ qubits ([4Fe-4S]), and up to $154$ qubits (P-cluster
and FeMo-co) (see SI S3.1). For [2Fe-2S], exact solutions can be obtained
using exact full configuration interaction (FCI). For all clusters, we obtain
a range of approximate solutions using the quantum chemistry density matrix
renormalization group (DMRG) [25, 26, 27, 28, 29] with a matrix product state
(MPS) bond dimension $D$; increasing $D$ improves the approximation, allowing
extrapolation to the exact result (see SI S3.3).Note that the classical
calculations in this section are of interest mainly to provide data to
understand quantum state preparation.

####  3.1.1 Nature of the ground-state and cost of ansatz state preparation

We first examine the nature of the ground-state $\Psi_{0}$ and the cost of
ansatz state preparation. For this, we compute the weight of a Slater
determinant $S^{2}=|\langle\Phi_{D}|\Psi_{0}\rangle|^{2}$, shown in Figure 1B.
$\Phi_{D}$ is parametrized by its orbitals $\\{\phi\\}$, and we choose a
priori, or optimize, $\\{\phi\\}$ to maximize this weight (for a best-case
scenario that uses information from the solution $\Psi_{0}$, see SI S3.4). The
weights decrease exponentially over a small number of metal centers, and are
already very small in FeMo-co ($\sim 10^{-7}$). The number of QPE repetitions
is $\text{poly}{(}1/S)$, yielding a large prefactor even for an “optimized”
Slater determinant.

Figure 1:  Ansatz state preparation and ansatz weights for model Fe-S
clusters. A, Structural models of [2Fe-2S], [4Fe-4S], P-cluster, and FeMo-co.
B, Weight of two different types of ansatz state: largest weight determinant
($\Phi_{D}$) (purple) and largest weight configuration state function
($\Phi_{\mathrm{CSF}}$) (orange) as a function of the number of metal centers
in each cluster (using split-localized orbitals). P${}^{\text{N}}$,
P${}^{\text{syn}}$, P${}^{\text{ox}}$ here refer to different oxidation states
of the metal ions in the P-cluster. Both types of ansatz state show an
exponential decrease in weight with the number of metal centers. For the
[2Fe-2S] clusters, we also show results for the largest weight determinant
using natural orbitals (empty symbols).

We next prepare more complex states with better overlap. We use a single
configuration state function (a linear combination of Slater determinants that
is an eigenfunction of total spin [30]). The weights improve but still show
exponential decay to small values.

These results indicate that the magnitude of the ansatz overlap can become a
relevant concern even in systems of modest size when using ansatz state
preparation. For any finite system, it may be possible to engineer a practical
quantum advantage for some target precision from a sufficiently good ansatz
overlap and a favourable ratio of classical and quantum costs. For example,
the systematic convergence of the variational energy of matrix product states
with increasing bond dimension in the Fe-S clusters suggests that they may be
good candidates here. However, the rapid decay of weights of the standard
classical heuristics illustrates the challenge of establishing EQA. In
particular, the problem of finding a classical heuristic that efficiently
yields $1/\text{poly}{(}L)$ overlap but which cannot efficiently reach the
target precision remains.

####  3.1.2 Adiabatic state preparation

We next compute the ASP cost for a simplified $n_{\text{act}}=12$ active space
(24 qubit) [2Fe-2S] model (see SI S4.1). The path is a heuristic input, and we
use one which linearly interpolates the Hamiltonian $H(s)$ (with ground-state
$\Upsilon_{0}(s)$) between an initial Hamiltonian ($s=0$, with ground-state
$\Upsilon_{0}(0)$) and the true Hamiltonian ($s=1$, with ground-state
$\Upsilon_{0}(1)\equiv\Psi_{0}$); the path preserves spin symmetry. We
consider two families of $H(0)$; a set of mean-field Hamiltonians (with
different Slater determinant ground-states) and a set of interacting
Hamiltonians (these retain interactions among $q$ active spin-orbitals
(qubits), definitions in SI S4.2).

Tight bounds on the ASP time ($T_{\text{ASP}}$) are difficult to obtain (see
SI S1.5). However, we have verified that the adiabatic estimate
$T^{\text{est}}_{\text{ASP}}\sim\max_{s}\tau(s)$, with
$\tau(s)=|\langle\Upsilon_{0}(s)|dH(s)/ds|\Upsilon_{1}(s)\rangle|/\Delta^{2}(s)$
with $\Delta(s)$ the ground-state gap and $\Upsilon_{1}(s)$ the first excited
state of $H(s)$, is a reasonable estimate for the desired preparation fidelity
(here assumed 75% final weight) by carrying out time-dependent simulations of
ASP for simple instances to compute
$T_{\text{ASP}}/T^{\text{est}}_{\text{ASP}}$ (Figure 2B); for a range of
examples, this ratio is $O(1)$. Thus we use $T^{\text{est}}_{\text{ASP}}$ as
the ASP time below.

Figure 2C shows $T_{\text{ASP}}$ across the sets of $H(0)$; it varies over 8
orders of magnitude depending on the choice of $H(0)$. We see a trend
$1/(\min_{s}\Delta(s))\sim\text{poly}{(}1/|\langle\Upsilon_{0}|\Psi_{0}\rangle|)$
and thus
$T_{\text{ASP}}\sim\text{poly}{(}1/|\langle\Upsilon_{0}|\Psi_{0}\rangle|)$
reminiscent of unstructured search. The practical consequence is that an a
priori good choice of initial Hamiltonian is non-trivial; the mean-field
Hamiltonian with the lowest ground state energy gives a large
$T_{\text{ASP}}>T_{\text{QPE}}$ (an estimate of the total coherent QPE
evolution time for 90% confidence, $\epsilon$=$10^{-3}E_{h}$, see analysis in
Sec. S2.4), while out of the interacting $H(0)$’s, we need to include almost
all the interactions when diagonalizing $H(0)$ for the initial state (20 out
of 24 qubits) before $T_{\text{ASP}}<T_{\text{QPE}}$. Although these results
are for the smallest FeS cluster, the dependence of $T_{\text{ASP}}$ on $S$ is
problematic for EQA should it scale to larger interesting problems because
heuristics will be essential. Although such heuristics may be found, they
would need to be exponentially advantageous over classical heuristics for EQA.

Figure 2: Adiabatic state preparation for a model [2Fe-2S] cluster. A,
Structure and simplified active space model of [2Fe-2S] cluster. B, ASP time
and the adiabatic estimate. We see that the ratio
$T_{\mathrm{ASP}}/T^{\mathrm{est}}_{\mathrm{ASP}}$ is $O(1)$. C, Adiabatic
estimates ($T^{\mathrm{est}}_{\mathrm{ASP}}$) for two families of initial
Hamiltonians against the weight of the initial ground state ($\Upsilon_{0}$)
in the final ground state ($\Psi_{0}$)
($|\langle\Upsilon_{0}|\Psi_{0}\rangle|^{2})$, showing an inverse dependence
on the initial weight. The mean-field Hamiltonians are constructed to have
different Slater determinants as their ground-state, while the interacting
Hamiltonians contain the full electron interaction amongst $n_{\text{act}}$
orbitals. Additional discussion in SI S4 and S2.2.

###  3.2 The scaling of classical heuristics

The Fe-S cluster simulations raise questions as to whether high quality
quantum state preparation can be assumed to be exponentially easier than
classical heuristic solution. We now consider if classical heuristics in fact
display $\exp(L)$ cost for fixed $\epsilon$ or $\bar{\epsilon}$, as is
required to establish EQA. We do so by considering examples that arguably
represent much of chemical space, which are evidence of classical heuristics
scaling to large problems and high accuracy at polynomial cost for fixed
$\bar{\epsilon}$. (If the error scaling is $\text{poly}{(}1/\bar{\epsilon})$
independent of $L$, this further implies $\text{poly}{(}L)$ cost overhead to
achieve fixed $\epsilon$). We note that the calculations below represent only
a small slice of relevant evidence from classical calculations; related
calculations can be found in the literature, although our focus here is on
characterizing the calculations e.g. with respect to cost and precision in a
way useful for understanding EQA. Some further discussion of these systems and
other calculations relevant to EQA is in SI S2.5.

For “single-reference” chemical problems (see SI S5) coupled cluster (CC)
wavefunctions are often described as the gold-standard. The heuristic assumes
that correlations of many excitations can be factorized into clusters of fewer
excitations; if the maximal cluster excitation level is independent of $L$,
the cost is $\text{poly}{(}L)$ (assuming a non-exponential number of
iterations for solution) without guaranteed error. To establish the error
dependence, Figure 3A shows the empirical convergence of error as a function
of cost, consistent with $\text{poly}{(}1/\epsilon)$ scaling, for a small
molecule (N_2). By the extensivity of the coupled cluster wavefunction, this
translates to $\text{poly}{(}L)\text{poly}{(}1/\bar{\epsilon})$ cost for a gas
of non-interacting $\ce{N_{2}}$ molecules, and thus
$\text{poly}{(}L)\text{poly}{(}1/\epsilon)$ given the error convergence above.
We can take this as a conjectured complexity of coupled cluster in single-
reference problems. To practically test this scaling form on larger systems,
we introduce another heuristic. CC methods can be formulated to exploit
locality, a commonly observed and widely conjectured feature of physical
ground-states (including gapless systems, see SI S1.4). This yields the local
CC heuristic that has cost linear in $L$ in gapped systems [31, 32]. Figure 3B
illustrates the application of local CC to $n$-alkanes, a set of organic
molecules, with the associated computational timing. This suggests the cost is
$O(L)$, while the computed enthalpy of formation per carbon achieves constant
error versus experimental data, reflecting constant $\bar{\epsilon}$ as a
function of $L$, consistent with the conjectured complexity. Many biomolecules
are single-reference problems, allowing local coupled cluster methods to be
applied to protein-fragment-scale simulations (Figure 3C).

Figure 3:  Computational complexity of classical heuristics for molecular
systems. A, Energy error of a nitrogen molecule (equilibrium geometry) as a
function of the level of CC approximation, against a computational time
metric. Data taken from Ref. [33], time metric defined in SI S2.6. The
observed precision cost is like $\text{poly}{(}1/\epsilon)$. B, Cost of a
state-of-the-art reduced-scaling coupled cluster (CCSD(T)) implementation
scales nearly-linearly with the system size in gapped systems, as demonstrated
here for $n$-alkanes (CmH2m+2) with with $m=[20\ldots 120]$. Size-extensivity
of the coupled-cluster ansatz ensures constant error per system subunit, as
illustrated in the subfigure for the error of explicitly-correlated reduced-
scaling CCSD(T)[34] (see SI S5.1 for details) with respect to the available
experimental gas-phase enthalpy of formation in the standard state for
$n$-alkanes with $m=[2\ldots 20]$. C, Reduced-scaling CCSD(T) implementations
can be routinely applied to systems with thousands of electrons on a few
computer cores, as demonstrated here for a small fragment of photosystem II.
[35] Figure 4: Computational complexity of classical heuristics for models of
strongly correlated material systems. A, Relative energy error of a tensor
network (PEPS) with respect to system sizes $3^{3}$ to $10^{3}$ for the 3D
Heisenberg cube model with a bond dimension ($D$) of 4. In bottom panel: total
computational time in seconds, divided by number of sites, as a function of
system size, demonstrating $\text{poly}{(}L)$ (close to linear) computational
effort. B, Energy convergence of PEPS with respect to the bond dimension for
2D Hubbard models at half filling ($4\times 4$ lattice, in top panel) and the
challenging 1/8 doping point ($4\times 4$, $8\times 4$ and $16\times 4$
lattice, in bottom panel). The plots are consistent with
$1/\bar{\epsilon}\sim\text{poly}{(}D)$ with a weak dependence on $L$.

Strongly correlated materials (e.g. bulk analogs of the Fe-S clusters) remain
challenging to treat with ab initio quantum chemistry (although there has been
considerable progress in recent years [36, 37]). To obtain insight into the
computational complexity, it is more practical to study simpler models of
correlated materials (e.g. the Heisenberg and Hubbard models, often used to
study quantum magnets and high temperature superconductors [38, 39]). Many
methods can now access large parts of these model phase diagrams to reasonable
accuracy without $\exp(L)$ cost. The use of locality is common to several
heuristics for strongly correlated problems; tensor networks are an example of
such a class of heuristics and we examine illustrative applications below.
(Note that this is not an exhaustive study of tensor networks, nor of other
heuristics (such as quantum embedding); for additional discussion see SI
S2.5).

Figure 4 shows results from a tensor network ansatz [40], where the
expressiveness of the ansatz is controlled by the bond dimension $D$. The
contraction here is explicitly performed with $\text{poly}{(}D)$ (typically a
high polynomial) cost, thus for given $D$ (assuming the number of iterations
is not exponential in $D$ or $L$ (see SI S6)), the algorithm cost is
$\text{poly}{(}L)\text{poly}{(}D)$, without guaranteed error. $\bar{\epsilon}$
and computational cost are shown as a function of $L$ in the 3D cubic
Heisenberg model, and $\bar{\epsilon}$ as a function of $D$ and $L$ in the 2D
Hubbard model. (Note: these examples were chosen for ease of generating exact
data, rather than representing the limits of classical methods in size,
accuracy, or complexity of physics; see SI S2.5 for other examples). Figure 4A
shows that the cost is close to $O(L)$ in the 3D Heisenberg model for up to
1000 sites, while achieving close to constant $\bar{\epsilon}$. Less data is
available for the error scaling as accessible $D$ remain small; in particular
it is currently too expensive to reach large enough $D$ to meaningfully study
the $\bar{\epsilon}$ scaling in 3D. However in the 2D Hubbard model (Figure
4B) we see $\bar{\epsilon}\sim 1/\text{poly}{(}D)$ (or slightly better) across
a range of studied $D$, (with a weak dependence on $L$) even at the
challenging 1/8 doped point of the model. Assuming this error form holds
asymptotically, the observed empirical cost is
$\text{poly}{(}L)\text{poly}{(}D)\text{poly}{(}1/\bar{\epsilon})$, which
corresponds to $\text{poly}{(}L)\text{poly}{(}D)\text{poly}{(}1/\epsilon)$ for
the assumed error scaling, and we can conjecture that this holds also in 3D.

Although the Hubbard and Heisenberg models are believed to contain the basic
physics of many strongly correlated materials, moving from such simplified
models to more detailed quantum chemistry models (i.e. ab initio Hamiltonians)
will certainly increase complexity. But establishing EQA requires evidence
that adding the polynomial number of terms in the Hamiltonian causes the
classical heuristic to fail or become exponentially expensive. The history of
development of classical heuristics does not support this, as methods
originally developed on simpler models routinely graduate to ab initio
simulations. For example, the coupled cluster methods described above were
first developed for use in model simulations, as were simpler tensor networks
such as the density matrix renormalization group and tree tensor networks now
used in ab initio calculations [25, 41, 42]; Sec. S2.5 provides more
discussion of this point as well as shows the performance of a quantum
embedding heuristic for the 2D and 3D hydrogen lattices, ab initio analogs of
the 2D Hubbard and 3D Heisenberg systems in Fig. 4. Further examples in the
literature consider the application of many different classical heuristics to
ab initio or model chemical ground-states of complex systems including
strongly correlated materials [36, 37, 29, 43, 32, 34, 44, 39, 45]. Although
the computational complexity is not formally analyzed, the success of such
studies of large and complex problems is compatible with the view that the
ground-state quantum chemistry problem is often soluble with classical
heuristics, to an energy density error $\bar{\epsilon}$ relevant to physical
problems, with $\text{poly}{(}L)$ cost. Thus, while there are many chemistry
problems that cannot currently be addressed by classical methods, the barrier
to solution may be of polynomial (even if impractically large) rather than
exponential cost.

##  4 Conclusions

We have examined the case for the exponential quantum advantage (EQA)
hypothesis for the central task of ground-state determination in quantum
chemistry. The specific version of EQA that we examined required quantum state
preparation to be exponentially easy compared to classical heuristics, and for
classical heuristics to be exponentially hard. Our numerical simulations raise
questions about whether quantum state preparation can be assumed easy in many
problems without additional heuristics. We also do not find evidence for the
exponential scaling of classical heuristics in a broad set of relevant
systems, consistent with existing results in the literature. In practice, the
same features of generic chemical problems that enable classical heuristics
very likely enable efficient state preparation heuristics for QPE and related
algorithms. However, this is not sufficient for EQA.

Numerical calculations are not mathematical proof of asymptotics with respect
to size and error, nor can we exclude EQA in specific problems. However, our
results suggest that without new and fundamental insights, there may be a lack
of generic EQA in this task. Identifying a relevant quantum chemical system
with strong evidence of EQA remains an open question.

We did not consider tasks other than ground-state determination, nor do we
rule out polynomial speedups. Depending on the precise form, polynomial
speedups could be associated with useful quantum advantage. Both aspects may
prove important in the further development of quantum algorithms in quantum
chemistry. Finally, we collect some answers to frequently asked questions in
Sec. 6.

##  5 Acknowledgement

Work by SL, HZ, GKC was funded by the US Department of Energy, Office of
Science, via Award DE-SC0019374. Work by PH was funded by the Simons
Collaboration on the Many-Electron Problem, and support from the Simons
Investigator Award to GKC. Work by ZC was funded by the US Department of
Energy, Office of Science, via Award DE-SC0019390. Work by JP was funded by
the US Department of Energy, Office of Science, via Awards DE-NA0003525, DE-
SC0020290, and by the National Science Foundation via Award PHY-1733907. Work
by YT was funded by the US Department of Energy, Office of Science via Award
DE-SC0017867. Work by LL was funded by the National Science Foundation via
Award OMA-2016245, and by the Simons Investigator Award. Research by AK and EV
was funded by the US Department of Energy, Office of Science, via Award DE-
SC0019374, and the associated software development efforts were supported by
the US National Science Foundation via Award OAC-1550456. RB thanks members of
the Google Quantum AI team for helpful feedback on earlier drafts.

##  6 Frequently asked questions (FAQ)

  1. 1.

Are there any published papers which suggest exponential quantum advantage for
ground-state quantum chemistry? Statements of this kind can be found in
various settings, and range from direct statements of EQA for ground-state
problems, to more implicit statements where the expectation of EQA could
reasonably be inferred by the reader. Some representative papers and further
discussion can be found in Ref. [46].

  2. 2.

Does this mean that quantum computers are not useful for generic ground-state
quantum chemistry? Even if EQA is not found in the ground-state problem,
quantum computers may still be useful for this task, since polynomial
advantage (or even large constant factor advantage) can be very useful. In
such cases, the details (e.g. degree of polynomial, size of constant) for both
the classical heuristic and quantum algorithm are important. It is difficult
to tie generic statements about advantage to other characteristics, such as
strength of correlation; for example, in more strongly correlated systems,
state preparation must be more carefully considered due to possible competing
phases. However, in terms of assessing the suitability of ground-state quantum
chemistry as an early target application for quantum computers, one should
compare the degree of available polynomial advantage in quantum chemistry to
that in other applications.

  3. 3.

We do not have answers to a certain problem by classical heuristics, and exact
classical solution is exponentially expensive, doesn’t this mean that there
should be EQA? As our work indicates, this is a subtle question. First, one
can definitely construct artificial ground-state problems which, for certain
precision requirements, can be solved efficiently quantumly but not
classically. See e.g. SI S1.3 as well as Refs. [47, 48]. The open question
there is whether such problems are related to the generic molecules and
materials studied in quantum chemistry. Second, there are relevant chemical
problems which are too large to treat with current classical heuristics with
the desired precision. However, for EQA, one must establish that e.g. to reach
the desired precision, the classical heuristic requires exponential effort as
a function of system size, and also that quantum algorithms are capable of
reaching the desired precision without exponential effort.

  4. 4.

What about potential improvements to quantum algorithms? We cannot anticipate
future improvements to quantum algorithms, for example, in the area of quantum
heuristics. However, to change the situation regarding EQA it is critical for
an improvement to change the ratio of the quantum to classical costs. For
example, when introducing locality into a quantum heuristic, we should
understand whether classical heuristics that also use locality are efficient
for the same problems.

  5. 5.

What about other classes of problems such as quantum dynamics for chemical
systems? We cannot conclude anything about other simulation tasks based on
this work. However, we note that other tasks, such as the simulation of
chemical dynamics, may also be amenable to heuristics because of the
particular chemical setting and question of interest; for example, dynamics of
heavier atoms can often be treated classically, or certain phenomena may take
place with strong dissipation. Thus heuristics should always be carefully
considered in claims of EQA and other types of quantum advantage.

## References and Notes

  * [1] Reiher, M., Wiebe, N., Svore, K. M., Wecker, D. & Troyer, M.  Elucidating reaction mechanisms on quantum computers.  _Proceedings of the National Academy of Sciences_ 114, 7555–7560 (2017).
  * [2] https://cen.acs.org/articles/95/i43/Chemistry-quantum-computings-killer-app.html.
  * [3] Bauer, B., Bravyi, S., Motta, M. & Chan, G. K.-L.  Quantum algorithms for quantum chemistry and quantum materials science.  _Chemical Reviews_ 120, 12685–12717 (2020).
  * [4] Cao, Y. _et al._ Quantum chemistry in the age of quantum computing.  _Chemical reviews_ 119, 10856–10915 (2019).
  * [5] McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C. & Yuan, X.  Quantum computational chemistry.  _Reviews of Modern Physics_ 92, 015003 (2020).
  * [6] Arute, F. _et al._ Quantum supremacy using a programmable superconducting processor.  _Nature_ 574, 505–510 (2019).
  * [7] Zhong, H.-S. _et al._ Quantum computational advantage using photons.  _Science_ 370, 1460–1463 (2020).
  * [8] Wu, Y. _et al._ Strong quantum computational advantage using a superconducting quantum processor.  _Physical review letters_ 127, 180501 (2021).
  * [9] Hangleiter, D. & Eisert, J.  Computational advantage of quantum random sampling.  _arXiv preprint arXiv:2206.04079_ (2022).
  * [10] Kempe, J., Kitaev, A. & Regev, O.  The complexity of the local hamiltonian problem.  _Siam journal on computing_ 35, 1070–1097 (2006).
  * [11] Kitaev, A. Y.  Quantum measurements and the abelian stabilizer problem.  _arXiv preprint quant-ph/9511026_ (1995).
  * [12] Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. & Head-Gordon, M.  Simulated quantum computation of molecular energies.  _Science_ 309, 1704–1707 (2005).
  * [13] Lin, L. & Tong, Y.  Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers.  _arXiv preprint arXiv:2102.11340_ (2021).
  * [14] O’Brien, T. E., Tarasinski, B. & Terhal, B. M.  Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments.  _New Journal of Physics_ 21, 023022 (2019).
  * [15] O’Malley, P. J. _et al._ Scalable quantum simulation of molecular energies.  _Physical Review X_ 6, 031007 (2016).
  * [16] Kohn, W.  Nobel lecture: Electronic structure of matter—wave functions and density functionals.  _Reviews of Modern Physics_ 71, 1253 (1999).
  * [17] Chan, G. K.-L.  Low entanglement wavefunctions.  _Wiley Interdisciplinary Reviews: Computational Molecular Science_ 2, 907–920 (2012).
  * [18] McClean, J. R., Babbush, R., Love, P. J. & Aspuru-Guzik, A.  Exploiting locality in quantum computation for quantum chemistry.  _The journal of physical chemistry letters_ 5, 4368–4380 (2014).
  * [19] Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M.  Quantum computation by adiabatic evolution.  _arXiv preprint quant-ph/0001106_ (2000).
  * [20] Albash, T. & Lidar, D. A.  Adiabatic quantum computation.  _Reviews of Modern Physics_ 90, 015002 (2018).
  * [21] Veis, L. & Pittner, J.  Adiabatic state preparation study of methylene.  _The Journal of Chemical Physics_ 140, 214111 (2014).
  * [22] Roland, J. & Cerf, N. J.  Adiabatic quantum search algorithm for structured problems.  _Physical Review A_ 68, 062312 (2003).
  * [23] Beinert, H., Holm, R. H. & Münck, E.  Iron-sulfur clusters: nature’s modular, multipurpose structures.  _Science_ 277, 653–659 (1997).
  * [24] Li, Z., Li, J., Dattani, N. S., Umrigar, C. & Chan, G. K.-L.  The electronic complexity of the ground-state of the femo cofactor of nitrogenase as relevant to quantum simulations.  _The Journal of chemical physics_ 150, 024302 (2019).
  * [25] White, S. R. & Martin, R. L.  Ab initio quantum chemistry using the density matrix renormalization group.  _The Journal of chemical physics_ 110, 4127–4130 (1999).
  * [26] Chan, G. K.-L. & Sharma, S.  The density matrix renormalization group in quantum chemistry.  _Annual review of physical chemistry_ 62, 465–481 (2011).
  * [27] Baiardi, A. & Reiher, M.  The density matrix renormalization group in chemistry and molecular physics: Recent developments and new challenges.  _The Journal of Chemical Physics_ 152, 040903 (2020).
  * [28] Sharma, S., Sivalingam, K., Neese, F. & Chan, G. K.-L.  Low-energy spectrum of iron–sulfur clusters directly from many-particle quantum mechanics.  _Nature chemistry_ 6, 927–933 (2014).
  * [29] Li, Z., Guo, S., Sun, Q. & Chan, G. K.-L.  Electronic landscape of the p-cluster of nitrogenase as revealed through many-electron quantum wavefunction simulations.  _Nature chemistry_ 11, 1026–1033 (2019).
  * [30] Helgaker, T., Jorgensen, P. & Olsen, J.  _Molecular electronic-structure theory_ (John Wiley & Sons, 2014).
  * [31] Riplinger, C., Pinski, P., Becker, U., Valeev, E. F. & Neese, F.  Sparse maps—A systematic infrastructure for reduced-scaling electronic structure methods. II. Linear scaling domain based pair natural orbital coupled cluster theory.  _The Journal of chemical physics_ 144, 024109 (2016).
  * [32] Yang, J. _et al._ Ab initio determination of the crystalline benzene lattice energy to sub-kilojoule/mole accuracy.  _Science_ 345, 640–643 (2014).
  * [33] Chan, G. K.-L., Kállay, M. & Gauss, J.  State-of-the-art density matrix renormalization group and coupled cluster theory studies of the nitrogen binding curve.  _The Journal of chemical physics_ 121, 6110–6116 (2004).
  * [34] Kumar, A., Neese, F. & Valeev, E. F.  Explicitly correlated coupled cluster method for accurate treatment of open-shell molecules with hundreds of atoms.  _The Journal of chemical physics_ 153, 094105 (2020).
  * [35] Müh, F. & Zouni, A.  The nonheme iron in photosystem II.  _Photosynthesis Research_ 116, 295–314 (2013).
  * [36] Motta, M. _et al._ Towards the solution of the many-electron problem in real materials: Equation of state of the hydrogen chain with state-of-the-art many-body methods.  _Physical Review X_ 7, 031059 (2017).
  * [37] Cui, Z.-H., Zhai, H., Zhang, X. & Chan, G. K.  Systematic electronic structure in the cuprate parent state from quantum many-body simulations.  _arXiv preprint arXiv:2112.09735_ (2021).
  * [38] Arovas, D. P., Berg, E., Kivelson, S. & Raghu, S.  The hubbard model.  _arXiv preprint arXiv:2103.12097_ (2021).
  * [39] Zheng, B.-X. _et al._ Stripe order in the underdoped region of the two-dimensional hubbard model.  _Science_ 358, 1155–1160 (2017).
  * [40] Orús, R.  Tensor networks for complex quantum systems.  _Nature Reviews Physics_ 1, 538–550 (2019).
  * [41] Nakatani, N. & Chan, G. K.-L.  Efficient tree tensor network states (ttns) for quantum chemistry: Generalizations of the density matrix renormalization group algorithm.  _The Journal of chemical physics_ 138, 134113 (2013).
  * [42] Mayhall, N. J.  Using higher-order singular value decomposition to define weakly coupled and strongly correlated clusters: The n-body tucker approximation.  _Journal of Chemical Theory and Computation_ 13, 4818–4828 (2017).
  * [43] Williams, K. T. _et al._ Direct comparison of many-body methods for realistic electronic hamiltonians.  _Physical Review X_ 10, 011041 (2020).
  * [44] Brandenburg, J. G. _et al._ Physisorption of water on graphene: Subchemical accuracy from many-body electronic structure methods.  _The journal of physical chemistry letters_ 10, 358–368 (2019).
  * [45] Qin, M. _et al._ Absence of superconductivity in the pure two-dimensional hubbard model.  _Physical Review X_ 10, 031016 (2020).
  * [46] Papers which suggest exponential quantum advantage for ground-state quantum chemistry are collected in the github repository.  https://github.com/seunghoonlee89/Refs_EQA_GSQC.
  * [47] Gharibian, S. & Gall, F. L.  Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum pcp conjecture.  _arXiv preprint arXiv:2111.09079_ (2021).
  * [48] Cade, C., Folkertsma, M. & Weggemans, J.  Complexity of the guided local hamiltonian problem: Improved parameters and extension to excited states.  _arXiv preprint arXiv:2207.10097_ (2022).

See pages - of figure/figs_for_manuscript/initial_submission/arXiv_SI.pdf