Algorithme quantique pour les systèmes linéaires d'équations (HHL09): Étape 2 - Qu'est-ce que

9

Ceci est une suite de l' algorithme quantique pour les systèmes linéaires d'équations (HHL09): Étape 1 - Confusion concernant l'utilisation de l'algorithme d'estimation de phase et de l' algorithme quantique pour les systèmes linéaires d'équations (HHL09): Étape 1 - Nombre de qubits nécessaires .


Dans l'article: Algorithme quantique pour les systèmes linéaires d'équations (Harrow, Hassidim & Lloyd, 2009) , ce qui est écrit dans la partie

La prochaine étape consiste à décomposer |b dans la base de vecteurs propres, en utilisant l' estimation de phase [5-7]. Notons par les vecteurs propres de (ou de manière équivalente, de ), et par les valeurs propres correspondantes.|ujAeiAtλj

à la page 2 un certain sens pour moi (les confusions jusque-là ont été abordées dans les messages précédents liés ci-dessus). Cependant, la partie suivante, à savoir la rotation R(λ1) semble un peu cryptique.

Soit

|Ψ0:=2Tτ=0T1sinπ(τ+12)T|τ

pour un grand . Les coefficients de sont choisis (après [5-7]) pour minimiser une certaine fonction de perte quadratique qui apparaît dans notre analyse d'erreur (voir [13] pour plus de détails).T|Ψ0

Ensuite, nous appliquons l'évolution Hamiltonienne conditionnelle sur , où . | Ψ 0 C| b t 0 = O ( κ / ε )τ=0T1|ττ|CeiAτt0/T|Ψ0C|bt0=O(κ/ϵ)

Des questions:

1. Qu'est-ce que c'est exactement |Ψ0 ? Que représentent T et τ ? Je n'ai aucune idée d'où cette expression gigantesque

2Tτ=0T1sinπ(τ+12)T|τ
vient soudainement et ce que son utilisation est.

2. Après l'étape d'estimation de phase, l'état de notre système est apparemment :

(j=1j=Nβj|uj|λ~j)|0ancilla

Ce sûrement ne peut pas être écrit -à- dire

(j=1j=Nβj|uj)(j=1j=N|λ~j)|0ancilla

|b(j=1j=N|λ~j)|0ancilla

Il est donc clair que ne sont pas disponibles séparément dans le second registre. Je n'ai donc aucune idée de comment ils préparent un état comme | Ψ 0 C| b en premier lieu! De plus, qu'est-ce que ce C en exposant de | Ψ 0 C représentent?|b|Ψ0C|bC|Ψ0C

3. D'où vient cette expression apparaissent soudainement de? Quelle est l'utilité de la simuler? Et qu'est-ce que κ dans O ( κ / ϵ ) ?τ=0T1|ττ|CeiAτt0/TκO(κ/ϵ)

Sanchayan Dutta
la source

Réponses:

5

1. Définitions

Les noms et symboles utilisés dans cette réponse suivent ceux définis dans les algorithmes des systèmes linéaires quantiques: une amorce (Dervovic, Herbster, Mountney, Severini, Usher et Wossnig, 2018) . Un rappel est effectué ci-dessous.

1.1 Enregistrer les noms

Les noms de registre sont définis dans la figure 5 des algorithmes de systèmes linéaires quantiques: une amorce (Dervovic, Herbster, Mountney, Severini, Usher et Wossnig, 2018) (reproduit ci-dessous):

  • (1 qubit) est le registre ancilla utilisé pour vérifier si la sortie est valide ou non.S
  • ( n qubits) est le registre d'horloge, c'est-à-dire le registre utilisé pour estimer les valeurs propres de l'hamiltonien avec estimation de phase quantique (QPE).Cn
  • ( m qubits) est le registre stockant le côté droit de l'équation A x = b . Il stocke x , le résultat de l'équation, lorsque S est mesuré pour être | 1 à la fin de l'algorithme.ImAx=bxS|1

Algorithme HHL

2. À propos :|Ψ0

  1. Qu'est-ce que c'est exactement ?|Ψ0

    est un état initial possible du registre d'horlogeC.|Ψ0C

  2. Que représentent et τ ?Tτ

    représente un grand entier positif. Ce T doit être aussi grand que possible car l'expression de | Ψ 0 asymptotiquement minimiser une erreur donnée pour T croissante àinfini. Dans l'expression de | Ψ 0 , T sera 2 n , le nombre d'états possibles pour l'horloge quantique C .TT|Ψ0T|Ψ0T2nC

    est juste l'indice de sommationτ

  3. Pourquoi une expression si gigantesque pour ?|Ψ0

    Voir le post de DaftWullie pour une explication détaillée.

    En suivant les citations de l' algorithme Quantum pour les systèmes linéaires d'équations (Harrow, Hassidim & Lloyd, 2009 v3), nous nous retrouvons avec:

    1. La version précédente du même article Quantum algorithm for linear systems of equations (Harrow, Hassidim & Lloyd, 2009 v2) . Les auteurs ont révisé le document 2 fois (il existe 3 versions du document HHL original) et la version n ° 3 n'inclut pas toutes les informations fournies dans les versions précédentes. Dans la V2 (section A.3. À partir de la page 17), les auteurs fournissent une analyse détaillée de l'erreur avec cet état initial spécial.
    2. Horloges quantiques optimales (Buzek, Derka, Massar, 1998) où l'expression de est donnée comme | Ψ o p t dans l' équation 10. Je n'ai pas les connaissances nécessaires pour comprendre cette partie, mais il semble que cette expression est « optimale » dans un certain sens.|Ψ0|Ψopt

3. Préparation de :|Ψ0

Comme indiqué dans la partie précédente, est un état initial. Ils ne se préparent pas | Ψ 0 après la procédure d'estimation de phase. L'ordre des phrases n'est pas vraiment optimal dans le papier. La procédure d'estimation de phase qu'ils utilisent dans l'article est un peu différente de l'algorithme d'estimation de phase "classique" représenté dans le circuit quantique lié dans la partie 1, et c'est pourquoi ils l'expliquent en détail.|Ψ0|Ψ0

Leur algorithme d'estimation de phase est:

  1. Préparez le état dans le registre C .|Ψ0C
  2. Appliquer l'évolution hamiltonien conditionnelle aux registres et I (qui sont dans l'état | Ψ 0 | b ).CI|Ψ0|b
  3. Appliquez la transformée de Fourier quantique à l'état résultant.

Enfin, le dans | Ψ 0 C signifie que l'état | Ψ 0 est stocké dans le registre C . Il s'agit d'une notation courte et pratique pour garder une trace des registres utilisés.C|Ψ0C|Ψ0C

4. Simulation hamiltonienne:

Tout d' abord, est le numéro de la condition ( la page Wikipedia sur « Numéro d'état » ) de la matrice A .κA

est la représentation mathématique d'une porte quantique.τ=0T1|ττ|CeiAτt0/T

La première partie de la somme est une partie de contrôle. Cela signifie que l'opération sera contrôlée par l'état du premier registre quantique (le registre C comme nous le dit l'exposant).|ττ|CC

La deuxième partie est la porte « de simulation hamiltonien », à savoir une grille de quantum qui applique la matrice unitaire donnée par pour le second registre (le registre I qui est à l'état initial | b ).eiAτt0/TI|b

La somme totale est la représentation mathématique de l'opération de U contrôlée dans le circuit de quantum de « 1. Définitions », avec .U=eiAτt0/T

Nelimee
la source
3

En réponse à votre première question, je me suis écrit quelques notes il y a quelque temps sur ma compréhension du fonctionnement. La notation est probablement un peu différente (j'ai essayé de l'aligner davantage, mais il est facile de manquer des bits), mais tente d'expliquer ce choix de l'état . Il semble également y avoir des facteurs de 1|Ψ0 flottant par endroits.12

Lorsque nous étudions pour la première fois l'estimation de phase, nous y pensons généralement en ce qui concerne l'utilisation dans un algorithme particulier, tel que l'algorithme de Shor. Cela a un objectif spécifique: obtenir la meilleure approximation en bits de la valeur propre. Soit vous le faites, soit vous ne le faites pas, et la description de l'estimation de phase est spécifiquement réglée pour donner une probabilité de réussite aussi élevée que possible.t

Dans HHL, nous essayons de produire un état | b=Σjβj| λj, en utilisantestimation de phase. La précision de l'approximation dépendra de façon beaucoup plus critique d'une estimation précise des valeurs propres proches de 0 plutôt que de celles qui sont loin de 0. Une étape évidente consiste donc à tenter de modifier le protocole d'estimation de phase de manière à ce que que d'utiliser des «bacs» de largeur fixe2π/Tpour approximer les phases dee-iAt(T=

|ϕ=jβjλj|λj,
|b=jβj|λj2π/TeiAt et t est le nombre de qubits dans le registre d'estimation de phase), nous pourrions plutôt spécifier un ensemble de ϕ y pour y { 0 , 1 } t pour agir comme le centre de chaque bin afin que nous puissions avoir une précision considérablement accrue proche de Phase 0. Plus généralement, vous pouvez spécifier une fonction de compromis pour la tolérance que vous pourriez avoir à l'égard des erreurs en fonction de la phase ϕT=2ttϕyy{0,1}tϕ. La nature précise de cette fonction peut ensuite être ajustée à une application donnée, et le facteur de mérite particulier que vous utiliserez pour déterminer le succès. Dans le cas de l'algorithme de Shor, notre valeur de mérite était simplement ce protocole de binning - nous avons réussi si la réponse était dans le bon bin, et sans succès en dehors. Ce ne sera pas le cas dans HHL, dont le succès est plus raisonnablement capturé par une mesure continue telle que la fidélité. Ainsi, pour le cas général, nous désignerons une fonction de coût qui spécifie une pénalité pour les réponses ϕ si la vraie phase est ϕ .C(ϕ,ϕ)ϕϕ

Rappelons que le protocole standard d'estimation de phase a fonctionné en produisant un état d'entrée qui était la superposition uniforme de tous les états de base pour x { 0 , 1 } t . Cet état a été utilisé pour contrôler l'application séquentielle de multiples portes U contrôlées , qui sont suivies d'une transformée de Fourier inverse. Imaginez que nous pourrions remplacer l'état d'entrée par un autre état | Ψ 0 = Σ x { 0 , 1 } t α x | x ,|xx{0,1}tU

|Ψ0=x{0,1}tαx|x,
puis le reste du protocole pourrait fonctionner comme avant. Pour l'instant, nous ignorerons la question de la difficulté de produire le nouvel état , comme nous juste essayer de transmettre le concept de base. À partir de cet état, l'utilisation des portes U contrôlées (ciblant un vecteur propre de U de valeur propre ϕ ), produit l'état x { 0 , 1 } t α x e i ϕ x | x . L'application de la transformée de Fourier inverse donne 1|Ψ0UUϕ
x{0,1}tαxeiϕx|x.
1Tx,y{0,1}teix(ϕ2πyM)αx|y.
yϕ=2πy/T
1T|x{0,1}teix(ϕ2πyT)αx|2
ϕ
C¯=12πT02πdϕy{0,1}t|x{0,1}teix(ϕ2πyT)αx|2C(ϕ,2πy/T),
and our task is to select the amplitudes αx that minimise this for any specific realisation of C(ϕ,ϕ). If we make the simplifying assumption that C(ϕ,ϕ) is only a function of ϕϕ, then we can make a change of variable in the integration to give
C¯=12π02πdϕ|x{0,1}teixϕαx|2C(ϕ),
As we noted, the most useful measure is likely to be a fidelity measure. Consider we have a state |+ and we wish to implement the unitary Uϕ=|00|+eiϕ|11|, but instead we implement Uϕ=|00|+eiϕ|11|. The fidelity measures how well this achieves the desired task,
F=|+|UϕU|+|2=cos2(ϕϕ2),
so we take
C(ϕϕ)=sin2(ϕϕ2),
since in the ideal case F=1, so the error, which is what we want to minimise, can be taken as 1F. This will certainly be the correct function for evaluating any Ut, but for the more general task of modifying the amplitudes, not just the phases, the effects of inaccuracies propagate through the protocol in a less trivial manner, so it is difficult to prove optimality, although the function C(ϕϕ) will already provide some improvement over the uniform superposition of states. Proceeding with this form, we have
C¯=12π02πdϕ|x{0,1}teixϕαx|2sin2(12ϕ),
The integral over ϕ can now be performed, so we want to minimise the function
12x,y=0T1αxαy(δx,y12δx,y112δx,y+1).
This can be succinctly expressed as
minΨ0|H|Ψ0
where
H=12x,y=0T1(δx,y12δx,y112δx,y+1)|xy|.
The optimal choice of |Ψ0 is the minimum eigenvector of the matrix H,
αx=2T+1sin((x+1)πT+1),
and C¯ is the minimum eigenvalue
C¯=1212cos(πT+1).
Crucially, for large T, C¯ scales as 1/T2 rather than the 1/T that we would have got from the uniform coupling choice αx=1/T. This yields a significant benefit for the error analysis.

If you want to get the same |Ψ0 as reported in the HHL paper, I believe you have to add the terms 14(|0T1|+|T10|) to the Hamiltonian. I have no justification for doing so, however, but this is probably my failing.

DaftWullie
la source