Алгоритм Дойча-Йожи

Для цього модуля Qiskit у класі студенти повинні мати робоче середовище Python з такими встановленими пакетами:

• qiskit v2.1.0 або новіше
• qiskit-ibm-runtime v0.40.1 або новіше
• qiskit-aer v0.17.0 або новіше
• qiskit.visualization
• numpy
• pylatexenc

Щоб налаштувати та встановити наведені вище пакети, дивись посібник Встановлення Qiskit. Щоб запускати задачі на справжніх квантових комп'ютерах, студентам потрібно зареєструватися в IBM Quantum®, виконавши кроки з посібника Налаштування облікового запису IBM Cloud.

Цей модуль було протестовано — він використав чотири секунди часу QPU. Це лише оцінка. Твоє фактичне використання може відрізнятися.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Подивись огляд модуля від Dr. Katie McCormick нижче або клікни сюди, щоб переглянути на YouTube.

---

Вступ

На початку 1980-х років квантові фізики та вчені в галузі комп'ютерних наук мали нечітке уявлення про те, що квантову механіку можна використати для обчислень, які були б набагато потужнішими, ніж те, на що здатні класичні комп'ютери. Їхня логіка була такою: класичному комп'ютеру важко моделювати квантові системи, але квантовий комп'ютер повинен робити це ефективніше. А якщо квантовий комп'ютер може ефективніше моделювати квантові системи, можливо, є й інші завдання, які він може виконувати ефективніше за класичний комп'ютер.

Логіка була правильною, але деталі ще належало з'ясувати. Це розпочалося в 1985 році, коли Девід Дойч описав перший «універсальний квантовий комп'ютер». У тій самій статті він навів перший приклад задачі, яку квантовий комп'ютер міг розв'язати ефективніше за класичний. Цей перший іграшковий приклад тепер відомий як «алгоритм Дойча». Покращення в алгоритмі Дойча було скромним, але згодом Дойч разом із Річардом Йожою ще більше розширили розрив між класичними та квантовими комп'ютерами.

Ці алгоритми — Дойча та розширення Дойча-Йожи — не є особливо корисними на практиці, але вони залишаються дуже важливими з кількох причин:

1. Історично вони були одними з перших квантових алгоритмів, які продемонстрували перевагу над класичними аналогами. Розуміння їх допомагає зрозуміти, як еволюціонувало мислення спільноти щодо квантових обчислень з часом.
2. Вони допомагають зрозуміти деякі аспекти відповіді на несподівано тонке питання: у чому полягає сила квантових обчислень? Іноді квантові комп'ютери порівнюють із гігантськими, експоненційно масштабованими паралельними процесорами. Але це не зовсім правильно. Хоча частина відповіді на це питання лежить у так званому «квантовому паралелізмі», витягнути максимум інформації за один запуск — справжнє мистецтво. Алгоритми Дойча та Дойча-Йожи показують, як це можна зробити.

У цьому модулі ми вивчимо алгоритм Дойча, алгоритм Дойча-Йожи та те, що вони розповідають нам про силу квантових обчислень.

Квантовий паралелізм та його межі

Частина сили квантових обчислень походить із «квантового паралелізму» — тобто здатності виконувати операції над кількома вхідними даними одночасно, оскільки вхідні стани кубіта можуть перебувати в суперпозиції кількох класично дозволених станів. ОДНАК, хоча квантова схема може одночасно обчислювати функцію на кількох вхідних станах, витягти всю цю інформацію за один раз неможливо.

Щоб краще зрозуміти це, уявімо, що маємо біт $x$ і деяку функцію від цього біту, $f(x)$. Існують чотири можливі бінарні функції, що відображають один біт в інший:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Нам потрібно з'ясувати, яка з цих функцій (1–4) є нашою $f(x)$. Класично нам довелось би запустити функцію двічі — один раз для $x=0$, один раз для $x=1$. Але подивімось, чи зможемо ми зробити краще за допомогою квантової схеми. Ми можемо дізнатися про функцію, використовуючи такий Gate:

