Session II.5 - Random Matrices
Thursday, June 15, 16:30 ~ 17:30
Random sparse Hamiltonians and quantum advantage
Joel Tropp
Caltech, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
This talk introduces a simple and elegant random matrix ensemble, called a sparse random Hamiltonian. This model contains very little randomness, yet the spectrum is close to the semicircular distribution. A quantum computer can reliably produce a low-energy state of this type of random Hamiltonian, while it is unlikely that the same task is tractable for a classical computer. As a consequence, this ensemble provides evidence of a potential "quantum advantage".
The proof of these claims involves new tools from nonasymptotic random matrix theory. In particular, a novel application of the Lindeberg principle yields a comparison between the sparse random Hamiltonian and a GUE matrix. The talk focuses on the probabilistic aspects and proof ideas, and no prior knowledge of quantum computation is assumed.
Joint work with Chi-Fang (Anthony) Chen (Caltech, AWS), Alexander M. Dalzell (AWS, Caltech), Mario Berta (Aachen) and Fernando G. S. L. Brandao (Caltech).