Процедура оцінювання фази

Далі ми розглянемо процедуру оцінювання фази — квантовий алгоритм розв'язання задачі оцінювання фази.

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

Розігрів: апроксимація фаз із низькою точністю

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

Використання фазового відкидання

Простий підхід до задачі оцінювання фази, який дозволяє дізнатися дещо про значення $\theta$, що ми шукаємо, ґрунтується на явищі фазового відкидання. Як ми побачимо, це фактично однокубітна версія загальної процедури оцінювання фази, яку обговоримо пізніше в уроці.

Як частина вхідних даних задачі оцінювання фази, у нас є унітарна квантова схема для операції $U.$ Ми можемо використати опис цієї схеми, щоб побудувати схему для операції контрольованого-$U$, яку можна зобразити так, як показано на малюнку (ліворуч — операція $U$ як квантовий вентиль, праворуч — операція контрольованого-$U$).

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

Тепер розглянемо таку схему, де вхідний стан $\vert\psi\rangle$ усіх кубітів, крім верхнього, є власним вектором квантового стану $U.$

Ймовірності результатів вимірювання для цієї схеми залежать від власного значення $U$, що відповідає власному вектору $\vert\psi\rangle.$ Детально проаналізуємо схему, щоб з'ясувати, як саме.

Початковий стан схеми:

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

і перший вентиль Адамара переводить цей стан у

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Далі виконується операція контрольованого-$U$, що призводить до стану

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

Використовуючи припущення, що $\vert\psi\rangle$ є власним вектором $U$ з власним значенням $\lambda = e^{2\pi i\theta},$ можна виразити цей стан інакше.

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

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

Нарешті виконується другий вентиль Адамара. Після невеликого спрощення отримуємо такий вираз для цього стану.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

Вимірювання дає результати $0$ і $1$ із такими ймовірностями:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Ось графік ймовірностей двох можливих результатів, $0$ і $1,$ як функцій $\theta.$

Природно, що дві ймовірності завжди у сумі дають $1.$ Зауважимо, що коли $\theta = 0,$ результат вимірювання завжди $0,$ а коли $\theta = 1/2,$ результат вимірювання завжди $1.$ Отже, хоча результат вимірювання не розкриває точного значення $\theta,$ він надає нам певну інформацію про нього — і якщо нам заздалегідь обіцяно, що або $\theta = 0,$ або $\theta = 1/2,$ ми можемо дізнатися зі схеми, яке з них правильне, без помилок.

Інтуїтивно можна вважати, що результат вимірювання схеми є здогадкою про $\theta$ з «точністю до одного біту». Іншими словами, якщо записати $\theta$ у двійковому позначенні й округлити до одного біту, отримаємо число такого вигляду:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Результат вимірювання можна розглядати як здогадку для біту $a.$ Коли $\theta$ не є ні $0,$ ні $1/2,$ існує ненульова ймовірність неправильної здогадки — але ймовірність помилки стає дедалі меншою, коли ми наближаємося до $0$ або $1/2.$

Природно запитати, яку роль відіграють два вентилі Адамара в цій процедурі:

• Перший вентиль Адамара переводить контрольний кубіт у рівномірну суперпозицію $\vert 0\rangle$ і $\vert 1\rangle,$ щоб під час фазового відкидання воно відбувалося для стану $\vert 1\rangle,$ а не $\vert 0\rangle,$ створюючи відносну різницю фаз, що впливає на ймовірності результатів вимірювання. Якби ми цього не робили, і фазове відкидання давало б глобальну фазу, це б не мало жодного впливу на ймовірності отримання різних результатів вимірювання.

• Другий вентиль Адамара дозволяє нам дізнатися дещо про число $\theta$ через явище інтерференції. До другого вентиля Адамара стан верхнього кубіта є

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  і якщо виміряти цей стан, ми отримаємо $0$ і $1$ кожен із ймовірністю $1/2,$ нічого не дізнавшись про $\theta.$ Але виконавши другий вентиль Адамара, ми змушуємо число $\theta$ впливати на вихідні ймовірності.

