{"id":"arxiv/2609.15926","url":"https://arxiv.org/abs/2609.15926","tags":["quant-ph","cs.CC"],"score":0,"title":"Achieving perfect completeness for one- and two-message quantum proof systems","domain":"quant-ph","source":"arxiv","authors":["Yupan Liu","Thomas Vidick"],"reviews":0,"subject":"quant-ph","summary":"While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is achievable for one- and two-message quantum proof systems has remained open. For the one-message case, whether $\\sf QMA$ can achieve perfect completeness was posed as an open problem in Watrous (FOCS 2000) and Aharonov and Naveh (2002); for the two-message case, the corresponding problems were (implicitly) posed in Jain, Upadhyay, and Watrous~(FOCS 2009) and Kobayashi, Le Gall, and Nishimura (SICOMP, 2019). In this…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}