# Quantum spin Hamiltonian problems and Interactive Proofs

### APA

Bravyi, S. (2006). Quantum spin Hamiltonian problems and Interactive Proofs. Perimeter Institute. https://pirsa.org/06110006

### MLA

Bravyi, Sergey. Quantum spin Hamiltonian problems and Interactive Proofs. Perimeter Institute, Nov. 08, 2006, https://pirsa.org/06110006

### BibTex

@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}} }

IBM (United States)

**Collection**

Talk Type

**Subject**

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.