Merlin-Arthur Games and Stoquastic Complexity

Abstract

MA is a class of decision problems for which `yes'-instances have a proof that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem which we call the stoquastic k-SAT problem. This is a matrix-valued analogue of the satisfiability problem in which clauses are k-qubit projectors with non-negative matrix elements, while a satisfying assignment is a vector that belongs to the space spanned by these projectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete problem. We also study the minimum eigenvalue problem for local stoquastic Hamiltonians that was introduced in quant-ph/0606140, stoquastic LH-MIN. A new complexity class StoqMA is introduced so that stoquastic LH-MIN is StoqMA-complete. Lastly, we consider the average LH-MIN problem for local stoquastic Hamiltonians that depend on a random or `quenched disorder' parameter, stoquastic AV-LH-MIN. We prove that stoquastic AV-LH-MIN is contained in the complexity class \AM, the class of decision problems for which yes-instances have a randomized interactive proof with two-way communication between prover and verifier.

20 pages, 2 figures (proof of AM-hardness is simplified in Section 5)

References in corpus (4)

• N-representability is QMA-complete
• Quantum NP - A Survey
• Identity check is QMA-complete
• Consistency of Local Density Matrices is QMA-complete

Cited by in corpus (20)

• Adiabatic Quantum Computing
• Quantum Hamiltonian Complexity
• QMA-complete problems for stoquastic Hamiltonians and Markov matrices
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Stoquasticity in circuit QED
• Complexity classification of local Hamiltonian problems
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Tensor network non-zero testing
• Approximation, Proof Systems, and Correlations in a Quantum World
• Complexity of stoquastic frustration-free Hamiltonians
• StoqMA vs. MA: the power of error reduction
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• StoqMA meets distribution testing
• Simulated Quantum Annealing is Efficient on the Spike Hamiltonian
• Non-NP-Hardness of Translationally-Invariant Spin-Model Problems
• On polynomially many queries to NP or QMA oracles
• Two remarks on the local Hamiltonian problem
• Classical Simulation of High Temperature Quantum Ising Models