Квантові алгоритми: Оцінка фази

примітка

Kento Ueda (15 травня 2024)

Цей ноутбук містить основні концепції та реалізацію Квантового перетворення Фур'є (QFT) і Квантової оцінки фази (QPE).

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

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

1. Вступ

Квантове перетворення Фур'є (QFT)

Квантове перетворення Фур'є є квантовим аналогом класичного дискретного перетворення Фур'є. Це лінійне перетворення, застосоване до квантових станів, яке відображає обчислювальні базиси в їхні представлення у базисі Фур'є. QFT відіграє ключову роль у багатьох квантових алгоритмах, пропонуючи ефективний метод отримання інформації про періодичність із квантових станів. QFT можна реалізувати за допомогою $O(N^2)$ операцій з квантовими вентилями, такими як вентилі Адамара та вентиль керованої фази для $N$ кубітів, що забезпечує експоненційне прискорення порівняно з класичним перетворенням Фур'є.

• Застосування: Він є фундаментальною складовою квантових алгоритмів, таких як алгоритм Шора для факторизації великих цілих чисел і дискретного логарифму.

Квантова оцінка фази (QPE)

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

• Застосування: Вона дає змогу розв'язувати задачі на кшталт пошуку власних значень унітарних матриць та симуляції квантових систем.

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

2. Основи Квантового перетворення Фур'є (QFT)

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"numpy": "numpy", "qiskit": "qiskit", "qiskit_aer": "qiskit-aer", "qiskit_ibm_runtime": "qiskit-ibm-runtime"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

За аналогією з дискретним перетворенням Фур'є, QFT діє на квантовий стан $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ для $N$ кубітів і відображає його в квантовий стан $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

де $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

Або у вигляді унітарної матриці:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. Інтуїція

Квантове перетворення Фур'є (QFT) здійснює перехід між двома базисами: обчислювальним (Z) базисом і базисом Фур'є. Але що означає базис Фур'є в цьому контексті? Ти, мабуть, пам'ятаєш, що перетворення Фур'є $F(\omega)$ функції $f(x)$ описує згортку $f(x)$ із синусоїдальною функцією частоти $\omega$. Простіше кажучи: перетворення Фур'є — це функція, яка описує, скільки кожної частоти $\omega$ потрібно, щоб побудувати функцію $f(x)$ із синусоїд (або косинусоїд). Щоб краще зрозуміти, що означає QFT у цьому контексті, розглянь покрокові зображення нижче, які показують число, закодоване у двійковому вигляді з використанням чотирьох кубітів:

В обчислювальному базисі ми зберігаємо числа у двійковому вигляді, використовуючи стани $|0\rangle$ та $|1\rangle$.

Зверни увагу на частоту, з якою змінюються різні кубіти: крайній лівий кубіт перевертається при кожному збільшенні числа, наступний — кожні 2 кроки, третій — кожні 4 кроки, і так далі.

Якщо застосувати квантове перетворення Фур'є до цих станів, ми отримуємо відображення:

$$|\text{Стан в обчислювальному базисі}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{Стан у базисі Фур'є}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Стани у базисі Фур'є ми часто позначаємо тильдою (~)).

У базисі Фур'є ми зберігаємо числа за допомогою різних обертань навколо осі Z:

IFRAME

Число, яке ми хочемо зберегти, визначає кут повороту кожного кубіта навколо осі Z. У стані $|\widetilde{0}\rangle$ всі кубіти перебувають у стані $|{+}\rangle$. Як видно з прикладу вище, щоб закодувати стан $|\widetilde{5}\rangle$ на 4 кубітах, ми повернули крайній лівий кубіт на $\tfrac{5}{2^n} = \tfrac{5}{16}$ повних оборотів ($\tfrac{5}{16}\times 2\pi$ радіан). Наступний кубіт повертається вдвічі більше ($\tfrac{10}{16}\times 2\pi$ радіан, або $10/16$ повних оборотів), цей кут подвоюється для наступного кубіта, і так далі.

Знову зверни увагу на частоту зміни кожного кубіта. Крайній лівий кубіт (qubit 0) у цьому випадку має найнижчу частоту, а крайній правий — найвищу.

2.2. Приклад: QFT для 1 кубіта

Розглянемо випадок $N = 2^1 = 2$.

Унітарну матрицю можна записати:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

Ця операція є результатом застосування Gate Адамара ($H$).

2.3. Добутне представлення QFT