Тут Gate $U_f$ обчислює $f(x)$, де $x$ — стан кубіта 0, і застосовує результат до кубіта 1. Тому результуючий стан, $|x\rangle|y\oplus f(x)\rangle$, просто стає $|x\rangle|f(x)\rangle$ при $|y\rangle = |0\rangle$. Він містить усю необхідну інформацію про функцію $f(x)$: кубіт 0 говорить нам, чому дорівнює $x$, а кубіт 1 — чому дорівнює $f(x)$. Отже, якщо ми ініціалізуємо $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, то кінцевий стан обох кубітів буде: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Але як нам отримати цю інформацію?

2.1. Спробуй у Qiskit:

За допомогою Qiskit ми випадково оберемо одну з чотирьох можливих функцій вище та запустимо схему. Твоє завдання — використати результати вимірювань квантової схеми, щоб визначити функцію якомога меншою кількістю запусків.

У цьому першому експерименті та протягом усього модуля ми використовуватимемо підхід до квантових обчислень, відомий як «Qiskit patterns», який розбиває робочі процеси на такі кроки:

• Крок 1: Відображення класичних вхідних даних у квантову задачу
• Крок 2: Оптимізація задачі для квантового виконання
• Крок 3: Виконання за допомогою примітивів Qiskit Runtime
• Крок 4: Постобробка та класичний аналіз

Почнемо з завантаження необхідних пакетів, включно з примітивами Qiskit Runtime. Ми також оберемо найменш завантажений доступний квантовий комп'ютер.

Нижче наведено код для збереження твоїх облікових даних при першому використанні. Обов'язково видали цю інформацію з ноутбука після збереження у своє середовище, щоб твої облікові дані не були випадково розкриті під час обміну ноутбуком. Дивись Налаштування облікового запису IBM Cloud та Ініціалізація сервісу в ненадійному середовищі для отримання додаткових вказівок.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

Клітинка нижче дозволить тобі перемикатися між використанням симулятора або справжнього обладнання протягом усього ноутбука. Рекомендуємо запустити її зараз:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Тепер, коли ми завантажили необхідні пакети, можемо продовжити з робочим процесом Qiskit patterns. На кроці відображення нижче ми спочатку створюємо функцію, яка вибирає одну з чотирьох можливих функцій, що відображають один біт в інший.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

У наведеній вище схемі Gate Адамара «H» переводить кубіт 0, який спочатку перебуває у стані $|0\rangle$, до стану суперпозиції $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Потім $U_f$ обчислює функцію $f(x)$ і застосовує її до кубіта 1.

Далі нам потрібно оптимізувати та транспілювати схему для запуску на квантовому комп'ютері:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

Нарешті, ми виконуємо транспільовану схему на квантовому комп'ютері та візуалізуємо результати:

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

Вище показана гістограма наших результатів. Залежно від кількості пострілів (shots), з якими ти обрав запустити схему на кроці 3 вище, ти можеш побачити один або два стовпці, що представляють виміряні стани двох кубітів у кожному пострілі. Як завжди у Qiskit та в цьому ноутбуці, ми використовуємо позначення «little endian», що означає: стани кубітів від 0 до n записуються у висхідному порядку справа наліво, тому кубіт 0 завжди найправіший.

Отже, оскільки кубіт 0 перебував у стані суперпозиції, схема обчислила функцію одразу для обох $x=0$ та $x=1$ одночасно — щось, чого класичні комп'ютери не можуть зробити! Але підступ з'являється, коли ми хочемо дізнатися про функцію $f(x)$ — коли ми вимірюємо кубіти, ми руйнуємо їхній стан. Якщо ти виберешь «shots = 1», щоб запустити схему лише один раз, ти побачиш лише один стовпець у гістограмі вище, і твоя інформація про функцію буде неповною.

Перевір своє розуміння

Прочитай запитання нижче, подумай над відповіддю, а потім клікни на трикутник, щоб побачити розв'язок.

