This repository collects some representative papers in relation to the article, "Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry" by Seunghoon Lee et al. We created this list in response to a reviewer's comment that they were not aware of any claims of exponential quantum advantage (EQA) in quantum chemistry in the literature. The purpose of the list is not to criticize the papers or authors below in any way, but rather simply to provide a few examples that show where and in what sense these statements exist in the literature.
Note that the set below is only representative; many more such papers exist with alternative authors. Also some of the papers below are very highly cited in journals with broad audiences, others are less so, or may be in more specialized journals; our intent is to simply sample the literature out there.
While some papers contain quite direct statements about EQA for ground-state chemistry, others have more indirect statements or assumptions, which might reasonably be interpreted by a reader to mean that EQA is implied. We discuss this in more detail with each reference.
In these papers, there is generally some statement that obtaining the exact ground-state classically is exponentially expensive AND a statement that quantum computation for the same task is exponentially faster.
Orthogonal State Reduction Variational Eigensolver for the Excited-State Calculations on Quantum Computers
Q. X. Xie, S. Liu, Y. Zhao
Some progress has been achieved in calculating the ground-state energies of molecules. The quantum phase estimation (QPE) algorithm has been shown to bring about exponential speedup over the currently best classical algorithms for determining the ground states of a given Hamiltonian.
J. Lee, W. J. Huggins, M. Head-Gordon, K. B. Whaley
It was shown early on that quantum phase estimation (QPE) provides an exponential speed-up over the best “currently” known classical algorithms for determining the ground state of the molecular Hamiltonian.
D. Lu, B. Xu, N. Xu, Z. Li, H. Chen, X. Peng, R. Xu, J. Du
This is the same situation as in quantum chemistry, where given a time-independent Hamiltonian of a molecule, the first task is to calculate the ground state energy, i.e., the lowest eigenvalue of the Hamiltonian. In classical computers, it is a non-deterministic polynomial (NP) problem. All known classical algorithms for it require exponential time. On the other hand, quantum algorithm or quantum simulation is theoretically proved to be able to solve this problem efficiently, in polynomial time.
Progress toward larger molecular simulation on a quantum computer: Simulating a system with up to 28 qubits accelerated by point-group symmetry
C. Cao, J. Hu, W. Zhang, X. Xu, D. Chen, F. Yu, J. Li, H. S. Hu, D. Lv, M. H. Yung
The exact evaluation of the molecular ground state in quantum chemistry requires an exponentially increasing computational cost. Quantum computation is a promising way to overcome the exponential problem using polynomial-time quantum algorithms.
Papers that state that electronic structure and/or full configuration interaction/exact diagonalization/computation of exact energies is exponentially spedup on quantum computers
These papers have the characteristics that (i) the main application discussed is ground-state electronic structure, and (ii) there are statements that quantum computers (may) exponentially speedup electronic structure/computation of exact energies/full configuration interaction/many-body simulations, without explicitly referencing exponential speedup for ground state electronic structure/exact ground-state energies/ground-state full configuration interaction/ground-state many-body simulations. For example, a prototype of such a statement might be "exact computation of the ground-state energy is exponentially hard classically; quantum phase estimation allows exact energies to be obtained in polynomial time". Because of the juxtaposition of these comments, and because of the emphasis of the papers on (i), one might assume EQA for ground-states is implied.
M. Reiher, N. Wiebe, K. Svore, D. Wecker, M. Troyer
The promise of exponential speedups for the electronic structure problem has led many to suspect that quantum computers will one day revolutionize chemistry and materials science.
B. Senjean, S. Yalouz, M. Saubanère
One of the nearest-term application of quantum computers is quantum chemistry, where the focus is on wavefunction theory (WFT) that targets a numerically exact solution of the electronic structure problem. While quantum phase estimation (QPE) algorithms are in principle capable of solving the problem in its entirety ... However, despite the exponential speed-up announced by quantum computers, it remains ... The full configuration interaction (FCI) method – equivalent to exact diagonalization – scales exponentially with respect to the system size, and an exponential speed-up is given by the KSDFT formalism or by employing quantum computers (QFCI).
B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri, A. Aspuru-Guzik, A. G. White
Exact first-principles calculations of molecular properties are currently intractable because their computational cost grows exponentially with both the number of atoms and basis set size. A solution is to move to a radically different model of computing by building a quantum computer, which is a device that uses quantum systems themselves to store and process data ... It has been proposed that a quantum computer can simulate many-body physical quantum systems (such as molecules) and calculate their energies to a fixed accuracy with a number of quantum computational resources that increases only polynomially with the number of particles.
T. M. Graham, Y. Song, J. Scott, C. Poole, L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinkemeyer, M. Kwon, M. Ebert, J. Cherek, M. T. Lichtman, M. Gillette, J. Gilbert, D. Bowman, T. Ballance, C. Campbel, E. D. Dahl, O. Crawford, N. S. Blunt, B. Rogers, T. Noel, M. Saffman
The time required for a complete classical calculation of molecular energies scales exponentially with the number of electronic orbitals. However, quantum phase estimation allows polynomial time energy estimates.
I. Rungger, N. Fitzpatrick, H. Chen, C. H. Alderete, H. Apel, A. Cowtan, A. Patterson, D. M. Ramo, Y. Zhu, N. H. Nguyen, E. Grant, S. Chretien, L. Wossnig, N. M. Linke, R. Duncan
The computationally challenging part arises from solving the effective problem of an interacting impurity coupled to a bath, which scales exponentially with system size on conventional computers. An exponential speedup is expected on quantum computers.
An efficient adaptive variational quantum solver of the Schrödinger equation based on reduced density matrices
J. Liu, Z. Li, J. Yang
The electronic structure problem is one of the most appealing applications of quantum computing. To simulate the electronic structure properties of molecules and solids, quantum algorithms, such as quantum phase estimation (QPE) and variational quantum eigensolver (VQE) had been proposed for solving the Schrödinger equation on quantum hardware. Quantum algorithms offer a potentially exponential speedup of simulating many-electron systems over classical methods.
P. Gokhale, O. Angiuli, Y. Ding, K. Gui, T. Tomesh, M. Suchara, M. Martonosi, F. T. Chong
Quantum computational chemistry has been a long targeted problem on the classical computer. Due to the limits of classical computing resources ... The way to achieve chemical accuracy (1 kcal/mol) is to use full configuration interactions (CIs), which considers all necessary orbitals. Classically, this will generally require exponential runtime. On the other hand, quantum computation is able to encode an exponential amount of molecular information into a polynomial number of qubits and thereby achieve full CI in polynomial time.
I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, A. Aspuru-Guzik
An alternative way to compute a potential energy surface would be to embed an on-the-fly calculation of electronic structure in the quantum algorithm and thus avoid a classically precomputed fit. This can be done efficiently because electronic structure calculations can be performed in polynomial time on quantum computers. Hence, the quantum circuit 𝒱 would be replaced by a black box containing the efficient quantum version of the full configuration interaction (FCI) procedure.
How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?
V. E. Elfving, B. W. Broer, M. Webber, J. Gavartin, M. D. Halls, K. P. Lorton, A. Bochevarov
Even though an exponential speedup of quantum chemical calculations is theoretically expected on quantum hardware, a significant obstacle to consider is the enormous prefactor to the polynomial runtime of quantum computational algorithms.
L. Veis, J. Pittner
It was shown in [Aspuru-Guzik et al., Science 309, 1704 (2005)] that they, if available, would be able to perform the full configuration interaction (FCI) energy calculations with a polynomial scaling. This is in contrast to conventional computers where FCI scales exponentially.
G. Mazzola, P. J. Ollitrault, P. K. I. Barkoutsos, I. Tavernelli
Solving quantum many-body and electronic structure problems is one of the most anticipated applications of quantum computers, in view of the exponential speed-up that can be achieved compared to classical simulations ... The accuracy of this approach is demonstrated numerically in finding energies of entangled ground states of many-body lattice models.
J. Liu, L. Wan, Z. Li, J. Yang
Simulating a quantum system is more efficient on a quantum computer than on a classical computer. The time required for solving the Schrödinger equation to obtain molecular energies has been demonstrated to scale polynomially with system size on a quantum computer, in contrast to the well-known result of exponential scaling on a classical computer.
H. G. A. Burton, D. Marti-Dafcik, D. P. Tew, D. J. Wales
Quantum computers promise to revolutionise electronic simulations by overcoming the exponential scaling of many-electron problems ... Highly accurate numerical simulations on strongly correlated molecules, including water and molecular nitrogen, and the condensed-matter Hubbard model, demonstrate that our algorithm reliably advances the state-of-the-art, defining a new paradigm for quantum simulations featuring strong electron correlation.
I. G. Ryabinkin, T. C. Yen, S. N. Genin, A. F. Izmaylov
Computational cost of the exact numerical solution of eq 1 scales exponentially with the size (e.g., the number of electrons) of the system on a classical computer. To address this issue without introducing approximations, it was proposed to employ a quantum computer, which may solve the problem with polynomial scaling of computational cost with the system size.
V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Reiher, M. Roetteler, M. Troyer
Quantum computing has the potential to efficiently solve some computational problems that are exponentially hard to solve on classical computers. Among these problems, one of the most prominent cases is the calculation of quantum electronic energies in molecular systems.
Quantum chemistry on quantum computers: A method for preparation of multiconfigurational wave functions on quantum computers without performing post-hartree-fock calculations
K. Sugisaki, S. Nakazawa, K. Toyota, K. Sato, D. Shiomi, T. Takui
Computational time of the full-CI on classical computers scales exponentially against the system size, and it is an intractable problem to deal with even small molecules; however, time scaling becomes polynomial on quantum computers.
A. J. McCaskey, Z. P. Parks, J. Jakowski, S. V. Moore, T. D. Morris, T. S. Humble, R. C. Pooser
The utility of this (quantum) algorithm has been demonstrated in a number of fields, including high-energy and nuclear physics in addition to quantum chemistry. Its success is primarily due to the reliance on finite classical computing resources in tandem with invocations of the quantum computer for exponentially scaling aspects of the problem … We implemented calculations of the ground state energies of each of these molecules using four qubits on the 20-qubit IBM Tokyo and 16-qubit Rigetti Aspen superconducting circuit devices.
H. Liu, G. H. Low, D. S. Steiger, T. Häner, M. Reiher, M. Troyer
Given that the exponentially scaling wall in FCI calculations can be overcome by quantum computing, we first discuss how quantum algorithms can deliver such exact energies (i.e., eigenvalues of the FCI problem in a given orbital basis).
A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, M. Head-Gordon
The calculation time for the energy of atoms and molecules scales exponentially with system size on a classical computer but polynomially using quantum algorithms.
Quantum chemistry beyond Born–Oppenheimer approximation on a quantum computer: a simulated phase estimation study
L. Veis, J. Višňák, H. Nishizawa, H. Nakai, J. Pittner
This stems from the fact that the dimensionality of the Hilbert space needed for the description of a studied quantum system scales exponentially with its size. One of the consequences is, for example, the prohibitive exponential scaling of the full configuration interaction (FCI) method. Quantum computers, conversely, offer an exponential speed-up for this task
