Sparse random matrices are quantumly easy
- LecturerMr. Chi Fang Chen (California Institute of Technology)
Host: Kai-Min Chung - Time2022-10-13 (Thu.) 10:30 ~ 12:30
- Location資訊所新館106演講廳, Auditorium 106 at IIS new Building
Abstract
A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. A well-studied quantum algorithm for this task is to run 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, heuristic proposals for doing so, such as with adiabatic state preparation, appear insufficient in practical cases.
In this work, we prove that, for almost every random sparse Hamiltonian, the maximally mixed state is a sufficiently good trial state and phase estimation efficiently prepares low-energy states of the model. We also prove that any low-energy state must have non-negligible quantum circuit complexity, suggesting that low-energy states are classically non-trivial, and phase estimation is the optimal method for preparing such states (up to polynomial factors). We prove these statements for two models of random Hamiltonians: (a) sum of random signed Pauli strings and (b) random signed d-sparse Hamiltonians. Our main technical argument adapts and sharpens recent developments in non-asymptotic random matrix theory. We prove a refined concentration of spectral density that is needed for provable complexity guarantees for such random Hamiltonians.
In this work, we prove that, for almost every random sparse Hamiltonian, the maximally mixed state is a sufficiently good trial state and phase estimation efficiently prepares low-energy states of the model. We also prove that any low-energy state must have non-negligible quantum circuit complexity, suggesting that low-energy states are classically non-trivial, and phase estimation is the optimal method for preparing such states (up to polynomial factors). We prove these statements for two models of random Hamiltonians: (a) sum of random signed Pauli strings and (b) random signed d-sparse Hamiltonians. Our main technical argument adapts and sharpens recent developments in non-asymptotic random matrix theory. We prove a refined concentration of spectral density that is needed for provable complexity guarantees for such random Hamiltonians.