Le problème d'estimation de phase

Cette section de la leçon explique le problème d'estimation de phase. Nous commencerons par une brève discussion du théorème spectral de l'algèbre linéaire, puis nous passerons à l'énoncé du problème d'estimation de phase lui-même.

Théorème spectral

Le théorème spectral est un fait important de l'algèbre linéaire qui stipule que les matrices d'un certain type, appelées matrices normales, peuvent être exprimées d'une manière simple et utile. Nous n'aurons besoin de ce théorème que pour les matrices unitaires dans cette leçon, mais plus loin dans cette série nous l'appliquerons également aux matrices hermitiennes.

Matrices normales

Une matrice carrée $M$ à coefficients complexes est dite matrice normale si elle commute avec sa transposée conjuguée : $M M^{\dagger} = M^{\dagger} M.$

Toute matrice unitaire $U$ est normale car

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

Les matrices hermitiennes, qui sont des matrices égales à leur propre transposée conjuguée, sont une autre classe importante de matrices normales. Si $H$ est une matrice hermitienne, alors

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

donc $H$ est normale.

Toutes les matrices carrées ne sont pas normales. Par exemple, cette matrice n'est pas normale :

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

(C'est un exemple simple mais excellent de matrice qu'il est souvent très utile de considérer.) Elle n'est pas normale car

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

tandis que

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

Énoncé du théorème

Voici maintenant un énoncé du théorème spectral.

Théorème

Théorème spectral : Soit $M$ une matrice complexe normale $N\times N$. Il existe une base orthonormée de vecteurs complexes à $N$ dimensions $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ ainsi que des nombres complexes $\lambda_1,\ldots,\lambda_N$ tels que

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

L'expression d'une matrice sous la forme

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

est communément appelée décomposition spectrale. Remarque : si $M$ est une matrice normale exprimée sous la forme $(1)$, alors l'équation

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

doit être vraie pour chaque $j = 1,\ldots,N$. C'est une conséquence du fait que $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ est orthonormée :

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

Autrement dit, chaque nombre $\lambda_j$ est une valeur propre de $M$ et $\vert\psi_j\rangle$ est un vecteur propre correspondant à cette valeur propre.

• Exemple 1. Soit

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

  qui est normale. Le théorème implique que $\mathbb{I}$ peut être écrit sous la forme $(1)$ pour un certain choix de $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ et $\vert\psi_2\rangle.$ Il existe plusieurs choix qui fonctionnent, notamment

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

  Remarque : le théorème ne dit pas que les nombres complexes $\lambda_1,\ldots,\lambda_N$ sont distincts — on peut avoir le même nombre complexe répété, ce qui est nécessaire pour cet exemple. Ces choix fonctionnent parce que

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

  En effet, on pourrait choisir $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ comme n'importe quelle base orthonormée et l'équation sera vraie. Par exemple,

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

• Exemple 2. Considère une opération de Hadamard.

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

  Il s'agit d'une matrice unitaire, donc elle est normale. Le théorème spectral implique que $H$ peut être écrit sous la forme $(1)$, et en particulier nous avons

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

  où

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

  Plus explicitement,

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

  On peut vérifier que cette décomposition est correcte en effectuant les calculs requis :

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

Comme le révèle le premier exemple ci-dessus, il peut y avoir une certaine liberté dans le choix des vecteurs propres. Il n'y a cependant aucune liberté dans le choix des valeurs propres, à l'ordre près : les mêmes $N$ nombres complexes $\lambda_1,\ldots,\lambda_N$, qui peuvent inclure des répétitions du même nombre complexe, apparaîtront toujours dans l'équation $(1)$ pour un choix donné d'une matrice $M$.

Concentrons-nous maintenant sur les matrices unitaires. Supposons que nous ayons un nombre complexe $\lambda$ et un vecteur non nul $\vert\psi\rangle$ satisfaisant l'équation

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

Autrement dit, $\lambda$ est une valeur propre de $U$ et $\vert\psi\rangle$ est un vecteur propre correspondant à cette valeur propre.

Les matrices unitaires préservent la norme euclidienne, et nous concluons donc ce qui suit à partir de $(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\|$$

Comme $\vert\psi\rangle$ est non nul, on a $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, donc on peut simplifier par cette norme des deux côtés pour obtenir

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

Cela révèle que les valeurs propres des matrices unitaires doivent toujours avoir une valeur absolue égale à un, donc elles se trouvent sur le cercle unité.

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

(Le symbole $\mathbb{T}$ est un nom courant pour le cercle unité complexe. Le nom $S^1$ est également courant.)

Énoncé du problème d'estimation de phase

Dans le problème d'estimation de phase, on nous donne un état quantique $\vert \psi\rangle$ de $n$ qubits, ainsi qu'un circuit quantique unitaire agissant sur $n$ qubits. On nous promet que $\vert \psi\rangle$ est un vecteur propre de la matrice unitaire $U$ décrivant l'action du circuit, et notre objectif est de calculer ou d'approximer la valeur propre $\lambda$ à laquelle $\vert \psi\rangle$ correspond. Plus précisément, comme $\lambda$ se trouve sur le cercle unité complexe, on peut écrire

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

pour un unique nombre réel $\theta$ satisfaisant $0\leq\theta<1$. L'objectif du problème est de calculer ou d'approximer ce nombre réel $\theta$.

Problème d'estimation de phase

Entrée : Un circuit quantique unitaire pour une opération $U$ à $n$ qubits ainsi qu'un état quantique à $n$ qubits $\vert\psi\rangle$
Promesse : $\vert\psi\rangle$ est un vecteur propre de $U$
Sortie : une approximation du nombre $\theta\in[0,1)$ satisfaisant $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Voici quelques remarques sur cet énoncé du problème :

1. Le problème d'estimation de phase diffère des autres problèmes que nous avons vus jusqu'à présent dans le cours en ce que l'entrée comprend un état quantique. En général, nous nous intéressons à des problèmes dont les entrées et les sorties sont classiques, mais rien ne nous empêche de considérer des entrées d'état quantique comme celle-ci. En termes de pertinence pratique, le problème d'estimation de phase est généralement rencontré comme un sous-problème à l'intérieur d'un calcul plus grand, comme nous le verrons dans le contexte de la factorisation d'entiers plus tard dans la leçon.

2. L'énoncé du problème d'estimation de phase ci-dessus n'est pas précis sur ce qui constitue une approximation de $\theta$, mais nous pouvons formuler des énoncés de problème plus précis selon nos besoins et intérêts. Dans le contexte de la factorisation d'entiers, nous demanderons une approximation très précise de $\theta$, mais dans d'autres cas une approximation très grossière pourrait nous suffire. Nous discuterons bientôt de la façon dont la précision que nous exigeons affecte le coût de calcul d'une solution.

3. Remarque : lorsque nous allons de $\theta = 0$ vers $\theta = 1$ dans le problème d'estimation de phase, nous faisons le tour complet du cercle unité, en commençant de $e^{2\pi i \cdot 0} = 1$ et en nous déplaçant dans le sens inverse des aiguilles d'une montre vers $e^{2\pi i \cdot 1} = 1$. Autrement dit, quand nous atteignons $\theta = 1$ nous sommes de retour où nous avons commencé à $\theta = 0$. Donc, lorsque nous considérons la précision des approximations, les valeurs de $\theta$ proches de $1$ doivent être considérées comme étant proches de $0$. Par exemple, une approximation $\theta = 0.999$ doit être considérée comme étant à moins de $1/1000$ de $\theta = 0$.