Подвоєння фази

Наведена вище схема використовує явище фазового відкидання, щоб апроксимувати $\theta$ з точністю до одного біту. Одного біту точності може бути достатньо в деяких ситуаціях — але для факторизації нам знадобиться значно більша точність. Виникає природне питання: як дізнатися більше про $\theta?$

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

Два примірники операції контрольованого-$U$ еквівалентні операції контрольованого-$U^2.$ Якщо $\vert\psi\rangle$ є власним вектором $U$ з власним значенням $\lambda = e^{2\pi i \theta},$ то цей стан також є власним вектором $U^2,$ цього разу з власним значенням $\lambda^2 = e^{2\pi i (2\theta)}.$

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

Це справді може надати нам додаткову інформацію про $\theta.$ Якщо двійкове представлення $\theta$ є

$$\theta = 0.a_1 a_2 a_3\cdots$$

то подвоєння $\theta$ фактично зсуває двійкову кому на одну позицію праворуч:

$$2\theta = a_1. a_2 a_3\cdots$$

І оскільки ми ототожнюємо $\theta = 1$ із $\theta = 0$ при русі по одиничному колу, то біт $a_1$ не впливає на наші ймовірності, і ми фактично отримуємо здогадку для другого біту після двійкової коми, якщо округлити $\theta$ до двох бітів. Наприклад, якщо ми заздалегідь знаємо, що $\theta$ є або $0,$ або $1/4,$ то можемо повністю довіряти результату вимірювання для визначення правильного значення.

Однак не зовсім зрозуміло, як це оцінювання слід узгодити з тим, що ми дізналися з початкової (не подвоєної) схеми фазового відкидання, щоб отримати найточнішу можливу інформацію про $\theta.$ Тож зробимо крок назад і розглянемо, як діяти далі.

Двокубітне оцінювання фази

Замість окремого розгляду двох описаних вище варіантів, об'єднаємо їх в одну схему ось так.

Вентилі Адамара після контрольованих операцій прибрано, і вимірювань тут ще немає. Ми додамо більше до схеми, коли розглянемо варіанти дізнатися якомога більше про $\theta.$

Якщо запустити цю схему, коли $\vert\psi\rangle$ є власним вектором $U,$ стан нижніх кубітів залишатиметься $\vert\psi\rangle$ протягом усієї схеми, а фази будуть «відкидатися» у стан двох верхніх кубітів. Детально проаналізуємо схему за допомогою наступного малюнка.

Стан $\vert\pi_1\rangle$ можна записати так:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

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

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Другий і третій вентилі контрольованого-$U$ роблять щось подібне, але для $a_1$ замість $a_0,$ і з $\theta,$ заміненим на $2\theta.$ Стан, що виникає, можна виразити так:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Якщо розглядати двійковий рядок $a_1 a_0$ як ціле число $x \in \{0,1,2,3\}$ у двійковому записі, де $x = 2 a_1 + a_0,$ можна виразити цей стан інакше.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Наша мета — витягти якомога більше інформації про $\theta$ із цього стану.

На цьому етапі розглянемо спеціальний випадок, коли нам обіцяно, що $\theta = \frac{y}{4}$ для деякого цілого $y\in\{0,1,2,3\}.$ Іншими словами, маємо $\theta\in \{0, 1/4, 1/2, 3/4\},$ тож це число можна точно виразити у двійковому записі двома бітами: .$00,$ .$01,$ .$10$ або .$11.$ Загалом $\theta$ може не бути одним із цих чотирьох значень, але розмірковування над цим спеціальним випадком допоможе з'ясувати, як найефективніше витягти інформацію про $\theta$ в загальному випадку.

Спочатку визначимо двокубітний вектор стану для кожного можливого значення $y \in \{0, 1, 2, 3\}.$

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Після спрощення показників степенів ці вектори можна записати так.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Ці вектори ортогональні: якщо взяти будь-яку пару з них і обчислити їх скалярний добуток, отримаємо $0.$ Кожен із них також є одиничним вектором, тому $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ є ортонормованим базисом. Тому ми одразу знаємо, що існує вимірювання, яке може розрізнити їх ідеально — тобто, якщо нам дано один із них, але ми не знаємо який, ми можемо визначити, який саме, без помилок.

