Write, autoreview, editor, reviewer
3,125
edits
Verification of NP-complete problems: Difference between revisions
Jump to navigation
Jump to search
no edit summary
No edit summary |
|||
| Line 1: | Line 1: | ||
The aim of the protocol is to verify NP-complete problems in the context of [[ | The aim of the protocol is to verify NP-complete problems in the context of [[communication complexity]], so in the case in which the amount of communication between the involved parties is a resource. By definition, if a problem is in NP then it is possible to verify efficiently if a given solution is correct. However, if the given solution, or [[witness]], is incomplete then the verification process is exponential in the size of the missing information.</br> | ||
In this setting, Merlin, an overpowerful but untrusted prover, wants to convince Arthur, a honest but computationally bounded verifier, that he has the solution to a specific NP-complete problem. It was shown by [[Aaronson et al.]] that if Merlin sends quantum proofs revealing only partial information about the complete solution, Arthur can efficiently verify it in a probabilistic sense, giving rise to a computational advantage with no analogous in the classical world. These quantum class of problems is called QMA, as in Quantum Merlin Arthur, and is the generalization of NP problems as it consists to the class of languages that can be verified efficiently with quantum proofs.</br> | In this setting, Merlin, an overpowerful but untrusted prover, wants to convince Arthur, a honest but computationally bounded verifier, that he has the solution to a specific NP-complete problem. It was shown by [[Aaronson et al.]] that if Merlin sends quantum proofs revealing only partial information about the complete solution, Arthur can efficiently verify it in a probabilistic sense, giving rise to a computational advantage with no analogous in the classical world. These quantum class of problems is called QMA, as in Quantum Merlin Arthur, and is the generalization of NP problems as it consists to the class of languages that can be verified efficiently with quantum proofs.</br> | ||
| Line 11: | Line 11: | ||
* There is a promise of no [[entanglement]] between the quantum proofs. | * There is a promise of no [[entanglement]] between the quantum proofs. | ||
The first two conditions are always met when reducing the NP problem to a [[3SAT]] and then to a [[2-out-of-4SAT]]. The exponential hypothesis is unproven but very accredited conjecture which implies that <math>P\neq NP</math>. The | The first two conditions are always met when reducing the NP problem to a [[3SAT]] and then to a [[2-out-of-4SAT]]. The exponential hypothesis is unproven but very accredited conjecture which implies that <math>P\neq NP</math>. The [[un-entanglement]] promise is typical in these scenarios as it was proved that Merlin can always cheat by entangling the proofs and there is no way for Arthur to verify.state by pre-preparing the ancillary states with special coefficients. | ||
==Outline== | ==Outline== | ||
| Line 54: | Line 54: | ||
* | * | ||
== | ==References== | ||
*'''Theoretical Papers''' | |||
** [https://arxiv.org/abs/1711.02200 ADS (2017)] | |||
** [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.244.6864&rep=rep1&type=pdf Tapp (2008)] | |||
** [https://www.computer.org/csdl/10.1109/CCC.2008.5 ADBSF (2008)] | |||
*'''Experimental Papers''' There has not been any experimental implementation of this protocol so far. | |||
<div style='text-align: right;'>''*contributed by Federico Centrone''</div> | <div style='text-align: right;'>''*contributed by Federico Centrone''</div> | ||