Fetching the paper…

Reading the bibliography…

2010

Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements

Chen, Jing, Drucker, Andrew

Original
PDF
Post on X

Understand

BellQMA protocols are a subclass of multi-prover quantum Merlin-Arthur protocols in which the verifier is restricted to perform nonadaptive,unentangled measurements on the quantum states received from each Merlin.

In this paper, we prove that m-clause 3-SAT instances have BellQMA proofs of satisfiability with constant soundness gap, in which O(sqrt(m)polylog(m)) Merlins each send O(log m) qubits to Arthur.
Our result answers a question of Aaronson et al., who gave a protocol with similar parameters that used entangled measurements; the analysis of our protocol is significantly simpler than that of Aaronson et al.
Our result also complements recent work of Brandao, Christandl, and Yard, who showed upper bounds on the power of multiprover quantum proofs with unentangled but adaptive (LOCC) measurements.

Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements · Around

Built on

Concentrating partial entanglement by local operations
C. Bennett, H. Bernstein, S. Popescu, and B. Schumacher · 1996
Earlier work this paper cites.
Conditions for a class of entanglement transformations
M. Nielsen · 1999
Earlier work this paper cites.
Quantum fingerprinting
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf · 2001
Earlier work this paper cites.
Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur?
H. Kobayashi, K. Matsumoto, and T. Yamakami · 2003
Earlier work this paper cites.

Similar

The PCP theorem by gap amplification
I. Dinur · 2007
Cited alongside, same era.
Entanglement Theory and the Quantum Simulation of Many-Body Physics
Original
F. Brandao · 2008
Cited alongside, same era.
The power of unentanglement
S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor · 2009
Cited alongside, same era.
All languages in NP have very short quantum proofs
Original
H. Blier and A. Tapp · 2009
Cited alongside, same era.

Then

Faithful squashed entanglement, 2010
Original
F. Brandao, M. Christandl, and J. Yard · 2010
Closest in time.
NP vs QMA log
Original
S. Beigi · 2010
Closest in time.
An efficient test for product states, with applications to quantum Merlin-Arthur games, 2010
Original
A. Harrow and A. Montanaro · 2010
Closest in time.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…