An efficient algorithm for the spin chain problem with a constant spectral gap (Yichen Huang)

Abstract

MAX-2-SAT on a line (i.e., each clause involves x_i and x_{i+1} for some i, where x_1, x_2, ,,, x_n are Boolean variables) can be solved efficiently by dynamic programming. Its quantum analogue, called the spin chain problem, is fundamental in condensed matter physics. Here we provide a polynomial-time classical algorithm for the spin chain problem assuming a constant lower bound on the spectral gap. Previously, it was known that the problem is intractable even for a quantum computer if the spectral gap can decrease with n.

This result is a rigorous version of the heuristic density matrix renormalization group algorithm. The latter was invented in 1992 and is nowadays the leading numerical method for one-dimensional quantum systems. This talk assumes no prior background/knowledge in quantum mechanics.

Time

Speaker

Room