A mainstay of classical ground state algorithms gets a quantum speedup
By William Kirby, Mario Motta, Antonio Mezzacapo, IBM Quantum
Estimating ground and excited energies of a quantum system is one of the most important applications for quantum computers. In challenging cases, classical methods for this task become impractical as the systems we’re trying to simulate grow, because of the exponential cost of classically representing their states. A new paper from IBM Quantum researchers takes on this challenge.
Since classical computation is a more mature field than quantum computation, a natural design principle for quantum algorithms is to consider how the properties of a quantum computer may be used to mitigate difficulties in existing classical algorithms. A case-in-point is quantum Krylov algorithms, which are based on (surprise) classical Krylov algorithms. The latter is a family of related methods for approximating ground state energies that began with the Lanczos method, published in 1950. The central idea of all Krylov methods, as applied to ground state energies, is to obtain a compressed approximation of the energy operator, called the Hamiltonian, by expressing it in a small subspace, called a Krylov space, of the full state space of the system.
By choosing this Krylov space judiciously, one can ensure that it contains a good approximation to the ground state. We can then find the ground state by brute force (i.e., exact diagonalization) since the subspace is small, typically of dimension less than one hundred. The original Lanczos method accomplished this with a subspace created by repeatedly multiplying some starting state by the Hamiltonian, which leads to an energy estimate that converges exponentially quickly with the number of multiplications.
The problem with this classical method is that performing those multiplications to calculate the subspace generally requires exponential time, and storing the resulting states requires exponential memory. Subsequent classical Krylov methods vary and improve on the details, but this core problem remains. On the other hand, a quantum computer may be used to store and evolve a quantum state, which suggests we could provide value by developing quantum algorithms that replace just this first component of the classical algorithms: the calculation of the subspace. The final problem of locating the approximate ground state within the subspace would still be solved classically.
This quantum-classical hybrid algorithm is very appealing for near-term quantum computers. It has a degree of resilience to both physical errors and statistical noise “built in,” since the final energy estimate is obtained classically by finding the lowest energy state in the subspace. A noisy estimate of the subspace, coming from a noisy quantum computer, thus has a layer of classical processing between it and the output energy, which can to some extent compensate for the noise.
This is reminiscent of the error resilience of the variational quantum eigensolver (VQE), another near-term quantum algorithm, which comes from the ability of the classical optimizer to partially compensate for errors by varying the control parameters. However, the marked advantage of quantum Krylov algorithms over VQE is that they require no optimization feedback loop from the classical computer back to the quantum processor. The quantum part of the algorithm simply runs once, and then the results are passed to the classical computer for transformation into an energy estimate. This in practice dramatically reduces the quantum runtime required for the algorithm.
Several quantum Krylov algorithms have been proposed over the last few years, with the majority focusing on creating the Krylov space from time-evolved states with the given Hamiltonian. These methods are especially appealing for existing quantum computers, since one can obtain crude approximations of time evolutions using low-depth quantum circuits (i.e., Trotterization).
However, while these methods are well-adapted to the very near term, in the medium term their downside is that simulated time evolutions on quantum computers are always approximate. Obtaining high accuracy requires high quantum circuit depth.
Hence, in a recent paper published in the open-access journal Quantum, IBM Quantum researchers proposed an alternative approach to the quantum part of a Krylov method. The approach is inspired by the observation that the most accurate quantum algorithms for simulating time evolution are based on an input model called a block encoding of the Hamiltonian. A Hamiltonian by itself is not a transformation that is physically possible to implement on a quantum computer, but it can be embedded as a block in a larger matrix that represents a physical transformation; this is a block encoding. While block encodings are required for the most accurate time evolutions, they can be used to generate the same Krylov space as used in the original Lanczos method directly and exactly, without ever needing to approximate time evolutions. The resulting circuits have shorter depth in general than those that would be required for the corresponding high-accuracy time evolutions, while simultaneously eliminating this source of error completely.
As in nearly all quantum algorithms, not all of the errors can be completely eliminated since quantum algorithms are ultimately stochastic. In the case of quantum Krylov algorithms, this stochasticity requires many repetitions of the quantum circuits to build up the estimate of the Krylov space. In the long term, non-Krylov algorithms like quantum phase estimation will likely be preferable, since the number of repetitions they require will be lower in the high-accuracy, large-system limit.
In short, these algorithms together form a hierarchy of successively more costly but more accurate methods for approximating ground state energies, as shown above.
In the immediate future, quantum Krylov algorithms based on time evolutions present an excellent option for initial demonstrations of ground state energy estimates. In the slightly longer term, the construction of Krylov spaces using block encodings may become a method of choice. Given currently known block encodings, that transition appears likely to occur in the early fault-tolerant regime, and will be the least costly application of block encodings once they become feasible. Finally, at some point we will become capable of implementing quantum phase estimation and similar methods, which we hope can carry us into the limits of high accuracy and large systems on future large-scale fault-tolerant quantum computers.
Works Cited:
[1] Cornelius Lanczos. “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators”. Journal of
Research of the National Bureau of Standards 45, №4 (1950).
[2] Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O’Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brandão, and Garnet Kin-Lic Chan. “Determining eigenstates and thermal states on a quantum computer
using quantum imaginary time evolution”. Nature Physics 16, 205–210 (2020).
[3] Robert M. Parrish and Peter L. McMahon. “Quantum filter diagonalization: Quantum eigendecomposition without
full quantum phase estimation” (2019). url: doi.org/10.48550/arXiv.1909.08925.
[4] Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista. “A multireference quantum Krylov algorithm for strongly correlated electrons”. Journal of Chemical Theory and Computation 16, 2236–2245 (2020).
[5] Jeffrey Cohn, Mario Motta, and Robert M. Parrish. “Quantum filter diagonalization with compressed double-factorized Hamiltonians”. PRX Quantum 2, 040352 (2021).
[6] Katherine Klymko, Carlos Mejuto-Zaera, Stephen J. Cotton, Filip Wudarski, Miroslav Urbanek, Diptarka Hait, Martin Head-Gordon, K. Birgitta Whaley, Jonathan Moussa, Nathan Wiebe, Wibe A. de Jong,
and Norm M. Tubman. “Real-time evolution for ultracompact Hamiltonian eigenstates on quantum hardware”. PRX Quantum 3, 020323 (2022).
[7] Kazuhiro Seki and Seiji Yunoki. “Quantum power method by a superposition of time-evolved states”. PRX Quantum 2, 010333 (2021).
[8] Cristian L. Cortes and Stephen K. Gray. “Quantum Krylov subspace algorithms for ground- and excited-state energy estimation”. Phys. Rev. A 105, 022417 (2022).
[9] Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. “A theory of quantum subspace diagonalization”. SIAM Journal on Matrix Analysis and Applications 43, 1263–1290 (2022).
[10] William Kirby, Mario Motta, and Antonio Mezzacapo. “Exact and efficient Lanczos method on a quantum computer”. Quantum 7, 1018 (2023).
