Ist die Implementierung von Shors Algorithmus für 2016 wirklich skalierbar?

In der 2016 erschienenen wissenschaftlichen Arbeit " Realisation of a scalable Shor algorithm " [ 1 ] faktorisieren die Autoren 15 mit nur 5 Qubits, was weniger ist als die 8 Qubits, die gemäß Tabelle 1 von [ 2 ] und Tabelle 5 von [ 3 ] "erforderlich" sind ]. Die 8-Qubit-Anforderung ergibt sich aus dem Ende von [ 4 ], das besagt, dass die Anzahl der Qubits, die zum Faktorisieren einer Bit-Zahl sind, beträgt, was für 15 . $n$ $1.5n+2$ $1.5\cdot 4 + 2=8$

Die Arbeit, die nur 5 Qubits verwendet, gibt an, dass ihr Algorithmus "eine QFT, die auf M Qubits einwirkt, durch eine semiklassische QFT ersetzt, die wiederholt auf ein einzelnes Qubit einwirkt", aber die Konsequenzen davon auf die Komplexität des Algorithmus wurden in der Arbeit nie erwähnt.

Nun wurde das Papier, das behauptet, Faktor 15 sei "skalierbar", scharf kritisiert , wie in Abschnitt 2 zu lesen ist, dass das Komplexitätsargument für Shors Algorithmus nicht mehr zutrifft. Diese Kritik wurde jedoch nirgends bekräftigt, und das Science Paper wird immer wieder als "skalierbare" Version von Shors Algorithmus gefeiert. Wie komplex ist der "skalierbare" Shor-Algorithmus?

[ 1 ] Monz et al. (2016) Wissenschaft . Vol. 351, Ausgabe 6277, S. 1068-1070
[ 2 ] Smolin et al. (2013) Natur . 499, 163–165
[ 3 ] Dattani & Bryans (2014) arXiv: 1411,6758
[ 4 ] Zalka (2008), arXiv: quant-ph / 0601097
[ 5 ] Cao & Luo "Kommentar zu: Realisierung eines skalierbaren Shor-Algorithmus"

cc.complexity-theory ds.algorithms quantum-computing factoring security user1271772
quelle

Kommt darauf an, was du mit "skalierbar" meinst. Einige der Kritikpunkte an Cao und Liu wirken ziemlich pingelig. Eine ihrer Kritikpunkte ist beispielsweise, dass Kitaev nicht behauptete, Sie könnten nur ein Qubit in dem für dieses Ergebnis zitierten Papier verwenden. Sie scheinen nicht zu untersuchen, ob diese Behauptung tatsächlich wahr oder falsch ist. Kitaevs Algorithmus kann in der Tat so modifiziert werden, dass er nur ein Qubit verwendet, wie das Science Paper behauptet, obwohl diese Behauptung nicht in Kitaevs Artikel über seinen Algorithmus zu stehen scheint.

Peter Shor

@PeterShor, was für eine Ehre, von Ihnen zu hören! Ok, die Autoren haben die Ergebnisse von Kitaevs Artikel (korrekt) erweitert, um es mit einem Qubit zu ermöglichen, und Cao & Liu beschweren sich, dass sie es "Kitaevs Algorithmus" nennen und nicht "modifizierter Kitaev-Algorithmus oder so etwas". Sie sagen jedoch auch, dass das Komplexitätsargument nicht mehr gilt, wenn die QFT in die "semiklassische QFT" umgewandelt wird. Ich bin noch ein Student, wenn es um diese Art der Analyse geht, daher würde ich mich über Input freuen. Ist die Komplexität noch O (log n) ^ 3? Ist es immer noch "skalierbar" in Bezug auf das Polynom oder zumindest <GNFS?

User1271772

Ich lasse das von jemand anderem beantworten, da die Leute behaupten könnten, ich sei voreingenommen. Aber lassen Sie mich darauf hinweisen, dass die Autoren des Wissenschaftspapiers Kitaevs Algorithmus nicht erweitert haben ... es ist eine bekannte Erweiterung. Sie haben lediglich nicht die richtige Referenz zitiert.

Peter Shor

Diese Formeln, die zu 8 Qubits führen, benötigen eine bestimmte Implementierung von Shors Algorithmus und berechnen, wie viele Qubits diese Implementierung benötigt. Sie behaupten nicht, dass dies die bestmögliche Implementierung ist.

Peter Shor

@ user1271772 Dies wurde für die Moderationsaufmerksamkeit markiert, da Sie einer der in Ihrem eigenen Beitrag genannten Autoren sind. Nicht, dass das schlecht ist, einige Eigenwerbung ist ein unvermeidlicher Teil der Wissenschaft, aber vielleicht ist es das Beste, sich darüber klar zu werden?

