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

Для цього модуля Qiskit in Classrooms студенти повинні мати працюче середовище 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.

Цей модуль було протестовано і він використав 13 секунд часу 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'

Вступ

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

Сьогодні, після нагадування про класичне перетворення Фур'є, поговоримо про те, як ми реалізуємо квантове перетворення Фур'є на квантовому комп'ютері. Потім розглянемо одне із застосувань квантового перетворення Фур'є в алгоритмі, відомому як алгоритм оцінки фази. Квантова оцінка фази є підпрограмою у відомому алгоритмі факторизації Шора, який іноді називають «коронним коштовним каменем» квантових обчислень. Цей модуль є кроком до іншого модуля цілком про алгоритм Шора, але водночас він задуманий як самостійний. Квантове перетворення Фур'є — це чудовий і корисний алгоритм сам по собі!

Класичне перетворення Фур'є

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

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

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

У частотному базисі ми легко бачимо чіткий пік приблизно на 260 Гц. Це середнє до!

Можливо, ти й сам міг би визначити, що грає середнє до, без використання перетворення Фур'є, але що, якщо одночасно грають кілька нот? Тоді хвильова форма стає складнішою, якщо ми будуємо її у часовому базисі:

Але частотний спектр чітко виявляє три піки:

Це був акорд до мажор — ноти до, мі та соль.

Такий вид аналізу Фур'є допомагає нам виокремити частотні складові будь-якого складного сигналу.

Дискретне перетворення Фур'є

Перетворення Фур'є корисне для різноманітних задач обробки сигналів. Але в більшості цих реальних застосувань (включно з наведеним прикладом з музикою) ми хочемо перетворити дискретний набір із $N$ точок даних, а не неперервну функцію. У цьому випадку ми використовуємо дискретне перетворення Фур'є. Дискретне перетворення Фур'є (ДПФ) діє на вектор $(x_0, ..., x_{N-1})$ і відображає його у вектор $(y_0, ..., y_{N-1})$ відповідно до формули:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

де беремо $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Зауваж, що існують інші угоди зі знаком мінус у показнику степеня, тому будь уважний, коли стикаєшся з ДПФ на практиці.) Нагадаємо, що $e^{2\pi i \frac{jk}{N}}$ — це periodична функція з періодом $\frac{N}{k}$. Отже, множачи на цю функцію, перетворення Фур'є по суті є способом розкласти (дискретну) функцію $\{x_{j}\}$ у лінійну комбінацію її складових periodичних функцій, кожна з яких має період $\frac{N}{k}$.

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

Отже, ми щойно побачили, як перетворення Фур'є використовується для представлення функції у вигляді лінійної комбінації нового набору так званих «базисних функцій». Перетворення базисів регулярно виконуються і для станів кубітів. Наприклад, стан одиночного кубіта $|\psi\rangle$ можна виразити у обчислювальному базисі $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$ з базисними станами $|0\rangle$ і $|1\rangle$, або у $X$-базисі $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ з базисними станами $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ і $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Обидва рівноправні, але один може бути природнішим за інший, залежно від типу задачі, яку ти намагаєшся розв'язати.

Стани кубітів можна також виразити у базисі Фур'є, де стан записується у вигляді лінійної комбінації базисних станів Фур'є $|\phi_y\rangle$, а не звичайних обчислювальних базисних станів $|x\rangle$. Для цього потрібно застосувати квантове перетворення Фур'є (КПФ):

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

де $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$, як і раніше, а $N$ — кількість базисних станів у твоїй квантовій системі. Зверни увагу, що оскільки ми тепер працюємо з кубітами, $m$ кубітів дають тобі $2^m$ базисних станів, тобто $N=2^m$. Тут базисні стани записані у вигляді одного числа $|x\rangle$, де $x$ змінюється від $0$ до $N-1$, але зазвичай базисні стани записують як $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, де кожна двійкова цифра представляє стан кубіта від 0 до $m-1$, справа наліво. Є простий спосіб перетворити ці двійкові стани на одне число: просто розглядай їх як двійкові числа! Отже, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, і так далі — аж до $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Будуємо інтуїцію для базисних станів Фур'є

Отже, ми щойно розглянули, що таке обчислювальні базисні стани і як вони впорядковані: це набір станів, де кожен кубіт знаходиться або в $0$, або в $1$, і ми впорядковуємо їх від стану, де всі кубіти дорівнюють $0$, $|00...00\rangle$, до стану, де всі вони дорівнюють $1$, $|11...11\rangle$.

