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

''Алгоритм квантового запроса'' <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> , применяя последовательность Qf = Uk Of (7^-1 Of ■ ■■ U1 Oj Щ унитарных операторов на комплексном векторном пространстве, натянутом на все возможные базисные состояния jxi j aijzi. Унитарные операторы могут быть двух типов: запросы оракула О f. |x)|e)|z) i-> |х)|аф/(х))|г:), приносящие информацию о f, и шаги без запросов Uk, не зависящие от f. Сложность квантовых запросов P равна минимальному числу запросов оракула, требующихся квантовому алгоритму для вычисления P с вероятностью не менее 2/3.