Problema estimării fazei

Această secțiune a lecției explică problema estimării fazei. Vom începe cu o scurtă discuție despre teorema spectrală din algebră liniară, apoi vom trece la enunțarea problemei estimării fazei în sine.

Teorema spectrală

Teorema spectrală este un rezultat important din algebră liniară care afirmă că matricele de un anumit tip, numite matrice normale, pot fi exprimate într-un mod simplu și util. Vom avea nevoie de această teoremă doar pentru matrice unitare în această lecție, dar mai departe în această serie o vom aplica și matricelor hermitice.

Matrice normale

O matrice pătrată $M$ cu intrări numere complexe se numește matrice normală dacă comută cu transpusa sa conjugată: $M M^{\dagger} = M^{\dagger} M.$

Orice matrice unitară $U$ este normală deoarece

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

Matricele hermitice, care sunt matrice egale cu propria lor transpusă conjugată, reprezintă o altă clasă importantă de matrice normale. Dacă $H$ este o matrice hermitică, atunci

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

deci $H$ este normală.

Nu orice matrice pătrată este normală. De exemplu, această matrice nu este normală:

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

(Acesta este un exemplu simplu, dar excelent de matrice care este adesea foarte util de luat în considerare.) Nu este normală deoarece

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

în timp ce

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

Enunțul teoremei

Iată acum un enunț al teoremei spectrale.

Teoremă

Teorema spectrală: Fie $M$ o matrice complexă normală de dimensiune $N\times N$. Există o bază ortonormată de vectori complexi $N$-dimensionali $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ împreună cu numerele complexe $\lambda_1,\ldots,\lambda_N$ astfel încât

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

Expresia unei matrice în forma

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

se numește în mod obișnuit descompunere spectrală. Observă că dacă $M$ este o matrice normală exprimată în forma $(1),$ atunci ecuația

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

trebuie să fie adevărată pentru orice $j = 1,\ldots,N.$ Aceasta este o consecință a faptului că $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ este ortonormată:

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

Cu alte cuvinte, fiecare număr $\lambda_j$ este o valoare proprie a lui $M$, iar $\vert\psi_j\rangle$ este un vector propriu corespunzător acelei valori proprii.

• Exemplul 1. Fie

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

  care este normală. Teorema implică faptul că $\mathbb{I}$ poate fi scrisă în forma $(1)$ pentru o anumită alegere a lui $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ și $\vert\psi_2\rangle.$ Există mai multe alegeri care funcționează, inclusiv

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

  Observă că teorema nu afirmă că numerele complexe $\lambda_1,\ldots,\lambda_N$ sunt distincte — același număr complex poate apărea repetat, ceea ce este necesar în acest exemplu. Aceste alegeri funcționează deoarece

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

  Într-adevăr, am putea alege $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ să fie orice bază ortonormată și ecuația va fi adevărată. De exemplu,

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

• Exemplul 2. Consideră o operație Hadamard.

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

  Aceasta este o matrice unitară, deci este normală. Teorema spectrală implică faptul că $H$ poate fi scrisă în forma $(1),$ și în particular avem

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

  unde

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

  Mai explicit,

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

  Putem verifica că această descompunere este corectă efectuând calculele necesare:

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

După cum relevă primul exemplu de mai sus, poate exista o anumită libertate în modul în care sunt aleși vectorii proprii. Nu există însă nicio libertate în modul în care sunt alese valorile proprii, cu excepția ordinii lor: aceleași $N$ numere complexe $\lambda_1,\ldots,\lambda_N,$ care pot include repetări ale aceluiași număr complex, vor apărea întotdeauna în ecuația $(1)$ pentru o alegere dată a matricei $M.$

Să ne concentrăm acum pe matricele unitare. Presupunem că avem un număr complex $\lambda$ și un vector nenul $\vert\psi\rangle$ care satisfac ecuația

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

Adică, $\lambda$ este o valoare proprie a lui $U$ și $\vert\psi\rangle$ este un vector propriu corespunzător acestei valori proprii.

Matricele unitare păstrează norma euclidiană, astfel că deducem următoarele din $(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\|$$

Condiția că $\vert\psi\rangle$ este nenul implică $\bigl\| \vert\psi\rangle \bigr\|\neq 0,$ deci putem elimina acest factor din ambii membri și obținem

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

Aceasta arată că valorile proprii ale matricelor unitare trebuie să aibă întotdeauna valoarea absolută egală cu unu, deci se află pe cercul unitate.

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

(Simbolul $\mathbb{T}$ este un nume uzual pentru cercul unitate complex. Numele $S^1$ este de asemenea frecvent utilizat.)

Enunțul problemei de estimare a fazei

În problema estimării fazei, ni se dă o stare cuantică $\vert \psi\rangle$ pe $n$ qubiți, împreună cu un circuit cuantic unitar care acționează pe $n$ qubiți. Se garantează că $\vert \psi\rangle$ este un vector propriu al matricei unitare $U$ care descrie acțiunea circuitului, iar scopul nostru este să calculăm sau să aproximăm valoarea proprie $\lambda$ căreia îi corespunde $\vert \psi\rangle.$ Mai precis, deoarece $\lambda$ se află pe cercul unitate complex, putem scrie

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

pentru un număr real unic $\theta$ care satisface $0\leq\theta<1.$ Scopul problemei este să calculăm sau să aproximăm acest număr real $\theta.$

Problema estimării fazei

Intrare: Un circuit cuantic unitar pentru o operație $U$ pe $n$ qubiți, împreună cu o stare cuantică $\vert\psi\rangle$ pe $n$ qubiți
Promisiune: $\vert\psi\rangle$ este un vector propriu al lui $U$
Ieșire: o aproximare a numărului $\theta\in[0,1)$ care satisface $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Iată câteva observații despre acest enunț al problemei:

1. Problema estimării fazei este diferită de alte probleme văzute până acum în curs prin faptul că intrarea include o stare cuantică. De obicei ne concentrăm pe probleme cu intrări și ieșiri clasice, dar nimic nu ne împiedică să luăm în considerare intrări sub formă de stări cuantice ca aceasta. Din perspectiva relevanței practice, problema estimării fazei este întâlnită de obicei ca o subproblemă în cadrul unui calcul mai mare, cum vom vedea în contextul factorizării numerelor întregi mai târziu în lecție.

2. Enunțul problemei de estimare a fazei de mai sus nu specifică ce constituie o aproximare a lui $\theta,$ dar putem formula enunțuri mai precise ale problemei în funcție de nevoile și interesele noastre. În contextul factorizării numerelor întregi, vom cere o aproximare foarte precisă a lui $\theta,$ dar în alte cazuri s-ar putea să fim mulțumiți cu o aproximare foarte grosieră. Vom discuta în scurt timp cum precizia necesară afectează costul computațional al unei soluții.

3. Observă că pe măsură ce trecem de la $\theta = 0$ spre $\theta = 1$ în problema estimării fazei, parcurgem întreg cercul unitate, pornind de la $e^{2\pi i \cdot 0} = 1$ și deplasându-ne în sens invers acelor de ceasornic spre $e^{2\pi i \cdot 1} = 1.$ Adică, atunci când ajungem la $\theta = 1$ ne aflăm din nou la punctul de plecare, $\theta = 0.$ Prin urmare, când evaluăm acuratețea aproximărilor, alegerile lui $\theta$ apropiate de $1$ trebuie considerate ca fiind apropiate de $0.$ De exemplu, o aproximare $\theta = 0.999$ trebuie considerată ca fiind la o distanță de $1/1000$ față de $\theta = 0.$