Welche ganzen Zahlen wurden mit Shors Algorithmus berücksichtigt?

Es wird erwartet, dass Shors Algorithmus es uns ermöglicht, ganze Zahlen zu faktorisieren, die weitaus größer sind, als dies mit modernen klassischen Computern möglich wäre.

Derzeit wurden nur kleinere ganze Zahlen berücksichtigt. In diesem Artikel wird beispielsweise die Faktorisierung von erörtert . $15=5{\times}3$

Was ist in diesem Sinne der Stand der Forschung? Gibt es eine aktuelle Veröffentlichung, in der es heißt, dass einige größere Zahlen faktorisiert wurden?

shors-algorithm Liegender Tänzer
quelle

Eng verwandt, aber kein genaues Duplikat: Welches ist die höchste Zahl, die von der Qualitätskontrolle in einem unspezifischen Experiment faktorisiert wird?

Agaitaarino

Antworten:

Die Primfaktor-Faktorisierung von 21 (7x3) scheint die bisher größte zu sein, die mit Shors Algorithmus durchgeführt wurde. Es wurde im Jahr 2012 durchgeführt, wie in diesem Artikel beschrieben . Es sollte jedoch beachtet werden, dass viel größere Zahlen, wie z. B. 56.153 im Jahr 2014, unter Verwendung eines Minimierungsalgorithmus berücksichtigt wurden, wie hier detailliert beschrieben . Eine bequeme Referenz finden Sie in Tabelle 5 dieses Dokuments :