Але як розібратися з фур'євими базисними станами? Усі базисні стани Фур'є є рівноважними суперпозиціями всіх обчислювальних базисних станів, однак кожен стан відрізняється від інших periodичністю фази компонент. Щоб зрозуміти це конкретніше, давай поглянемо на чотири базисні стани Фур'є для системи з двома кубітами. Найнижчий стан Фур'є — це той, чия фаза взагалі не змінюється:

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Ми можемо візуалізувати цей стан, побудувавши комплексну амплітуду кожного члена. Червона лінія слугує орієнтиром, показуючи, як фаза цієї амплітуди обертається у комплексній площині як функція обчислювального базисного стану. Для $|\phi_0\rangle$ фаза залишається постійною:

Наступний базисний стан Фур'є — це той, чиї компоненти обертаються від $0$ до $2\pi$ рівно один раз:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

І ми можемо бачити це обертання на графіку комплексної амплітуди залежно від обчислювального базисного стану:

Отже, кожен стан має фазу, що є на $2\pi/4$ радіан більшою, ніж у попереднього стану при стандартному впорядкуванні, оскільки в цьому прикладі маємо чотири базисні стани ($N=4$). Наступний базисний стан обертається від 0 до $2\pi$ двічі:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

Нарешті, найвища компонента Фур'є — це та, що має найшвидше змінювану фазу. У нашому прикладі з двома кубітами це та, чиї фази обертаються від 0 до $2\pi$ три рази:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

Загалом, для $m$-кубітного стану буде $2^m$ базисних станів Фур'є, чия частота зміни фази варіюється від постійної — для $|\phi_0\rangle$ — до швидко мінливої — для $|\phi_{2^m-1}\rangle$, що здійснює $2^m-1$ обертів навколо $2\pi$ через суперпозицію станів. Отже, коли ми виконуємо КПФ квантового стану, ми по суті проводимо той самий базовий аналіз, що й для музичної хвильової форми у вступі. Ми визначаємо частотні компоненти Фур'є, що беруть участь у формуванні квантового стану, який нас цікавить.

Спробуй кілька прикладів КПФ

Спробуймо продовжити будувати інтуїцію для квантового перетворення Фур'є: створимо стан у обчислювальному базисі, а потім подивимося, що відбудеться, коли ми застосуємо КПФ до нього. Поки що будемо розглядати КПФ як чорну скриньку, яку застосовуємо за допомогою QFTGate з бібліотеки Circuit Qiskit. Пізніше ми заглянемо під капот, щоб побачити, як це реалізовано.

Почнемо із завантаження необхідних пакетів та вибору пристрою для запуску нашого Circuit:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# 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

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

Якщо у тебе немає доступного часу на обліковому записі або ти з будь-якої причини хочеш використовувати симулятор, ти можеш запустити наведену нижче комірку, щоб налаштувати симулятор, який імітуватиме вибраний нами квантовий пристрій:

# 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

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)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

Одиночний обчислювальний базисний стан

Спочатку спробуймо перетворити одиночний обчислювальний базисний стан. Почнемо зі створення випадкового обчислювального стану:

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
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 OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Тепер застосуймо перетворення Фур'є до цього стану за допомогою QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.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_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

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

Цей факт насправді пов'язаний із квантовою невизначеністю! Принцип невизначеності Гейзенберга зазвичай формулюється як $\Delta x \Delta p \ge \hbar / 2$. Отже, якщо невизначеність у $x$ ($\Delta x$) мала, невизначеність імпульсу ($\Delta p$) має бути великою, і навпаки. Виявляється, перехід від позиційного базису $x$ до імпульсного базису $p$ здійснюється через перетворення Фур'є.

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

Два обчислювальні базисні стани

Тепер подивимося, що відбудеться, коли ми підготуємо суперпозицію обчислювальних базисних станів. Як, на твою думку, виглядатиме перетворення Фур'є в цьому випадку?

Оберемо суперпозицію:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# 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 - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Тепер застосуймо перетворення Фур'є до цього стану за допомогою QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.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_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Цей результат може виявитися трохи несподіваним. Схоже, що КПФ стану $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ — це суперпозиція всіх парних базисних станів. Але якщо ми повернемося до нашої візуалізації кожного базисного стану $|\phi_y\rangle$ і того, як фаза кожної компоненти обертається $y$ разів навколо $2\pi$, причина такого результату може стати зрозумілою.

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

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

Використовуючи підказку вище, поясни, чому отриманий нами результат КПФ для $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ є очікуваним.

Відповідь:

