2012/01/01 by Sevag Gharibian, Julia Kempe · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Quantum Computing Algorithms and Architecture #Markov Chains and Monte Carlo Methods
paper · doi:10.1137/110842272
Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the “exhaustive sampling method” by Arora, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.