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\geqslant n-1.$

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

$\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:

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

$|\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 $|i\rangle \in \{0,1,...2^{n}-1\}$ jest liczbą zakodowaną na pierwszych $n$ bitach

$|\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$

$|\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 $\{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, ISBN 83-87674-57-5.
• Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, Volume 26, Issue 5, 1997, s. 1474–1483 ISSN 0097-5397.