Theory Seminar: The Boundary Between Classical and Quantum Constraint Satisfaction Problems: Rounding Almost Commuting Hamiltonians

Islam Faisal
Boston University 
Quantum Info & Computing Seminar, at the Seminar Room
Tuesday, June 30, 15:00 CET

In this talk, I will present some new work on almost commuting Hamiltonians which lie on the boundary between classical and quantum constraint satisfaction. We show how to efficiently approximate any almost commuting 2-local qubit Hamiltonian by a commuting one. Specifically, we give a locality-preserving ``rounding technique'' that maps any 2-local qubit Hamiltonian H to a nearby qubit Hamiltonian H' whose terms pair-wise commute, and which is within overall distance O(m ε^{1/6}). As a consequence, we show that (the decision version of) δ-approximations to the ground energy for ε-almost commuting 2-local qubit Hamiltonians lie in NP when δ >>  m ε^{1/6}, extending the classical containment well beyond the commuting setting. Additionally, our technique has two other applications beyond computational complexity theory: Gibbs sampling and fast Hamiltonian simulation for almost commuting systems.