期刊
SIAM JOURNAL ON COMPUTING
卷 41, 期 4, 页码 1028-1050出版社
SIAM PUBLICATIONS
DOI: 10.1137/110842272
关键词
QMA-complete; approximation algorithm; local Hamiltonian; constraint satisfaction
资金
- Natural Sciences and Engineering Research Council of Canada Canada Graduate Scholarship
- Michael Smith Foreign Study Supplement
- David R. Cheriton graduate scholarship
- EU-Canada Transatlantic Exchange Partnership programme
- Canadian Institute for Advanced Research
- Individual Research Grant of the Israeli Science Foundation
- European Research Council starting grant QUCO
- Wolfson Family Charitable Trust
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据