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

'''Запросы о сравнениях'''. В этом типе запросов входные данные для черного ящика состоят из двух индексов i, j, и он выдает один из трех возможных ответов: "<math>x_i > x_j</math>", "<math>x_i < x_j</math>" или "<math>x_i = x_j</math>". В квантовой версии на вход подается квантовое состояние, состоящее из базисных состояний <math>|i, j, z \rangle</math>, где i, j – два индекса, а z – рабочее пространство алгоритма.

Есть несколько причин, в силу которых задача различения элементов интересна для изучения. Во-первых, она связана с сортировкой. Возможность сортировки набора <math>x_1, ... , x_N</math> позволяет решить задачу различения элементов, сначала отсортировав <math>x_1, ... , x_N</math> в порядке возрастания. Если имеются два одинаковых элемента xi = xj, то в отсортированном списке они будут находиться рядом друг с другом. Поэтому после сортировки набора <math>x_1, ... , x_N</math> нужно только проверить отсортированный список, чтобы убедиться, что каждый элемент отличается от следующего. Из-за этой связи между задачами сложность различения элементов равносильна сложности сортировки. Результатом стал длинный список исследований классических нижних границ для задачи различения элементов (см. [6, 8, 15] и многие другие работы).

Во-вторых, центральным понятием алгоритмов для решения задачи различения элементов является понятие коллизии. Это понятие может быть обобщено разными способами, и его обобщения полезны для построения квантовых алгоритмов для решения разных теоретико-графовых (например, поиска треугольников [12]) и матричных задач (например, проверки матричных тождеств [7]).

Обобщением задачи различения элементов является задача о k-различении элементов [2], в которой нужно определить, существует ли k различных индексов <math> таких, что xi1 = xi2 = ■■■ = xik. Дальнейшим обобщением является задача нахождения k-подмножества [ ], в которой задается функция f(y1... ; yk) и нужно определить, существуют ли ii,..., lit € {1,... , N} такие, что /(х,-,д,2,...,xik) = 1.