Sparse Random Hamiltonians Are Quantumly Easy

Physical Review X, vol. 14

Abstract

A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. For this task, there is a well-studied quantum algorithm that performs quantum phase estimation on an initial trial state that has a non-negligible overlap with a low-energy state. However, it is notoriously hard to give theoretical guarantees that such a trial state can be prepared efficiently. Moreover, the heuristic proposals that are currently available, such as with adiabatic state preparation, appear insufficient in practical cases. This paper shows that, for most random sparse Hamiltonians, the maximally mixed state is a sufficiently good trial state, and phase estimation efficiently prepares states with energy arbitrarily close to the ground energy. Furthermore, any low-energy state must have non-negligible quantum circuit complexity, suggesting that low-energy states are classically nontrivial and phase estimation is the optimal method for preparing such states (up to polynomial factors). These statements hold for two models of random Hamiltonians: (i) a sum of random signed Pauli strings and (ii) a random signed d -sparse Hamiltonian. The main technical argument is based on some new results in nonasymptotic random matrix theory. In particular, a refined concentration bound for the spectral density is required to obtain complexity guarantees for these random Hamiltonians. Published by the American Physical Society 2024

Authors 5

1. Chi-Fang Chen

   California Institute of Technology · Amazon (United States)

   Affiliation as printed

   AWS Center for Quantum Computing, Pasadena, California, USA

   Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, California, USA

2. Alexander M. Dalzell

   California Institute of Technology · Amazon (United States)

   Affiliation as printed

   AWS Center for Quantum Computing, Pasadena, California, USA

   California Institute of Technology, Pasadena, California, USA

3. Mario Berta Aachen Institute for Quantum Information

   Imperial College London · RWTH Aachen University

   Affiliation as printed

   Department of Computing, Imperial College London, London, United Kingdom

   Institute for Quantum Information, RWTH Aachen University, Aachen, Germany

4. Fernando G. S. L. Brandão

   California Institute of Technology · Amazon (United States)

   Affiliation as printed

   AWS Center for Quantum Computing, Pasadena, California, USA

   Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, California, USA

5. Joel A. Tropp

   California Institute of Technology

   Affiliation as printed

   Department of Computing and Mathematical Sciences, Caltech, Pasadena, California, USA