Algorytm Simona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Problem[edytuj]

Niech istnieje funkcja:

gdzie .

Należy sprawdzić czy:

.

Rozwiązanie klasyczne[edytuj]

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

Rozwiązanie kwantowe[edytuj]

Rozwiązanie opiera się na układzie kwantowym, który niezależnie rozwiązuje się n-krotnie.

Wygląda on następująco:

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 , które podstawione do układu równań jednorodnych w przestrzeni powinny dać jako rozwiązanie szukane .

Bibliografia[edytuj]

  • 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