Write, autoreview, editor, reviewer
3,125
edits
Verification of NP-complete problems: Difference between revisions
→Notations Used
| Line 25: | 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== | |||
* '''Network Stage:''' [[:Category: Prepare and Measure Network Stage|Prepare and Measure]][[Category: Prepare and Measure Network Stage]] | |||
* '''Relevant Parameters:''' | |||
** <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. | |||
** KN phase-shifters, one for each mode. | |||
** One <math>K\times K</math> block switch that permutes groups 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. | |||
** 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== | ||