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

''Алгоритм квантового запроса'' <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.

Рассмотрим задачу поиска треугольников в неизвестном (простом, неориентированном) графе G С {(а, b) : a;b 2 [n]; a ф bg c вершинами [n] = {1, ... n} и m = |G| неориентированных ребер, где (a, b) = (b, a) по соглашению. Функция f, к которой выполняются запросы, представляет собой матрицу смежности графа G, а свойство P, которое необходимо вычислить, заключается в том, содержит ли G треугольник.

Задача 1 (поиск треугольников)