Algorytm Simona – algorytm kwantowy znajdujący rozwiązanie poniższego zagadnienia.

Problem

Niech istnieje funkcja:

${\displaystyle f:\{0,1\}^{n}->\{0,1\}^{m))$ gdzie ${\displaystyle m\geqslant n-1.}$

Należy sprawdzić czy istnieje takie ${\displaystyle s\in \{0,1\}^{n}\setminus \{0^{(}n)\))$ że:

${\displaystyle \forall _{x'\neq x}(f(x')=f(x)\Leftrightarrow x'=x\oplus s).}$

Rozwiązanie klasyczne

Nie istnieje rozwiązanie tego zagadnienia o złożoności obliczeniowej mniejszej od wykładniczej.

Rozwiązanie kwantowe

Rozwiązanie opiera się na układzie kwantowym, który niezależnie rozwiązuje się n-krotnie.

Wygląda ono następująco:

${\displaystyle |\phi _{0}\rangle =|0^{(n)}\rangle |0^{(m)}\rangle }$

${\displaystyle |\phi _{1}\rangle =H^{\otimes n}|\phi _{0}\rangle ={\frac {1}{\sqrt {2^{n))))\sum _{i=0}^{2^{n}-1}|i\rangle |0^{(m)}\rangle ,}$ gdzie ${\displaystyle |i\rangle \in \{0,1,...2^{n}-1\))$ jest liczbą zakodowaną na pierwszych ${\displaystyle n}$ bitach

${\displaystyle |\phi _{2}\rangle =U_{f}|\phi _{1}\rangle =U_{f}{\frac {1}{\sqrt {2^{n))))\sum _{i=0}^{2^{n}-1}|i\rangle |0^{(m)}\rangle ={\frac {1}{\sqrt {2^{n))))\sum _{i=0}^{2^{n}-1}|i\rangle |f(i)\rangle }$

${\displaystyle |\phi _{3}\rangle =H^{\otimes n}|\phi _{2}\rangle ={\frac {1}{2^{n))}\sum _{i=0}^{2^{n}-1}\sum _{j=0}^{2^{n}-1}(-1)^{ij}|i\rangle |f(j)\rangle }$

Taką procedurę należy niezależnie powtórzyć n-krotnie, za każdym razem mierząc stan pierwszego rejestru. W wyniku takiego działania powinniśmy otrzymać n liniowo niezależnych wektorów w ${\displaystyle \{0^{(}n)\},}$ które podstawione do układu równań jednorodnych w przestrzeni ${\displaystyle \mathbb {Z} _{2))$ powinny dać jako rozwiązanie szukane ${\displaystyle s.}$