Fetching the paper…
Reading the bibliography…
We present three contributions to the understanding of QMA with multiple provers: 1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap Omega(1/N^2).
A first course in probability
Sheldon Ross · 1984
Earlier work this paper cites.
Nearly linear time
Yuri Gurevich and Saharon Shelah · 1989
Earlier work this paper cites.
Optimization, approximation, and complexity classes
Christos H. Papadimitriou and Mihalis Yannakakis · 1991
Earlier work this paper cites.
Computational Complexity
Christos H. Papadimitriou · 1994
Earlier work this paper cites.
Quantum randomness and nondeterminism
Emanuel H. Knill · 1996
Earlier work this paper cites.
Stabilization of quantum computations by symmetrization
Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello · 1997
Earlier work this paper cites.
Quantum NP \mathrm{NP}
Alexei Yu. Kitaev · 1999
Earlier work this paper cites.
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang · 2000
Earlier work this paper cites.
Succinct quantum proofs for properties of finite groups
John Watrous · 2000
Earlier work this paper cites.
Quantum fingerprinting
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf · 2001
Cited alongside, same era.
On the complexity of k-SAT
Russel Impagliazzo and Ramamohan Paturi · 2001
Cited alongside, same era.
The approximability of constraint satisfaction problems
Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson · 2001
Cited alongside, same era.
Quantum NP \mathrm{NP} - a survey
Dorit Aharonov and Tomer Naveh · 2002
Cited alongside, same era.
The PCP theorem by gap amplification
Irit Dinur · 2007
Cited alongside, same era.
Quantum computational complexity of the n n -representability problem: QMA \mathrm{QMA} complete
Yi-Kai Liu, Matthias Christandl, and Frank Verstraete · 2007
Cited alongside, same era.
Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur?
Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami · 2009
Later among the works it cites.
Faithful squashed entanglement
Fernando Brandão, Matthias Christiandl, and Yard Jon · 2010
Later among the works it cites.
NP \mathrm{NP} vs. QMA log ( 2 ) \mathrm{QMA}_{\log}(2)
Salman Beigi · 2010
Later among the works it cites.
Short multi-prover quantum proofs for SAT without entangled measurements
Jing Chen and Andrew Drucker · 2010
Later among the works it cites.
An efficient test for product states, with applications to quantum merlin-arthur games
Aram Harrow and Ashley Montanaro · 2010
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Eli Ben-Sasson and Madhu Sudan · 2008
Cited alongside, same era.
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor · 2009
Cited alongside, same era.
All languages in NP have very short quantum proofs
Hugue Blier and Alain Tapp · 2009
Cited alongside, same era.
Later among the works it cites.
Quantum de Finetti theorems under local measurements with applications, 2012
Fernando Brandão and Aram W. Harrow · 2012
Closest in time.
On QMA protocols with two short quantum proofs
François Le Gall, Shota Nakagawa, and Harumichi Nishimura · 2012
Closest in time.
Multi-prover quantum Merlin-Arthur proof systems with small gap, 2012
Attila Pereszlényi · 2012
Closest in time.