Вихідний стан має відносну фазу 0 (або ціле кратне $2\pi$) між двома частинами суперпозиції. Тому ми знаємо, що цей стан має компоненти Фур'є, чиї фази також узгоджуються таким чином: ті, що мають нульовий зсув фази між членом |0000> і членом |1000>. Кожен базисний стан Фур'є $|\phi_y\rangle$ складається з членів, чия фаза накопичується зі швидкістю $2\pi y/N$, тобто при стандартному впорядкуванні кожен член суперпозиції має фазу на $2\pi y/N$ більшу, ніж попередній. Отже, у середній точці $N/2$ ми хочемо, щоб фаза $2\pi y/N \cdot N/2$ була цілим кратним $2\pi$. Це відбувається, коли $y$ парне.

Яка суперпозиція обчислювальних станів відповідала б КПФ з піками на кожному непарному двійковому числі?

Відповідь:

Якщо взяти КПФ стану $\psi = |0\rangle - |N/2\rangle$, то піки будуть на кожному непарному двійковому числі.

Розбираємо алгоритм КПФ

Тепер, коли ми краще розуміємо зв'язок між станами кубітів у обчислювальному базисі та базисі Фур'є, давай заглибимося безпосередньо в алгоритм КПФ. Інакше кажучи — які ж гейти ми насправді застосовуємо на квантовому комп'ютері, щоб здійснити це перетворення?

Почнімо з малого — з одного кубіта. Отже, у нас буде два базисних стани. КПФ$_2$ перетворює обчислювальні базисні стани $|0\rangle$ і $|1\rangle$ на стани базису Фур'є $\phi_0$ і $\phi_1$:

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

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

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

Використай рівняння для КПФ з попереднього розділу, щоб перевірити ці два стани базису Фур'є.

Відповідь:

Загальна формула КПФ:

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

Для одного кубіта ($n=1$), $N=2^n=2$, і $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Тоді маємо:

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Поглянь на ці два рівняння. Ти, можливо, вже знаєш квантовий гейт, який можна використати для реалізації цього перетворення. Тобто існує гейт, який переводить обчислювальні базисні стани $|0\rangle$ і $|1\rangle$ у відповідні стани базису Фур'є $|\phi_0\rangle$ і $|\phi_1\rangle$. Це гейт Адамара! Це стає ще очевиднішим, якщо ввести матричне представлення операції КПФ$_N$:

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

Якщо ти не знайомий з таким записом квантового оператора — нічого страшного! Це спосіб представити матрицю $N \times N$, де $x$ і $y$ нумерують стовпці та рядки матриці від $0$ до $N-1$, а $\omega_N^{xy}$ — значення конкретного елемента. Наприклад, елемент у 0-му стовпці та 2-му рядку дорівнює $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

У цьому представленні кожен обчислювальний базисний стан асоціюється з одним із базисних векторів:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

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

Спробуємо побудувати матрицю для КПФ$_4$. Скориставшись наведеною вище формулою, знаходимо:

\text\{QFT\}_4 = \frac\{1\}\{2\} \begin\{pmatrix\} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end\{pmatrix\}

Щоб реалізувати цю матрицю на квантовому комп'ютері, потрібно з'ясувати, яка комбінація гейтів, застосованих до яких кубітів, дасть унітарне перетворення, що відповідає матриці вище. Один із потрібних гейтів нам уже відомий — Адамар. Ще один — гейт контрольованої фази, який застосовує відносну фазу $\alpha$ до стану цільового кубіта за умови, що керуючий кубіт перебуває у стані $|1\rangle$. У матричній формі це виглядає так:

