Algorytm Simona – algorytm kwantowy znajdujący rozwiązanie poniższego zagadnienia.
Problem
Niech istnieje funkcja:
gdzie ![{\displaystyle m\geqslant n-1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b48b792da85e7f19192f9dbad552bc5c88e1b77)
Należy sprawdzić czy istnieje takie
że:
![{\displaystyle \forall _{x'\neq x}(f(x')=f(x)\Leftrightarrow x'=x\oplus s).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa6e6c7f1b73023fc343d03350773b050ea1284)
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:
![{\displaystyle |\phi _{0}\rangle =|0^{(n)}\rangle |0^{(m)}\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bfa989da1d006340d4bd486458827cd9f022c5e)
gdzie
jest liczbą zakodowaną na pierwszych
bitach ![{\displaystyle |\phi _{2}\rangle =U_{f}|\phi _{1}\rangle =U_{f}{\frac {1}{\sqrt {2^{n}}}}\sum _{i=0}^{2^{n}-1}|i\rangle |0^{(m)}\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{i=0}^{2^{n}-1}|i\rangle |f(i)\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f2c7eafebae789ff3ba98d44d0c93c9d33812c6)
![{\displaystyle |\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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/887c3a9d1dcd521ceb14697b8abd64aa93ef31b7)
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, ISBN 83-87674-57-5.
- Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, Volume 26, Issue 5, 1997, s. 1474–1483 ISSN 0097-5397.