Bjørn Kjos-Hanssen

Antworten:

Das Hauptargument von Cao und Luo ist, dass in der Variante des implementierten Algorithmus das erste Register - das schließlich die Ausgabe enthält - nur 1 Bit enthält. Und wenn der Algorithmus nur 1 Bit ausgibt, reicht dies nicht für die Faktorisierung aus. (Obwohl dies nicht ihr Argument ist, enthält 1 Bit eindeutig nicht genug Informationen, um die Faktoren zu bestimmen.)

Was Cao und Luo nicht zu realisieren scheinen, ist, dass für die Variation der Fourier-Transformation mit nur einem Bit im ersten Register derselbe Wert von ausgegeben wird wie im Standard-Faktorisierungsalgorithmus; Es wird jeweils nur ein Bit ausgegeben . Diese Änderung wirkt sich nicht auf die Laufzeit von . $c$ $O(\log^3 N)$

Um Cao und Luo gegenüber fair zu sein, sagen sie, dass sie nicht glauben, dass dieser Algorithmus funktioniert, und wenn er funktioniert, dann ist er nicht Shors Algorithmus, da er nicht genau mit dem im ursprünglichen Factoring-Paper beschriebenen Algorithmus übereinstimmt . Ein Zitat aus ihrem Papier:

Abschließend möchten wir betonen, dass es sich, wenn die Implementierung tatsächlich glaubwürdig ist, um einen neuen Quantenfaktor-Algorithmus handelt, nicht um den Shor-Algorithmus, da nicht alle Anforderungen des ursprünglichen Shor-Algorithmus erfüllt sind.

Und tatsächlich ist es nicht der Algorithmus aus meinem ursprünglichen Factoring-Papier. Es verwendet das Phasenschätzungsverfahren aus Kitaevs Faktorisierungsalgorithmus und eine Variante davon, die von Griffiths und Niu (nicht von Parker und Plenio, wie ich in einer früheren Ausgabe dieser Antwort sagte) entdeckt wurde und die es dem Algorithmus ermöglicht, die Schätzung der Phase auszugeben Stück für Stück.

Peter Shor
quelle

Zeigen Sie mir bitte, wo in Caos und Luos Zeitung steht, dass die Ausgabe eines Bits auf einmal die Betriebskosten beeinflusst. Wenn ich ihre Zeitung richtig lese, tun sie das nicht. Ich glaube, ich habe ihre Kritik angemessen widerlegt.

Peter Shor

Ihre Kritikpunkte sind (1) Wenn Sie nur ein Bit der Ausgabe haben, dann funktioniert der Algorithmus für fortgesetzte Brüche nicht. Dies wird dadurch widerlegt, dass Sie feststellen, dass tatsächlich mehr als ein Bit ausgegeben werden. (2) Wenn Sie nur ein Ausgabebit haben, sind die Wahrscheinlichkeiten für jeden Ausgang falsch. Dies wird wiederum dadurch widerlegt, dass Sie feststellen, dass Sie tatsächlich mehr als ein Bit der Ausgabe haben. (3) Die einzigen verwendeten Multiplikationsschaltungen waren solche, die multiplizieren , wobei eine feste Zahl ist, die in die Multiplikationsschaltung vorberechnet wurde. Ich habe dies in meiner Antwort nicht widerlegt, aber das ist alles, was Sie brauchen, um zu berücksichtigen.

c

$c$

x \cdot t

$x\cdot t$

t

$t$

Peter Shor

Ich werde nicht die Schaltung für die Schätzung der Ein-Qubit-Ausgangsphase durchgehen und erklären, warum die relativ kleine Änderung, die erforderlich ist, um dies zu erreichen, die zeitliche Komplexität nicht beeinflusst. Es ist der „semi-klassische“ Änderung auf Seite 2 von Parker und Plenio von Papier , effiziente Faktorisierung mit einem einzigen reinen Qubit und melden Sie sich gemischte Qubits N .

Peter Shor

Um von "einem Kontroll-Qubit oder fliegenden Qubits" zu , müssen Sie möglicherweise deren Papier verstehen. Die in ist das eine Kontroll-Qubit.

\log N + 1

$\log N + 1$

1

$1$

\log N + 1

$\log N + 1$

Peter Shor

Wie gesagt, man muss das Papier lesen und verstehen. Zählen Sie sie selbst, wenn Sie mir nicht vertrauen. Die Grundstruktur des Algorithmus hat sich nicht geändert.

Peter Shor