Was ist Shor-Algorithmus?

Antwort: A. Public-Key-Kryptografie wie RSA und Elliptische-Kurven-Kryptografie

Die Sicherheit von RSA beruht auf der Schwierigkeit, große Zahlen zu faktorisieren, die der Elliptische-Kurven-Kryptografie auf der Schwierigkeit des diskreten Logarithmusproblems. Der Shor-Algorithmus löst diese Probleme in Polynomialzeit, indem er mit der Quanten-Fourier-Transformation Perioden bestimmt. Schlüssel, die zu lang sind, um sie auf klassischen Computern in realistischer Zeit zu brechen, ließen sich dann mit einem ausreichend großen fehlertoleranten Quantencomputer brechen. Gegen symmetrische Verschlüsselung wie AES gibt es nur die quadratische Beschleunigung des Grover-Algorithmus, der sich mit längeren Schlüsseln begegnen lässt.

Antwort: C. Eine riesige Zahl von Gattern muss fehlerfrei ausgeführt werden, was viele durch Fehlerkorrektur gebildete logische Qubits und eine enorme Zahl physikalischer Qubits zu deren Unterstützung erfordert

Um RSA-2048 zu brechen, müssen auf grob tausend bis einigen tausend logischen Qubits Gatter in der Größenordnung von Milliarden nacheinander ausgeführt werden. Die logische Fehlerrate muss daher extrem niedrig sein, und die Fehlerkorrektur erfordert einige hundert oder mehr physikalische Qubits pro logischem Qubit. Schätzungen aus den 2020er-Jahren veranschlagen grob einige hunderttausend bis einige zehn Millionen physikalische Qubits mit Fehlerraten von etwa 0,1 % (die Zahlen hängen stark von den Annahmen ab), Größenordnungen jenseits des Umfangs heutiger Geräte. Diese Schätzungen sind jedoch mit verbesserten Algorithmen gesunken, daher muss die Vorbereitung der Umstellung der Kryptografie frühzeitig beginnen.