4501
правка
Квантовый алгоритм различения элементов: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм различения элементов (посмотреть исходный код)
Версия от 21:56, 7 марта 2023
, 7 марта 2023→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == В задаче различения элементов дается список из N элементов x1; x N 2f 1,…») |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
В задаче различения элементов дается список из N элементов | В задаче ''различения элементов'' дается список из N элементов <math>x_1, ..., x_N \in \{ 1, ..., m \}</math> и требуется определить, содержит ли список два одинаковых элемента. Доступ к списку предоставляется путем подачи запросов в «черный ящик», причем возможны два типа запросов. | ||
Запросы о значениях. В этом типе запросов входными данными для черного ящика является индекс i, а в качестве ответа он выдает | '''Запросы о значениях'''. В этом типе запросов входными данными для черного ящика является индекс 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. | ||
'''Запросы о сравнениях'''. В этом типе запросов входные данные для черного ящика состоят из двух индексов i, j, и он выдает один из трех возможных ответов: «xi > xj», «xi < xj» или «xi = xj». В квантовой версии на вход подается квантовое состояние, состоящее из базисных состояний j i; j; zi, где i, j – два индекса, а z – рабочее пространство алгоритма. | |||
Запросы о сравнениях. В этом типе запросов входные данные для черного ящика состоят из двух индексов i, j, и он выдает один из трех возможных ответов: «xi > xj», «xi < xj» или «xi = xj». В квантовой версии на вход подается квантовое состояние, состоящее из базисных состояний j i; j; zi, где i, j – два индекса, а z – рабочее пространство алгоритма. | |||