Editing Verification of NP-complete problems (section)

==Pseudocode==
<u>'''Stage 1'''</u> State Preparation
#  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>.
# Sends each copy <math>|\psi\rangle_k</math> to Arthur through their quantum channel.
# Arthur chooses at random which test to perform.
<u>'''Stage 2'''</u> Satisfiability
# Arthur partition the clauses in blocks so that each block contain at most one variable.
#He decides at random which block to use and prepares his interferometers so that for each clause the respective optical modes will interfere as in the figure.
# If he detects a photon in the first detector he rejects the proof, otherwise he accepts.
<u>'''Stage 3'''</u> Uniformity
# Arthur chooses a matching <math>\mathcal{M}</math> over [N].
# 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> .
# He rejects if for any (i,j) he detects a photon in both detectors.
<u>'''Stage 4'''</u> Symmetry
# Arthur chooses at random an index <math>k\in\{2, ..., K\}</math>
# Performs a SWAP test between <math>|\psi\rangle_1</math> and <math>|\psi\rangle_k</math>.
# Accepts if SWAP test accepts.