Write, autoreview, editor, reviewer
3,129
edits
Verification of NP-complete problems: Difference between revisions
→Pseudo Code
| Line 48: | Line 48: | ||
==Pseudo Code== | ==Pseudo Code== | ||
=== | <u>'''Stage 1'''</u> State Preparation | ||
<u>'''Stage | # 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. | ||
<u>'''Stage 2'''</u> | # 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. | |||
==References== | ==References== | ||