Editing Verification of NP-complete problems (section)

==Outline==
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.
*'''Satisfiability Test''' In this test Arthur chooses one of the copies of the quantum proofs and verifies that Merlin's assignment is correct, i.e. it solves his 2-out-of-4 SAT for some clauses. Because of the probabilistic nature of the protocol he will only be able to verify some of the clauses and will reject only if he detects incorrectness (so he will accept even if he does not detect anything at all).
*'''Uniformity Test''' Merlin can cheat by sending a state which is not proper, in which case the satisfiability test might accept even if there is no correct assignment to the problem. In order to avoid this, Arthur can perform a test on all the proofs to check if the incoming states are in the expected form.
*'''Symmetry Test:''' The quantum proofs might not be identical, which might mislead Arthur into believe a dishonest Merlin. To prevent this, Arthur chooses two copies at random and perform a SWAP test to see if they are the same quantum state.