Скільки разів потрібно запустити наведений вище алгоритм, щоб дізнатися функцію $f(x)$? Чи це краще за класичний випадок? Ти б надав(-ла) перевагу класичному чи квантовому комп'ютеру для розв'язання цієї задачі?

Відповідь:

Оскільки вимірювання руйнує суперпозицію та повертає лише одне значення, нам потрібно запустити схему принаймні двічі, щоб отримати обидва виходи функції $f(0)$ та $f(1)$. У найкращому випадку це працює так само добре, як і класичний варіант, де ми обчислюємо як $f(0)$, так і $f(1)$ за перші два запити. Але є ймовірність, що нам доведеться запускати її більше двох разів, оскільки фінальне вимірювання є імовірнісним і може повертати те саме значення $f(x)$ перші два рази. У цьому випадку я б надав(-ла) перевагу класичному комп'ютеру.

Отже, хоча квантовий паралелізм може бути потужним, якщо його використовувати правильно, неправильно стверджувати, що квантовий комп'ютер працює так само, як масивний класичний паралельний процесор. Акт вимірювання руйнує квантові стани, тому ми можемо отримати лише один вихід обчислення.

Алгоритм Дойча

Хоча квантовий паралелізм сам по собі не дає нам переваги над класичними комп'ютерами, ми можемо поєднати його з іншим квантовим явищем — інтерференцією — щоб досягти прискорення. Алгоритм, відомий сьогодні як «алгоритм Дойча», є першим прикладом алгоритму, який досягає цього.

Задача

Ось у чому полягала задача:

Дано вхідний біт $x = \{0,1\}$ та вхідну функцію $f(x) = \{0,1\}$. Потрібно визначити, чи функція є збалансованою чи константною. Тобто, якщо вона збалансована, то вихід функції дорівнює 0 половину часу та 1 — іншу половину. Якщо вона константна, то вихід функції завжди дорівнює або 0, або 1. Пригадаємо таблицю чотирьох можливих функцій, що відображають один біт в інший:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Перша та остання функції, $f_1(x)$ та $f_4(x)$, є константними, тоді як дві середні функції, $f_2(x)$ та $f_3(x)$, є збалансованими.

Алгоритм

Підхід Дойча до цієї задачі ґрунтувався на «моделі запитів». У моделі запитів вхідна функція ($f_i(x)$ вище) міститься у «чорному ящику» — ми не маємо прямого доступу до її вмісту, але можемо надсилати запити до чорного ящика, і він поверне нам вихід функції. Іноді кажуть, що цю інформацію надає «оракул». Дивись Урок 1: Квантові алгоритми запитів курсу «Основи квантових алгоритмів» для отримання додаткової інформації про модель запитів.

Щоб визначити, чи квантовий алгоритм ефективніший за класичний у моделі запитів, ми можемо просто порівняти кількість запитів до чорного ящика в кожному випадку. У класичному випадку, щоб дізнатися, чи функція в чорному ящику є збалансованою чи константною, нам потрібно зробити два запити, щоб отримати як $f(0)$, так і $f(1)$.

Однак у квантовому алгоритмі Дойча він знайшов спосіб отримати цю інформацію лише одним запитом! Він зробив одну поправку до схеми «квантового паралелізму» вище, підготувавши стан суперпозиції на обох кубітах, а не лише на кубіті 0. Тоді два виходи функції, $f(0)$ та $f(1)$, інтерферували, повертаючи 0, якщо вони були однаковими (функція константна), та 1, якщо вони відрізнялися (функція збалансована). Таким чином Дойч міг відрізнити константну від збалансованої функції за один запит.

Ось діаграма схеми алгоритму Дойча:

Щоб зрозуміти, як працює цей алгоритм, розглянемо квантові стани кубітів у трьох точках, позначених на діаграмі вище. Спробуй самостійно обчислити ці стани, перш ніж клікнути, щоб переглянути відповіді:

Перевір своє розуміння

Прочитай запитання нижче, подумай над відповідями, а потім клікни на трикутники, щоб побачити розв'язки.

Чому дорівнює стан $|\pi_1\rangle$?

Відповідь:

