Verification of NP-complete problems: Difference between revisions

Jump to navigation Jump to search

Verification of NP-complete problems (edit)

Revision as of 10:14, 18 April 2019

553 bytes removed ,  18 April 2019
→‎Properties
Line 27: Line 27:


==Properties==
==Properties==
*The protocol assumes that the original input qubit is unknown and the protocol is independent of the original input state (universality).
The protocol
*The output copies are not identical and we are able to control the likelihood (fidelity) of the output copies to the original state by pre-preparing the ancillary states with special coefficients.
* involves two parties and one-way communication from the prover to the verifier.
*Claims for General case:
* assumes that anyone might be dishonest and still provide perfect completeness and constant soundness.
**Following inequality holds between the scaling factors <math>s_0</math> and <math>s_1</math></br>
* has a communication complexity of <math>O(\sqrt{N}\log_2N)</math> bits of information.
<math>s_0^2 + s_1^2 + s_0 s_1 - s_0 - s_1 \leq 0</math>
* runs in exponential time, while it can be shown that by using classical proofs, the best protocol run in exponential time in the size of N.
**This elliptic inequality shows the possible value of the scaling parameters.
* can be implemented with linear optics (not exclusively).
**Trade-off inequality between the fidelities of the clones:</br>
* It has been theorized that N needs to be at least about 500 in order to have the advantage over the best classical protocol.
<math>\sqrt{(1 - F_a)(1 - F_b)} \geq \frac{1}{2} - (1 - F_a) - (1 - F_b)</math>
**Optimality is provided when the fidelities of two clones, <math>F_a</math> and <math>F_b</math>, saturate the above inequality
*Claims for Special case with bell state:
**Following ellipse equation holds between the scaling factors <math>a</math> and <math>b</math></br>
<math>a^2 + b^2 + ab = 1</math>
**Following equations holds for fidelities of the clones:
<math>F_a = 1 - \frac{b^2}{2}, F_b = 1 - \frac{a^2}{2}</math>


==Pseudo Code==
==Pseudo Code==
Shraddha
Write, autoreview, editor, reviewer
3,129

edits

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Special:MobileDiff/2031"

Navigation menu