Verification of NP-complete problems: Difference between revisions

Verification of NP-complete problems (edit)

1,196 bytes added , 18 April 2019

Write, autoreview, editor, reviewer

3,129

edits

@@ Line 48: / Line 48: @@
 ==Pseudo Code==
-===General Case===
+<u>'''Stage 1'''</u> State Preparation
-<u>'''Stage 1'''</u>
+#  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==