Write
262
edits
Verification of NP-complete problems: Difference between revisions
→Notations Used
| Line 17: | Line 17: | ||
*'''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. | *'''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. | *'''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. | ||
== | ==Notation== | ||
**<math>N:</math> size of the problem | **<math>N:</math> size of the problem | ||
**<math>x=\{x_1 x_2 ... x_N\}:</math> Merlin's assignment to solve the problem | **<math>x=\{x_1 x_2 ... x_N\}:</math> Merlin's assignment to solve the problem | ||
| Line 24: | Line 24: | ||
**<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 | **<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 | ||
**<math>\mathcal{M}</math>: set of all the possible matchings between two indices in [N]. | **<math>\mathcal{M}</math>: set of all the possible matchings between two indices in [N]. | ||
==Hardware Requirements== | ==Hardware Requirements== | ||
* '''Network Stage:''' [[:Category: Prepare and Measure Network Stage|Prepare and Measure]][[Category: Prepare and Measure Network Stage]] | * '''Network Stage:''' [[:Category: Prepare and Measure Network Stage|Prepare and Measure]][[Category: Prepare and Measure Network Stage]] | ||