Алгоритм Гровера: что вводить в Oracle?

Я запутался в том, что вводить в Oracle в алгоритме Гровера.

Разве нам не нужно вводить то, что мы ищем, и где найти то, что мы ищем в Oracle, в дополнение к суперпозиционным квантовым состояниям?

Например, предположим, что у нас есть список имен людей {"Алиса", "Боб", "Кори", "Дио"}, и мы хотим выяснить, есть ли в списке "Дио". Затем Oracle должен принять в качестве входа и выхода . Я вроде это понимаю. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

Но разве нам не нужно вводить слово «Dio» и список {«Алиса», «Боб», «Кори», «Дио»} в Oracle? Иначе, как Oracle может вернуть результат? Не упоминается ли это явно, поскольку Oracle является черным ящиком, и нам не нужно думать о том, как его реализовать?

Я понимаю, что Oracle

Oracle имеет возможность распознавать, есть ли слово «Dio» в списке.
Для этого Oracle принимает суперпозиционные квантовые состояния в качестве входных данных, где каждое квантовое состояние представляет индекс списка.
Таким образом, ввод для Oracle означает, проверьте, находится ли слово «Dio» в индексе 0 списка, и верните если да, и верните противном случае. $|00\rangle$ $-|00\rangle$ $|00\rangle$
В нашем случае Oracle возвращает . $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
Но как насчет списка и слова?

algorithm grovers-algorithm oracles Бик
источник

Несмотря на то, что этот вопрос сформулирован не так, я полагаю, что ваш вопрос более или менее такой же, как этот: алгоритм Гровера: где список?

DaftWullie

Ответы:

Хотя популярные объяснения алгоритма Гровера говорят о поиске по списку, в действительности вы используете его для поиска возможных входных данных 0..N-1 для функции. Стоимость алгоритма $O(\sqrt{N} \cdot F)$ где $N$ это количество входов, которые вы хотите найти и $F$ стоимость оценки функции. Если вы хотите, чтобы эта функция осуществляла поиск по списку, вы должны жестко закодировать список в функцию.

Жесткое кодирование функции для использования списка из элементов, как правило, является очень плохой идеей, поскольку она приводит к тому, что становится равным . Что составило бы общую стоимость алгоритма Гровера . Какой вид поражений вся цель, так . $N$ $F$ $O(N)$ $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$ $N^{1.5} > N$

Крейг Гидни
источник

Разве вы не вводите упорядоченный список, что делает поиск намного быстрее? Конечно, вы можете захотеть включить стоимость заказа списка, но я думаю, что в целом он все равно будет равен .

O (\sqrt{N} \log (N))

$O(\sqrt{N}\log(N))$

DaftWullie

@DaftWullie Проблема в том, что Гровер должен выполнить поиск в суперпозиции, и для этого требуется схема мультиплексора с вентилями N AND (или другими операциями, не относящимися к Клиффорду). Квантовый логический элемент И (то есть Toffoli) имеет немаловажную стоимость при выполнении исправления ошибок. Эта стоимость технически также присутствует в классической машине (т. Е. ОЗУ имеет О (N) И вентили), просто она ничтожна и даже ее можно избежать в этом контексте.

Крейг Гидни

Я не понимаю, что вы говорите. Сможете ли вы выразить вопрос и ответить на него, чтобы показать детали? (Я не думаю, что смогу

сформулировать

@DaftWullie Я думаю, что вопрос будет что-то вроде «как я могу дать квантовому компьютеру доступ для чтения к классической базе данных и насколько это дорого».

Крейг Гидни