Algorytm Simona – algorytm kwantowy znajdujący rozwiązanie poniższego zagadnienia.
Problem Niech istnieje funkcja: gdzie
Należy sprawdzić czy istnieje takie że:
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:
gdzie jest liczbą zakodowaną na pierwszych bitach
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 Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, . Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, Volume 26, Issue 5, 1997, s. 1474–1483 .
Kategoria:Algorytmy kwantowe