Fetching the paper…

Reading the bibliography…

2011

On QMA Protocols with Two Short Quantum Proofs

Gall, Francois Le, Nakagawa, Shota, Nishimura, Harumichi

Original
PDF
Post on X

Understand

This paper gives a QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarithmic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is Omega(1/n polylog(n)).

This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

On QMA Protocols with Two Short Quantum Proofs · Around

Built on

E. Knill. Quantum randomness and nondeterminism. Technical Report LAUR-96-2186, Los Alamos National Laboratory, 1996. arXiv:quant-ph/9610012
1996
Earlier work this paper cites.
M. Nielsen and I. Chuang. Quantum Computation and Quantum Information
2000
Earlier work this paper cites.
J. Watrous. Succinct quantum proofs for properties of finite groups. Proc. 41st FOCS
Original
2000
Earlier work this paper cites.
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters
2001
Earlier work this paper cites.
A. Y. Kitaev, A. H. Shen and M. N. Vyalyi. Classical and Quantum Computation
2002
Earlier work this paper cites.

Similar

C. Marriott and J. Watrous. Quantum Arthur-Merlin games. Computational Complexity
2005
Cited alongside, same era.
I. Dinur. The PCP theorem by gap amplification. Journal of the ACM
2007
Cited alongside, same era.
Y.-K. Liu, M. Christandl and F. Verstraete. Quantum computational complexity of the N N -representability problem: QMA complete. Physical Review Letters
2007
Cited alongside, same era.
S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. W. Shor. The power of unentanglement. Theory of Computing
Original
2009
Cited alongside, same era.
H. Blier and A. Tapp. All languages in NP have very short quantum proofs. Proc. 3rd ICQNM
Original
2009
Cited alongside, same era.
J. Chen and A. Drucker. Short multi-prover quantum proofs for SAT without entangled measurements. arXiv:1011.0716

Then

H. Kobayashi, K. Matsumoto and T. Yamakami. Quantum Merlin-Arthur proof Systems: Are multiple Merlins more helpful to Arthur? Chicago Journal of Theoretical Computer Science
2009
Later among the works it cites.
S. Beigi. NP vs QMA log
Original
2010
Later among the works it cites.
A. W. Harrow and A. Montanaro. An efficient test for product states with applications to quantum Merlin-Arthur games. Proc. 51th FOCS
Original
2010
Later among the works it cites.
S. Nakagawa and H. Nishimura. On the soundness of the Blier-Tapp QMA protocol. Proc. 23rd Quantum Information Technology Symposium (QIT23)
2010
Later among the works it cites.
A. Chiesa and M. Forbes. Improved soundness for QMA with multiple provers. arXiv:1108.2098
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Cited in the paper.

2098

Closest in time.