Щоб виконати таке розрізнення за допомогою квантової схеми, можна спочатку визначити унітарну операцію $V,$ що перетворює стандартні базисні стани на чотири стани, перелічені вище.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Щоб записати $V$ у вигляді матриці $4\times 4$, достатньо взяти стовпці $V$ як стани $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle.$

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Це особлива матриця, і деякі читачі, певно, вже зустрічали її раніше: це матриця, пов'язана з $4$-вимірним дискретним перетворенням Фур'є. З огляду на це назвемо її $\mathrm{QFT}_4$ замість $V.$ Назва $\mathrm{QFT}$ — скорочення від квантового перетворення Фур'є (quantum Fourier transform) — яке є, по суті, просто дискретним перетворенням Фур'є, розглянутим як унітарна операція. Квантове перетворення Фур'є ми обговоримо докладніше й у більшій загальності незабаром.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Ми можемо застосувати обернену операцію, щоб піти в іншому напрямку — перетворити стани $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ на стандартні базисні стани $\vert 0\rangle,\ldots,\vert 3\rangle.$ Якщо зробити це, то зможемо виміряти й дізнатися, яке значення $y\in\{0,1,2,3\}$ описує $\theta$ як $\theta = y/4.$ Ось схема квантової схеми, що це реалізує.

Підсумовуючи: якщо запустити цю схему, коли $\theta = y/4$ для $y\in\{0,1,2,3\},$ стан безпосередньо перед вимірюванням буде $\vert \psi\rangle \vert y\rangle$ (де $y$ закодовано як двобітний двійковий рядок), тому вимірювання виявлять значення $y$ без помилок.

Ця схема мотивована спеціальним випадком $\theta \in \{0,1/4,1/2,3/4\}$ — але ми можемо запустити її для будь-якого вибору $U$ і $\vert \psi\rangle,$ а отже, і будь-якого значення $\theta,$ яке захочемо. Ось графік вихідних ймовірностей, що їх дає схема для довільних значень $\theta.$

Це помітне покращення порівняно з однокубітним варіантом, описаним раніше в уроці. Схема не ідеальна — вона може давати неправильну відповідь — але відповідь сильно зміщена до значень $y,$ для яких $y/4$ близьке до $\theta.$ Зокрема, найімовірніший результат завжди відповідає найближчому значенню $y/4$ до $\theta$ (ототожнюючи $\theta = 0$ і $\theta = 1$ як раніше), і з графіка видно, що це найближче значення завжди з'являється з ймовірністю дещо більше $40\%.$ Коли $\theta$ знаходиться рівно посередині між двома такими значеннями, як, наприклад, $\theta = 0.375,$ два однаково близькі значення $y$ рівноймовірні.

Підготовка до узагальнення на багато кубітів

З огляду на покращення, щойно отримане завдяки використанню двох контрольних кубітів замість одного разом із оберненням $4$-вимірного квантового перетворення Фур'є, природно розглянути подальше узагальнення — шляхом додавання більшої кількості контрольних кубітів. Коли ми це зробимо, отримаємо загальну процедуру оцінювання фази. Незабаром ми побачимо, як це працює, але щоб описати це точно, нам потрібно обговорити квантове перетворення Фур'є в більшій загальності — подивитися, як воно визначається для інших розмірностей і як його можна реалізувати (або його обернення) за допомогою квантової схеми.

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

Квантове перетворення Фур'є — це унітарна операція, яку можна визначити для будь-якої натуральної розмірності $N.$ У цьому розділі ми побачимо, як визначається ця операція і як її можна реалізувати квантовою схемою на $m$ кубітах із вартістю $O(m^2)$, коли $N = 2^m.$

