Всякий раз, когда рекламируется новая технология, людям становится любопытно, что она может предложить. Учитывая внимание, которое привлекают квантовые вычисления, вы можете задаться вопросом, действительно ли они имеют преимущества перед компьютерами, которые у нас есть сегодня. В этом посте я представлю алгоритм Дойча-Йожа [1], первый предложенный квантовый алгоритм, который оказался быстрее, чем лучшее классическое решение.
Представьте, что у вас есть «черный ящик», и он действует как функция f:{0,1}ⁿ→{0,1}, то есть принимает на вход n бит и выдает 1 бит, а вы не знаете как эта функция реализована или как она себя ведет. Единственное, что вы знаете, это то, что функция может иметь только одно из двух вариантов поведения: функция либо постоянная, то есть она всегда выводит 0, либо всегда выводит 1, либо она сбалансирована, поэтому выводит 0 ровно для половины входных данных, и выходы 1 для другой половины входов. Чтобы привести пример, скажем, у нас есть n = 2, поэтому возможные входные данные: 00, 01, 10, 11. Если функция постоянна, мы имеем:
- f(00)=f(01)=f(10)=f(11)=0 or
- f(00)=f(01)=f(10)=f(11)=1
Если функция сбалансирована, у нас есть много возможностей, и вы можете увидеть несколько примеров ниже.
- f(00)=f(01)=0 и f(10)=f(11)=1 или
- f(00)=f(11)=0 и f(01)=f(10)=1
Цель алгоритма Дойча-Йожы — определить, является ли функция постоянной или сбалансированной, используя наименьшее количество возможных вызовов функции. Чтобы понять, в чем превосходство квантового алгоритма, мы должны сначала рассмотреть классическое решение.
Классическое решение:
В лучшем случае для классического решения требуется два вызова функции. В этом случае первый вызов возвращает 0, а второй возвращает 1 или наоборот. Это верно, потому что если есть два разных выхода, то функция должна быть сбалансирована.
Однако в худшем случае нам потребуется ((2ⁿ÷2) +1) вызовов функции. Это связано с тем, что возможно, что первая половина вызовов вернет одно и то же значение, поэтому, если следующий вызов возвращает то же самое, что и предыдущие, то f является постоянным, а если выходные данные отличаются, то f сбалансировано.
Квантовое решение:
Используя для этой задачи квантовый компьютер, мы можем решить ее с помощью одного вызова. Итак, ясно, что даже при n=1 квантовое решение быстрее, и преимущество становится еще больше, когда мы увеличиваем размер входных данных. Итак, как это возможно?
Первый шаг — реализовать функцию f в виде квантового оракула, похожего на черный ящик, и этот оракул сопоставит ввод |x⟩|y⟩ с |x⟩|y ⊕ f(x)⟩. Знак ⊕ означает сложение по модулю 2, также известное как XOR. Мы будем называть этот оракул Уф.
Полная схема алгоритма выглядит следующим образом:
На случай, если вы запутались, это «⊗n», которое вы видите, означает, что действие происходит в n кубитах. Это означает, что имеется n кубитов, инициализированных как |0⟩, и затем к ним применяются n вентилей Адамара.
Чтобы объяснить, что происходит, будет интересно посмотреть на состояние системы во время каждого шага.
- Шаг 0:
- Шаг 1 (после Адамара):
Здесь приятно видеть эффект Адамара только на оба регистра, а затем эффект на всю систему.
- Шаг 2 (после Uf):
Обратите внимание, что в текущем состоянии y = (|0⟩ -|1⟩). Когда применяется U_f, результат следующий.
Чтобы упростить это состояние, обратите внимание на следующие свойства XOR:
При этом мы можем написать, что:
Это позволяет переписать этот термин как
В результате состояние
- Шаг 3 (после последнего Адамара):
Здесь мы можем игнорировать второй регистр (вспомогательный кубит), так как он не будет измеряться. Это оставляет нас со следующим состоянием.
Чтобы понять этот следующий шаг, знайте, что мы можем записать эффект вентилей Адамара в некотором состоянии | x⟩ как
где x.y является побитовым произведением, поэтому x.y=x₀y₀ ⊕ x₁y₁ ⊕ … ⊕xₙyₙ. С учетом сказанного, когда Адамар применяется к |ψ2⟩, мы получаем наше конечное состояние.
Заметьте, что если вы хотите быть строгим, то промежуточные шаги этой последней операции неверны, поскольку сумма является частью определения состояния |x⟩, и Адамар фактически применяется и к ней. Но так как это не повлияет на результаты, и я считаю, что это облегчает понимание того, что было сделано, я решил оставить это как есть.
- Измерение:
Теперь пришло время измерить, и здесь происходит волшебство. Заметим, что если мы хотим измерить состояние |00…0⟩, то есть |y⟩ = |00…0⟩, то вероятность этого измерения определяется выражением
Итак, как видите, если мы измеряем результат один раз и он равен |00…0⟩, то мы точно знаем, что функция постоянна, а если получаем любой другой результат, то функция уравновешена. Итак, как было сказано ранее, вместо ((2ⁿ÷2) +1) мы использовали один вызов функции, то есть этот алгоритм экспоненциально быстрее классического.
Теперь, когда вы знаете теорию, лежащую в основе алгоритма, мы можем использовать такую платформу, как qiskit, чтобы реализовать его и опробовать на реальном квантовом компьютере. Должен сказать, что большая часть приведенного ниже кода основана на документации qiskit [2], поэтому, если вам нужна дополнительная информация, ознакомьтесь с ней.
Реализация Qiskit:
Настройка среды:
import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
n=3 #size of the input
from qiskit import IBMQ
IBMQ.save_account("*token*")
IBMQ.load_account()
provider = IBMQ.get_provider("ibm-q")
Создание Оракула:
Мы можем создать постоянный оракул или сбалансированный. Я создам оба, чтобы вы знали, как они выглядят.
- Постоянный оракул:
const_oracle = QuantumCircuit(n+1)
output = np.random.randint(2) #Randomly decides if f(x)=0 or f(x)=1
if output == 1:
const_oracle.x(n)
const_oracle.draw()
- Сбалансированный оракул:
Сбалансированный оракул реализуется через некоторые вентили CNOT. Кроме того, мы добавляем несколько вентилей НЕ, чтобы изменить управляющие кубиты, чтобы CNOT имел некоторый эффект. Однако НЕ применяется дважды, поэтому управляющий кубит переходит в исходное состояние после Uf.
balanced_oracle = QuantumCircuit(n+1)
b_str = "101" # This string simply determines the balance
# Place X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)
# Use barrier as divider
balanced_oracle.barrier()
# Controlled-NOT gates
for qubit in range(n):
balanced_oracle.cx(qubit, n)
balanced_oracle.barrier()
# Place X-gates to return qubits to original state
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)
# Show oracle
balanced_oracle.draw()
Остальная часть алгоритма:
dj_circuit = QuantumCircuit(n+1, n)
# Apply H-gates
for qubit in range(n):
dj_circuit.h(qubit)
# Put ancilla qubit in state |->
dj_circuit.x(n)
dj_circuit.h(n)
# Add oracle
dj_circuit += balanced_oracle #You can change for constant oracle
# Repeat H-gates
for qubit in range(n):
dj_circuit.h(qubit)
dj_circuit.barrier()
# Measure
for i in range(n):
dj_circuit.measure(i, i)
# Display circuit
dj_circuit.draw()
Примечания: Схема создана с использованием n+1 кубитов, потому что у нас есть вспомогательный кубит, инициализированный как |1⟩. Кроме того, обратите внимание, что вы можете добавить оракул к этой схеме с помощью операции +=, поэтому НЕ, которые вы видите в полной схеме, являются частью оракула, а не частью внешней схемы.
Результаты:
from qiskit import execute
backend = provider.get_backend("ibmq_quito")
job = execute(dj_circuit, backend=backend, shots=500)
result = job.result()
answer = result.get_counts()
plot_histogram(answer)
Как видите, небольшая вероятность получить результат 000 все еще была, но это из-за некоторого шума, который возникает на реальных квантовых компьютерах, таких как тот, на котором выполнялись алгоритмы. Это означает, что ожидаемый результат не равен 000, то есть функция сбалансирована, что правильно. Если хотите, можете переключить оракулов и проверить, верны ли результаты.
Несмотря на то, что это первый алгоритм, превосходящий классический, его преимущества не очень полезны, поскольку проблема, которую он решает, не является чем-то, что нам нужно решать часто. Таким образом, несмотря на то, что это доказывает, что квантовые компьютеры могут превзойти классические, существуют другие алгоритмы, которые могут делать то же самое, но также решать полезные и интересные задачи, такие как алгоритм Гровера и алгоритм Шора. Помимо алгоритмов, эту технологию можно использовать и в других областях, таких как машинное обучение и химия.
Учитывая все вышесказанное, я считаю, что можно с уверенностью сказать, что квантовые компьютеры — это не только шумиха, но и то, что они смогут предложить нам реальные преимущества в ближайшем будущем.
Использованная литература:
[1] Дэвид Дойч и Ричард Джосса (1992). Быстрое решение задач с помощью квантовых вычислений. Труды Лондонского королевского общества A. 439: 553–558. doi:10.1098/rspa.1992.0167