Застосування Gate Адамара переводить стан $|0\rangle$ до $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, а стан $|1\rangle$ — до $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Отже, повний стан стає: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Чому дорівнює стан $|\pi_2\rangle$?

Відповідь:

Перед тим як застосувати $U_f$, пригадаємо, що він робить. Він змінює стан кубіта 1 залежно від стану кубіта 0. Тому має сенс виокремити стан кубіта 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Тоді, якщо $f(0)=f(1)$, обидва доданки перетворяться однаково, і відносний знак між ними залишиться позитивним; але якщо $f(0)\neq f(1)$, то другий доданок отримає знак мінус відносно першого, змінюючи стан кубіта 0 з $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ на $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Отже:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Чому дорівнює стан $|\pi_3\rangle$?

Відповідь:

Тепер стан кубіта 0 є або $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, або $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, залежно від функції. Застосування Gate Адамара дасть або $|0\rangle$, або $|1\rangle$ відповідно.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Переглядаючи свої відповіді на наведені вище запитання, зверни увагу на дещо несподіване. Хоча $U_f$ явно нічого не робить зі станом кубіта 0, оскільки він змінює кубіт 1 залежно від стану кубіта 0, може статися, що це спричиняє фазовий зсув у кубіті 0. Це явище відоме як «фазовий відкат» (phase-kickback) і докладніше обговорюється в Уроці 1: Квантові алгоритми запитів курсу «Основи квантових алгоритмів».

Тепер, коли ми розуміємо, як працює цей алгоритм, реалізуємо його за допомогою Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

Алгоритм Дойча-Йожи

Алгоритм Дойча був важливим першим кроком у демонстрації того, як квантовий комп'ютер може бути ефективнішим за класичний, але це було лише скромне покращення: він вимагав лише одного запиту порівняно з двома у класичному випадку. У 1992 році Дойч та його колега Річард Йожа розширили оригінальний двокубітний алгоритм до більшої кількості кубітів. Задача залишилася тією самою: визначити, чи є функція збалансованою чи константною. Але цього разу функція відображає $n$ бітів в один біт. Або функція повертає 0 та 1 однакову кількість разів (вона збалансована), або функція завжди повертає 1 або завжди 0 (вона константна).

Ось діаграма схеми алгоритму:

Цей алгоритм працює так само, як і алгоритм Дойча: фазовий відкат дозволяє зчитати стан кубіта 0, щоб визначити, чи функція є константною чи збалансованою. Це дещо складніше зрозуміти, ніж для двокубітного випадку алгоритму Дойча, оскільки стани включатимуть суми по $n$ кубітах, тому обчислення цих станів залишено як необов'язкову вправу для тебе наприкінці модуля. Алгоритм поверне рядок з усіх 0, якщо функція константна, і рядок із принаймні одним 1, якщо функція збалансована.

Щоб побачити, як алгоритм працює у Qiskit, спочатку нам потрібно згенерувати наш оракул: випадкову функцію, яка гарантовано є або константною, або збалансованою. Наведений нижче код генеруватиме збалансовану функцію в 50% випадків і константну — в 50% випадків. Не хвилюйся, якщо не зовсім розумієш код — він складний і не є обов'язковим для розуміння квантового алгоритму.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

    for state in on_states:
        # qc_dj.barrier()  # Barriers are added to help visualize how the functions are created. They can safely be removed.
        qc_dj = add_cx(qc_dj, f"{state:0b}")
        qc_dj.mcx(list(range(num_qubits)), num_qubits)
        qc_dj = add_cx(qc_dj, f"{state:0b}")

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

Це оракул-функція, яка є або збалансованою, або константною. Чи можеш ти, дивлячись на неї, визначити, чи залежить вихід останнього кубіта від значень, введених для перших $n$ кубітів? Якщо вихід останнього кубіта залежить від перших $n$ кубітів, чи можеш ти сказати, чи є цей залежний вихід збалансованим?

