Physics – Quantum Physics
Scientific paper
2011-01-20
Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, pages 178-188
Physics
Quantum Physics
22 pages, comments welcome
Scientific paper
10.1109/CCC.2011.15
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 and initiate its study. We present two main results. The first shows that a non-trivial 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 et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.
Gharibian Sevag
Kempe Julia
No associations
LandOfFree
Approximation algorithms for QMA-complete problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximation algorithms for QMA-complete problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation algorithms for QMA-complete problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-333482