Editing Verification of NP-complete problems
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 6: | Line 6: | ||
==Assumptions== | ==Assumptions== | ||
* The problem must be a ''[[balanced formula]]'', meaning that every variable occurs in at most a constant number of clauses; | * The problem must be a ''[[balanced formula]]'', meaning that every variable occurs in at most a constant number of clauses; | ||
\item it must be a [[PCP]], i.e. either the formula is satisfiable, or at least a fraction of the clauses must | |||
*''Exponential time hypothesis'', i.e. any NP-complete problem cannot be solved in | be unsatisfiable; | ||
*''Exponential time hypothesis'', i.e. any NP-complete problem cannot be solved in subexponential time in the worst case. | |||
* There is a promise of no [[entanglement]] between the quantum proofs. | * There is a promise of no [[entanglement]] between the quantum proofs. | ||
The first two conditions are always met when reducing the NP problem to a [[3SAT]] and then to a [[2-out-of-4SAT]]. The exponential hypothesis is unproven but very accredited conjecture which implies that <math>P\neq NP</math>. The [[un-entanglement]] promise is typical in these scenarios as it was proved that Merlin can always cheat by entangling the proofs and there is no way for Arthur to verify state by pre-preparing the ancillary states with special coefficients. | The first two conditions are always met when reducing the NP problem to a [[3SAT]] and then to a [[2-out-of-4SAT]]. The exponential hypothesis is unproven but very accredited conjecture which implies that <math>P\neq NP</math>. The [[un-entanglement]] promise is typical in these scenarios as it was proved that Merlin can always cheat by entangling the proofs and there is no way for Arthur to verify.state by pre-preparing the ancillary states with special coefficients. | ||
==Outline== | ==Outline== | ||
Line 17: | Line 18: | ||
*'''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. | ||
== | ==Notations Used== | ||
**<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 25: | ||
**<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]] | ||
* '''Relevant Parameters:''' | * '''Relevant Parameters:''' | ||
** <math>K=O(\sqrt{N} | ** <math>K=O(\sqrt{N}</math> single photon sources. | ||
** K fixed cascades of beamsplitters of depth <math>O(\log N)</math> each preparing a single photon in an equal superposition over N modes. | ** K fixed cascades of beamsplitters of depth <math>O(\log N)</math> each preparing a single photon in an equal superposition over N modes. | ||
** KN phase-shifters, one for each mode. | ** KN phase-shifters, one for each mode. | ||
Line 34: | Line 34: | ||
** <math>K N\times N</math> active switches that perform arbitrary permutations of N modes. | ** <math>K N\times N</math> active switches that perform arbitrary permutations of N modes. | ||
** One <math>2N\times 2N</math> switch performing permutation of 2N modes. | ** One <math>2N\times 2N</math> switch performing permutation of 2N modes. | ||
** | ** O(N) four-mode interferometers for the satisfiability test. | ||
** | ** O(KN) two-mode interferometers for uniformity and symmetry tests. | ||
** | ** O(KN) photon number resolving detectors. | ||
==Properties== | ==Properties== | ||
Line 47: | Line 47: | ||
* It has been theorized that N needs to be at least about 500 in order to have the advantage over the best classical protocol. | * It has been theorized that N needs to be at least about 500 in order to have the advantage over the best classical protocol. | ||
== | ==Pseudo Code== | ||
===General Case=== | |||
<u>'''Stage 1'''</u> | |||
# | |||
<u>'''Stage 2'''</u> | |||
<u>'''Stage | * | ||
# | |||
<u>'''Stage | |||
== | ==References== | ||
*'''Theoretical Papers''' | *'''Theoretical Papers''' | ||
** [https://arxiv.org/abs/1711.02200 ADS (2017)] | ** [https://arxiv.org/abs/1711.02200 ADS (2017)] |