L'algorithme de Grover: un exemple réel?

13

Je suis assez confus quant à la façon dont l'algorithme de Grover pourrait être utilisé dans la pratique et je voudrais demander de l'aide sur la clarification à travers un exemple.

Supposons une base de données d'éléments qui contient des couleurs Rouge, Orange, Jaune, Vert, Cyan, Bleu, Indigo et Violet, et pas nécessairement dans cet ordre. Mon objectif est de trouver du rouge dans la base de données.N=8

L'entrée pour l'algorithme de Grover est qubits, où les 3 qubits codent les indices de l'ensemble de données. Ma confusion vient ici (peut être confondue à propos des prémisses alors disons plutôt que la confusion frappe ici) que, si je comprends bien, l'oracle recherche en fait l'un des indices de l'ensemble de données (représenté par la superposition des 3 qubits), et de plus, l'oracle est "codé en dur" pour quel index il doit rechercher.n=Journal2(N=8)=3

Mes questions sont:

  • Qu'est-ce que je me trompe ici?
  • Si l'oracle recherche vraiment l'un des indices de la base de données, cela signifie que nous savons déjà quel indice nous recherchons, alors pourquoi chercher?
  • Compte tenu des conditions ci-dessus avec les couleurs, quelqu'un pourrait-il indiquer s'il est possible avec Grover de rechercher le rouge dans un ensemble de données non structuré?

Il existe des implémentations pour l'algorithme de Grover avec un oracle pour recherchant | 111>, par exemple (ou voir une implémentation R du même oracle ci-dessous): /quantum//a/2205n=3Oracle pour 111

Encore une fois, ma confusion est, étant donné que je ne connais pas la position de éléments dans un ensemble de données, l'algorithme m'oblige à rechercher une chaîne qui code la position de N éléments. Comment savoir quelle position je dois rechercher lorsque l'ensemble de données n'est pas structuré?NN

Code R:

 #START
 a = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 # 1st CNOT
 a1= CNOT3_12(a)
 # 2nd composite
 # I x I x T1Gate
 b = TensorProd(TensorProd(I2,I2),T1Gate(I2)) 
 b1 = DotProduct(b,a1)
 c = CNOT3_02(b1)
 # 3rd composite
 # I x I x TGate
 d = TensorProd(TensorProd(I2,I2),TGate(I2))
 d1 = DotProduct(d,c)
 e = CNOT3_12(d1)
 # 4th composite
 # I x I x T1Gate
 f = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 f1 = DotProduct(f,e)
 g = CNOT3_02(f1)
 #5th composite
 # I x T x T
 h = TensorProd(TensorProd(I2,TGate(I2)),TGate(I2))
 h1 = DotProduct(h,g)
 i = CNOT3_01(h1)
 #6th composite
 j = TensorProd(TensorProd(I2,T1Gate(I2)),I2)
 j1 = DotProduct(j,i)
 k = CNOT3_01(j1)
 #7th composite
 l = TensorProd(TensorProd(TGate(I2),I2),I2)
 l1 = DotProduct(l,k)
 #8th composite
 n = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 n1 = DotProduct(n,l1)
 n2 = TensorProd(TensorProd(PauliX(I2),PauliX(I2)),PauliX(I2))
 a = DotProduct(n2,n1)
 #repeat the same from 2st not gate
 a1= CNOT3_12(a)
 # 2nd composite
 # I x I x T1Gate
 b = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 b1 = DotProduct(b,a1)
 c = CNOT3_02(b1)
 # 3rd composite
 # I x I x TGate
 d = TensorProd(TensorProd(I2,I2),TGate(I2))
 d1 = DotProduct(d,c)
 e = CNOT3_12(d1)
 # 4th composite
 # I x I x T1Gate
 f = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 f1 = DotProduct(f,e)
 g = CNOT3_02(f1)
 #5th composite
 # I x T x T
 h = TensorProd(TensorProd(I2,TGate(I2)),TGate(I2))
 h1 = DotProduct(h,g)
 i = CNOT3_01(h1)
 #6th composite
 j = TensorProd(TensorProd(I2,T1Gate(I2)),I2)
 j1 = DotProduct(j,i)
 k = CNOT3_01(j1)
 #7th composite
 l = TensorProd(TensorProd(TGate(I2),I2),I2)
 l1 = DotProduct(l,k)
 #8th composite
 n = TensorProd(TensorProd(PauliX(I2),PauliX(I2)),PauliX(I2))
 n1 = DotProduct(n,l1)
 n2 = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 n3 = DotProduct(n2,n1)
 result=measurement(n3)
 plotMeasurement(result)

Image2

01000001
la source
3
Duplicata possible de l'algorithme
DaftWullie

Réponses:

5

|Xadresse|0valeur|Xadresse|charge(X)0valeur=|Xadresse|charge(X)valeur.

Hadressen|0adresse|0valeur=12n/2X=02n-1|Xadresse|0valeur
appliquer la charge12n/2X=02n-1|Xadresse|charge(X)valeur
O(N)X
|Xadresse|charge(X)valeur.

Peut-être que le principal problème que vous rencontrez est de comprendre la base de données et non l'algorithme Grover. Vous pouvez voir une explication plus détaillée dans le chapitre 6.5 Nielsen & Chuang pour cela.

Je pense également que l'application la plus utile de l'algorithme Grover n'est pas l'application de base de données, mais ses généralisations comme amplification d'amplitude (voir https://arxiv.org/abs/quant-ph/0005055 ) sur n'importe quel algorithme quantique.

Alex Go
la source
k|k|skksk=+1sk.
glS
4

Ceci est déjà partiellement discuté dans cette question connexe , mais je vais essayer ici d'aborder plus spécifiquement certaines des questions que vous soulevez.

|je(-1)F(Xje)|je,
jeXjeje

F(Xje)XjeXjeXjePP

FXjejeXje

Xje=jeXje

Dans un tel cas, l'algorithme n'est en effet pas particulièrement utile dans la mesure où la réponse doit être codée en dur dans l'oracle, mais cela n'a pas besoin d'être le cas en général.

glS
la source
Merci pour votre réponse! Serait-il possible de fournir un exemple concret où le Grover est "utile" appliqué à certaines données réelles étant donné l'oracle présenté? Par exemple, comment cela fonctionnerait-il avec une base de données à 8 éléments avec des nombres premiers et non premiers?
01000001
1
FFX