Задача оцінки фази

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

Спектральна теорема

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

Нормальні матриці

Квадратна матриця $M$ з комплексними елементами називається нормальною, якщо вона комутує зі своїм спряженим транспонуванням: $M M^{\dagger} = M^{\dagger} M.$

Кожна унітарна матриця $U$ є нормальною, оскільки

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

Ермітові матриці — матриці, що дорівнюють своєму спряженому транспонуванню, — ще один важливий клас нормальних матриць. Якщо $H$ — ермітова матриця, то

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

тобто $H$ є нормальною.

Не кожна квадратна матриця є нормальною. Наприклад, ця матриця не є нормальною:

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

(Це простий, але дуже корисний приклад матриці, про яку часто варто думати.) Вона не є нормальною, оскільки

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

тоді як

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

Формулювання теореми

Ось формулювання спектральної теореми.

Теорема

Спектральна теорема: нехай $M$ — нормальна матриця розміру $N\times N$ з комплексними елементами. Існує ортонормований базис із $N$-вимірних комплексних векторів $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ разом із комплексними числами $\lambda_1,\ldots,\lambda_N$ такий, що

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

Вираз матриці у формі

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

зазвичай називають спектральним розкладом. Зауваж, що якщо $M$ — нормальна матриця, подана у формі $(1),$ то рівняння

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

виконується для кожного $j = 1,\ldots,N.$ Це випливає з ортонормованості $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$:

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

Тобто кожне число $\lambda_j$ є власним значенням $M$, а $\vert\psi_j\rangle$ — власним вектором, що відповідає цьому власному значенню.

• Приклад 1. Нехай

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  яка є нормальною. Теорема стверджує, що $\mathbb{I}$ можна записати у формі $(1)$ для деякого вибору $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ і $\vert\psi_2\rangle.$ Існує кілька варіантів, що підходять, зокрема

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  Зверни увагу, що теорема не вимагає, щоб комплексні числа $\lambda_1,\ldots,\lambda_N$ були різними — одне й те саме число може повторюватися, що і необхідно в цьому прикладі. Ці значення підходять, оскільки

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  Насправді, можна взяти $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ як будь-який ортонормований базис і рівняння виконуватиметься. Наприклад,

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• Приклад 2. Розглянемо операцію Адамара.

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

  Це унітарна матриця, тому вона є нормальною. Спектральна теорема стверджує, що $H$ можна записати у формі $(1),$ і, зокрема, маємо

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  де

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  Більш явно,

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  Можна переконатися, що цей розклад правильний, виконавши відповідні обчислення:

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

Як показує перший приклад, у виборі власних векторів може бути певна свобода. Однак у виборі власних значень свободи немає зовсім, окрім їхнього порядку: одні й ті самі $N$ комплексних чисел $\lambda_1,\ldots,\lambda_N,$ (серед яких можуть бути повтори), завжди фігурують у рівнянні $(1)$ для заданої матриці $M.$

Тепер зосередимося на унітарних матрицях. Припустімо, що комплексне число $\lambda$ і ненульовий вектор $\vert\psi\rangle$ задовольняють рівняння

$$U\vert\psi\rangle = \lambda\vert\psi\rangle. \tag{2}$$

Тобто $\lambda$ — власне значення $U$, а $\vert\psi\rangle$ — відповідний власний вектор.

Унітарні матриці зберігають евклідову норму, тому з $(2)$ отримуємо:

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

Умова $\vert\psi\rangle \neq 0$ означає, що $\bigl\| \vert\psi\rangle \bigr\|\neq 0,$ тому можна скоротити обидві частини й отримати

$$\vert \lambda \vert = 1.$$

Це означає, що власні значення унітарних матриць завжди мають абсолютну величину, що дорівнює одиниці, тобто вони лежать на одиничному колі.

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(Символ $\mathbb{T}$ є загальноприйнятою назвою комплексного одиничного кола. Також часто використовується позначення $S^1$.)

Формулювання задачі оцінки фази

У задачі оцінки фази нам дається квантовий стан $\vert \psi\rangle$ із $n$ кубітів разом із унітарною квантовою схемою, що діє на $n$ кубітів. Нам гарантують, що $\vert \psi\rangle$ є власним вектором унітарної матриці $U$, яка описує дію схеми, і наша мета — обчислити або наблизити власне значення $\lambda$, якому відповідає $\vert \psi\rangle$. Оскільки $\lambda$ лежить на комплексному одиничному колі, можна записати

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

для єдиного дійсного числа $\theta$, що задовольняє $0\leq\theta<1.$ Мета задачі — обчислити або наблизити це дійсне число $\theta.$

Задача оцінки фази

Вхід: унітарна квантова схема для $n$-кубітної операції $U$ разом із $n$-кубітним квантовим станом $\vert\psi\rangle$
Обіцянка: $\vert\psi\rangle$ є власним вектором $U$
Вихід: наближення до числа $\theta\in[0,1)$, що задовольняє $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Кілька зауважень щодо цього формулювання задачі:

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

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

3. Зверни увагу: коли $\theta$ зростає від $0$ до $1$ у задачі оцінки фази, ми обходимо увесь одиничний круг, починаючи від $e^{2\pi i \cdot 0} = 1$ і рухаючись проти годинникової стрілки до $e^{2\pi i \cdot 1} = 1.$ Тобто при $\theta = 1$ ми повертаємося туди, де почали, при $\theta = 0.$ Тому при оцінці якості наближень значення $\theta$ поблизу $1$ слід вважати близькими до $0.$ Наприклад, наближення $\theta = 0.999$ слід вважати таким, що відрізняється від $\theta = 0$ менш ніж на $1/1000.$