On QMA protocols with two short quantum proofs

Type: Article

Publication Date: 2012-07-01

Citations: 27

DOI: https://doi.org/10.26421/qic12.7-8-4

Abstract

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.

Locations

  • Quantum Information and Computation - View
  • arXiv (Cornell University) - View - PDF
  • DataCite API - View

Similar Works

Action Title Year Authors
+ Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements 2010 Jing Chen
Andrew Drucker
+ Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap 2012 Attila Pereszlényi
+ Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap 2012 Attila Pereszlényi
+ On quantum interactive proofs with short messages 2011 Attila Pereszlényi
+ On quantum interactive proofs with short messages 2011 Attila Pereszlényi
+ NP vs QMA_log(2) 2008 Salman Beigi
+ All languages in NP have very short quantum proofs 2007 Hugue Blier
Alain Tapp
+ Quantum Versus Classical Proofs and Advice 2006 Scott Aaronson
Greg Kuperberg
+ PDF Chat Quantum versus Classical Proofs and Advice 2007 Scott Aaronson
Greg Kuperberg
+ Quantum Versus Classical Proofs and Advice 2006 Scott Aaronson
Greg Kuperberg
+ Quantum free games 2023 Anand Natarajan
Tina Zhang
+ PDF Chat None 2009 Scott Aaronson
Salman Beigi
Andrew Drucker
Bill Fefferman
Peter W. Shor
+ Quantum Information and the PCP Theorem 2005 Ran Raz
+ Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers 2020 Abhijit S. Mudigonda
Ryan Williams
+ Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers 2020 Abhijit S. Mudigonda
Ryan Williams
+ NP vs QMA_log(2) 2008 Salman Beigi
+ Quantum Information and the PCP Theorem 2005 Ran Raz
+ PDF Chat Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete 2015 Hirotada Kobayashi
François Le Gall
Harumichi Nishimura
+ PDF Chat owards a quantum-inspired proof for IP = PSPACE 2021 Ayal Green
Guy Kindler
Yupan Liu
+ PDF Chat Quantum Merlin-Arthur with an internally separable proof 2024 Roozbeh Bassirian
Bill Fefferman
Itai Leigh
Kunal Marwaha
Pei Wu