Изменения

|definition=Пусть имеется функция <tex> f: A \{0,1\}^n \rightarrow B \{0,1\} </tex>, такая, что <tex>f(x)=xux\cdot u\pmod2\equiv (x_1\wedge u_1) \oplus (x_2\wedge u_2)\oplus\ldots\oplus(x_n\wedge u_n)</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.

|style="background-color:#FFF;padding:2px 10px"| '''1'''}|}то <tex>u = 101</tex>.

'''''Квантовый алгоритм:''''' <tex>O(1)</tex>. Такая сложность достигается благодаря квантовым свойствасвойствам<ref>[https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80 Википедия {{---}} Квантовый компьютер]</ref>, а конкретно параллелизму<ref>[https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D0%B8%D0%B7%D0%BC Википедия {{---}} Квантовый параллелизм]</ref>.

|definition=Пусть имеется функция <tex> f: A \{0,1\}^n \rightarrow B \{0,1\} </tex>, такая, что <tex>f(x+\oplus S)=f(x)</tex> с неизвестным <tex>S\in \{0,1\}^n</tex>. Найти <tex>S</tex> за минимальное количество обращений к функции <tex>f</tex>.

|style="background-color:#FFF;padding:2px 10px"| '''001'''|style="background-color:#FFF;padding:2px 10px"| '''100'''}|style="background-color:#FFF;padding:2px 10px"| '''010'''|style="background-color:#FFF;padding:2px 10px"| '''000'''|style="background-color:#FFF;padding:2px 10px"| '''100'''|style="background-color:#FFF;padding:2px 10px"| '''001'''|}то <tex>S = 101110</tex>.

Аналогично предыдущему алгоритму вычисляем все возможные суперпозиции передаём в "черный ящик", полученный результатопять пропускаем через гейт Адамара. В конце измеряем полученные значения, который будет которые будут являться некоторой строкой<tex>y</tex>, дающей ноль при скалярном умножении на искомую <tex>S</tex> ноль<tex>((y_1\wedge S_1)+(y_2\wedge S_2)+\ldots+(y_n\wedge S_n))</tex>. После <tex>n - 1</tex> итерации алгоритма получим систему из <tex>n - 1</tex> линейных уравнений; решив эту систему уравнений, найдём искомую <tex>S</tex>.:

\left\{\begin{casesalign} y_{1}^1S_1 + y_{1}^1S_2 + y_1 \dots + y_{n}^1S_n cdot s &= 0,\\ y_{1}^2S_1 + y_{2}^2S_2 + y_2 \dots + y_{n}^2S_n cdot s &= 0,\\ &\,\,\,\dotsvdots \\ y_{1}^{n-1}S_1 + y_{2}^{n-1}S_2 + \dots + y_{n}^{n-1}S_n cdot s &= 0.\\,\end{casesalign}\right.

* алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью <tex> ε < \dfrac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < εe^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \dfrac{1}{20000} </tex>.

|definition=Пусть имеется функция <tex> f: \{0,\ldots,N-1\} \rightarrow S </tex>, такая, что <tex>f((x+r)\pmod N)=f(x)</tex> с неизвестным периодом <tex>r</tex>. Найти <tex>r</tex> за минимальное количество обращений к функции <tex>f</tex>.

Так аналогично предыдущему алгоритму, но используя '''''QFT''''', получаем результат вида <tex>m\dfrac{N}{r}</tex>, где <tex>m</tex> {{---}} какое-то произвольное (случайное) натуральное число, возникающее из того, что форма рационального числа <tex>\dfrac{m}{r}</tex> не единственна в ходе алгоритма, мешающее нам сразу найти периодсвоем роде, <tex>N</tex> {{---}} модуль, <tex>r</tex> {{---}} период. Выполнив данный алгоритм <tex>n</tex> раз, найдём наибольший общий делитель<ref>[https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C Википедия {{---}} Наибольший общий делитель]</ref> от <tex>n</tex> полученных чисел, который, с некоторой вероятностью, будет искомым периодом <tex>r</tex>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.

* [https://arxiv.org/pdf/quant-ph/0012114v1.pdf Алгоритм проверки чётностиImplementation of a quantum algorithm to solve Bernstein-Vazirani’s parity problem without entanglement on an ensemble quantum computer]* [https://en.wikipedia.org/wiki/Simon%27s_problem Алгоритм СаймонаWikipedia {{---}} Simon's problem]

* [https://en.wikipedia.org/wiki/Quantum_Fourier_transform Квантовое преобразование ФурьеWikipedia {{---}} Quantum Fourier transform]* [https://pdfs.semanticscholar.org/d9dc/64159f94bde3fbe81b172e60369f3ee410f4.pdf Алгоритм ГровераQuantum parity algorithms as oracle calls, and application in Grover Database search]* [https://en.wikipedia.org/wiki/Shor%27s_algorithm Алгоритм ШораWikipedia {{---}} Shor's algorithm]