Finding ground states of quantum many-body systems is one of the most important---and one of the most notoriously difficult---problems in physics, both in scientific research and in practical applications.  Indeed, we know from a complexity-theoretic perspective that all methods  (quantum or classical) must necessarily fail to find the ground state efficiently in general. The ground state energy problem is already NP-hard even for classical, frustration-free, local Hamiltonians with constant spectral gap. For general quantum Hamiltonians, the problem becomes QMA-hard.

Nonetheless, as ground state problems are of such importance, and classical algorithms are often successful despite the theoretical exponential worst-case complexity, a number of quantum algorithms for the ground state problem have been proposed and studied. From quantum phase estimation-based methods, to adiabatic state preparation, to dissipative state engineering, to the variation quantum eigensolver (VQE), to quantum/probabilistic imaginary-time evolution (QITE/PITE).

Dissipative state engineering was first introduced in 2009 by Verstraete, Cirac and Wolf and by Kraus et al. However, it only works for the restricted class of frustration-free Hamiltonians.

In this talk, I will show how to construct a dissipative state preparation dynamics that provably produces the correct ground state for arbitrary Hamiltonians, including frustrated ones. This leads to a new quantum algorithm for preparing ground states: the Dissipative Quantum Eigensolver (DQE). DQE has a number of interesting advantages over previous ground state preparation algorithms:

  • The entire algorithm consists simply of iterating the same set of   simple local measurements repeatedly.
  • The expected overlap with the ground state increases monotonically with the length of time this process is allowed to run.
  • It converges to the ground state subspace unconditionally, without any assumptions on or prior information about the Hamiltonian (such as spectral gap or ground state energy bound).
  • The algorithm does not require any variational optimisation over parameters.
  • It is often able to find the ground state in low circuit depth in practice.
  • It has a simple implementation on certain types of quantum hardware, in particular photonic quantum computers.
  • It is immune to errors in the initial state.
  • It is inherently fault-resilient, without incurring any fault-tolerance overhead. I.e.\ not only is it resilient to errors on the quantum state, but also to faulty implementations of the algorithm itself; the overlap of the output with the ground state subspace degrades smoothly with the error rate, independent of the total run-time.

I give a mathematically rigorous analysis of the DQE algorithm and proofs of all the above properties, using non-commutative generalisations of methods from classical probability theory.

Video Recording