Quantum spin Hamiltonian problems and Interactive Proofs

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

Scientific Areas: 
PIRSA Number: 


Complexity class MA is a class of yes/no problems for which the answer `yes\' has a short certificate that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete
problem: stoquastic k-SAT. This is a quantum-mechanical analogue of the satisfiability problem such that k-bit clauses are replaced by k-qubit projectors with non-negative matrix elements. Complexity class AM is a generalization of MA in which the certificate may include a short conversation between Prover and Verifier. We prove that AM also has a natural complete problem: stoquastic Local Hamiltonian with a quenched disorder. The problem is to evaluate expectation value of the ground state energy of disordered local Hamiltonian with non-positive matrix elements.