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

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