Quelle est la valeur entière minimale pour que la factorisation quantique en vaille la peine?

11

Supposons que nous ayons des ordinateurs quantiques et classiques tels que, expérimentalement, chaque opération logique élémentaire de factorisation mathématique soit également coûteuse en temps en factorisation classique et quantique: qui est la valeur entière la plus basse pour laquelle la procédure quantique est plus rapide que la classique un?

SalvaCardona
la source
2
Un calcul très précis dépendrait de détails tels que la mise en œuvre d'opérations d'addition dans l'algorithme quantique, ainsi que des opérations précises utilisées dans le meilleur algorithme de factorisation classique. Dans les deux cas, nous sommes souvent habitués à ignorer des facteurs constants dans la quantité de travail requise, mais même plus dans le cas classique que dans le cas quantique. Seriez-vous satisfait d'une estimation de l'ordre de grandeur (par exemple, un avantage quantique obtenu entre 350 et 370 bits --- pour fournir une réponse possible que j'ai créée à partir de rien sans aucune analyse réelle)?
Niel de Beaudrap
@NieldeBeaudrap Je dirais que pour les raisons que vous avez indiquées, un nombre exact serait impossible à fournir. Si votre estimation «hors des airs» est basée sur un raisonnement, je pense que ce serait intéressant. (En d' autres termes, une instruction estimation a une valeur, mais une supposition sauvage n'a pas)
Discrète lézard
@DiscreteLizard: si j'avais un moyen d'estimation solide à portée de main, je n'aurais pas produit d'exemple de réponse basé sur aucune analyse :-) Je suis sûr qu'il existe un moyen raisonnable de produire une estimation intéressante, mais celles que je serais pouvoir fournir facilement aurait des barres d'erreur trop grandes pour être très intéressantes.
Niel de Beaudrap
Étant donné que ce problème est (ou a été) généralement considéré comme une "preuve" typique que les ordinateurs quantiques sont capables de prouesses en dehors des domaines de l'informatique classique, mais presque toujours en termes de complexité de calcul stricte (donc, en négligeant toutes les constantes et uniquement valable pour une entrée arbitrairement élevée) Je dirais qu'une réponse d'ordre de grandeur approximative (et sa dérivation) serait déjà utile / pédagogique. Peut-être que les personnes sur CS / theoryCS pourraient être disposées à aider.
agaitaarino
1
@agaitaarino: Je suis d'accord, même si la réponse devra supposer un compte rendu plus ou moins précis des performances des meilleurs algorithmes classiques de factorisation. Le reste peut alors être fait par un étudiant raisonnablement bon en calcul quantique.
Niel de Beaudrap

Réponses:

8

La partie quantique de l'algorithme de Shor est, essentiellement, une seule exponentiation modulaire effectuée sous superposition suivie d'une transformée de Fourier puis d'une mesure. L'exponentiation modulaire est de loin la partie la plus chère.

Supposons que chaque [...] opération logique élémentaire de factorisation mathématique soit également coûteuse en temps en factorisation classique et en factorisation quantique

Si nous supposons que l'exponentiation modulaire prend exactement autant de temps sur un ordinateur quantique que sur un ordinateur classique, alors la transition où le calcul quantique s'est amélioré se produira à un nombre très faible. Le calcul d'exponentiations modulaires est très rapide, classiquement, car vous pouvez utiliser la quadrature répétée. Je voudrais énormément estimer que le croisement se produira avant même que vous n'atteigniez même des nombres de 30 bits (nombres supérieurs à un milliard).

Mais les ordinateurs quantiques ne feront pas les mathématiques presque aussi vite que les ordinateurs classiques . Par exemple, sur mon ordinateur portable, je peux faire une exponentiation modulaire de 1000 bits en python en une fraction de seconde. Mais sur les ordinateurs quantiques prévisibles, cela prendrait des heures ou des jours. Le problème est la différence énorme ( massive ) dans le coût d'une porte ET.

|T

