Verification of NP-complete problems: Difference between revisions

Verification of NP-complete problems (edit)

42 bytes added , 18 April 2019

Write, autoreview, editor, reviewer

3,125

edits

@@ Line 22: / Line 22: @@
 **<math>x=\{x_1 x_2 ... x_N\}:</math> Merlin's assignment to solve the problem
 **<math>K=O(\sqrt{N}):</math> number of copies of the quantum proof
-**<math>\ket{i}=\ket{0}_1\ket{0}_2...\ket{1}_i...\ket{0}_N:</math> state of one photon in the ith optical mode and zero in the others
+**<math>|i\rangle=|0\rangle_1|0\rangle_2...|1\rangle_i...|0\rangle_N:</math> state of one photon in the <math>i^th</math> optical mode and zero in the others
-**<math>\ket{\psi_x}_k=\frac{1}{\sqrt{N}}\sum_{i=1}^N(-1)^{x_i}\ket{i}:</math> kth quantum proof encoding the assignment x
+**<math>|\psi_x\rangle_k=\frac{1}{\sqrt{N}}\sum_{i=1}^N(-1)^{x_i}|i\rangle:</math> <math>k^th</math> quantum proof encoding the assignment x
 ==Properties==