Algorytm Simona

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.}$

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.