Квантові алгоритми: пошук Гровера та застосування

примітка

Atsushi Matsuo (10 травня 2024)

Завантажити PDF оригінальної лекції. Зверни увагу: деякі фрагменти коду можуть бути застарілими, оскільки це статичні зображення.

Приблизний час QPU для цього експерименту — 2 секунди.

1. Вступ до алгоритму Гровера

Цей ноутбук є четвертим у серії лекцій «Шлях до практичної квантової обчислювальності». У ньому ми вивчимо алгоритм Гровера.

Алгоритм Гровера — один із найвідоміших квантових алгоритмів завдяки квадратичному прискоренню порівняно з класичними методами пошуку. У класичних обчисленнях пошук у невпорядкованій базі даних з $N$ елементів потребує часової складності $O(N)$: у найгіршому випадку доводиться перебирати кожен елемент окремо. Натомість алгоритм Гровера дозволяє виконати той самий пошук за час $O(\sqrt{N})$, використовуючи принципи квантової механіки для ефективнішого знаходження цільового елемента.

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

Базова структура алгоритму Гровера

Алгоритм Гровера складається з чотирьох основних компонентів:

1. Ініціалізація: створення суперпозиції всіх можливих станів.
2. Оракул: застосування функції-оракула, яка позначає цільовий стан шляхом інвертування його фази.
3. Оператор дифузії: застосування серії операцій для підсилення імовірності позначеного стану.

Кожен із цих кроків відіграє ключову роль у забезпеченні ефективної роботи алгоритму. Детальні пояснення кожного кроку наведено далі.

2. Реалізація алгоритму Гровера

2.1 Підготовка

Імпортуй необхідні бібліотеки та налаштуй середовище для запуску квантової схеми.

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

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

Крок 1: відображення задачі на квантові схеми та оператори

Розглянемо список із 4 елементів, де наша мета — знайти індекс елемента, що задовольняє певну умову. Наприклад, ми хочемо знайти індекс елемента, рівного 2. У цьому прикладі квантовий стан $|01\rangle$ представляє індекс елемента, що задовольняє умову, оскільки вказує на позицію, де знаходиться значення 2.

Крок 2: оптимізація для цільового апаратного забезпечення

1: Ініціалізація

На кроці ініціалізації ми створюємо суперпозицію всіх можливих станів. Це досягається застосуванням вентиля Адамара до кожного кубіта в n-кубітному регістрі, що дає рівну суперпозицію $2^n$ станів. Математично це можна записати як:

$$\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$

де $N = 2^n$ — загальна кількість можливих станів. Ми також переводимо стан допоміжного біта в $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2: Оракул

Оракул — ключова частина алгоритму Гровера. Він позначає цільовий стан, застосовуючи фазовий зсув — зазвичай інвертуючи знак амплітуди, пов'язаної з цим станом. Оракул, як правило, специфічний для задачі й будується на основі критеріїв визначення цільового стану. У математичних термінах оракул застосовує таке перетворення:

f(x) = \begin\{cases\} 1, & \text\{if \} x = x_\{\text\{target}\} \\ 0, & \text\{otherwise\} \end\{cases\}

Цей фазовий переворот досягається шляхом застосування від'ємного знаку до амплітуди цільового стану через фазовий відкат.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3: Оператор дифузії

Підсилення амплітуди — це те, що відрізняє алгоритм Гровера від класичного пошуку. Після того як оракул позначив цільовий стан, ми застосовуємо серію операцій, що збільшують амплітуду цього позначеного стану, роблячи його більш імовірним для спостереження при вимірюванні. Цей процес реалізується через оператор дифузії, який фактично виконує інверсію відносно середньої амплітуди. Математична операція виглядає так:

$D = 2|\psi\rangle\langle\psi| - I$

де $D$ — оператор дифузії, $I$ — одинична матриця, а $|\psi\rangle$ — стан рівної суперпозиції. Комбінація оракула та оператора дифузії застосовується приблизно $\sqrt{N}$ разів для досягнення максимальної імовірності вимірювання позначеного стану.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 Приклад пошуку Гровера на 2 кубітах

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 Експеримент із симуляторами

Крок 3: виконання схеми

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

Крок 4: постобробка результатів

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Ми отримали правильну відповідь $|01\rangle$. Зверни увагу на порядок кубітів.

3. Експеримент на реальних пристроях

Крок 2: оптимізація для цільового апаратного забезпечення

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

Після транспіляції схема була перетворена на схему, що використовує нативні базисні вентилі пристрою.

Крок 3: виконання схеми

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

Крок 4: постобробка результатів

plot_histogram(result_real[0].data.meas.get_counts())

4. Пошук Гровера на 3 кубітах

Тепер спробуймо приклад пошуку Гровера на 3 кубітах.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

Цього разу $|111\rangle$ є «хорошим» станом.

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

$|0111\rangle$ спостерігається з найвищою імовірністю, як і очікувалося. Зверни увагу, що дві ітерації є оптимальними в цьому випадку. Проте імовірність отримання правильної відповіді не становить 100%, що є типовим для пошуку Гровера.

Що відбувається при 3 ітераціях?

Тепер спробуємо виконати 3 ітерації.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

$|0111\rangle$ все ще спостерігається з найвищою ймовірністю, однак ймовірність отримання правильної відповіді дещо зменшилась.

А що, якщо ітерувати 4 рази?

Тепер спробуємо виконати 4 ітерації.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

$|0111\rangle$ спостерігається з найнижчою ймовірністю, і ймовірність отримання правильної відповіді зменшилась ще більше. Це демонструє важливість вибору оптимальної кількості ітерацій в алгоритмі Гровера для досягнення найкращих результатів.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'