Grovers Algorithmus: Ein reales Beispiel?

13

Ich bin ziemlich verwirrt darüber, wie der Algorithmus von Grover in der Praxis eingesetzt werden könnte, und möchte an einem Beispiel um Hilfe bei der Klärung bitten.

Angenommen, eine Element-Datenbank enthält die Farben Rot, Orange, Gelb, Grün, Cyan, Blau, Indigo und Violett und nicht unbedingt in dieser Reihenfolge. Mein Ziel ist es, Rot in der Datenbank zu finden. $N=8$

Die Eingabe für Grovers Algorithmus ist Qubits, wobei die 3 Qubits die Indizes des Datensatzes codieren. Meine Verwirrung kommt hierher (vielleicht verwirrt über die Prämissen, also sagen wir eher, dass hier Verwirrung herrscht), dass das Orakel meines Wissens tatsächlich nach einem der Indizes des Datensatzes sucht (dargestellt durch die Überlagerung der 3 Qubits). Das Orakel ist "fest codiert", nach welchem Index es suchen soll. $n = \log_2(N=8) = 3$

Meine Fragen sind:

Was mache ich hier falsch?
Wenn das Orakel wirklich nach einem der Indizes der Datenbank sucht, bedeutet dies, dass wir bereits wissen, nach welchem Index wir suchen. Warum also suchen?
Könnte jemand in Anbetracht der obigen Bedingungen für die Farben darauf hinweisen, ob es mit Grovers möglich ist, in einem unstrukturierten Datensatz nach Rot zu suchen?

Es gibt Implementierungen für Grover-Algorithmus mit einem Orakel für Suchen nach | 111>, zB (oder einer R - Implementierung des gleichen Orakels siehe unten): /quantum//a/2205 $n=3$

Da ich die Position von Elementen in einem Datensatz nicht kenne , muss ich nach einer Zeichenfolge suchen, die die Position von Elementen codiert . Woher weiß ich, nach welcher Position ich suchen soll, wenn der Datensatz unstrukturiert ist? $N$ $N$

R-Code:

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

grovers-algorithm 01000001
quelle

3

Mögliches Duplikat von Grovers Algorithmus: Wo ist die Liste?

DaftWullie

auch im Zusammenhang mit: quantumcomputing.stackexchange.com/q/175/55

glS

5

| x ⟩_{address} | 0 ⟩_{value} \to | x ⟩_{address} | load (x) \oplus 0 ⟩_{value} = | x ⟩_{address} | load (x) ⟩_{value} .

$|x\rangle_{\text{address}}|0\rangle_{\text{value}} \rightarrow |x\rangle_{\text{address}}|\textrm{load}(x)\oplus 0\rangle_{\text{value}} = |x\rangle_{\text{address}}|\textrm{load}(x)\rangle_{\text{value}}.$

H_{address}^{\otimes n} | 0 ⟩_{address} | 0 ⟩_{value} = \frac{1}{2^{n / 2}} \sum_{x = 0}^{2^{n} - 1} | x ⟩_{address} | 0 ⟩_{value}

$H^{\otimes n}_{\text{address}} |0\rangle_{\text{address}}|\textrm0\rangle_{\text{value}}=\frac1{2^{n/2}}\sum_{x=0}^{2^n-1} |x\rangle_{\text{address}}|\textrm0\rangle_{\text{value}}$

apply load \to \frac{1}{2^{n / 2}} \sum_{x = 0}^{2^{n} - 1} | x ⟩_{address} | load (x) ⟩_{value}

$\text{apply load}\rightarrow \frac1{2^{n/2}}\sum_{x=0}^{2^n-1} |x\rangle_{\text{address}}|\textrm{load}(x)\rangle_{\text{value}}$

O (\sqrt{N})

$O(\sqrt{N})$

x^{*}

$x^*$

| x^{*} ⟩_{address} | load (x^{*}) ⟩_{value} .

$|x^*\rangle_{\text{address}}|\textrm{load}(x^*)\rangle_{\text{value}}.$

Möglicherweise besteht das Hauptproblem darin, die Datenbank und nicht den Grover-Algorithmus zu verstehen. Eine ausführlichere Erklärung dazu finden Sie in Kapitel 6.5 Nielsen & Chuang.

Ich denke auch, dass die nützlichste Anwendung des Grover-Algorithmus nicht die Datenbankanwendung ist, sondern dessen Verallgemeinerungen als Amplitudenverstärkung (siehe https://arxiv.org/abs/quant-ph/0005055 ) für jeden Quantenalgorithmus.

$\neq$

Alex Go
quelle

\neq

$\neq$

\sum_{k} | k ⟩ \otimes | s_{k} ⟩

$\sum_k |k\rangle\otimes|s_k\rangle$

k

$k$

s_{k} = + 1

$s_k=+1$

s_{k}

$s_k$ .

glS

\neq

$\neq$

4

Dies wird in dieser verwandten Frage bereits teilweise erörtert , aber ich werde hier versuchen, einige der von Ihnen aufgeworfenen Probleme genauer zu behandeln.

| i ⟩ \mapsto (- 1)^{f (x_{i})} | i ⟩,

$|i\rangle\mapsto(-1)^{f(x_i)}|i\rangle,$

i

$i$

x_{i}

$x_i$

i

$i$

$f(x_i)$ $x_i$ $x_i$ $x_i$ $P$ $P$

$f$ $x_i$ $i$ $x_i$

$x_i=i$ $x_i$

In einem solchen Fall ist der Algorithmus zwar nicht besonders nützlich, da die Antwort im Orakel fest codiert werden muss, dies muss jedoch im Allgemeinen nicht der Fall sein.

glS
quelle

Danke für Ihre Antwort! Wäre es vielleicht möglich, ein Beispiel aus dem wirklichen Leben zu liefern, in dem der Grover "nützlich" ist, wenn er auf einige reale Daten angewendet wird, wenn das vorgestellte Orakel gegeben ist? ZB wie würde es mit einer Datenbank mit 8 Elementen mit Primzahlen und Nichtprimzahlen arbeiten?

01000001

1

f

$f$

f

$f$

x

$x$

Grovers Algorithmus: Ein reales Beispiel?

Antworten: