Algorytm Grovera: przykład z prawdziwego życia?

13

Jestem dość zdezorientowany, w jaki sposób algorytm Grovera może być wykorzystywany w praktyce i chciałbym prosić o pomoc w wyjaśnieniu na przykładzie.

Załóżmy, że baza danych elementów zawiera kolory: czerwony, pomarańczowy, żółty, zielony, cyjan, niebieski, indygo i fioletowy i niekoniecznie w tej kolejności. Moim celem jest znalezienie Reda w bazie danych.N=8

Dane wejściowe dla algorytmu Grovera to kubity, przy czym 3 kubity kodują wskaźniki zestawu danych. Moje zamieszanie przychodzi tutaj (może być mylone co do przesłanek, więc powiedzmy, że dochodzi tu do zamieszania), że, jak rozumiem, wyrocznia faktycznie szuka jednego z wskaźników zbioru danych (reprezentowanego przez superpozycję 3 kubitów), a ponadto wyrocznia jest „zakodowana na stałe”, dla którego indeksu powinna szukać.n=log2(N=8)=3

Moje pytania to:

  • Co się tutaj mylę?
  • Jeśli wyrocznia naprawdę szuka jednego z indeksów bazy danych, oznaczałoby to, że już wiemy, którego indeksu szukamy, więc po co szukać?
  • Biorąc pod uwagę powyższe warunki związane z kolorami, czy ktoś mógłby wskazać, czy Grover może poszukać Czerwonego w nieustrukturyzowanym zbiorze danych?

Istnieją implementacje algorytmu Grovera z wyrocznią dla szukającą | 111>, np. (Lub zobacz implementację R tej samej wyroczni poniżej): /quantum//a/2205n=3Oracle dla 111

Ponownie moje zamieszanie polega na tym, że biorąc pod uwagę, że nie znam pozycji elementów w zbiorze danych, algorytm wymaga ode mnie wyszukania ciągu, który koduje pozycję N elementów. Skąd mam wiedzieć, której pozycji powinienem szukać, gdy zbiór danych jest nieustrukturyzowany?NN

Kod 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)

Zdjęcie 2

01000001
źródło
3
Możliwy duplikat algorytmu Grovera: gdzie jest lista?
DaftWullie
powiązane również z: quantumcomputing.stackexchange.com/q/175/55
glS

Odpowiedzi:

5

|xaddress|0value|xaddress|load(x)0value=|xaddress|load(x)value.

Haddressn|0address|0value=12n/2x=02n1|xaddress|0value
apply load12n/2x=02n1|xaddress|load(x)value
O(N)x
|xaddress|load(x)value.

Być może głównym problemem jest zrozumienie bazy danych, a nie algorytmu Grovera. Bardziej szczegółowe wyjaśnienie można znaleźć w rozdziale 6.5 Nielsen i Chuang.

Myślę też, że najbardziej użyteczną aplikacją algorytmu Grovera nie jest aplikacja bazy danych, ale jej uogólnienie jako wzmocnienie amplitudy (patrz https://arxiv.org/abs/quant-ph/0005055 ) na dowolnym algorytmie kwantowym.

Alex Go
źródło
k|k|skksk=+1sk.
glS
4

Jest to już częściowo omówione w tym powiązanym pytaniu , ale postaram się tutaj rozwiązać bardziej szczegółowo niektóre z poruszanych przez ciebie problemów.

|i(1)f(xi)|i,
ixii

f(xi)xixixiPP

fxiixi

xi=ixi

W takim przypadku algorytm rzeczywiście nie jest szczególnie przydatny, ponieważ odpowiedź musi być zakodowana w wyroczni, ale nie musi tak być w ogóle.

glS
źródło
Dziękuję za odpowiedź! Być może byłoby możliwe podanie prawdziwego przykładu, w którym Grover jest „przydatny” w odniesieniu do niektórych rzeczywistych danych, biorąc pod uwagę prezentowaną wyrocznię? Np. Jak miałby działać z 8-elementową bazą danych z liczbami pierwszymi i niepierwszymi?
01000001
1
ffx