Ми можемо визначити, чи є функція збалансованою чи константною, дивлячись на наведену вище схему. Але пам'ятай: для цілей цієї задачі ми розглядаємо цю функцію як «чорний ящик». Ми не можемо зазирнути всередину ящика і подивитися на діаграму схеми. Натомість нам потрібно надіслати запит до ящика.

Щоб надіслати запит, ми використовуємо алгоритм Дойча-Йожи і визначаємо, чи є функція константною чи збалансованою:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

Вище перший рядок виводу — це бітовий рядок результатів вимірювання. Другий рядок показує, чи означає цей бітовий рядок, що функція була збалансованою чи константною. Якщо бітовий рядок містить самі нулі — функція константна; якщо ні — збалансована. Отже, лише за один запуск наведеної квантової схеми можна визначити, чи є функція константною або збалансованою!

Перевір своє розуміння

Прочитай запитання нижче, подумай над відповідями, а потім натисни трикутники, щоб побачити рішення.

Скільки запитів знадобиться класичному комп'ютеру, щоб зі 100% впевненістю визначити, чи є функція константною або збалансованою? Пам'ятай: класично один запит дозволяє застосувати функцію лише до одного бітового рядка.

Відповідь:

Є $2^n$ можливих бітових рядків для перевірки, і в найгіршому випадку потрібно перевірити $2^n/2+1$ з них. Наприклад, якщо функція константна і ти весь час отримуєш «1» як результат, ти не можеш бути певен(-на), що вона справді константна, доки не перевіриш більше половини результатів. До цього моменту тобі просто могло не щастити і ти весь час отримував(-ла) «1» на збалансованій функції. Це схоже на підкидання монети знову і знову, і вона весь час падає орлом. Малоймовірно, але не неможливо.

Як зміниться твоя відповідь, якщо треба просто вимірювати до тих пір, поки один результат (збалансована або константна) не стане більш імовірним за інший? Скільки запитів знадобиться в цьому випадку?

Відповідь:

У цьому випадку достатньо двох вимірювань. Якщо два результати різні — функція збалансована. Якщо однакові — функція може бути як збалансованою, так і константною. Імовірність того, що вона збалансована при такому наборі вимірювань, дорівнює: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Це менше 1/2, тому в цьому випадку більш імовірно, що функція константна.

Таким чином, алгоритм Дойча–Йожи продемонстрував експоненційне прискорення порівняно з детерміністичним класичним алгоритмом (тим, що повертає відповідь зі 100% впевненістю), але не суттєве прискорення порівняно з імовірнісним (тим, що повертає результат, який ймовірно є правильним).

Задача Бернштейна–Вазірані

У 1997 році Ітан Бернштейн і Умеш Вазірані скористалися алгоритмом Дойча–Йожи, щоб розв'язати конкретнішу, більш обмежену задачу порівняно з задачею Дойча–Йожи. Замість того щоб просто відрізняти два різних класи функцій, як у випадку Д-Дж, Бернштейн і Вазірані застосували алгоритм Дойча–Йожи, щоб дізнатися рядок, закодований у функції. Ось у чому задача:

Функція $f:\{0,1\}^n \rightarrow \{0,1\}$ як і раніше приймає $n$-бітовий рядок і повертає один біт. Але тепер, замість обіцянки, що функція збалансована або константна, нам обіцяють, що функція є скалярним добутком вхідного рядка $x$ і деякого секретного $n$-бітового рядка $s$ за модулем 2. (Цей скалярний добуток за модулем 2 називається «бінарним скалярним добутком».) Задача полягає в тому, щоб з'ясувати, яким є секретний $n$-бітовий рядок.

Іншими словами, нам дана функція «чорного ящика» $f: {0,1}^n \rightarrow {0,1}$, яка задовольняє $f(x) = s \cdot x$ для деякого рядка $s$, і нам потрібно дізнатися рядок $s$.

Розглянемо, як алгоритм Д-Дж розв'язує цю задачу:

1. Спочатку до $n$ вхідних Qubit застосовується Gate Адамара, а до вихідного Qubit — Gate NOT і Gate Адамара, що переводить стан у:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

