Problém odhadu fáze

Tato část lekce vysvětluje problém odhadu fáze. Začneme krátkou diskuzí o spektrální větě z lineární algebry a poté přejdeme k formulaci samotného problému odhadu fáze.

Spektrální věta

Spektrální věta je důležitý fakt z lineární algebry, který říká, že matice určitého typu, nazývané normální matice, lze vyjádřit jednoduchým a užitečným způsobem. V této lekci budeme tuto větu potřebovat pouze pro unitární matice, ale v dalších částech této série ji aplikujeme i na hermitovské matice.

Normální matice

Čtvercová matice $M$ s komplexními čísly jako prvky se nazývá normální matice, pokud komutuje se svou konjugovanou transpozicí: $M M^{\dagger} = M^{\dagger} M.$

Každá unitární matice $U$ je normální, protože

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

Hermitovské matice, což jsou matice rovné své vlastní konjugované transpozici, jsou další důležitou třídou normálních matic. Pokud $H$ je hermitovská matice, pak

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

takže $H$ je normální.

Ne každá čtvercová matice je normální. Například tato matice není normální:

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

(Toto je jednoduchý, ale skvělý příklad matice, kterou je často velmi užitečné zvážit.) Není normální, protože

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

zatímco

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

Formulace věty

Nyní zde je formulace spektrální věty.

Věta

Spektrální věta: Nechť $M$ je normální $N\times N$ komplexní matice. Existuje ortonormální báze $N$-rozměrných komplexních vektorů $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ spolu s komplexními čísly $\lambda_1,\ldots,\lambda_N$ takovými, že

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

Vyjádření matice ve tvaru

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

se běžně nazývá spektrální rozklad. Všimni si, že pokud je $M$ normální matice vyjádřená ve tvaru $(1)$, pak rovnice

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

musí platit pro každé $j = 1,\ldots,N$. To je důsledek toho, že $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ je ortonormální:

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

To znamená, že každé číslo $\lambda_j$ je vlastní hodnota matice $M$ a $\vert\psi_j\rangle$ je vlastní vektor odpovídající této vlastní hodnotě.

• Příklad 1. Nechť

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

  což je normální matice. Věta říká, že $\mathbb{I}$ lze zapsat ve tvaru $(1)$ pro nějakou volbu $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle$ a $\vert\psi_2\rangle.$ Existuje více voleb, které fungují, například

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

  Všimni si, že teorém neříká, že komplexní čísla $\lambda_1,\ldots,\lambda_N$ jsou navzájem různá — stejné komplexní číslo se může opakovat, což je pro tento příklad nutné. Tyto volby fungují, protože

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

  Ve skutečnosti bychom mohli zvolit $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ jako libovolnou ortonormální bázi a rovnice by platila. Například

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

• Příklad 2. Uvažuj Hadamardovu operaci.

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

  Jedná se o unitární matici, takže je normální. Spektrální teorém říká, že $H$ lze zapsat ve tvaru $(1)$, a konkrétně máme

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

  kde

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

  Explicitněji zapsáno,

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

  Můžeme ověřit, že tento rozklad je správný, provedením příslušných výpočtů:

  $$\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 ukazuje první příklad výše, při volbě vlastních vektorů může existovat určitá svoboda. V případě vlastních čísel však žádná svoboda neexistuje, s výjimkou jejich pořadí: stejných $N$ komplexních čísel $\lambda_1,\ldots,\lambda_N$, která mohou zahrnovat opakování téhož komplexního čísla, se vždy objeví v rovnici $(1)$ pro danou matici $M$.

Nyní se zaměřme na unitární matice. Předpokládejme, že máme komplexní číslo $\lambda$ a nenulový vektor $\vert\psi\rangle$, které splňují rovnici

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

To znamená, že $\lambda$ je vlastní číslo $U$ a $\vert\psi\rangle$ je vlastní vektor příslušný tomuto vlastnímu číslu.

Unitární matice zachovávají euklidovskou normu, a tak z $(2)$ plyne následující.

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

Podmínka, že $\vert\psi\rangle$ je nenulový, znamená, že $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, takže můžeme obě strany vydělit a získat

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

Z toho vyplývá, že vlastní čísla unitárních matic musí mít vždy absolutní hodnotu rovnu jedné, takže leží na jednotkové kružnici.

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

(Symbol $\mathbb{T}$ je běžné označení pro komplexní jednotkovou kružnici. Běžný je také název $S^1$.)

Formulace problému odhadu fáze

V problému odhadu fáze máme k dispozici kvantový stav $\vert \psi\rangle$ o $n$ qubitech spolu s unitárním kvantovým obvodem, který působí na $n$ qubitů. Máme příslib, že $\vert \psi\rangle$ je vlastní vektor unitární matice $U$, která popisuje činnost obvodu, a naším cílem je vypočítat nebo aproximovat vlastní číslo $\lambda$, kterému $\vert \psi\rangle$ odpovídá. Přesněji řečeno, protože $\lambda$ leží na komplexní jednotkové kružnici, můžeme zapsat

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

pro jedinečné reálné číslo $\theta$ splňující $0\leq\theta<1$. Cílem problému je vypočítat nebo aproximovat toto reálné číslo $\theta$.

Phase estimation problem

Vstup: Unitární kvantový obvod pro $n$-qubitovou operaci $U$ spolu s $n$-qubitovým kvantovým stavem $\vert\psi\rangle$
Příslib: $\vert\psi\rangle$ je vlastní vektor $U$
Výstup: aproximace čísla $\theta\in[0,1)$ splňujícího $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Zde je několik poznámek k této formulaci problému:

1. Problém odhadu fáze se od ostatních problémů, které jsme dosud v kurzu viděli, liší tím, že vstup zahrnuje kvantový stav. Typicky se zaměřujeme na problémy s klasickými vstupy a výstupy, ale nic nám nebrání uvažovat vstupy v podobě kvantových stavů, jako je tento. Z hlediska praktického významu se problém odhadu fáze typicky vyskytuje jako podproblém uvnitř většího výpočtu, jak uvidíme v kontextu faktorizace celých čísel později v této lekci.

2. Formulace problému odhadu fáze výše nespecifikuje, co přesně představuje aproximaci $\theta$, ale můžeme formulovat přesnější zadání v závislosti na našich potřebách a zájmech. V kontextu faktorizace celých čísel budeme požadovat velmi přesnou aproximaci $\theta$, ale v jiných případech nám může stačit i velmi hrubá aproximace. Brzy probereme, jak požadovaná přesnost ovlivňuje výpočetní náročnost řešení.

3. Všimni si, že při postupu od $\theta = 0$ k $\theta = 1$ v problému odhadu fáze procházíme celou jednotkovou kružnicí, přičemž začínáme od $e^{2\pi i \cdot 0} = 1$ a pohybujeme se proti směru hodinových ručiček k $e^{2\pi i \cdot 1} = 1$. To znamená, že když dosáhneme $\theta = 1$, jsme zpět tam, kde jsme začali, tedy u $\theta = 0$. Proto při posuzování přesnosti aproximací je třeba pohlížet na hodnoty $\theta$ blízké $1$ jako na hodnoty blízké $0$. Například aproximace $\theta = 0{,}999$ by měla být považována za ležící v rozmezí $1/1000$ od $\theta = 0$.