Supposons donc que nous obtenions un million d'états T par seconde, et nous voulons convertir cela en un taux d'additions 64 bits à comparer avec la machine classique. Un ajout 64 bits nécessite 64 portes ET, chacune nécessitant 4 portes T. 1 million divisé par 4 divisé par 64 donne ... environ 4KHz. Par contraste, une machine classique fera facilement un milliard d'ajouts par seconde. Les additionneurs quantiques sont un million de fois plus lents que les additionneurs classiques (encore une fois, une estimation extravagante et gardez à l'esprit que ce nombre devrait s'améliorer avec le temps).

Un autre facteur à considérer est la différence des coûts des ordinateurs quantiques et classiques. Si vous avez cent millions de dollars et que vous choisissez entre un ordinateur quantique et mille ordinateurs classiques, ce facteur de 1000 doit être pris en compte. En ce sens, on pourrait dire que les additionneurs quantiques sont un milliard de fois moins efficaces que les additionneurs classiques (en FLOPS / $).

Une pénalité constante d' un milliard de dollars est normalement une rupture immédiate. Et pour les algorithmes quantiques avec un simple avantage quadratique (comme Grover), je soutiens qu'il s'agit en fait d'un facteur de rupture. Mais l'algorithme de Shor s'améliore de façon exponentielle par rapport à la stratégie classique lorsque vous augmentez le nombre de bits du nombre à factoriser. Combien de morceaux avant de ronger cette constante "maigre" 10 ^ 9 avec notre croissance exponentielle en avantage?

Considérez que le RSA-640 a été pris en compte en 2005 en utilisant environ 33 années CPU. Un ordinateur quantique devrait être capable de faire ce nombre en moins d'une journée. Si vous avez un millier d'ordinateurs classiques travaillant sur le problème, ils finiraient dans environ deux semaines. Il semble donc que le quantum gagne par 640 bits, mais seulement par un ordre de grandeur ou trois. Alors peut-être que la coupure se produirait quelque part autour de 500 bits?

Quoi qu'il en soit, je sais que ce n'est pas une réponse dure et rapide. Mais j'espère que j'ai donné une idée des quantités auxquelles je penserais en comparant le classique et le quantique. Personne ne connaît vraiment les facteurs constants impliqués, donc je serais surpris si quelqu'un pouvait vous donner une estimation correcte mieux que "quelque part dans les centaines de bits".

Craig Gidney
la source
C'est un bon effort, mais comment obtenez-vous l'estimation de 30 bits? À quoi comparez-vous précisément l'algorithme de Shor, lorsque vous considérez qu'il s'agit d'un point de croisement probable?
Niel de Beaudrap
1
@NieldeBeaudrap Comme je l'ai dit, c'est une supposition sauvage. Je figure: la multiplication modulaire a un facteur constant décent (classiquement). Il en va de même pour les fractions continues. Les algorithmes de factorisation ont-ils également de bons facteurs constants? Probablement pas? Si c'est le cas, le croisement se produirait presque immédiatement au lieu d'un grand nombre. Si quelqu'un veut comparer ces deux choses, je mettrai à jour la réponse. Je considère que la "viande" est le reste.
Craig Gidney
1
Je ne m'opposerais pas normalement à cela comme fournissant une intuition, sauf que votre supposition sauvage est précisément sur le sujet de la question. (La question est également posée de manière à suggérer une prise de conscience des problèmes de vitesse d'horloge.) Les techniques les plus rapides pour factoriser de très grands nombres impliquent de grands facteurs constants, mais en fait, en tenir compte est le point de la question; mais pour des nombres d'environ un milliard, nous pourrions même envisager la division d'essai en utilisant un tableau de nombres premiers jusqu'à environ 32 767, ce qui serait très rapide en pratique. Une comparaison quantitative, même avec cela, serait un début.
Niel de Beaudrap
6

Comme je l'ai mentionné dans les commentaires, une réponse très précise dépendra probablement de nombreux choix techniques qui sont quelque peu arbitraires. Il sera probablement plus important d'obtenir une estimation de l'ordre de grandeur et d'en tenir compte autant que possible pour la faire.

