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

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 annealing the presence of a sign problem has at times been sought as a virtue, because it helps to increase the complexity of the quantum system beyond the range of classical simulation. In this work we propose a "de-signing" operation for adiabatic optimization, which removes the sign problem from a Hamiltonian path, and we use methods including random matrix theory, spectral graph theory, and numerical simulation to argue that this de-signing operation tends to increase the spectral gap with high probability.