Узагальнимо перетворення для $N = 2^n$, $QFT_{N}$, що діє на стан $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{since}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{and}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{rewriting in fractional binary notation}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{after expanding the exponential of a sum to a product of exponentials,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{after rearranging the sum and products, and expanding} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4. Приклад: Побудова Circuit для QFT з 3 кубітів

З наведеного вище опису може бути незрозуміло, як побудувати Circuit для QFT. Поки що просто зверни увагу на те, що ми очікуємо, що три кубіти матимуть фази, які еволюціонують із різною «швидкістю». Розуміння того, як саме це перетворюється на Circuit, залишається вправою для читача. У PDF лекції є кілька діаграм і прикладів. Додаткові ресурси включають цей урок із курсу «Основи квантових алгоритмів».

Ми продемонструємо QFT лише з використанням симуляторів, тому не будемо використовувати фреймворк шаблонів Qiskit, поки не перейдемо до квантової оцінки фази.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

Спробуємо застосувати QFT до $|5\rangle$ як приклад.

Спочатку підтвердимо двійковий запис числа 5 і створимо Circuit, що кодує стан 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Перевіримо квантові стани за допомогою симулятора Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Нарешті, додамо QFT і подивимося на кінцевий стан наших кубітів:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Ми бачимо, що функція QFT спрацювала правильно. Qubit 0 повернувся на $\tfrac{5}{8}$ повного оберту, qubit 1 — на $\tfrac{10}{8}$ повних оберту (що еквівалентно $\tfrac{1}{4}$ повного оберту), а qubit 2 — на $\tfrac{20}{8}$ повних оберту (що еквівалентно $\tfrac{1}{2}$ повного оберту).

2.5. Вправа: QFT

(1) Реалізуй QFT для 4 кубітів.

##your code goes here##

(2) Застосуй QFT до $|14\rangle$, виконай симуляцію та побудуй вектор стану на сфері Блоха.

##your code goes here##

Розв'язок вправи: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. Основи Квантової оцінки фази (QPE)

За наявності унітарної операції $U$, QPE оцінює $\theta$ у рівнянні $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$. Оскільки $U$ є унітарним, усі його власні значення мають норму 1.

3.1. Процедура

1. Налаштування

$\vert\psi\rangle$ знаходиться в одному наборі реєстрів кубітів. Додатковий набір із $n$ кубітів утворює лічильний регістр, у якому ми зберігатимемо значення $2^n\theta$:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. Суперпозиція

Застосуй $n$-бітну операцію Gate Адамара $H^{\otimes n}$ до лічильного регістру:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. Операції керованого унітарного оператора

Нам потрібно ввести керований унітарний оператор $CU$, який застосовує унітарний оператор $U$ до цільового регістру лише тоді, коли відповідний керуючий біт дорівнює $|1\rangle$. Оскільки $U$ є унітарним оператором із власним вектором $|\psi\rangle$ таким, що $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, це означає:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2. Приклад: QPE для T-gate

Використаємо Gate $T$ як приклад QPE та оцінимо її фазу $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

Очікуємо отримати:

$$\theta = \frac{1}{8}$$

де

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

Ми ініціалізуємо $\vert\psi\rangle = \vert1\rangle$ власного вектора гейта $T$, застосовуючи гейт $X$:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

Далі ми застосовуємо гейти Адамара до лічильних кубітів:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

Виконуємо керовані унітарні операції:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

Ми застосовуємо обернене квантове перетворення Фур'є, щоб перетворити стан лічильного регістру, а потім вимірюємо лічильний регістр:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Ми можемо провести симуляцію за допомогою симулятора Aer:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

Бачимо, що з імовірністю 1 отримуємо єдиний результат (001), тобто 1 у десятковому записі. Тепер нам потрібно поділити наш результат (1) на $2^n$, щоб отримати $\theta$:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

Алгоритм Шора дозволяє нам факторизувати число, побудувавши схему з невідомим $\theta$ та отримавши $\theta$.

3.3 Вправа

Оціни $\theta = 1/3$, використовуючи 3 кубіти для лічильного регістру і один кубіт для власного вектора.

$P|1\rangle = e^{i\lambda}|1\rangle$. Оскільки ми хочемо реалізувати $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, потрібно встановити $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Розв'язання вправи: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Виконання за допомогою примітиву Sampler з IBM Quantum

Ми виконаємо QPE на реальному квантовому пристрої та дотримаємось 4 кроків шаблонів Qiskit.

1. Відобразити задачу у квантово-нативний формат

2. Оптимізувати схеми

3. Виконати цільову схему

4. Постобробити результати

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

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

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

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

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 Крок 3: Виконання на цільовому обладнанні

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

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

from qiskit.visualization import plot_histogram

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

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'