Квантовый алгоритм поиска треугольников: различия между версиями

''Алгоритм квантового запроса'' <math>Q_f : | \psi_0 \rangle \mapsto | \psi_f \rangle \;</math> вычисляет свойство P функции f при помощи отображения исходного состояния <math>| \psi_0 \rangle = | 0 \rangle | 0 \rangle | 0 \rangle \;</math> (в котором регистры ''запроса'', ''ответа'' и ''рабочего пространства'' очищены) на конечное состояние <math>| \psi_f \rangle = Q_f | \psi_0 \rangle \;</math> , применяя последовательность <math>Q_f = U_k O_f U_{k - 1} O_f ... U_1 O_f U_0 \;</math> унитарных операторов на комплексном векторном пространстве, натянутом на все возможные базисные состояния <math>| x \rangle | a \rangle | z \rangle \;</math>. Унитарные операторы могут быть двух типов: ''запросы оракула'' <math>O_f : | x \rangle | a \rangle | z \rangle \mapsto | x \rangle | a \oplus f(x) \rangle | z \rangle</math>, приносящие информацию о f, и ''шаги без запросов'' <math>U_k \;</math>, не зависящие от f. ''Сложность квантовых запросов'' P равна минимальному числу запросов оракула, требующихся квантовому алгоритму для вычисления P с вероятностью не менее 2/3.