Algorytm Simona

Z Wikipedii

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

Spis treści

1 Problem
2 Rozwiązanie klasyczne
3 Rozwiązanie kwantowe
4 Literatura

[edytuj] Problem

Niech istnieje funkcja

$f :{0,1} n - > {0,1} m$ gdzie $m \geq 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)$

[edytuj] Rozwiązanie klasyczne

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

[edytuj] 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$ .

[edytuj] Literatura

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, ISSN 0097-5397

Kategorie: Algorytmy • Informatyka kwantowa

We provide Linux to the World

Algorytm Simona

Z Wikipedii

Spis treści

[edytuj] Problem

[edytuj] Rozwiązanie klasyczne

[edytuj] Rozwiązanie kwantowe

[edytuj] Literatura

Views

nawigacja

zmiany

dla edytorów

Szukaj