Матриці, що описують квантове перетворення Фур'є, походять від аналогічної операції над $N$-вимірними векторами, відомої як дискретне перетворення Фур'є. Цю операцію можна розглядати по-різному. Наприклад, можна розглядати дискретне перетворення Фур'є в суто абстрактних математичних термінах як лінійне відображення. Або можна розглядати його в обчислювальному контексті, де нам дано $N$-вимірний вектор комплексних чисел (використовуючи двійковий запис для кодування дійсних та уявних частин елементів) і мета — обчислити $N$-вимірний вектор, отриманий застосуванням дискретного перетворення Фур'є. Наша увага зосередиться на третьому способі — розгляді цього перетворення як унітарної операції, яку можна виконати над квантовою системою.

Існує ефективний алгоритм обчислення дискретного перетворення Фур'є для заданого вхідного вектора, відомий як швидке перетворення Фур'є. Він має застосування в обробці сигналів та багатьох інших галузях і вважається багатьма одним із найважливіших алгоритмів, коли-небудь відкритих. Як з'ясовується, реалізація квантового перетворення Фур'є, коли $N$ є степенем двійки, яку ми вивчатимемо, ґрунтується саме на тій самій базовій структурі, що робить можливим швидке перетворення Фур'є.

Визначення квантового перетворення Фур'є

Щоб визначити квантове перетворення Фур'є, спочатку визначимо комплексне число $\omega_N$ для кожного натурального $N$ ось так:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Це число на комплексному одиничному колі, яке ми отримуємо, якщо починаємо з $1$ і рухаємося проти годинникової стрілки на кут $2\pi/N$ радіан, або на частку $1/N$ периметра кола. Ось кілька прикладів:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Тепер можна визначити $N$-вимірне квантове перетворення Фур'є, яке описується матрицею $N\times N$, рядки та стовпці якої пов'язані зі стандартними базисними станами $\vert 0\rangle,\ldots,\vert N-1\rangle.$ Для оцінювання фази нам потрібна ця операція лише коли $N = 2^m$ є степенем $2,$ але операцію можна визначити для будь-якого натурального $N.$

