Estimation de phase quantique et algorithme HHL - connaissance des valeurs propres requise?

10

L' algorithme d'estimation de phase quantique (QPE) calcule une approximation de la valeur propre associée à un vecteur propre donnée d'une porte quantique .U

Formellement, laissez être un vecteur propre de U , EPQ permet de trouver | ~ & Thetav , la meilleure m approximation de bits de 2 m & thetav tel que & thetav [ 0 , 1 ) et U | ψ = e 2 π i & thetav | ψ .|ψU|θ~m2mθθ[0,1)

U|ψ=e2πiθ|ψ.

L' algorithme HHL ( papier original ) prend en entrée une matrice qui satisfait e i A t  est unitaire  et un état quantique | b et calcule | x qui code pour la solution du système linéaire A x = b .A

eiAt is unitary 
|b|xAx=b

Remarque : Chaque matrice hermitienne la condition sur statisfy .A

Pour ce faire, l'algorithme HHL utilise le QPE sur la porte quantique représentée par . Merci aux résultats d'algèbre linéaire, nous savons que si { λ j } j sont les valeurs propres de A alors { e i λ j t } j sont les valeurs propres de U . Ce résultat est également indiqué dans les algorithmes des systèmes linéaires quantiques: une amorce (Dervovic, Herbster, Mountney, Severini, Usher et Wossnig, 2018) (page 29, entre les équations 68 et 69).U=eiAt{λj}jA{eiλjt}jU

θ[0,1)ei2πθ=eiλjt

2πθ=λjt+2kπ,kZ, θ[0,1)
θ=λjt2π+k,kZ, θ[0,1)
kZθ[0,1)λjt2π[0,1)k0

AAλjt2π[0,1)

eiAt16A{1,2,4,8}λjt2π[0,1)

t

Aλjt2π[0,1)

Nelimee
la source
t=1k=2t=10<(λ/2π)+2<14π<λ<2πλ=3πλ/2π0
λθ[0,1)λ<0λλ2kπk=λ2πλ2π

Réponses:

6

Atλt2πANQ

maxiaii+ji|aij|NQ,
a i j A
miniaiiji|aij|NQ.
aijA

Dans les valeurs de , , si vous vous inquiétez que pour une grande matrice (disons qubits), alors que la somme des lignes peut être facile à calculer (car il n'y a pas beaucoup d'entrées), le maximum sur toutes les lignes peut prendre un certain temps temps (parce qu'il y a lignes), il y aura une variété de façons d'obtenir de bonnes approximations (par exemple l'échantillonnage ou en utilisant la connaissance de la structure du problème). Le pire des cas, vous pouvez probablement utiliser la recherche de Grover pour l'accélérer un peu.Q n 2 nNQn2n

DaftWullie
la source
1
Grover n'est pas une amélioration: même si nous pouvons utiliser l'algorithme, nous aurons toujours besoin de requêtes , qui détruisent l'amélioration exponentielle de HHL par rapport aux méthodes classiques et la remplacent par une accélération quadratique. Donc, le seul espoir qui reste est l'échantillonnage (introduire une autre source d'erreurs) ou prier et espérer que le problème nous permette d'estimer les limites supérieures / inférieures. Cela me semble être un défaut majeur de l'algorithme. O(N)
Nelimee
2
Bien sûr, je voulais seulement dire que Grover vous donne une accélération de racine carrée par rapport à la façon naïve d'obtenir le maximum. Bien sûr, cela a un mauvais impact sur le temps de fonctionnement global.
DaftWullie