Как алгоритм Гровера применяется к базе данных?

Вопрос

Я хочу использовать алгоритм Гровера для поиска в несортированной базе данных элемента . Теперь возникает вопрос, как я могу инициализировать индекс и значение базы данных с кубитами?$x$

пример

• Допустим, у меня есть кубита. Таким образом, классических значений могут быть сопоставлены.$4$$2 ^ 4 = 16$
• Моя несортированная база данных имеет следующие элементы: .$d$$d [\text{Value}] = [3,2,0,1]$
• Я хочу найти .$x = 2_d = 10_b = |10\rangle$
• Мой подход: индексировать базу данных с помощью . Регистры и для индекса и регистры и для значения. Затем примените алгоритм Гровера только к регистрам и . Может ли это быть реализовано? Есть ли другой подход?$d$$d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$$0$$1$$2$$3$$2$$3 (\text{Value})$

Что я уже реализовал ( на GitHub )

«Алгоритм Гровера с 2-, 3-, 4-кубитами», но он прост: биты инициализируются с помощью , оракул помечает мое решение (это просто число типа ), часть Гровера будет увеличивать вероятность выбранного элемента и уменьшать все другие вероятности, а затем считываются кубиты, отображаясь в классические биты. Мы позволяем этому процессу запускаться несколько раз подряд и, таким образом, получаем распределение вероятностей, где наибольшая вероятность имеет искомый элемент .$|0\rangle$$x$$2_d = 10_b$$x$$x$

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

Я также работал над этой проблемой. Будучи новичком и классическим программистом (то есть я не говорю на квантовой механике), трудно получить представление о концепциях без полных примеров. Я работал с примером поиска в базе данных Microsoft Q # . Он просто ищет определенный индекс / ключ в базе данных, что не очень полезно. Я расширил этот пример, чтобы найти список значений в базе данных и вернуть соответствующий ключ.

Как и в вашем примере, есть один двухкбитовый «регистр ключей» для индексов и отдельный двухкбитовый регистр для значений. Существует также пятый «помеченный кубит», полученный из образца Microsoft, чтобы указать, когда будет найдено желаемое значение. Ключи и значения связаны через запутывание. Это лучше всего продемонстрировать на схеме. Нажмите здесь, чтобы увидеть фактическую схему Quirk .

Обратите внимание, что эта схема содержит только оракула. Он не реализует весь алгоритм Гровера.

• Два верхних кубита - это регистр ключа, следующие два - регистр значения, а нижний кубит - помеченный кубит.
• Первый раздел помещает регистр ключей в единую суперпозицию с использованием вентилей Харамара, как того требует алгоритм Гровера.
• Второй раздел, где ключи связаны со значениями через запутывание. Каждый ключ запутывается с соответствующим значением в регистре значений, применяя (Анти-) Контролируемые ворота X. Таким образом, когда регистр ключа равен 0, тогда регистр значения будет установлен на 3. Когда ключ равен 1, значение установлено на 2, и так далее.
• Третий раздел схемы - поисковый оракул. Регистр значений запутан с отмеченным кубитом. В этом примере требуемое значение равно 2. Когда регистр значений содержит 2, отмеченный кубит будет установлен в 1.
• Алгоритм Гровера смотрит на регистр ключей и помеченный кубит. Оракул поиска смотрит на регистр значений и устанавливает помеченный кубит. Это приведет к усилению клавиши 1, когда значение равно 2.

Интересно отметить, что ключи и значения хранятся не в кубитах, а в схеме / программе. Можно сказать, что на самом деле это не база данных. Это больше похоже на оператор switch / case, но может работать с суперпозицией значений.

Для получения дополнительной информации, предупреждений и кода Q # см. Мой репозиторий GitHub .

РЕДАКТИРОВАТЬ: Что-то, что я понимаю лучше с момента ответа ... вы должны повернуть / отменить схему как часть каждой итерации. В коде Q # это обрабатывает вызов Adjoint StatePreperationOracle () в операции ReflectStart (), поэтому мне не пришлось делать это явно. Я не знаю, есть ли у Qiskit похожая функция. Если я сделал перевод правильно, вот полная схема для примера выше.

При представлении алгоритма Гровера применительно к поиску в базе данных предполагается, что Oracle имеет доступ к элементам классического списка. Тем не менее, это очень сильное предположение, и именно поэтому мы представляем это с помощью управляемого селектора с использованием CNOT / Toffolis индекса, представляющего просто эту операцию (как схема Toffoli в случае ).$n=4$

Вы упомянули подход вычисления значений в другом регистре: Вы снова предполагаете, что вам дали оракула за это и эффективно (простой способ - контролировать НЕ, но вы должны делать это для каждого индекса / значения, поэтому не очень эффективного). В этом случае оракулом будет функция в формате квантовой схемы (опять же, управляемый селектор), помечающая это состояние и продолжающая итерации Гровера.

Я думаю, что лучше рассматривать алгоритм квантового поиска как оптимизирующую функцию, а не искать в списке / базе данных. Вот статья, над которой я работал, где квантовый поиск используется для решения проблемы комбинаторной максимизации, если вы хотите продолжить свое понимание алгоритма.

Вам также необходимо преобразовать оракул в базу данных, в результате чего общий Oracle (Phase Inversion) будет иметь два субракула, чтобы взглянуть на рисунок.

Первый подракул, который должен быть подготовлен, - это схема памяти, в отличие от QRAM, которая хранит квантовые данные (состояние) в своем теле, эта схема памяти (массива) подготовлена ​​для хранения только классической информации в своем кадре. Пример такого рода схемы , которая хранит массив двоичных файлов [010, 110, 100, 011] отображается ниже: Более прочитать эту бумагу .