\text\{CP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^\{i\alpha\} \\ \end\{pmatrix\}

Оскільки змінюється лише стан $|11\rangle$, насправді не важливо, який кубіт вважати «керуючим», а який — «цільовим». Результат буде однаковим в обох випадках.

Нарешті, знадобляться ще й гейти SWAP. Гейт SWAP міняє стани двох кубітів місцями. Виглядає він так:

\text\{SWAP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end\{pmatrix\}

Процедура побудови Circuit КПФ$_{2^m}$ на $m$ кубітах є ітеративною: спочатку застосовуємо КПФ$_{2^{m-1}}$ до кубітів від $1$ до $m-1$, потім додаємо кілька гейтів між кубітом $0$ і рештою $m-1$ кубітів. Але щоб застосувати КПФ$_{2^{m-1}}$, треба спочатку застосувати КПФ$_{2^{m-2}}$ до кубітів від $2$ до $m-1$, потім додати гейти між кубітом $1$ і кубітами від $2$ до $m-1$. Це нагадує російські матрьошки: кожна лялька збільшує розмірність Circuit КПФ у два рази, а найменша лялька в самому центрі — це КПФ$_2$, тобто гейт Адамара.

Щоб вставити ляльку всередину наступної за розміром, і тим самим збільшити розмірність КПФ удвічі, завжди виконуй одну і ту ж процедуру:

1. Спочатку застосуй КПФ$_{2^{m-1}}$ до $m-1$ нижніх кубітів. Це твоя «менша лялька» з набору матрьошок, яку ти незабаром вставиш у наступну за розміром.
2. Використай наступний кубіт вище як керуючий і застосуй гейти контрольованої фази до кожного з нижніх $m-1$ кубітів з фазами, що відповідають стандартним базисним станам кожного з $m-1$ кубітів, що залишилися.
3. Виконай Адамар на тому самому верхньому кубіті, який використовувався як керуючий у фазових гейтах.
4. Використай гейти SWAP, щоб переставити кубіти так, щоб найменш значущий (верхній) біт став найбільш значущим (нижнім), а всі інші зсунулися на одну позицію вгору.

Ми вже використовували функцію QFTGate з бібліотеки Qiskit circuit library, але тепер давай заглянемо всередину деяких із цих гейтів КПФ, щоб перевірити описану вище процедуру. Зробити це можна за допомогою decompose().

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

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

Застосовуємо КПФ: оцінка фази

Подивімося, як КПФ можна використати для розв'язання корисної задачі у квантових обчисленнях. Обчислення оберненого квантового перетворення Фур'є є необхідним кроком в алгоритмі, відомому як квантова оцінка фази (КОФ), яка, своєю чергою, є підпрограмою багатьох інших алгоритмів, зокрема «перлини серед квантових алгоритмів» — алгоритму факторизації Шора.

Мета КОФ — оцінити власні значення унітарного оператора. Унітарні оператори повсюдно зустрічаються у квантових обчисленнях, і часто знаходження власних значень відповідних власних векторів є необхідним кроком у більшому алгоритмі. Залежно від задачі власне значення може представляти енергію гамільтоніана у задачі симуляції, допомагати знаходити прості множники числа в алгоритмі Шора або містити іншу важливу інформацію. КОФ — одна з найважливіших і найбільш використовуваних підпрограм у квантових обчисленнях.

То ж яке відношення все це має до квантового перетворення Фур'є? Ну, як ти, можливо, пам'ятаєш, будь-яке власне значення $\lambda$ унітарного оператора має модуль $|\lambda| = 1$. Тому кожне власне значення можна записати як комплексне число з одиничним модулем:

$\lambda = e^{2\pi i \theta}$

де $\theta$ — дійсне число від 0 до 1. Якщо хочеш дізнатися більше про унітарні матриці, перегляньте урок Джона Ватруса на цю тему у курсі «Основи квантової інформації».

Зауваж, що $\lambda$ є періодичним за $\theta$. Вже це може наводити на думку про КПФ, адже ми бачили, наскільки корисним він є для аналізу періодичних функцій. Нижче ми розберемо алгоритм і побачимо, яку саме роль відіграє КПФ.

Як працює КОФ

Спочатку розглянемо найпростіший алгоритм КОФ, який приблизно оцінює фазу з точністю до одного двійкового розряду. Іншими словами, цей алгоритм може розрізнити $\theta = 0$ і $\theta = 1/2$, але не більше. Ось схема Circuit:

Кубіти підготовлені у стані $|\pi_0\rangle = |\psi\rangle|0\rangle$, де кубіт $0$ перебуває у стані $|0\rangle$, а решта кубітів — у стані $|\psi\rangle$, який є власним вектором $U$. Після першого Адамара стан кубітів набуває вигляду:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

Наступний гейт — «controlled-$U$». Він застосовує унітарну операцію $U$ до нижніх кубітів у стані $|\psi\rangle$, якщо кубіт 0 перебуває у стані $|1\rangle$, і нічого не робить з $|\psi\rangle$, якщо кубіт 0 у стані $|0\rangle$. Це перетворює кубіти в стан:

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

Щось дивне тут сталося: гейт controlled-$U$ використовує кубіт $0$ лише як керуючий, тому можна було б подумати, що цей гейт взагалі не змінить стан кубіта 0. Але він таки змінюється! Хоча операція застосовувалась до нижніх кубітів, загальний ефект гейта — зміна фази кубіта $0$. Це явище відоме як «механізм зворотного відкидання фази» (phase kickback), і воно використовується у багатьох квантових алгоритмах, зокрема в алгоритмах Дойча–Йожи та Гровера. Якщо хочеш дізнатися більше про механізм зворотного відкидання фази, перегляньте урок Джона Ватруса про квантові алгоритми на запитах у курсі «Основи квантових алгоритмів».

Після зворотного відкидання фази застосовуємо ще один Адамар до кубіта $0$, що дає стан:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

Отже, коли ми вимірюємо кубіт $0$ наприкінці, ми отримаємо $|0\rangle$ зі стовідсотковою впевненістю, якщо $\theta = 0$, і $|1\rangle$ зі стовідсотковою впевненістю, якщо $\theta = \frac{1}{2}$ (за умови ідеального квантового комп'ютера без шуму). Якщо $\theta$ відрізняється від цих значень, фінальне вимірювання є лише імовірнісним і дає обмежену інформацію.

КОФ з більшою точністю: більше кубітів

Ми можемо розширити цю просту ідею до більш складного алгоритму з довільною точністю. Якщо замість одного кубіта $0$ для вимірювання фази використовувати $m$ кубітів від $0$ до $m-1$, то можна оцінити фазу з точністю $m$ бітів. Подивімося, як це працює:

Цей більш точний Circuit КОФ починається так само, як одноразрядна версія: Адамари застосовуються до перших $m$ кубітів, а решта кубітів підготовлені у стані $|\psi\rangle$, що дає стан:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

Тепер застосовуються контрольовані унітарні оператори. Кубіт $0$ є керуючим для того самого унітарного $U$, що й раніше. Але тепер кубіт $1$ є керуючим для унітарного $U^2$, тобто $U$, застосованого двічі. Тоді власне значення $U^2$ дорівнює $e^{2*2\pi i \theta}$. Загалом, кожен кубіт $k$ від 0 до $m-1$ є керуючим для унітарного $U^{2^k}$. Це означає, що кожен із цих кубітів зазнає зворотного відкидання фази $e^{2^k*2\pi i \theta}$. Це дає стан:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

Це можна переписати як суму за обчислювальними базисними станами:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

Ця сума тобі нічого не нагадує? Це КПФ! Згадай рівняння для квантового перетворення Фур'є:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

Отже, якщо фаза $\theta = y/2^m$ для деякого цілого $y$ від $0$ до $2^m-1$, то застосування оберненого КПФ до цього стану дасть:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

і зі стану $|y\rangle$ можна визначити $\theta$.

Якщо ж $\theta/2^m$ не є цілим кратним, то обернений КПФ лише апроксимує $\theta$. Наскільки точною буде ця апроксимація — питання імовірнісне: ми не завжди отримаємо найкращий результат, але він буде досить близьким, і чим більше кубітів $m$ використовується, тим точнішою буде апроксимація. Щоб дізнатися, як кількісно оцінити цю апроксимацію $\theta$, ознайомся з уроком Джона Ватруса про оцінку фази та факторизацію у курсі «Основи квантових алгоритмів».

Висновок

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

Ключові концепції

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

Запитання

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

1. П/Х Квантове перетворення Фур'є є квантовим аналогом класичного дискретного перетворення Фур'є (ДПФ).
2. П/Х КПФ можна реалізувати, використовуючи лише гейти Адамара та CNOT.
3. П/Х КПФ є ключовою складовою алгоритму Шора.
4. П/Х Результатом квантової оцінки фази є квантовий стан, що представляє власний вектор оператора.
5. П/Х КОФ вимагає застосування оберненого квантового перетворення Фур'є (КПФ$^\dag$).
6. П/Х У КОФ, якщо фаза $\phi$ точно представляється $n$ бітами, алгоритм дає правильний результат з імовірністю 1.

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

1. Скільки кубітів потрібно для виконання КПФ над системою з $2^n$ точками даних?
2. Чи можна застосувати КПФ до стану, який не є обчислювальним базисним станом? Якщо так, що при цьому відбувається?
3. Як кількість керуючих кубітів у КОФ впливає на роздільну здатність отриманої оцінки фази?

Задачі

1. Використай матричне множення, щоб перевірити, що кроки алгоритму КПФ справді дають матрицю $\text{QFT}_4$:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(Робити це вручну не обов'язково!)

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

1. Створи чотирикубітний стан, який є рівною суперпозицією всіх непарних обчислювальних базисів: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Потім виконай КПФ над цим станом. Який стан отримується в результаті? Поясни, чому твій результат має сенс, спираючись на знання перетворень Фур'є.