Стан Qubit з 1 по $n$ можна записати простіше як суму по всіх $2^n$ базисних станах $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Позначимо множину цих базисних станів як $\Sigma^n$. (Детальніше дивись у курсі Основи квантових алгоритмів.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. Далі до Qubit застосовується Gate $U_f$. Цей Gate приймає перші n Qubit як вхід (які тепер перебувають у рівній суперпозиції всіх можливих n-бітових рядків) і застосовує функцію $f(x)=s \cdot x$ до вихідного Qubit, так що цей Qubit тепер перебуває у стані: $|- \oplus f(x)\rangle$. Завдяки механізму зворотного відбиття фази стан цього Qubit залишається незмінним, але деякі доданки у стані вхідного Qubit отримують знак мінус:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. Тепер до Qubit від 0 до $n-1$ застосовується наступний набір Gate Адамара. Відстежувати знаки мінус у цьому випадку може бути непросто. Корисно знати, що застосування шару Gate Адамара до $n$ Qubit у стандартному базисному стані $|x\rangle$ можна записати як:

$$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}}\sum\limits_{y \in \Sigma^n}{(-1)^{x \cdot y}|y\rangle}$$

Тоді стан набуває вигляду:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. Наступний крок — виміряти перші $n$ бітів. Але що ми виміряємо? Виявляється, наведений вище стан спрощується до: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, хоча це далеко не очевидно. Якщо хочеш розібрати математику докладніше, дивись курс Джона Ватруса Основи квантових алгоритмів. Головне ж полягає в тому, що механізм зворотного відбиття фази призводить до того, що вхідні Qubit опиняються у стані $|s\rangle$. Тому, щоб дізнатися секретний рядок $s$, достатньо просто виміряти Qubit!

Перевір своє розуміння

Прочитай запитання нижче, подумай над відповідями, а потім натисни трикутники, щоб побачити рішення.

Перевір, що стан з кроку 3 вище справді є станом $|s\rangle$ для окремого випадку $n=1$.

Відповідь:

Якщо явно розписати дві суми, отримаємо стан із чотирьох доданків (опустимо вихідний стан $|-\rangle$ тут):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Якщо $s=0$, перші два доданки складаються конструктивно, а два останні скорочуються, залишаючи $|\Psi\rangle = |0\rangle$. Якщо $s=1$, два останні доданки складаються конструктивно, а два перших скорочуються, залишаючи $|\Psi\rangle = |1\rangle$. Отже, в обох випадках $|\Psi\rangle = |s\rangle$. Сподіваємося, цей найпростіший випадок дає тобі відчуття того, як працює загальний випадок із $n$ Qubit: усі доданки, що не є $|s\rangle$, інтерферують і зникають, залишаючи лише стан $|s\rangle$.

Як один і той самий алгоритм розв'язує і задачу Бернштейна–Вазірані, і задачу Дойча–Йожи? Щоб розібратися, подумай про функції Бернштейна–Вазірані вигляду $f(x) = s \cdot x$. Чи є ці функції також функціями Дойча–Йожи? Тобто визнач, чи задовольняють функції такого вигляду обіцянку задачі Дойча–Йожи: бути або константними, або збалансованими. Як це допомагає зрозуміти, чому один алгоритм розв'язує дві різні задачі?

Відповідь:

Кожна функція Бернштейна–Вазірані вигляду $f(x) = s \cdot x$ також задовольняє обіцянку задачі Дойча–Йожи: якщо s=00...00, то функція константна (завжди повертає 0 для будь-якого рядка x). Якщо s — будь-який інший рядок, то функція збалансована. Отже, застосування алгоритму Дойча–Йожи до однієї з таких функцій одночасно розв'язує обидві задачі! Він повертає рядок, і якщо цей рядок 00...00 — ми знаємо, що функція константна; якщо в рядку є хоча б одна «1» — ми знаємо, що вона збалансована.

Ми також можемо перевірити, що цей алгоритм успішно розв'язує задачу Бернштейна–Вазірані, протестувавши його експериментально. Спочатку створимо функцію Б-В, яка живе всередині чорного ящика:

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