{\begin{matrix} Table 5: Quantum factorization records \\ \begin{array}{cccccc} Number & # of factors & \begin{matrix} # of qubits \\ needed \end{matrix} & Algorithm & \begin{matrix} Year \\ implemented \end{matrix} & \begin{matrix} Implemented \\ without prior \\ knowledge of \\ solution \end{matrix} \\ 15 & 2 & 8 & Shor & 2001 [2] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2009 [5] & χ \\ 2 & 8 & Shor & 2012 [6] & χ \\ 21 & 2 & 10 & Shor & 2012 [7] & χ \\ 143 & 2 & 4 & Minimierung & 2012 [1] & ✓ \\ 56153 & 2 & 4 & Minimierung & 2012 [1] & ✓ \\ 291311 & 2 & 6 & Minimierung & noch nicht & ✓ \\ 175 & 3 & 3 & Minimierung & noch nicht & ✓ \end{array} \end{matrix}}_{.}

$\begin{array}{c} \textbf{Table 5:}~\text{Quantum factorization records} \\ \hline \small{ \begin{array}{cccccc} \text{Number} & \text{# of factors} & \begin{array}{c}\text{# of qubits} \\ \text{needed} \end{array} & \text{Algorithm} & \begin{array}{c}\text{Year} \\ \text{implemented} \end{array} & \begin{array}{c}\text{Implemented} \\ \text{without prior} \\ \text{knowledge of} \\ \text{solution} \end{array} \\ \hline 15 & 2 & 8 & \text{Shor} & 2001~\left[2\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2009~\left[5\right] & \chi \\ & 2 & 8 & \text{Shor} & 2012~\left[6\right] & \chi \\ 21 & 2 & 10 & \text{Shor} & 2012~\left[7\right] & \chi \\ 143 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ 56153 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ \hline 291311 & 2 & 6 & \text{minimization} & \text{not yet} & \checkmark \\ 175 & 3 & 3 & \text{minimization} & \text{not yet} & \checkmark \end{array}} \end{array}_{\Large{.}}$

Heide
quelle

@SqueamishOssifrage: Wo steht, dass der Minimierungsalgorithmus "auf Zahlen beschränkt ist, deren Faktoren bekannte Beziehungen haben, wodurch der Suchraum viel kleiner wird, z. B. Unterschiede in nur wenigen Bitpositionen oder Unterschiede in allen Positionen"?

user1271772

@ user1271772 Soweit ich weiß, besteht die Technik darin, das Problem so zu reduzieren, dass nur eine vertretbare Anzahl von Qubits erforderlich ist, indem Variablen durch bekannte Beziehungen zwischen den Bits der Faktoren entfernt werden. Obwohl die Anzahl der Qubits bis zum Faktor

nur mit

skaliert werden kann, schien keine der von mir gelesenen Arbeiten einen Versuch zu unternehmen, das Wachstum der Zeit bis zur Lösung in Abhängigkeit von der Anzahl der Qubits oder von

abzuschätzen .

N

$N$

O (\log^{2} N)

$O(\log^2 N)$

\log N

$\log N$

Squeamish Ossifrage

\log (N)

$\log(N)$

\log^{2} N

$\log^2 N$

\log (N)

$\log(N)$

\log^{2} N

$\log^2 N$

user1271772

@SqueamishOssifrage: "Keine der Veröffentlichungen, die ich gelesen habe, schien einen Versuch zu machen, das Wachstum der Zeit bis zur Lösung in Abhängigkeit von der Anzahl der Qubits abzuschätzen". Dieser hat einen Versuch unternommen: journals.aps.org/prl/abstract/10.1103/PhysRevLett.101.220405 Aber "Zeit zur Lösung" ist nicht wichtig, sondern der Aufwand. GNF-Sieben ist einfach, aber der Matrixschritt ist schrecklich umständlich. Es ist mühsam, Shors Algorithmus auf einigermaßen optimale Weise auszuführen. Der Minimierungsalgorithmus ist einfach.

user1271772

@SqueamishOssifrage: Schließlich: "Beachten Sie, dass der Minimierungsalgorithmus auf Zahlen beschränkt ist, deren Faktoren bekannte Beziehungen haben". Kein Teil des Algorithmus ist auf "bekannte" Beziehungen beschränkt. Der Algorithmus geht von keinen Faktoren aus. Keine Beziehungen. Die Bits sind alle unbekannten Variablen , die durch Minimierung bestimmt werden. Die Minimierung kann für einige Zahlen mit weniger Qubits als für andere durchgeführt werden. Gleiches gilt für Shors Algorithmus. Gleiches gilt für GNFS. In der Tat, wenn die Zahl, die Sie faktorisieren möchten, gerade ist, ist es ziemlich einfach, sie zu faktorisieren.

user1271772

$21=7\times 3$ $a$

Für den Annealing-Algorithmus gilt : Stand der Technik ist 376289 . Wir wissen aber nicht, wie sich das skalieren lässt. Eine sehr grobe Obergrenze für die Anzahl der Qubits, die benötigt werden, um RSA-230 zu faktorisieren, liegt bei 5,5 Milliarden Qubits (was jedoch von besseren Compilern erheblich gesenkt werden kann ), während Shors Algorithmus dies mit 381 Qubits schafft .

user1271772
quelle

Sie werden in meiner Antwort in der Tabelle feststellen , gibt es eine Spalte für „ohne vorherige Kenntnis der Lösung implementiert : “ Es gibt ein „x“ für alle Algorithmus - Implementierungen des Shor, was mir 15 etwas Ähnliches gilt für Factoring glauben

Heide

Die Größe der berücksichtigten Zahl ist kein gutes Maß für die Komplexität des Faktorisierungsproblems und dementsprechend für die Leistungsfähigkeit eines Quantenalgorithmus. Das relevante Maß sollte vielmehr die Periodizität der resultierenden Funktion sein, die im Algorithmus erscheint.

Dies wird in J. Smolin, G. Smith, A. Vargo diskutiert : Vorgeben, große Zahlen auf einem Quantencomputer zu faktorisieren , Nature 499, 163-165 (2013) . Insbesondere geben die Autoren auch ein Beispiel für eine Zahl mit 20000 Binärziffern an, die mit einem Zwei-Qubit-Quantencomputer mit genau der Implementierung berücksichtigt werden kann, die zuvor zum Faktorisieren anderer Zahlen verwendet wurde.

Es ist anzumerken, dass die "manuellen Vereinfachungen", die die Autoren durchführen, um zu diesem Quantenalgorithmus zu gelangen, auch etwas sind, was z. B. für das ursprüngliche Experiment Factoring 15 durchgeführt wurde.

Norbert Schuch
quelle