## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 1028-1050 |

Number of pages | 23 |

Journal | SIAM Journal on Computing |

Volume | 41 |

Issue number | 4 |

DOIs | |

State | Published - 2012 |

## Keywords

- Approximation algorithm
- Constraint satisfaction
- Local Hamiltonian
- QMA-complete

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics