Können wir den Grover-Algorithmus beschleunigen, indem wir parallele Prozesse ausführen?

Beim klassischen Rechnen können wir die Schlüsselsuche (z. B. AES) ausführen, indem wir so viele parallele Rechenknoten wie möglich ausführen.

Es ist klar, dass wir auch viele Grover-Algorithmen ausführen können.

Meine Frage ist ; Ist es möglich, mit mehr als einem Grover-Algorithmus wie beim klassischen Computing schneller zu werden?

classical-computing grovers-algorithm cryptography Kelalaka
quelle

Antworten:

Bestimmt! Stellen Sie sich vor, Sie haben Kopien des , die Sie verwenden können. Normalerweise würden Sie suchen, indem Sie die Aktion ausgehend von einem Anfangszustand . Dies dauert Zeit . (Ich benutze , um die Identitätsmatrix zu bezeichnen.) $K=2^k$ $U_S$

H^{\otimes n} (I_{n} - 2 | 0 ⟩ ⟨ 0 |^{\otimes n}) H^{\otimes n} U_{S},

$H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S,$

(H | 0 ⟩)^{\otimes n}

$(H|0\rangle)^{\otimes n}$

Θ (\sqrt{N})

$\Theta(\sqrt{N})$

I_{n}

$\mathbb{I}_n$

2^{n} \times 2^{n}

$2^n\times 2^n$

Sie können dies durch parallele Kopien ersetzen , die jeweils durch ein indiziert sind , indem Sie und ausgehend von einem Zustand Die zum Ausführen dieser Zeit erforderliche Zeit würde auf reduziert) auf Kosten des mal mehr Platzbedarfs. $2^k$ $x\in\{0,1\}^k$

(I_{k} \otimes H^{\otimes (n - k)}) I_{k} \otimes (I_{n - k} - 2 | 0 ⟩ ⟨ 0 |^{\otimes (n - k)}) (I_{k} \otimes H^{\otimes (n - k)}) U_{S}

$\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)\mathbb{I}_k\otimes(\mathbb{I}_{n-k}-2|0\rangle\langle 0|^{\otimes (n-k)})\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)U_S$

| x ⟩ (H | 0 ⟩)^{\otimes (n - k)}

$|x\rangle(H|0\rangle)^{\otimes(n-k)}$

O (\sqrt{N / K})

$O(\sqrt{N/K})$

K

$K$

In einem skalierenden Sinne könnte man dies als irrelevantes Ergebnis betrachten. Wenn Sie eine feste Anzahl von Orakeln haben, , dann erhalten Sie eine feste ( ) Verbesserung (genau wie wenn Sie parallele klassische Kerne haben, ist die beste Verbesserung, die Sie erhalten können, ein Faktor von ) und das ändert nichts an der Skalierung. Aber es ändert die grundlegende Laufzeit. Wir wissen, dass der Grover-Algorithmus genau optimal ist. Es dauert die absolut minimale Zeit, die mit einem einzelnen Orakel möglich ist. Das Wissen, dass Sie eine -Zeitverbesserung erhalten, ist im Hinblick auf diesen Benchmark einer bestimmten Laufzeit bei einem bestimmten Wert von hilfreich . $K$ $\sqrt{K}$ $K$ $K$ $\sqrt{K}$ $N$

DaftWullie
quelle

Aber wenn Sie dies tun, verliert der Vergleich mit der klassischen Aufführung etwas an Bedeutung, nicht wahr? Schließlich können Sie die klassische Suche auch beschleunigen, indem Sie die Operation ausführen, die prüft, ob ein bestimmtes das Ziel parallel über alle Eingaben ist. Dies erfordert eindeutig zusätzliche Annahmen über die verfügbaren Ressourcen, aber die gleichen Annahmen, die in Ihrem Argument getroffen werden

x

$x$

glS

N

$N$ geht ins Unendliche, aber nicht. Ihr Problem wird größer, aber Ihre Ressourcen bleiben gering.

K

$K$

AHusain

