We collect 20 papers which state exponential quantum advantage for ground-state quantum chemistry. We classify them into three categories.
Papers that explicitly state that ground-state computation (“electronic structure”) is exponentially spedup on quantum computers
Papers that state that quantum chemistry or obtaining energies is exponentially spedup on quantum computers, which then go on to discuss the ground-state problem
Papers that state that quantum phase estimation allows for exponential speedup for energies, then discuss the ground-state problem without discussing state preparation
Papers that explicitly state that ground-state computation (“electronic structure”) is exponentially spedup on quantum computers
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. Hu, D. Lv, M. 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.
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. Lanyon, J. Whitfield, G. Gillett, M. Goggin, M. Almeida, I. Kassal, J. Biamonte, M. Mohseni, B. Powell, M. Barbieri, others
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. Graham, Y. Song, J. Scott, C. Poole, L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinkemeyer, others
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. Alderete, H. Apel, A. Cowtan, A. Patterson, D. Ramo, Y. Zhu, N. Nguyen, others
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.
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).
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. 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. Jordan, P. 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.
Papers that state that quantum chemistry or obtaining energies is exponentially spedup on quantum computers, which then go on to discuss the ground-state problem
H. Wang, S. Kais, A. Aspuru-Guzik, M. Hoffmann
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.
How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?
V. Elfving, B. Broer, M. Webber, J. Gavartin, M. Halls, K. 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. Ollitrault, P. 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.
L. Ratini, C. Capecci, F. Benfenati, L. Guidoni
Computational quantum chemistry is among the most promising applications that quantum computers will be able to tackle in coming years. As an example, proof-of-concept calculations solving the time independent Schrödinger equation for small molecular systems has paved the way for the development of robust and efficient algorithms that can exploit the exponential speedup offered by quantum coprocessors. … The ground state energy is estimated using the variational principle by measuring expectation values of the Pauli strings on a parametrized quantum circuit, i.e., wave function ansatz.
Papers that state that quantum phase estimation allows for exponential speedup for energies, then discuss the ground-state problem without discussing state preparation
Orthogonal State Reduction Variational Eigensolver for the Excited-State Calculations on Quantum Computers
Q. 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.
A. Peruzzo, J. McClean, P. Shadbolt, M. Yung, X. Zhou, P. Love, A. Aspuru-Guzik, J. O’brien
Recent developments in the field of quantum computation offer a way forward for determining efficient solutions of many instances of large eigenvalue problems that are classically intractable. Quantum approaches to finding eigenvalues have previously relied on the quantum phase estimation (QPE) algorithm. The QPE algorithm offers an exponential speedup over classical methods and requires a number of quantum operations O(p^-1) to obtain an estimate with precision p. Moreover, this scaling will also reflect the number of state preparation repetitions required, whereas in QPE the number of state preparation steps is constant. In essence, we dramatically reduce the coherence time requirement while maintaining an exponential advantage over the classical case, by adding a polynomial number of repetitions with respect to QPE.
J. Liu, L. Wan, Z. Li, J. Yang
The QPE and VQE algorithms are two leading quantum algorithms for solving electronic structure problems on a quantum computer. The standard QPE algorithm evolves in time a quantum state under the Hamiltonian Ĥ of interest, which offers an exponential speedup for determining the molecular spectra over classical methods.
Quantum simulation of resonant transitions for solving the eigenproblem of an effective water Hamiltonian
Z. Li, X. Liu, H. Wang, S. Ashhab, J. Cui, H. Chen, X. Peng, J. Du
For instance, the quantum phase estimation algorithm (PEA), which can be used to obtain some eigenvalues of a Hamiltonian with exponential speedup over classical algorithms, has been implemented to determine the ground-state energy of the hydrogen molecule. The success probability of the PEA depends on the overlap between the trial state and the desired energy eigenstate. The initial guess of the wave function is usually based on either polynomial-scaling classical ab initio methods or the output of the adiabatic state preparation method.
H. Burton, D. Marti-Dafcik, D. Tew, D. 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.
Characterizing the performance effect of trials and rotations in applications that use Quantum Phase Estimation
S. Patil, A. JavadiAbhari, C. Chiang, J. Heckey, M. Martonosi, F. Chong
Quantum Phase Estimation (QPE) is one of the key techniques used in quantum computation to design quantum algorithms which can be exponentially faster than classical algorithms. … Simulation algorithms, such as Ground State Estimation (GSE) for quantum chemistry, also use QPE.