$$\mathrm{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$-вимірним дискретним перетворенням Фур'є. Часто провідний множник $1/\sqrt{N}$ не включається у визначення цієї матриці, але нам потрібно його включити, щоб отримати унітарну матрицю.

Ось квантове перетворення Фур'є у вигляді матриці для деяких малих значень $N.$

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Зауважимо, зокрема, що $\mathrm{QFT}_2$ — це інша назва операції Адамара.

Унітарність

Перевіримо, що $\mathrm{QFT}_N$ є унітарним для будь-якого вибору $N.$ Один зі способів це зробити — показати, що його стовпці утворюють ортонормований базис. Можна визначити вектор, що відповідає стовпцю з номером $y,$ починаючи з $y = 0$ і до $y = N-1,$ так:

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

Обчислюючи скалярний добуток між будь-якими двома такими векторами, отримаємо такий вираз:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Суми такого вигляду можна обчислити за допомогою такої формули суми перших $N$ членів геометричного ряду.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Зокрема, цю формулу можна застосувати при $\alpha = \omega_N^{y-z}.$ Коли $y = z,$ маємо $\alpha = 1,$ тому з формули після ділення на $N$ отримаємо

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Коли $y\neq z,$ маємо $\alpha \neq 1,$ тому формула дає такий результат:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Це відбувається тому, що $\omega_N^N = e^{2\pi i} = 1,$ а отже $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ що робить чисельник нульовим, тоді як знаменник ненульовий, бо $\omega_N^{y-z} \neq 1.$ Інтуїтивно, ми підсумовуємо точки, рівномірно розподілені по одиничному колу, і вони взаємно скорочуються, даючи $0.$

Ми встановили, що $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ — ортонормована система,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

що свідчить про унітарність $\mathrm{QFT}_N.$

Вентилі керованої фази

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

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

для будь-якого дійсного числа $\alpha.$ Керована версія цього вентиля має таку матрицю:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

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

У третій формі мітку $\alpha$ іноді також розміщують збоку від лінії керування або під нижньою точкою керування, коли це зручніше.

Щоб виконати квантове перетворення Фур'є при $N = 2^m$ і $m\geq 2,$ нам потрібна операція на $m$ кубітах, дія якої на стандартні базисні стани описується формулою

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

де $a$ — це біт, а $y \in \{0,\ldots,2^{m-1} - 1\}$ — число, закодоване в бінарному записі як рядок із $m-1$ бітів. Це можна реалізувати за допомогою вентилів керованої фази, узагальнюючи такий приклад для $m=5.$

У загальному випадку, для довільного $m\geq 2,$ верхній кубіт, що відповідає біту $a,$ можна розглядати як керуючий, а вентилі фази $P_{\alpha}$ варіюються від $\alpha = \pi/2^{m-1}$ на кубіті, що відповідає молодшому біту $y,$ до $\alpha = \frac{\pi}{2}$ на кубіті, що відповідає старшому біту $y.$ Усі ці вентилі керованої фази комутують між собою і можуть виконуватись у будь-якому порядку.

Схемна реалізація КПФ

Тепер подивимось, як можна реалізувати квантове перетворення Фур'є за допомогою схеми, коли розмірність $N = 2^m$ є степенем двійки. Насправді існує кілька способів реалізувати квантове перетворення Фур'є, але цей, мабуть, найпростіший із відомих. Знаючи, як реалізувати квантове перетворення Фур'є у вигляді квантової схеми, легко реалізувати і його обернене: потрібно замінити кожен вентиль на його обернений (або, еквівалентно, на спряжено-транспонований) і застосувати вентилі у зворотному порядку. Будь-яку квантову схему, складену лише з унітарних вентилів, можна інвертувати таким способом.

Реалізація рекурсивна за своєю природою, тому саме так її найзручніше описати. Базовий випадок — $m=1,$ коли квантове перетворення Фур'є є операцією Адамара.

Щоб виконати квантове перетворення Фур'є на $m$ кубітах при $m \geq 2,$ можна виконати такі кроки, дію яких ми опишемо для стандартних базисних станів вигляду $\vert x \rangle \vert a\rangle,$ де $x\in\{0,\ldots,2^{m-1} - 1\}$ — ціле число, закодоване $m-1$ бітами в бінарному записі, а $a$ — один біт.

1. Спочатку застосуй $2^{m-1}$-вимірне квантове перетворення Фур'є до нижніх/лівих $m-1$ кубітів, щоб отримати такий стан:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Це робиться рекурсивним застосуванням описаного методу для одного кубіта менше, де базовим випадком є операція Адамара на одному кубіті.

2. Використай верхній/правий кубіт як керуючий, щоб впорснути фазу $\omega_{2^m}^y$ для кожного стандартного базисного стану $\vert y\rangle$ решти $m-1$ кубітів (як описано вище), отримавши такий стан:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Виконай вентиль Адамара на верхньому/правому кубіті, щоб отримати такий стан:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Переставляй порядок кубітів так, щоб молодший біт став старшим, а всі інші зсунулись вгору/вправо:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Наприклад, ось схема для $N = 32 = 2^5.$ На цій діаграмі кубіти позначені іменами, що відповідають стандартним базисним векторам $\vert x\rangle \vert a\rangle$ (для входу) і $\vert b\rangle \vert y\rangle$ (для виходу), для наочності.

Аналіз

Ключова формула, яка потрібна, щоб перевірити, що описана схема реалізує $2^m$-вимірне квантове перетворення Фур'є, виглядає так:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Ця формула справедлива для будь-яких цілих $a,$ $b,$ $x$ і $y,$ але нам вона потрібна лише для $a,b\in\{0,1\}$ і $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Перевірити її можна, розкривши добуток у показнику степеня в правій частині,

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

де друга рівність спирається на спостереження, що

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

$2^m$-вимірне квантове перетворення Фур'є визначається так для кожного $u\in\{0,\ldots,2^m - 1\}.$

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Якщо записати $u$ і $v$ як

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

для $a,b\in\{0,1\}$ і $x,y\in\{0,\ldots,2^{m-1} - 1\},$ то отримаємо

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Нарешті, розглядаючи стандартні базисні стани $\vert x \rangle \vert a\rangle$ і $\vert b \rangle \vert y \rangle$ як бінарне кодування цілих чисел у діапазоні $\{0,\ldots,2^m-1\},$

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

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

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

Позначимо через $s_m$ кількість вентилів для кожного можливого вибору $m.$ При $m=1$ квантове перетворення Фур'є — це просто операція Адамара, тому

$$s_1 = 1.$$

При $m\geq 2$ у наведеній схемі потрібно $s_{m-1}$ вентилів для квантового перетворення Фур'є на $m-1$ кубітах, плюс $m-1$ вентилів керованої фази, плюс вентиль Адамара, плюс $m-1$ вентилів перестановки, тому

$$s_m = s_{m-1} + (2m - 1).$$

Замкнений вираз можна отримати підсумовуванням:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

Насправді стільки вентилів перестановки не потрібно. Якщо трохи перегрупувати вентилі, можна перенести всі вентилі перестановки вправо і скоротити їх кількість до $\lfloor m/2\rfloor.$ Асимптотично це не суттєве покращення: схеми для $\mathrm{QFT}_{2^m}$ все одно мають розмір $O(m^2).$

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

Насправді квантове перетворення Фур'є можна досить добре апроксимувати субквадратичною кількістю вентилів, скориставшись тим, що $P_{\alpha}$ дуже близький до тотожної операції при дуже малому $\alpha$ — а отже, більшість вентилів керованої фази можна просто відкинути без великої втрати точності.

Загальна процедура та аналіз

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

Зверни увагу: з кожним новим керуючим кубітом, доданим зверху, кількість виконань унітарної операції $U$ подвоюється. Це позначено в діаграмі степенями на $U$ для кожної з операцій керованого унітарного.

Найпростіший спосіб реалізувати керовану операцію $U^k$ для деякого $k$ — просто повторити операцію керованого $U$ $k$ разів. Якщо справді використовується саме такий підхід, слід усвідомити, що додавання керуючих кубітів суттєво збільшує розмір схеми: при $m$ керуючих кубітах, як показано на діаграмі, потрібно загалом $2^m - 1$ копій операції керованого $U.$ Це означає, що зі збільшенням $m$ обчислювальна вартість значно зростає — але, як ми побачимо, це також призводить до суттєво точнішого наближення $\theta.$

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

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

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Окремий випадок

Аналогічно до того, що ми робили у випадку $m=2,$ спочатку розглянемо окремий випадок, коли $\theta = y/2^m$ для $y\in\{0,\ldots,2^m-1\}.$ У цьому випадку стан перед оберненим квантовим перетворенням Фур'є можна записати інакше:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Отже, після застосування оберненого квантового перетворення Фур'є стан стає

$$\vert\psi\rangle \vert y\rangle$$

і вимірювання дають $y$ (у бінарному кодуванні).

Оцінка ймовірностей

Для інших значень $\theta,$ тобто тих, що не мають вигляду $y/2^m$ для цілого $y,$ результати вимірювань не будуть детермінованими, але можна довести оцінки на ймовірності різних результатів. Далі розглянемо довільне $\theta,$ що задовольняє $0\leq \theta < 1.$

Після застосування оберненого квантового перетворення Фур'є стан схеми має вигляд:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Тому при вимірюванні верхніх $m$ кубітів кожен результат $y$ з'являється з імовірністю

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

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

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Суму у формулі для $p_y$ можна спростити, взявши $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Ось що отримаємо.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

Отже, у випадку $\theta = y/2^m$ отримаємо $p_y = 1$ (що вже відомо з розгляду цього окремого випадку), а у випадку $\theta \neq y/2^m$

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

Більше про ці ймовірності можна дізнатись, проаналізувавши зв'язок між довжинами дуг і хорд на одиничному колі. Ось рисунок, що ілюструє потрібні співвідношення для будь-якого дійсного числа $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

По-перше, довжина хорди (синя) не може бути більшою за довжину дуги (фіолетова):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Порівнюючи ці довжини в іншому напрямку, бачимо, що відношення довжини дуги до довжини хорди є найбільшим при $\delta = \pm 1/2,$ і в цьому випадку воно дорівнює половині довжини кола, поділеній на діаметр, тобто $\pi/2.$ Таким чином,

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

і тому

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Аналіз на основі цих співвідношень дає два таких факти.

1. Нехай $\theta$ — дійсне число, а $y\in \{0,\ldots,2^m-1\}$ задовольняє

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Це означає, що $y/2^m$ є або найкращим $m$-бітним наближенням до $\theta,$ або рівно посередині між $y/2^m$ і $(y-1)/2^m$ чи $(y+1)/2^m,$ тобто одним із двох найкращих наближень до $\theta.$

   Доведемо, що $p_y$ у цьому випадку має бути досить великим. З нашого припущення випливає, що $\vert 2^m \theta - y \vert \leq 1/2,$ тому з другого спостереження про дуги і хорди отримаємо

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   З першого спостереження про дуги і хорди також випливає, що

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Використовуючи ці дві нерівності для $p_y,$ отримаємо

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Це пояснює наше спостереження, що найкращий результат з'являється з імовірністю понад $40\%$ у версії оцінки фази з $m=2,$ розглянутій раніше. Точніше, це не просто $40\%$, а $4/\pi^2,$ і ця оцінка справедлива для будь-якого $m.$

2. Тепер нехай $y\in \{0,\ldots,2^m-1\}$ задовольняє

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Це означає, що між $\theta$ і $y/2^m$ існує краще наближення $z/2^m.$

   Цього разу доведемо, що $p_y$ не може бути надто великим. Почнемо з простого спостереження:

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   що випливає з того, що будь-які дві точки на одиничному колі відрізняються за модулем не більше ніж на $2.$

   З другого спостереження про дуги і хорди, застосованого цього разу до знаменника $p_y,$ а не до чисельника, отримаємо

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Поєднуючи обидві нерівності, отримаємо

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Зауважимо, що хоча ця оцінка достатня для наших цілей, вона досить груба — насправді ймовірність зазвичай набагато менша за $1/4.$

Головний висновок цього аналізу полягає в тому, що дуже близькі наближення до $\theta$ виникають часто — найкраще $m$-бітне наближення з'являється з імовірністю понад $40\%$ — тоді як наближення з похибкою понад $2^{-m}$ виникають рідше, з імовірністю не більше $25\%.$

Враховуючи ці гарантії, можна підвищити впевненість у результаті, повторивши процедуру оцінки фази кілька разів для збору статистичних даних про $\theta.$ Важливо зауважити, що стан $\vert\psi\rangle$ нижньої групи кубітів залишається незмінним після процедури оцінки фази, тому її можна запускати скільки завгодно разів. Зокрема, кожного разу, коли ми запускаємо схему, найкраще $m$-бітне наближення до $\theta$ з'являється з імовірністю понад $40\%,$ тоді як ймовірність похибки понад $2^{-m}$ обмежена $25\%.$ Якщо запустити схему кілька разів і взяти найчастіший результат, то результат, що з'являється найчастіше, майже напевно не буде тим, що виникає щонайбільше $25\%$ часу. Завдяки цьому ми з великою ймовірністю отримаємо наближення $y/2^m,$ яке відрізняється від $\theta$ не більше ніж на $1/2^m.$ Насправді малоймовірна можливість похибки понад $1/2^m$ зменшується експоненційно зі збільшенням кількості запусків процедури.

Ось два графіки, що показують імовірності для трьох послідовних значень $y$ при $m = 3$ і $m=4$ як функції від $\theta.$ (Для наочності показано лише три результати. Імовірності для інших результатів отримуються циклічним зсувом тієї ж базової функції.)