数理解析研究所講究録
2011年度冬のLAシンポジウム On QMA Protocols with Two Short Quantum Proofs (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
François Le Gall, Shota Nakagawa, Harumichi Nishimura
Abstract
This paper gives $a$ .QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarith- mic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{npoly\log(n)})$ .This improves the best completeness/soundness gaps known for NP-complete problems in this setting.