Построение Oracle для алгоритма Гровера

16

В «Квантовых вычислениях и квантовой информации» Майка и Айка алгоритм Гровера объясняется очень подробно. Тем не менее, в книге и во всех объяснениях, которые я нашел в Интернете для алгоритма Гровера, кажется, нет упоминания о том, как устроен Оракул Гровера, если только мы уже не знаем, какое именно состояние мы ищем, в ущерб цели алгоритм. В частности, мой вопрос заключается в следующем: учитывая некоторое f (x) такое, что для некоторого значения x f (x) = 1, но для всех остальных f (x) = 0, как можно построить оракула, который получит нас от наше начальное, произвольное состояние | x> | y> to | x> | y + f (x)>? Будем весьма благодарны как можно более подробные подробности (возможно, пример?). Если такая конструкция для любой произвольной функции возможна с Адамаром, Паули или другими стандартными квантовыми вентилями,

quantum-computing quantum-information oracles search-problem black-box Будет
источник
«здесь, похоже, нет упоминания о том, как устроен Oracle Гровера, если только мы уже не знаем, какое именно состояние мы ищем, в ущерб цели алгоритма.» ... «Oracle Гровера» - это проблема, которую нужно решить. Вы не строите это. Вам дали (доступ к оракулу) это и попросили выполнить вычисление, чтобы раскрыть значение. Если это поможет, сделайте вид, что я создаю оракула, а затем попросите вас решить проблему. (Также обратите внимание, что чтение / запись / подготовка базы данных из элементов занимает больше времени, чем запуск Гровера √NАлгоритм N- времени.)N
Даниэль Апон
2
Но что, если вместо того, чтобы получить оракула, нам дадут немного f (x)? Представьте, что мы решаем проблему 3-SAT и хотим использовать решения Grover для ускорения решения. Мы знаем рассматриваемое f (x) (предложения истинности 3-SAT), но не обязательно знаем, какая строка битов x даст истинный результат при подключении к 3-SAT. Неужели нет способа создать оракула из функции 3-SAT, чтобы найти правильную строку битов? Если нет, и это, как вы предлагаете, что-то, что должно быть предоставлено кем-то другим, алгоритм Гровера кажется довольно искусственным, просто упражнение, данное вам.
Будет

Ответы:

20

Оракул - это просто реализация предиката, для которого вы хотите найти удовлетворительное решение.

Например, предположим, что у вас есть проблема с 3-мя соседями:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Или, в форме таблицы, где каждая строка состоит из 3-х предложений, x означает «эта переменная false», o означает «эта переменная true», а пробел означает «не в предложении»:

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Теперь создайте схему, которая вычисляет, является ли ввод решением, например:

проверка решения

Теперь, чтобы превратить вашу схему в оракула, нажмите выходной бит с помощью Z-шлюза и вычислите весь мусор, который вы сделали (т.е. запустите вычислительную схему в обратном порядке):

цепь оракула

Это все, что нужно сделать. Вычислите предикат, ударьте результат Z, отмените вычисление предиката. Это оракул.

Итерируйте шаги диффузии с шагами оракула, и вы получите большой поиск :

Гровер поиск

... хотя вам, вероятно, следует выбрать пример с меньшим количеством решений, поэтому прогресс будет постепенным (вместо того, чтобы вращаться вдоль плоскости состояния начального состояния-решения более чем на 90 градусов за шаг, как в моем примере).

Крейг Гидни
источник
Спасибо, это было очень полезно. Невероятно ясно, ответил на все, что я просил (и даже использовал общие квантовые вентили!). Есть ли причина, по которой вы решаете изменить все свои стартовые кубиты на состояние | 1>, прежде чем ставить их в суперпозицию с вентилями Адамара вместо того, чтобы просто ставить | 0 > Государственные кубиты через Адамара (т.е. есть ли в этом преимущество)? Кроме того, что это за операции диффузии? Выглядит как контролируемый X, но вы используете | 1> или | 0> в качестве элементов управления?
Будет
(12|0⟩−12|1⟩)⊗n
Фантастический ответ, и спасибо за ссылку на algassert.com/quirk !
Фредерик