The phase estimation problem

Ta część lekcji wyjaśnia problem estymacji fazy. Zaczniemy od krótkiego omówienia twierdzenia spektralnego z algebry liniowej, a następnie przejdziemy do sformułowania samego problemu estymacji fazy.

Spectral theorem

Twierdzenie spektralne to ważny fakt z algebry liniowej, który stwierdza, że macierze pewnego rodzaju — zwane normal matrices — można wyrazić w prosty i użyteczny sposób. W tej lekcji będziemy potrzebować tego twierdzenia wyłącznie dla macierzy unitary, ale dalej w tej serii zastosujemy je również do macierzy Hermitian.

Normal matrices

O kwadratowej macierzy $M$ o elementach zespolonych mówimy, że jest normal, jeśli komutuje ze swoją sprzężoną transpozycją: $M M^{\dagger} = M^{\dagger} M.$

Każda macierz unitary $U$ jest normal, ponieważ

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

Macierze Hermitian, czyli macierze równe swojej sprzężonej transpozycji, to kolejna ważna klasa normal matrices. Jeśli $H$ jest macierzą Hermitian, to

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

więc $H$ jest normal.

Nie każda macierz kwadratowa jest normal. Na przykład ta macierz nie jest normal:

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

(To prosty, ale świetny przykład macierzy, którą warto często brać pod uwagę.) Nie jest normal, ponieważ

$$\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}$$

podczas gdy

$$\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}.$$

Sformułowanie twierdzenia

Oto teraz sformułowanie twierdzenia spektralnego.

Twierdzenie

Twierdzenie spektralne (spectral theorem): Niech $M$ będzie normalną macierzą zespoloną wymiaru $N\times N$. Istnieje orthonormal basis (baza ortonormalna) $N$-wymiarowych wektorów zespolonych $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ oraz liczby zespolone $\lambda_1,\ldots,\lambda_N$ takie, że

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

Zapis macierzy w postaci

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

nazywamy powszechnie rozkładem spektralnym (spectral decomposition). Zauważmy, że jeśli $M$ jest macierzą normalną zapisaną w postaci $(1),$ to równanie

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

musi zachodzić dla każdego $j = 1,\ldots,N.$ Wynika to z faktu, że $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ jest orthonormal:

$$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$$

Innymi słowy, każda liczba $\lambda_j$ jest eigenvalue (wartością własną) macierzy $M,$ a $\vert\psi_j\rangle$ jest eigenvector (wektorem własnym) odpowiadającym tej wartości własnej.

• Przykład 1. Niech

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

  co jest macierzą normalną. Z twierdzenia wynika, że $\mathbb{I}$ można zapisać w postaci $(1)$ dla pewnego wyboru $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle$ i $\vert\psi_2\rangle.$ Istnieje wiele poprawnych wyborów, w tym

  $$\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.$$

  Zauważmy, że twierdzenie nie mówi, że liczby zespolone $\lambda_1,\ldots,\lambda_N$ są parami różne — ta sama liczba zespolona może się powtarzać, co jest konieczne w tym przykładzie. Powyższe wybory są poprawne, ponieważ

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

  Co więcej, możemy wybrać $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ jako dowolną orthonormal basis i równanie nadal będzie prawdziwe. Na przykład:

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

• Przykład 2. Rozważmy operację Hadamarda.

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

  Jest to macierz unitary, a więc normalna. Z twierdzenia spektralnego wynika, że $H$ można zapisać w postaci $(1),$ a w szczególności mamy

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

  gdzie

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

  Bardziej szczegółowo:

  $$\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}$$

  Możemy sprawdzić poprawność tego rozkładu, wykonując wymagane obliczenia:

  $$\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.$$

Jak pokazuje pierwszy z powyższych przykładów, przy wyborze eigenvectors (wektorów własnych) istnieje pewna swoboda. Nie ma natomiast żadnej swobody w wyborze eigenvalues (wartości własnych), poza ich kolejnością: te same $N$ liczb zespolonych $\lambda_1,\ldots,\lambda_N,$ które mogą zawierać powtórzenia tej samej liczby, zawsze będą występować w równaniu $(1)$ dla danej macierzy $M.$

Skupmy się teraz na macierzach unitary. Załóżmy, że mamy liczbę zespoloną $\lambda$ i niezerowy wektor $\vert\psi\rangle$ spełniające równanie

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

Czyli $\lambda$ jest eigenvalue macierzy $U,$ a $\vert\psi\rangle$ jest eigenvector odpowiadającym tej wartości własnej.

Macierze unitary zachowują normę euklidesową, więc z $(2)$ wyciągamy następujący wniosek.

$$\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\|$$

Z tego, że $\vert\psi\rangle$ jest niezerowy, wynika $\bigl\| \vert\psi\rangle \bigr\|\neq 0,$ więc możemy skrócić obie strony i otrzymać

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

Oznacza to, że eigenvalues macierzy unitary muszą mieć moduł równy jeden, a zatem leżą na okręgu jednostkowym (unit circle).

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

(Symbol $\mathbb{T}$ jest powszechnie używaną nazwą dla zespolonego okręgu jednostkowego. Często spotyka się też nazwę $S^1$.)

Phase estimation problem statement

W problemie phase estimation dane są: stan kwantowy $\vert \psi\rangle$ złożony z $n$ qubitów oraz unitarny obwód kwantowy działający na $n$ qubitach. Zakładamy, że $\vert \psi\rangle$ jest eigenvectorem macierzy unitarnej $U$ opisującej działanie tego obwodu, a naszym celem jest obliczenie lub przybliżenie eigenvalue $\lambda$, któremu odpowiada $\vert \psi\rangle$. Dokładniej, ponieważ $\lambda$ leży na zespolonej okręgu jednostkowym, możemy zapisać

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

dla jednoznacznie wyznaczonej liczby rzeczywistej $\theta$ spełniającej $0\leq\theta<1.$ Celem problemu jest obliczenie lub przybliżenie tej liczby rzeczywistej $\theta.$

Phase estimation problem

Wejście: unitarny obwód kwantowy dla $n$-qubitowej operacji $U$ wraz z $n$-qubitowym stanem kwantowym $\vert\psi\rangle$
Założenie: $\vert\psi\rangle$ jest eigenvectorem $U$
Wyjście: przybliżenie liczby $\theta\in[0,1)$ spełniającej $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Kilka uwag dotyczących tego sformułowania problemu:

1. Problem phase estimation różni się od innych problemów, które poznałeś dotychczas w tym kursie, tym że wejście zawiera stan kwantowy. Zazwyczaj skupiamy się na problemach z klasycznymi wejściami i wyjściami, ale nic nie stoi na przeszkodzie, by rozważać takie kwantowe stany wejściowe jak tutaj. Jeśli chodzi o praktyczne zastosowania, problem phase estimation najczęściej pojawia się jako podproblem w ramach większego obliczenia — tak jak zobaczymy w kontekście faktoryzacji liczb całkowitych w dalszej części lekcji.

2. Powyższe sformułowanie problemu phase estimation nie precyzuje, czym dokładnie jest przybliżenie $\theta,$ jednak możemy formułować bardziej szczegółowe wersje problemu w zależności od naszych potrzeb i zainteresowań. W kontekście faktoryzacji liczb całkowitych będziemy wymagać bardzo dokładnego przybliżenia $\theta,$ lecz w innych przypadkach może wystarczyć nam bardzo przybliżona wartość. Wkrótce omówimy, jak wymagana precyzja wpływa na koszt obliczeniowy rozwiązania.