Cette réponse ne se veut pas une réponse définitive, mais un pas dans la bonne direction en se référant à la littérature existante (bien que certes vieille de plus d'une décennie), en particulier:

  • Van Meter, Itoh et Ladd. Temps d'exécution dépendant de l'architecture de l'algorithme de Shor . Proc. Supraconductivité mésoscopique + spintronique 2006; [ arXiv: quant-ph / 0507023 ]

Van Meter, Itoh et Ladd tentent de comparer les performances de l'algorithme de Shor avec la technologie informatique disponible exécutant le Number Field Sieve (l'algorithme classique le plus connu pour la factorisation). Je n'ai pas eu le temps de parcourir les détails du document - une réponse supérieure pourrait probablement être obtenue en le faisant - mais la figure 1 de cet article nous permet de faire une estimation numérique raisonnable:

entrez la description de l'image ici

Ici, les courbes abruptes représentent le temps de calcul des réseaux informatiques classiques. La courbe intitulée «NFS, 104 PC, 2003» semble indiquer les calculs (et le temps de calcul projeté) de cent quatre ordinateurs personnels vers 2003, tel que rapporté par RSA Security Inc. en 2004 [ http: //www.rsasecurity. com / rsalabs / node.asp? id = 2096] .

nnvv2×dix11opérations par seconde. Un étalonnage hypothétique de l'algorithme de Shor devrait être effectué par rapport à un ordinateur quantique fonctionnant à une vitesse d'horloge comparable.

dix9

  • Malgré un avantage d'opérations par seconde d'un facteur de 200 ou plus, le graphique indique quand cette implémentation NFS classique à 200 GHz est dépassée par un ordinateur quantique à 1 GHz exécutant l'algorithme de Shor (à environ 200 chiffres) et par un ordinateur quantique à 1 MHz ( à environ 330 chiffres).
  • Nous avons également une courbe projetant les performances "en 2018", représentant 1000 fois la puissance de calcul classique: les interceptions avec les ordinateurs quantiques 1 GHz et 1 MHz sont à 350 bits et 530 bits.

L'augmentation des points de croisement par rapport aux calculs quantiques, du calcul en 2003 à celui prévu en 2018, représentant une augmentation de la vitesse d'horloge de 1000, est un facteur d'environ 5/3. À partir de cela, nous pouvons estimer que l'avantage de calcul par rapport à la taille des nombres qui peut être rapidement résolu par un ordinateur classique, en raison d'une augmentation de la vitesse d'un facteur de 200, est d'environ 7/6. Ensuite, nous pouvons estimer que le point de croisement d'un seul ordinateur classique à 1 GHz exécutant NFS, avec un ordinateur quantique à 1 GHz exécutant l'algorithme de Shor, est à environ 170 bits.

En bout de ligne - une réponse précise dépendra de nombreuses hypothèses techniques qui peuvent changer le résultat précis de manière significative, il est donc préférable de rechercher une estimation approximative. Mais cette question a été étudiée au moins une fois auparavant, et en faisant un certain nombre d'hypothèses et d'extrapolations sur les performances basées sur les performances classiques en 2003, il semble que les algorithmes de Shor surclasseront le meilleur algorithme classique connu opération par opération pour les nombres. environ 170 bits.

Niel de Beaudrap
la source
C'est une bonne réponse. Il convient de noter que l'idée de ce document d'une "opération logique élémentaire" se situe (de manière très appropriée) au niveau d'une porte ET, par opposition au niveau d'une instruction CPU ou d'une opération BigInt (ce que je soupçonne être ce que le demandeur était en pensant). Dans ma propre réponse, je supposais que l'exponentiation modulaire se faisait "comme si elle était classique", ce qui impliquerait par exemple des multiplications FFT. C'est pourquoi j'ai deviné un nombre qui était tellement inférieur à cet article, qui (à juste titre) fait la multiplication des manuels scolaires avec des additionneurs de report d'ondulation pour son arithmétique quantique.
Craig Gidney
@SalvaCardona: Je vous recommande de ne pas accepter ma réponse. Mon analyse est très superficielle, et vous devriez attendre pour une meilleure analyse.
Niel de Beaudrap