Algorithme quantique pour les systèmes linéaires d'équations (HHL09): Étape 1 - Confusion concernant l'utilisation de l'algorithme d'estimation de phase

Cela fait un certain temps que j'essaie de me familiariser avec le célèbre (?) Algorithme quantique papier pour les systèmes linéaires d'équations (Harrow, Hassidim et Lloyd, 2009) (plus connu sous le nom de papier algorithme HHL09 ).

À la toute première page, ils disent :

Nous esquissons ici l'idée de base de notre algorithme, puis en discutons plus en détail dans la section suivante. Étant donné un hermitienne la matrice , et une unité vecteur , supposons que nous aimerions trouver satisfaisant . (Nous discutons des questions ultérieures d'efficacité ainsi que de la façon dont les hypothèses que nous avons faites à propos de et peuvent être assouplies.) Premièrement, l'algorithme représente comme un état quantique . Ensuite, nous utilisons des techniques de simulation hamiltonienne [3, 4] pour appliquer àA → b → x A → x = → b A → b → b | b ⟩ = Σ N i = 1 b i | i ⟩ e i A t | b i$N\times N$$A$$\vec{b}$$\vec{x}$$A\vec{x} = \vec{b}$$A$$\vec{b}$$\vec{b}$$|b\rangle = \sum_{i=1}^{N}b_i|i\rangle$$e^{iAt}$$|b_i\rangle$pour une superposition de temps différents . Cette capacité d'exponentier traduit, via la technique bien connue d'estimation de phase [5–7], par la capacité de décomposer dans la base propre de et de trouver les valeurs propres correspondantes Informellement, l'état de la après cette étape, le système est proche de , où est la base du vecteur propre de et .A | b ⟩ A λ j Σ j = N j = 1 β j | u j ⟩ | λ j ⟩ u j A | b ⟩ = Σ j = N j = 1 β j | u j$t$$A$$|b\rangle$$A$$\lambda_j$$\sum_{j=1}^{j=N} \beta_j |u_j\rangle|\lambda_j\rangle$$u_j$$A$$|b\rangle = \sum_{j=1}^{j=N} \beta_j|u_j\rangle$

Jusqu'ici tout va bien. Comme décrit dans Nielsen & Chuang dans le chapitre " La transformée de Fourier quantique et ses applications ", l'algorithme d'estimation de phase est utilisé pour estimer dans qui est la valeur propre correspondant à un vecteur propre de l'opérateur unitaire .e i 2 π φ | u ⟩ $\varphi$$e^{i2\pi \varphi}$$|u\rangle$$U$

Voici la partie pertinente de Nielsen & Chuang:

L'algorithme d'estimation de phase utilise deux registres. Le premier registre contient qubits initialement dans l'état . La façon dont nous choisissons dépend de deux choses: le nombre de chiffres de précision que nous souhaitons avoir dans notre estimation pour , et avec quelle probabilité nous souhaitons que la procédure d'estimation de phase réussisse. La dépendance de à l' égard de ces quantités ressort naturellement de l'analyse suivante.| 0 ⟩ t φ $t$$|0\rangle$$t$$\varphi$$t$

Le deuxième registre commence dans l'état et contient autant de qubits que nécessaire pour stocker . L'estimation de phase est effectuée en deux étapes. Tout d'abord, nous appliquons le circuit illustré à la figure 5.2. Le circuit commence par l'application d'une transformée de Hadamard au premier registre, suivie par l'application d' opérations contrôlées - sur le deuxième registre, avec élevé à deux puissances successives. L'état final du premier registre est facilement visible:| u ⟩ U $|u\rangle$$|u\rangle$$U$$U$

$$\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)= \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}\text{exp}(2\pi i \varphi k)|k\rangle$$

La deuxième étape de l'estimation de phase consiste à appliquer la transformée de Fourier quantique inverse sur le premier registre. Ceci est obtenu en inversant le circuit de la transformée de Fourier quantique dans la section précédente (exercice 5.5) et peut être fait en étapes . La troisième et dernière étape de l'estimation de phase consiste à lire l'état du premier registre en effectuant une mesure sur la base du calcul. Nous montrerons que cela fournit une assez bonne estimation de . Un schéma général de l'algorithme est présenté à la figure 5.3.$\Theta (t^2)$$\varphi$

