Algorytm Simona

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

Problem

Niech istnieje funkcja:

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

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

${\mathrm{\forall }}_{x^{\prime }\ne x}(f(x^{\prime })=f(x)\iff x^{\prime }=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:

$|{\varphi }_0⟩=|0^{(n)}⟩|0^{(m)}⟩$

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

$|{\varphi }_2⟩=U_f|{\varphi }_1⟩=U_f\frac{1}{\sqrt{2^n}}\sum _{i=0}^{2^n-1}|i⟩|0^{(m)}⟩=\frac{1}{\sqrt{2^n}}\sum _{i=0}^{2^n-1}|i⟩|f(i)⟩$

$|{\varphi }_3⟩=H^{\otimes n}|{\varphi }_2⟩=\frac{1}{2^n}\sum _{i=0}^{2^n-1}\sum _{j=0}^{2^n-1}(-1{)}^{ij}|i⟩|f(j)⟩$

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 $\{0^{(}n)\},$ które podstawione do układu równań jednorodnych w przestrzeni ${\mathbb{Z}}_2$ powinny dać jako rozwiązanie szukane $s.$

Bibliografia

• Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, Szablon:ISBN.
• Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, Volume 26, Issue 5, 1997, s. 1474–1483 Szablon:ISSN.