[PYTHON] Was ist der Shore-Algorithmus? Stimmt es, dass ein Quantencomputer eine Primfaktorisierung in Polynomzeit durchführen kann? Ich habe es nachgeschlagen!
Einführung
Um die Primfaktorisierung auf einem klassischen Computer durchzuführen, wird $ O (\ sqrt {N}) $ berechnet, und selbst der effizienteste Algorithmus, der derzeit entwickelt wird, benötigt ungefähr eine exponentielle Zeit von Ziffern. Es scheint, dass es enden wird. Aber wenn ich versuche, eine 300-stellige Primfaktorisierung durchzuführen, dauert es lange, bis ich sterbe. e? Primfaktorzerlegung in Polynomzeit? Ich kann es schaffen! Das ist Shores Algorithmus. In diesem Artikel besteht das Ziel dieses Artikels darin, diesen Shore-Algorithmus in qiskit zu implementieren und auf einem echten Quantencomputer auszuführen. Dieses Mal werden wir 15 nach unten faktorisieren. Ich denke, dass dieser Artikel wahrscheinlich (oder mit Sicherheit) Fehler und Druckfehler enthält. Wenn Sie also einen finden, lassen Sie es mich bitte wissen ...
fließen
Um den Landalgorithmus zu erklären, sind verschiedene Vorbereitungen erforderlich, aber zuerst möchte ich den Gesamtfluss schreiben.
Betrachten Sie zunächst eine natürliche Zahl $ N $, die Sie in einen Primfaktor zerlegen möchten, und eine natürliche Zahl $ x $, die sich gegenseitig primiert (Sie können durch die euklidische Methode der gegenseitigen Teilung bestimmen, ob sie Primzahlen sind oder nicht). Lassen Sie uns darüber in der Welt von modN unten nachdenken. Das kleinste r, so dass $ x ^ r = 1 $ ist, wird als Ziffer bezeichnet. Es ist bekannt, dass das Finden dieser Ziffer für die Primfaktorisierung effektiv ist. Bei einem klassischen Computer dauert diese Berechnung jedoch auch exponentiell. Der Phasenschätzungsalgorithmus löst dieses Problem. Der Phasenschätzungsalgorithmus gibt eine ungefähre Phase des Eigenwerts (Absolutwert ist 1) der Einheitsmatrix an. Wenn man U so betrachtet, dass $ U ^ r = I $ in der Welt von $ \ mod N $ ist, kann r aus seinem eindeutigen Wert erhalten werden. Der unten beschriebene Adamar-Test und die Quanten-Fourier-Transformation sind als Unterprogramme für diesen Phasenschätzungsalgorithmus erforderlich.
Adamar-Test
Zunächst erkläre ich einen Algorithmus namens Adamal-Test.
Der Adamal-Test wird durch die folgende Schaltung realisiert ($ U $ ist ein beliebiges Gate).
In dieser Schaltung
control-Das Quantenbit nach dem Durchgang durch das U-Gatter
Quanten-Fourier-Transformation
Die Quanten-Fourier-Transformation ist ein Algorithmus, der eine diskrete Fourier-Transformation durchführt. Unter der Annahme, dass die Länge der Sequenz $ 2 ^ n $ beträgt, kann der klassische Computer die diskrete Fourier-Transformation mit $ O (n2 ^ n) $ in der Hochgeschwindigkeits-Fourier-Transformation durchführen, die jeder liebt, aber die Quanten-Fourier-Transformation kann die diskrete Fourier-Transformation mit $ O (n ^ n ^) durchführen. 2) Es kann in $ n $ Polypoly-Zeit namens $ gelöst werden!
Erinnern wir uns zunächst an die Definitionsformel der diskreten Fourier-Transformation.
Tatsächlich ist diese Transformation einheitlich, und da der Quantencomputer jede einheitliche Transformation mit dem universellen Gate-Satz approximieren kann, ist diese Transformation auf dem Quantencomputer möglich. Ich weiß jedoch nicht, welche Art von Tor ich beißen soll, deshalb möchte ich es in eine Form verwandeln, die einfacher zu verwenden ist. Wenn Sie k binär erweitern und Ihr Bestes geben, ist dies wie folgt.
Tatsächlich verwendet Shores Algorithmus die inverse Quanten-Fourier-Transformation, die ebenfalls unten gezeigt wird. Dadurch wurde das Tor nur von der gegenüberliegenden Seite aufgehängt (aber die Drehung ist umgekehrt).
Übrigens müssen Sie vorsichtig mit der Leserichtung des Quantenbits sein. Hier lesen wir in der Reihenfolge q0q1q2q3. Das heißt, wenn $ q0 = 1, q1 = q2 = q3 = 0 $, dann ist $ x = 1000 (2) = 8 $. Derzeit ist H dasselbe wie das Adamal-Gate, U1 ist dasselbe wie das Rz-Gate und nur $ | 1 \ rangle $ ist das Gate, das die Phase von $ e ^ {i \ theta} $ setzt. Weitere Informationen finden Sie hier (https://quantum-computing.ibm.com/support/guides/gate-overview?section=5d00d964853ef8003c6d6820#).
Phasenschätzungsalgorithmus
Der Phasenalgorithmus ist eine verbesserte Version des Adamar-Tests.
Der Eigenwert der Einheitsmatrix $ U $ der Größe $ 2 ^ n $ sei $ e ^ {2 \ pi i \ lambda} $, und der entsprechende Eigenvektor sei $ | \ varphi \ rangle $. Wenn $ \ lambda $ als Bruchteil der $ m $ -Ziffer binär dargestellt werden kann,
M für den Phasenschätzungsalgorithmus+Verwendet n Quantenbits für die Eingabe
Anwendung auf die Primfaktorisierung
Warum ist es möglich, eine Primfaktorisierung durchzuführen, sobald die Ziffer r erhalten wird? Nehmen wir zunächst an, dass r gerade ist (es scheint, dass es gerade ist, wenn Sie es zufällig nehmen). Dann können die folgenden Transformationen durchgeführt werden.
Implementierung in Qiskit
Nun, hier ist die Produktion. Lassen Sie uns den oben gezeigten Algorithmus in einem Simulator ausführen und $ N = 15 $ in $ x = 4 $ faktorisieren. Dieses Mal werden wir eine Quantenberechnungsbibliothek namens qiskit verwenden. Weitere Informationen zu qiskit finden Sie unter Offizielle Dokumentation. Die gesamte Ausführung erfolgt auf dem Jupyter-Notebook.
Der Quantencomputerteil ist wie folgt. Obwohl es sich um die im vorherigen Kapitel erwähnte Implementierung von U handelt, ist es schwierig, eine allgemeine Restoperation zu implementieren. Daher haben wir die Tatsache ausgenutzt, dass $ N = 15, x = 4 $ ($ {U} ^ {2 ^). Für i} $ habe ich auch die Tatsache verwendet, dass die Ziffer 2 ist, also habe ich sie weggelassen ...), aber diesmal ist es okay, weil es nur ein Gefühl dafür bekommt.
from qiskit import *
from qiskit.providers.ibmq import least_busy
from qiskit.visualization import plot_histogram
from qiskit.tools.monitor import job_monitor
import math
q = QuantumRegister(8, "q")
c = ClassicalRegister(4, "c")
circuit = QuantumCircuit(q, c)
circuit.x(7)
#Hadamard transform
for i in range(4):
circuit.h(i)
#U4^1 gate
circuit.cswap(3, 4, 6)
circuit.cswap(3, 5, 7)
circuit.barrier()
#U4^2 gate
#U4^4 gate
#U4^8 gate
circuit.barrier()
#inverse quantum Fourier transform
circuit.swap(0, 3)
circuit.swap(1, 2)
circuit.h(3)
circuit.cu1(-np.pi/2, 3, 2)
circuit.h(2)
circuit.barrier()
circuit.cu1(-np.pi/4, 3, 1)
circuit.cu1(-np.pi/2, 2, 1)
circuit.h(1)
circuit.barrier()
circuit.cu1(-np.pi/8, 3, 0)
circuit.cu1(-np.pi/4, 2, 0)
circuit.cu1(-np.pi/2, 1, 0)
circuit.h(0)
circuit.barrier()
#measure
for i in range(4):
circuit.measure(q[i], c[3-i])#X in binär=Ich versuche q1q2q3q4 zu sein
circuit.draw(output='mpl')
Der Rest ist der klassische Berechnungsteil. Ich habe die kontinuierliche Fraktionserweiterung wie folgt implementiert (es ist ziemlich verdächtig, weil ich sie gerade richtig geschrieben und ein kleines Beispiel ausprobiert habe ...). Ich versuche zu beenden, wenn der relative Fehler kleiner als eps ist.
eps = 0.01
def continued_fractions_algorithm(x):
res = [int(x)]
x-=int(x)
if x/(res[0]+0.1)>eps:
a = continued_fractions_algorithm(1/x)
res+=a
return res
Schätzen wir nun den Rechenaufwand (als Quantencomputer). Unter der Annahme, dass die natürliche Zahl, die Sie als Primfaktor verwenden möchten, $ n $ Bit ist, ist der diskrete Fourier-Transformationsteil $ O (n ^ 2) $ und der Teil des Phasenschätzungsalgorithmus ist $ O (n ^ 3) $. Der klassische Teil wird nicht zu einem Engpass, daher konnte ich ihn in einer Polypoly-Zeit von insgesamt $ O (n ^ 3) $ lösen! Wenn Sie danach den folgenden Code ausführen,
def shor_algorithm(use_simulator):
if use_simulator:
backend = BasicAer.get_backend('qasm_simulator')
else:
backend = IBMQ.get_provider().get_backend('ibmq_16_melbourne')
flag = False
job = execute(circuit, backend, shots = N)
job_monitor(job)
result = job.result()
counts = result.get_counts(circuit)
measures = np.array(list(map(lambda x:int(x, 2), counts.keys())), dtype = np.int64)
probs = np.array(list(counts.values()))/N
for i in range(5):
output = np.random.choice(measures, p = probs)
a = continued_fractions_algorithm(output/2**4)
r , s =1, a[-1]
for i in range(len(a)-1)[::-1]:
r, s = s, a[i]*s+r
if r % 15 == 0 or s == 0:
continue
d = math.gcd(15, 4**(r-1)-1)
if d != 1:
flag = True
break
plot_histogram(result.get_counts())
if flag:
print('{0} devides 15 with r = {1}'.format(d, r))
else:
print('the algorithm failed')
return result
%matplotlib inline
use_simulator = True
result = shor_algorithm(use_simulator)
plot_histogram(result.get_counts())
Und es gelang uns zu faktorisieren!
Berechnung an der tatsächlichen Maschine
Sie können IBM Q, einen kostenlosen Quantencomputer, von qiskit aus bedienen. Die offizielle Seite ist hier. Sie müssen ein Konto für den Vorgang erstellen.
Führen Sie zunächst den folgenden Code aus.
from qiskit import IBMQ
my_token = ""
IBMQ.save_account(my_token)
provider = IBMQ.load_account()
Geben Sie in my_token den von Mein Konto erhaltenen Token auf der offiziellen Seite ein.
Da ich dieses Mal 8qubit verwende, werde ich ibmq_16_melbourne verwenden. Es wird einige Zeit dauern, aber wenn Sie es mit use_simulator = False im obigen Code ausführen,
Was?
Zusammenfassung
Wie war es? Ich habe diesmal versucht, mit einem Quantencomputer zu faktorisieren, aber wie wir im vorherigen Kapitel gesehen haben, gibt es einen erheblichen Fehler in der tatsächlichen Maschine. Natürlich versuche ich diesmal etwas Einfaches, das jeder verwenden kann, aber es scheint, dass es einige Zeit dauern wird, bis der Quantencomputer in die Praxis umgesetzt ist, wenn selbst die Faktorisierung von 15 schwierig ist.
Referenz
Quantum Native Dojo https://dojo.qulacs.org/ja/latest/ Kenjiro Miyano, Akira Furusawa, Einführung in Quantencomputer Japan Kritiker 2016 Michael A. Nilsen,Isaac L. Chuang Quantum Computation and Quantum Information 10th Anniversary Edition 2010
Recommended Posts