Diese Antwort ist richtig (obwohl sie möglicherweise nicht optimal ist, wie DaftWullie warnt). Dies ist die gleiche Einstellung zur Parallelisierung wie bei der klassischen Schaltungskomplexität. Wenn Sie eine Beschleunigung aufgrund von Parallelisierung wünschen, achten Sie auf die Schaltungstiefe (da die Koordination mehrerer Prozesse die Gesamtarbeit nicht verringert ). Es spielt nicht einmal eine Rolle, ob konstant ist - entweder sind Sie an der Tiefenverbesserung durch Parallelisierung interessiert oder nicht. Wie bei der Quantenberechnung selbst macht es nicht alles auf magische Weise schnell, mehr Computer auf ein Problem zu werfen!

K

$K$

Niel de Beaudrap

In gewisser Weise würden Sie Zeit für die Ausführung sparen, wenn wir dies parallel auf verschiedenen Knoten tun würden. Wenn wir jedoch über Komplexität sprechen (das ist es, was wir allgemein als Beschleunigung bezeichnen), brauchen wir ein wenig Analyse.

Sie stimmen zu, dass wir für den nicht parallelen Fall ungefähr benötigen . Angenommen, wir haben zwei Knoten und trennen die Liste der N Elemente in zwei Listen der Größe . Die Suche in den Unterlisten dauert ungefähr . $\sqrt{N}$ $N_1,N_2$ $\sqrt{N_1},\sqrt{N_2}$

Wir haben jedoch das

\sqrt{N} = \sqrt{N_{1} + N_{2}} \leq \sqrt{N_{1}} + \sqrt{N_{2}}

$\sqrt{N} = \sqrt{N_1+N_2} \le \sqrt{N_1} + \sqrt{N_2}$

Und Sie müssten immer noch überprüfen, welche Ausgabe unter den von den parallelen Prozessen zurückgegebenen die gewünschte ist. Es fügt der Komplexität eine Konstante hinzu, sodass wir sie im Allgemeinen in der Notation verbergen . $O$

Dies wäre jedoch immer noch interessant, insbesondere wenn wir Hardware gruppieren müssen, da die Anzahl der Qubits oder andere Einschränkungen begrenzt sind.

cnada
quelle

Für N1 = N2 ist es immer noch eine Ungleichung: sqrt (2) * sqrt (N1) <2 * sqrt (N1)

Mariia Mykhailova

Oh, in der Tat. In meinem Kopf dachte ich $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $. Ich sollte hier um Mitternacht und wenn ich müde bin, aufhören, Antworten zu beantworten. Vielen Dank für den Hinweis.

cnada

@cnada: Es gibt mindestens zwei verschiedene Begriffe von Komplexität, die beide für die Beschleunigung relevant sind. Eine ist die Größenkomplexität und eine die Tiefenkomplexität. Sofern nicht anders angegeben, ziehen wir es oft vor, die Größenkomplexität zu berücksichtigen, aber die Tiefenkomplexität ist immer noch von großem Interesse für die Komplexität der Quantenberechnung, beispielsweise in MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] und den jüngsten Ergebnissen zu bedingungslose Tiefenabstände [arXiv: 1704.00690 ].

Niel de Beaudrap

@NieldeBeaudrap Ich dachte, die Leute schauen mehr auf die Komplexität der Tiefe. Für Grover liegen Größe und Tiefenkomplexität jedoch in etwa in der gleichen Größenordnung. Das ist quadratisch in der Größe des Problems (im Allgemeinen als die Größe einer Liste von N Elementen angesehen). Denken Sie, dass mein Ansatz hier nicht richtig ist?

cnada

Sie sagen nichts Falsches , ich möchte nur darauf hinweisen, dass Sie die Größenkomplexität übermäßig betonen und den Nutzen der Tiefenkomplexität nicht wirklich herausarbeiten. Nicht viel Interessantes passiert, wenn Sie nur parallelen Grover-Prozessen ausführen, aber wie die Antwort von DaftWullie nahe legt (und die klassische Nachbearbeitung berücksichtigt), geht die Tiefenkomplexität von nach für parallelen Grover-Prozessen, was eine Verbesserung um den Faktor (den Log-Faktor) darstellt kommt von der Identifizierung, welcher Prozess eine Lösung gefunden hat).

k \in O (1)

$k \in O(1)$

\sqrt{N}

$\sqrt N$

\log (k) \sqrt{N / k}

$\log(k) \sqrt{N/k}$

k (N) \in Ω (1)

$k(N) \in \Omega(1)$

\sqrt{k} / \log (k)

$\sqrt{k}/\!\!\;\log(k)$

Niel de Beaudrap