Algorytm Simona

Algorytm Simona to 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

$\exists_{s \in \{0,1\}^n \setminus \{0^\left(n\right )\}} \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 on następująco:

$| \phi_0 \rangle = |0^{\left(n\right)} \rangle |0^{\left(m\right)} \rangle$

$| \phi_1 \rangle = H^{\otimes n} |0^{\left(n\right)} \rangle |0^{\left(m\right)} \rangle = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} | i \rangle |0^{\left(m\right)} \rangle$

$| \phi_2 \rangle = U_f | \phi_1 \rangle = U_f \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} | i \rangle |0^{\left(m\right)} \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^\left(n\right )\}$, 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, pp. 1474-1483 ISSN 0097-5397