Pour affiner notre intuition quant au fonctionnement de l'estimation de phase, supposons que peut être exprimé exactement en bits, comme . Ensuite, l'état (5.20) résultant de la première étape d'estimation de phase peut être réécritφ = 0. φ 1 . . . φ $\varphi$$\varphi = 0.\varphi_1 ... \varphi_t$

$$\frac{1}{2^{t/2}}(|0\rangle + \exp(2\pi i 0.\varphi_t|1\rangle)(|0\rangle + \exp(2\pi i 0.\varphi_{t-1}\varphi_t|1\rangle)...(|0\rangle + \exp(2\pi i 0.\varphi_1...\varphi_t|1\rangle)$$

La deuxième étape de l'estimation de phase consiste à appliquer la transformée de Fourier quantique inverse. Mais en comparant l'équation précédente avec la forme du produit pour la transformée de Fourier, l'équation (5.4), nous voyons que l'état de sortie du deuxième étage est l'état du produit . Une mesure dans la base de calcul nous donne donc exactement !$|\varphi_1 ...\varphi_t\rangle$$\varphi$

En résumé, l'algorithme d'estimation de phase permet d'estimer la phase d'une valeur propre d'un opérateur unitaire , étant donné le vecteur propre correspondant . Une caractéristique essentielle au cœur de cette procédure est la capacité de la transformée de Fourier inverse à effectuer la transformation$\varphi$$U$$|u\rangle$

$$\frac{1}{2^{t/2}}\sum_{j = 0}^{2^t-1}\exp(2\pi i \varphi j)|j\rangle |u\rangle \to |\tilde \varphi \rangle |u\rangle$$

Continuons d'ici. J'ai trouvé un joli schéma de circuit pour l' algorithme HHL09 ici ^{[ ]$\dagger$} :

Étape 1 (estimation de phase):

Dans la première étape de l' algorithme HHL09, le même concept (de l'algorithme standard d'estimation de phase quantique tel que décrit dans Nielsen et Chuang) est utilisé. Cependant, nous devons garder à l'esprit que en soi n'est pas un opérateur unitaire. Cependant, si nous supposons que est hermitien, alors l'exponentielle est unitaire (pas de soucis, il existe une solution de contournement dans le cas où n'est pas hermitien!). $A$$A$$e^{iAt}$$A$

Ici, nous pouvons écrire . Il y a un autre point subtil impliqué ici. Nous ne connaissons pas au les vecteurs propres de (mais nous savons que pour toute matrice unitaire de taille il existe vecteurs propres orthonormés). De plus, nous devons nous rappeler que si les valeurs propres de sont alors les valeurs propres de seront . Si nous comparons cela avec la forme de valeurs propres donnée dans Nielsen et Chuang pour c'est-à-dire si $U=e^{iAt}$$|u_j\rangle$$U$$N\times N$$N$$A$$\lambda_j$$e^{iAt}$$e^{i \lambda_j t}$$U$$e^{2\pi i \varphi} \equiv e^{ i \lambda_j t}$, nous trouverions . Dans ce cas, nous commençons dans l'état (qui peut être écrit comme une superposition des vecteurs propres de ie ) plutôt que tout vecteur propre particulier de , en ce qui concerne le deuxième registre de qubits. Si nous avions commencé dans l'état nous nous serions retrouvés avec ie (considérant que$\varphi = \frac{\lambda_j t}{2\pi}$$|b\rangle$$U$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$|u_j\rangle$$U$$|u\rangle \otimes (|0\rangle)^{\otimes t}$$|u\rangle \otimes |\tilde\varphi\rangle$$|u_j\rangle \otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$$\lambda_j$est la valeur propre associée au vecteur propre de ). Maintenant, à la place, si nous commençons par la superposition de vecteurs propres nous devrions nous retrouver avec .$|u_j\rangle$$A$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Question:

Partie 1 : Dans l' article HHL09 , ils ont écrit sur l'état du système après cette étape d'estimation de phase: . Cependant, d'après ce que j'ai écrit ci-dessus, il me semble que l'état du système devrait plutôt être .$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde\lambda_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Qu'est-ce que j'oublie ici? Où le facteur disparu dans leur algorithme?$\frac{t}{2\pi}$

Edit: la partie 2 a été demandée ici pour rendre les questions individuelles plus ciblées.

^{J'ai également plusieurs confusions concernant les étapes 2 et 3 de l'algorithme HHL09, mais j'ai décidé de les publier en tant que fils de questions séparés, car celui-ci devient trop long. J'ajouterai les liens vers ces fils de questions, sur ce post, une fois qu'ils seront créés.}

[ ]: Expériences de chiffrement homomorphique sur la plate-forme informatique quantique en nuage d'IBM Huang et al. (2016)$\dagger$

Cela dépend des papiers mais j'ai vu 2 approches:

1. Dans la plupart des articles que j'ai lus sur l'algorithme HHL et sa mise en œuvre, le temps d'évolution hamiltonien est pris de telle sorte que ce facteur disparaisse, c'est-à-dire .$t$$t = t_0 = 2\pi$

2. La valeur propre approximative est souvent écrite . Dans certains articles, cette notation signifie vraiment «l'approximation de la vraie valeur propre » et dans d'autres articles, elle semble inclure dans cette définition, c'est-à-dire que « est l'approximation de la valeur de ".$\tilde \lambda$$\lambda$$\frac{t}{2\pi}$$\tilde \lambda$$\frac{\lambda t}{2\pi}$

Voici quelques liens:

1. Algorithmes de systèmes linéaires quantiques: une introduction (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) : un article complet et très bon sur l'algorithme HHL et quelques améliorations qui ont été découvertes. Le document date du 22 février 2018. La valeur de vous intéresse est d'abord abordée à la page 30, dans la légende de la figure 5 et est fixée à .$t$$2\pi$

2. Conception de circuits quantiques pour la résolution de systèmes linéaires d'équations (Cao, Daskin, Frankel et Kais, 2013) (prenez la v2 et non la v3): une implémentation détaillée de l'algorithme HHL pour une matrice 4x4 fixe. Si vous prévoyez d'utiliser l'article, permettez-moi de vous avertir qu'il contient des erreurs. Je peux vous fournir celles que j'ai trouvées si vous êtes intéressé. La valeur de (notée dans cet article) est fixée à dans la deuxième page (au début de la colonne de droite).$t$$t_0$$2\pi$

3. Expérimental Quantum Computing to Solve Systems of Linear Equations (Cai, Weedbrook, Su, Chen, Gu, Zhu, Li, Liu, Lu & Pan, 2013) : a implementation of HHL algorithm for a 2x2 matrix on a experimental setup. Ils fixent dans la légende de la figure 1.$t = 2\pi$

4. Réalisation expérimentale d'un algorithme quantique pour la résolution de systèmes linéaires d'équations (Pan, Cao, Yao, Li, Ju, Peng, Kais & Du, 2013) : mise en œuvre de HHL pour une matrice 2x2. L'implémentation est similaire à celle donnée au deuxième point ci-dessus, avec la matrice 4x4. Ils fixent en page 3, puce n ° 2.$t_0 = 2\pi$

Qu'est-ce que j'oublie ici? Où le facteur disparu dans leur algorithme?$\frac{t}{2\pi}$

N'oubliez pas qu'en notation Dirac, tout ce que vous écrivez à l'intérieur du ket est une étiquette arbitraire faisant référence à quelque chose de plus abstrait. Donc, il est vrai que vous trouvez le vecteur propre (approximatif) à , qui a la valeur propre et donc ce que vous extrayez est , mais c'est le même que le vecteur propre de avec valeur propre , et c'est ce qui est mentionné dans la notation. Mais si vous voulez être vraiment clair, vous pouvez l'écrire commee - i λ t λ t / ( 2 π ) A $U$$e^{-i\lambda t}$$\lambda t/(2\pi)$$A$$\lambda$

| vecteur propre approximatif de pour lequel la valeur propre est et de pour laquelle valeur propre si ,e - i λ t A λ $U$$e^{-i\lambda t}$$A$$\lambda\rangle$

mais peut-être qu'au lieu d'écrire cela à chaque fois, nous pourrions simplement écrire pour plus de brièveté!$|\tilde\lambda\rangle$