Ускорение неструктурированного поиска с помощью квантового компьютера
После алгоритма Дойча-Йожа мы обсудим алгоритм Гровера, с помощью которого было показано, что квантовые компьютеры (КК) могут быть значительно быстрее для поиска в базах данных, чем классические компьютеры. Задачу, которую призван решить алгоритм Гровера, можно выразить следующим образом: задана классическая функция f(x):{0,1}ⁿ→{0,1}, где n — размер пространства поиска в битах, найдите вход x_0, для которого f(x _0)=1. Наша идея состоит в том, чтобы подумать об оракуле (черном ящике), который способен распознавать решение задачи поиска, и это распознавание сигнализируется использованием кубита оракула. Мы подойдем к этому позже более подробно. Классически, в наихудшем сценарии мы должны оценить f(x) всего N−1 раз, где N=2ⁿ , испробовав все возможности. Мы знаем, что после N−1 элементов это должен быть оставшийся элемент. Мы увидим, что квантовый алгоритм Гровера может решить эту задачу гораздо быстрее, обеспечивая квадратичное ускорение (sqrt{N}) по сравнению с классическимслучай(N).
1. На пути к созданию оператора Гровера
Обозначим искомый вход через |x′⟩, поэтому f(x′)=1 и для любого другого x, f(x)= 0. Еще раз важно подчеркнуть, что мы предполагаем, что решение уже существует в базе данных, и мы хотим, чтобы наш алгоритм узнать решение. Основная идея заключается в том, что мы создадим состояние суперпозиции и повернем это состояние к решению |x′⟩, используя оператор Гровера. Прежде чем мы обсудим шаги итерации Гровера, давайте сначала обсудим несколько первоначальных концепций. Сначала мы рассматриваем n-битное входное состояние и создаем однородную суперпозицию, применяя H вентилей к каждому кубиту. Этот шаг и вся связанная с ним математика подробно обсуждались до, поэтому я буду использовать результат здесь —
Мы определяем это состояние суперпозиции |ψ⟩, которое является суперпозицией всех возможных состояний |x⟩. Также состояние суперпозиции уже включает состояние решения |x′⟩. Так что мы также можем написать -
Мы можем исключить это состояние решения |x′⟩, чтобы рассмотреть суперпозицию всех оставшихся состояний (плохое состояние). С этого момента «хорошее состояние» будет относиться к состоянию решения, а суперпозиция остальных состояний будет считаться «плохим состоянием». Таким образом, «плохое состояние» можно записать как —
«Плохое состояние» ортонормировано состоянию решения (также может быть более 1 решения, для простоты мы рассматриваем только одно решение). Таким образом, эти хорошие и плохие состояния образуют ортонормированный базис, и мы можем представить любой вектор, лежащий в плоскости, натянутой на эти ортонормированные векторы. Давайте сделаем это -
Теперь мы вводим оператор, который мы будем называть оператором отражения, определенным ниже:
Причина, по которой мы называем это операторным отражением состояния |ψ⟩, заключается в том, что любое состояние, перпендикулярное |ψ⟩ (скажем, состояние |ϕ ⟩) будет инвертирован как 2|ψ⟩⟨ψ|ϕ⟩−I|ϕ⟩ = −|ϕ⟩, где любое состояние, параллельное |ψ⟩, останется незатронутым этим оператором.
2. Этапы итерации Гровера:
Имея в виду эти основы, давайте теперь напишем шаги для алгоритма Гровера:
- Начните с регистра из n кубитов, инициализированного в состоянии |0⟩.
- Подготовьте регистр к однородной суперпозиции, применив H к каждому кубиту регистра.
- Примените следующие операции (1–4) к регистру N_{opt} раз. Позже мы покажем, как получить N_{opt}.
- Фазовый оракул, который применяет условный фазовый сдвиг -1 для элементов решения.
- Примените H к каждому кубиту в регистре.
- Условный фазовый сдвиг -1 для каждого базового вычислительного состояния, кроме |0⟩. Это тоже унитарная операция, и она будет обсуждаться в следующем разделе.
- Примените вентиль H к каждому кубиту в регистре.
- Измерьте регистр, чтобы получить индекс элемента, который является решением с очень высокой вероятностью.
- Проверьте, является ли это допустимым решением. Если нет, начните снова.
Теперь мы шаг за шагом поймем, используя приведенные выше уравнения, как алгоритм Гровера поможет нам распознать элемент (ы) решения.
3. Как работает алгоритм Гровера?
Мы уже обсуждали в разделе 1 единообразное состояние суперпозиции, чтобы понять, как работает алгоритм Гровера, мы сосредоточимся на шагах с 1 по 4, описанных в разделе 2.
- Первый шаг - понять, как мы можем интерпретировать действие фазового оракула, который применяет условный фазовый сдвиг -1 для элемента решения. Мы можем думать об этом как о размышлении о состоянии |ψ′⟩ или «плохом состоянии». Поскольку состояние решения перпендикулярно |ψ′⟩.
- Мы рассматриваем шаг применения условного фазового сдвига −1 к каждому вычислительному базисному состоянию, кроме |0⟩, этот шаг можно представить как — O₀ = −2|0⟩⟨0|+I. Этот шаг сопровождается применением вентилей H до и после, поэтому всю операцию можно записать как —
- Итак, теперь у нас есть оператор, представляющий отражение состояния |ψ⟩, которое является нашим однородным состоянием суперпозиции и определяется в уравнении 1, Таким образом, полный оператор Гровера может быть записан как —
Так что именно произошло на этих этапах? или как мы можем думать об операторе Гровера? ниже геометрическое представление -
Опять же, |ψ′⟩ — это суперпозиция всех состояний, кроме состояния решения, а |x′⟩ — это состояние решения. Таким образом, состояние суперпозиции |ψ⟩ находится в плоскости, натянутой на |ψ′⟩ и |x′⟩.
Именно здесь мы применяем оракул, который применяет условный фазовый сдвиг -1 для пункта решения, и мы думаем об этом как об отражении |ψ⟩ о «плохих состояниях» |ψ′⟩.
Затем мы применяем еще одно размышление об исходном состоянии суперпозиции |ψ⟩. Важно помнить урок геометрии средней школы, что композиция отражений над двумя пересекающимися линиями эквивалентна вращению. Таким образом, комбинированный эффект каждой итерации Гровера представляет собой поворот против часовой стрелки на угол 2θ (в соответствии с рисунками, которые я нарисовал, где угол между |ψ⟩ и|ψ′⟩ равен θ). Этот угол довольно легко найти, из изображений мы видим, что θ — это угол между начальным состоянием суперпозиции |ψ⟩ и |ψ ′⟩. Из уравнения 4 мы можем получить —
Здесь мы предположили, что существует только одно состояние решения, если у нас есть более одного состояния решения, мы можем соответствующим образом обобщить выражение. Используя θ, мы также можем обобщить уравнение 4, как показано ниже —
Как видно из рисунков, совокупный эффект каждой итерации Гровера представляет собой поворот против часовой стрелки на угол 2θ. Отсюда следует, что дальнейшее применение G принимает состояние —
Допустим, после поворота m мы достигли состояния решения |x′⟩, поэтому из уравнения 10, (2m+1)θ=π/2. Предполагая приближение малого угла, мы получаем -
Это на самом деле говорит нам, как и почему алгоритм Гровера помогает нам находить решение намного быстрее, обеспечивая квадратичное ускорение по сравнению с классическим алгоритмом.
4. Реализуйте алгоритм Гровера:
Теперь давайте построим схему, чтобы показать алгоритм Гровера в действии, и здесь я буду использовать Qiskit. Мы рассматриваем вентили с двумя кубитами и выбираем состояние решения как |00⟩. Вы можете рассчитать из шагов, описанных выше, что нам нужен всего один оборот, чтобы достичь состояния решения, начиная с исходного состояния суперпозиции. Если мы вернемся к разделу 2, то первым шагом к реализации алгоритма Гровера будет применение вентилей H. Для 2 кубитов состояние суперпозиции после параллельных вентилей H равно |ψ⟩=0,5(|00⟩+|01⟩+|10⟩+|11⟩). Таким образом, оракул фазового сдвига, который мы описали ранее, будет действовать следующим образом (для состояния решения |00⟩)—
Как построить оракул, который может преобразовать однородное состояние суперпозиции в приведенное выше уравнение? Рассмотрим вентиль Control Z, а матричное представление вентиля CZ —
CZ будет действовать как оракул для состояния |11⟩. Чтобы создать оракул для |00⟩, мы применяем вентиль X к каждому кубиту через вентиль CZ. В некотором смысле мы можем думать о превращении состояния |00⟩ в состояние |11⟩. Давайте медленно построим схему —
import qiskit as q import matplotlib.pyplot as plt def build_circ(num_qbits, num_cbits): qr = q.QuantumRegister(num_qbits) cr = q.ClassicalRegister(num_cbits) final_circ = q.QuantumCircuit(qr, cr) return final_circ, qr, cr def h_gates(qcirc, a, b): # 2 inputs and h gates in parallel qcirc.h(a) qcirc.h(b) hadamard_front, qr, cr = build_circ(2, 2) ### prepare the uniform superposition state h_gates(hadamard_front, qr[0], qr[1]) ### define the oracle for state |00> hadamard_front.x(qr[0]) hadamard_front.x(qr[1]) hadamard_front.cz(qr[0], qr[1]) hadamard_front.x(qr[0]) hadamard_front.x(qr[1]) hadamard_front.draw()
Пока схема выглядит так:
Для шагов со 2 по 4 в разделе 2 мы сначала применяем вентиль H к каждому кубиту в регистре, условный фазовый сдвиг -1 к каждому вычислительному базовому состоянию, кроме |0⟩, и заканчиваем H ворота для каждого кубита. Отражение состояния |0⟩ можно построить, применив вентиль Z к обоим кубитам, а затем добавив вентиль CZ. Давайте посмотрим все эти шаги в действии —
def reflection_psi(qcirc, a, b): h_gates(qcirc, a, b) qcirc.z(a) qcirc.z(b) qcirc.cz(a, b) h_gates(qcirc, a, b) reflection_psi_circ, qr_rf, cr_rf = build_circ(2, 2) reflection_psi(reflection_psi_circ, qr_rf[0], qr_rf[1]) reflection_psi_circ.draw()
Схема для размышлений о состоянии |ψ⟩ (равномерное состояние суперпозиции) выглядит следующим образом:
Таким образом, полная схема может быть составлена из комбинации вышеперечисленных схем —
complete_circuit = hadamard_front.compose(reflection_psi_circ)
for n in range(2):
complete_circuit.measure(n, n)
complete_circuit.draw('mpl', scale=1.1)
Окончательная схема выглядит так:
Прежде чем смоделировать приведенную выше схему на нашем локальном компьютере с помощью Qiskit, мы уже можем построить квантовое состояние, используя plot_bloch_multivector, и рисунок 5 уже показывает, что мы находимся в правильном направлении. Смоделируем схему —
qasm_sim = q.Aer.get_backend(‘qasm_simulator’) counts = q.execute(complete_circuit, backend=qasm_sim, shots=1024).result().get_counts() q.visualization.plot_histogram([counts], legend=[‘output’])
Мы строим гистограмму отсчетов после выполнения схемы, чтобы подтвердить, что мы вернули состояние |00⟩.
Теперь мы используем квантовый компьютер IBM, чтобы смоделировать схему и получить график гистограммы ниже. Тестирование алгоритма Гровера на квантовом компьютере показывает, что наиболее вероятным результатом будет |00⟩. По сравнению со смоделированным случаем реальное устройство по-прежнему восприимчиво к квантовому шуму, и поэтому мы можем видеть, что компоненты, отличные от |00⟩, также присутствуют.
Мы показали рабочий пример алгоритма Гровера в действии для схемы с 2 кубитами, предполагающей состояние решения |00⟩. Помимо построения оракула, как описано выше, для состояния |00⟩, есть ли другие способы построить оракул? Ниже приведен еще один пример —
Наконец, в заключение мы прошли теорию, необходимую математику одного из фундаментальных алгоритмов квантовых вычислений, алгоритма Гровера, и в конечном итоге проверили наше понимание, протестировав его с помощью Qiskit. Подробности в моем блокноте.
Держитесь и будьте здоровы!!!
Использованная литература:
[1] Оригинальная статья Гровера.
