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

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

Дано: матрица смежности графа G с n вершинами. Требуется: найти треугольник с вероятностью не менее 2/3, если таковой существует (версия с поиском) либо булево значение, показывающее, существует ли треугольник, с вероятностью не менее 2/3 (версия с принятием решений).

Нижняя граница сложности квантовых запросов <math>\Omega (n) \;</math> задачи поиска треугольников была найдена Бурманом и коллегами [6]. Тривиальная верхняя граница <math>O(n^2) \;</math> получается в результате классического опроса каждого элемента.

'''Классические результаты'''

 

Классический показатель сложности рандомизированных запросов определяется подобно сложности квантовых запросов, с той разницей, что операторы <math>U_k \;</math> являются стохастическими, а не унитарными; в частности, это означает, что запросы оракула могут выполняться в соответствии с классическим распределением, а не с квантовыми суперпозициями. Легко увидеть, что сложность рандомизированных запросов для задачи поиска треугольников (в версиях с поиском и принятием решений) составляет <math>\Theta (n^2) \;</math>.