Quantum spin Hamiltonian problems and Interactive Proofs

          @misc{ pirsa_PIRSA:06110006,
            doi = {10.48660/06110006},
            url = {https://pirsa.org/06110006},
            author = {Bravyi, Sergey},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum spin Hamiltonian problems and Interactive Proofs},
            publisher = {Perimeter Institute},
            year = {2006},
            month = {nov},
            note = {PIRSA:06110006 see, \url{https://pirsa.org}}
          }
          

Abstract

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.