Editing Verification of NP-complete problems

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 [[Verification of NP-complete problems#References|ADS (2008)]] 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>

* It must be a [[PCP]], i.e. either the formula is satisfiable, or at least a fraction of the clauses must be unsatisfiable;

*''Exponential time hypothesis'', i.e. any NP-complete problem cannot be solved in sub-exponential time in the worst case.

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.

In order to verify an N size 2-out-of-4SAT problem, Merlin is required to send the proof encrypted in the phase of a quantum state in a superposition of N orthogonal modes. Furthermore, he will need to send order <math>\sqrt{N}</math> identical copies of this quantum state. However, due to the Holevo bound, Arthur can retrieve at most order <math>\sqrt{N}\log_2 N</math> bits of information on average by just measuring the state, which is only a small fraction of the whole N bits solution. Therefore, to verify the correctness of the proof and the honesty of Merlin, Arthur will need to perform three distinct tests. In [[Verification of NP-complete problems#References|ADS (2017)]] they specify how these tests could be performed using a single photon source and linear optics, so in the following we will refer to it, even though the protocol can be implemented with any quantum information carriers. Each test is performed with probability 1/3.

==Notation==

** <math>K=O(\sqrt{N})</math> single photon sources.

** <math>O(N)</math> four-mode interferometers for the satisfiability test.

** <math>O(KN)</math> two-mode interferometers for uniformity and symmetry tests.

** <math>O(KN)</math> photon number resolving detectors.

==Pseudocode==

#  Merlin prepares  <math>K=O(\sqrt{N})</math> copies of the state <math>|\psi_x\rangle_k=\frac{1}{\sqrt{N}}\sum_{i=1}^N(-1)^{x_i}|i\rangle</math>.

<u>'''Stage 2'''</u> Satisfiability

# Arthur partition the clauses in blocks so that each block contain at most one variable.

<u>'''Stage 3'''</u> Uniformity

# He then measures each copy in the basis <math>\frac{|i\rangle+|j\rangle}{\sqrt{2}}, \frac{|i\rangle-|j\rangle}{\sqrt{2}}</math>, <math>\forall (i,j)\in \mathcal{M}</math> .

<u>'''Stage 4'''</u> Symmetry

# Arthur chooses at random an index <math>k\in\{2, ..., K\}</math>

==Further Information==