this talk is tomorrow.

“The sign problem and its relation to the spectral gap of quantum many-body systems”

Elizabeth Crosson, University of New Mexico
Abstract: The partition function of a quantum system without a sign problem can be represented
by a path integral in which every amplitude is efficiently computable and nonnegative, which is a
substantial simplification from the interference of complex amplitudes in the general quantum
case. In quantum computing the presence of a sign problem has been recast as a virtue, because
it helps to increase the complexity of the quantum system beyond the range of classical
simulation. This is particularly important for quantum adiabatic algorithms based on ground
states, where the run time depends on the scaling of the spectral gap above the ground state. This
motivates us to study the relation of the sign problem to the spectral gap, using methods such as
random matrix theory and spectral graph theory. The latter relates the discrete geometry of
ground states (in a world where vertices are basis elements and edges are Hamiltonian matrix
elements) to the level spacings in the low energy spectrum using the higher-order signed Cheeger
inequalities. This talk will include analytical results from 1703.10133 and 2004.07681.