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

'''Запросы о значениях'''. В этом типе запросов входными данными для черного ящика является индекс i, а в качестве ответа он выдает <math>x_i</math>. В квантовой версии этой модели входные данные представляют собой квантовое состояние, которое может быть запутано с рабочим пространством алгоритма. Совместное состояние запроса, регистра ответа и рабочего пространства может быть представлено в виде <math>\sum_{i, y, z} a_{i, y, z} | i, y, z \rangle</math>, причем y – это дополнительный регистр, который будет содержать ответ на запрос, а z – рабочее пространство алгоритма. Черный ящик преобразует это состояние в <math>\sum_{i, y, z} a_{i, y, z} | i, (y + x_i) mod \; m, z \rangle</math>. Простейшим частным случаем является случай, когда входные данные для черного ящика имеют вид <math>\sum_i a_i | i, 0 \rangle</math>. Тогда черный ящик выдает <math>\sum_i a_i | i, x_i \rangle</math>. То есть квантовое состояние, состоящее из индекса i, преобразуется в квантовое состояние, каждый компонент которого содержит <math>x_i</math> вместе с соответствующим индексом i.

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