Algorytm Simona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm Simonaalgorytm kwantowy znajdujący rozwiązanie poniższego zagadnienia.

Problem[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Rozwiązanie kwantowe[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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