Отже, лише за один запит алгоритм Дойча–Йожи поверне рядок $s$, що використовується у функції: $f(x)=x \cdot s$, коли ми застосовуємо його до задачі Бернштейна–Вазірані. Класичному алгоритму для розв'язання тієї самої задачі знадобилося б $n$ запитів.

Висновок

Сподіваємося, що, розглянувши ці прості приклади, ми дали тобі краще відчуття того, як квантові комп'ютери здатні використовувати суперпозицію, заплутаність та інтерференцію для досягнення переваги над класичними комп'ютерами.

Алгоритм Дойча–Йожи має величезне історичне значення, бо він був першим, що продемонстрував будь-яке прискорення порівняно з класичним алгоритмом, хоча це прискорення було лише поліноміальним. Алгоритм Дойча–Йожи — лише початок цієї історії.

Після того як вони використали алгоритм для розв'язання своєї задачі, Бернштейн і Вазірані взяли її за основу для складнішої рекурсивної задачі, яку назвали задачею рекурсивного вибірки Фур'є. Їхнє рішення запропонувало над-поліноміальне прискорення порівняно з класичними алгоритмами. І ще до Бернштейна та Вазірані Пітер Шор вже розробив свій знаменитий алгоритм, який дозволяє квантовим комп'ютерам розкладати великі числа на множники експоненційно швидше, ніж будь-який класичний алгоритм. Ці результати в сукупності показали захопливі перспективи майбутніх квантових комп'ютерів і підштовхнули фізиків та інженерів до втілення цього майбутнього в реальність.

Запитання

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

Ключові поняття

• Алгоритми Дойча та Дойча–Йожи використовують квантовий паралелізм у поєднанні з інтерференцією, щоб знайти відповідь на задачу швидше, ніж класичний комп'ютер.
• Механізм зворотного відбиття фази — це неочікуване квантове явище, яке переносить операції над одним Qubit на фазу іншого. Алгоритми Дойча та Дойча–Йожи використовують цей механізм.
• Алгоритм Дойча–Йожи забезпечує поліноміальне прискорення порівняно з будь-яким детерміністичним класичним алгоритмом.
• Алгоритм Дойча–Йожи можна застосувати до іншої задачі — задачі Бернштейна–Вазірані — щоб знайти прихований рядок, закодований у функції.

Правда/хибність

1. П/Х Алгоритм Дойча є окремим випадком алгоритму Дойча–Йожи, де вхід складається з одного Qubit.
2. П/Х Алгоритми Дойча та Дойча–Йожи використовують квантову суперпозицію та інтерференцію для досягнення своєї ефективності.
3. П/Х Алгоритм Дойча–Йожи вимагає кількох обчислень функції, щоб визначити, чи є вона константною або збалансованою.
4. П/Х «Алгоритм Бернштейна–Вазірані» насправді є тим самим алгоритмом Дойча–Йожи, застосованим до іншої задачі.
5. П/Х Алгоритм Бернштейна–Вазірані може одночасно знаходити кілька секретних рядків.

Короткі відповіді

1. Скільки часу знадобиться класичному алгоритму для розв'язання задачі Дойча–Йожи в найгіршому випадку?

2. Скільки часу знадобиться класичному алгоритму для розв'язання задачі Бернштейна–Вазірані? Яке прискорення пропонує алгоритм Д-Дж у цьому випадку?

3. Опиши механізм зворотного відбиття фази і те, як він працює при розв'язанні задач Дойча–Йожи та Бернштейна–Вазірані.

Задача підвищеної складності

1. Алгоритм Дойча–Йожи: Пригадай, що вище було запитання, де тебе просили обчислити проміжні стани кубітів $\pi_1$ та $\pi_2$ алгоритму Дойча. Зроби те саме для проміжних $(n+1)$-кубітних станів $\pi_1$ та $\pi_2$ алгоритму Дойча–Йожи для конкретного випадку $n=2$. Потім перевір, що $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, знову ж таки для конкретного випадку $n=2$.