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

9

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

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

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

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

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

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

Ответы:

4

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

Жесткое кодирование функции для использования списка из элементов, как правило, является очень плохой идеей, поскольку она приводит к тому, что становится равным . Что составило бы общую стоимость алгоритма Гровера . Какой вид поражений вся цель, так .NFО(N)О(NF)знак равноО(NN)знак равноО(N1,5)N1,5>N

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