Comment montrer la quantité de qubits nécessaire pour déchiffrer le protocole RSA-2048 en utilisant l'algorithme de Shor?

Dec 19 2020

J'ai lu qu'avec la technologie actuelle, nous aurions besoin d'environ 20 millions de qubits pour déchiffrer le protocole RSA-2048. Comment prouverait-on cela?

Réponses

6 JSdJ Dec 19 2020 at 22:28

Je suppose que vous voulez dire le résultat de cet article , où les auteurs (y compris `` notre propre '' Craig Gidney ) ont estimé que si vous avez$\sim20$ millions de qubit bruyants ça vous emmènerait $8$ heures pour `` exécuter '' l'algorithme de Shor pendant un $2048$ clé de bit.

Pour une `` preuve '', vous pouvez lire l'article, mais il y a quelques choses importantes à réaliser ici:

  • Ceci est une estimation
  • Ce nombre est pour les qubits physiques , qui sont bruyants, et qui sont donc combinés en qubits logiques en utilisant QECC
  • L'estimation dépend des niveaux de bruit actuels (quoi et où alors) - des niveaux de bruit plus faibles signifient moins de besoin de correction d'erreur, ce qui signifie moins de frais généraux
  • Il n'y a pas de nombre défini de qubits (logiques), c'est toujours un compromis entre le nombre de qubits nécessaires et le nombre de portes nécessaires. C'est pourquoi le temps nécessaire à l'exécution de l'algorithme est inclus dans le titre de l'article ci-dessus, car la mise en œuvre des portes prend du temps et est donc d'une importance vitale

Si vous ne vous souciez que des qubits logiques, cette question et réponse pourrait être ce que vous recherchez. Cependant, rappelez-vous qu'il n'y a pas de réponse unique et définitive à cette question.