Est-ce que l'usage courant en informatique de «ignorer les constantes» est utile pour comparer l'informatique classique à l'informatique quantique?

Daniel Sank a mentionné dans un commentaire , répondant à (mon) avis que l' accélération constante de sur un problème d'admission d'un algorithme de temps polynomial est maigre, que$10^8$

La théorie de la complexité est trop obsédée par les limites d'échelle de taille infinie. Ce qui compte dans la vie réelle, c'est la rapidité avec laquelle vous obtenez la réponse à votre problème.

En informatique, il est courant d'ignorer les constantes dans les algorithmes, et dans l'ensemble, cela s'est avéré fonctionner plutôt bien. (Je veux dire, il y a de bonnes et pratiques algorithmes . J'espère que vous m'accorderez des algorithmes (théoriques) que les chercheurs ont eu un rôle assez important dans ce domaine!)

Mais, je comprends que c'est une situation légèrement différente comme nous le sommes maintenant:

1. Ne pas comparer deux algorithmes fonctionnant sur le même ordinateur, mais deux algorithmes (légèrement) différents sur deux très différents ordinateurs .
2. Nous travaillons maintenant avec des ordinateurs quantiques , pour lesquels les mesures de performance traditionnelles peuvent être insuffisantes.

En particulier, les méthodes d'analyse algorithmique ne sont que des méthodes . Je pense que des méthodes informatiques radicalement nouvelles appellent un examen critique de nos méthodes actuelles d'évaluation des performances!

Donc, ma question est:

Lors de la comparaison des performances des algorithmes sur un ordinateur quantique par rapport aux algorithmes sur un ordinateur classique, la pratique d'ignorer les constantes est-elle une bonne pratique?

L'usage courant de l'informatique pour «ignorer les constantes» n'est utile que lorsque les différences de performances de divers types d'architecture matérielle ou de logiciels peuvent être ignorées avec un peu de massage. Mais même dans le calcul classique, il est important d'être conscient de l'impact de l'architecture (comportement de mise en cache, utilisation du disque dur) si vous souhaitez résoudre des problèmes difficiles ou de gros problèmes.

La pratique d'ignorer les constantes n'est pas une pratique qui est motivée (dans le sens d'être continuellement affirmée) du point de vue de la mise en œuvre. Elle est principalement motivée par un intérêt pour une approche de l'étude des algorithmes qui se comporte bien en composition et admet des caractérisations simples, d'une manière proche des mathématiques pures. Les théorèmes d'accélération des machines de Turing signifiaient que toute définition sensée ne pouvait pas tenter de cerner trop précisément la complexité des problèmes afin d'arriver à une théorie sensible; et d'ailleurs, dans la lutte pour trouver de bons algorithmes pour des problèmes difficiles, les facteurs constants n'étaient pas la partie mathématiquement intéressante ...

Cette approche plus abstraite de l'étude des algorithmes a été et est largement fructueuse. Mais maintenant, nous sommes confrontés à une situation où nous avons deux modèles de calcul, où

• L'un est dans un état avancé de maturité technologique (calcul classique); et
• L'un est dans un état très immature, mais tente de réaliser un modèle théorique qui peut conduire à des améliorations asymptotiques significatives (calcul quantique).

Dans ce cas, on peut se demander s'il est même logique de considérer le bénéfice asymptotique, avec ou sans prise en compte soigneuse des facteurs constants. En raison de l'effort supplémentaire qui peut être nécessaire pour effectuer un calcul quantique évolutif, non seulement des facteurs scalaires mais aussi des polynômes "accélérations" performances théoriques peuvent être éliminées une fois que tous les frais généraux liés à la réalisation d'un algorithme quantique sont pris en compte.

Dans ces premiers jours, il peut également y avoir des différences significatives dans les performances des différentes approches de l'architecture quantique. Cela pourrait rendre le choix de l'architecture aussi important (sinon plus important) pour la performance d'un algorithme que l'analyse asymptotique - tout comme cela aurait beaucoup d'importance pour vous si vous effectuez votre calcul conventionnel sur une machine von Neumann ou un réseau hautement distribué avec des latences importantes.

La chose réellement importante pour le calcul pratique n'est pas - et a toujours été - non seulement des algorithmes, mais des implémentations d'algorithmes : un algorithme réalisé d'une certaine manière, sur une certaine architecture. La pratique courante de l'analyse asymptotique qui ignore les facteurs constants nous permet de prêter attention aux raisons systématiques et mathématiques des différences de performances des algorithmes, et est pratiquement motivée dans les cas où les différences architecturales ne sont pas assez importantes pour dominer les performances pratiques. .

En ce qui concerne les technologies quantiques, nous ne sommes pas dans cette situation heureuse où nous pouvons en toute sécurité ignorer des facteurs constants dans n'importe quel contexte pratique. Mais peut-être qu'un jour nous pourrons le faire. C'est le long jeu des technologies de l'information quantique - jusqu'à présent, presque le seul jeu auquel les informaticiens universitaires ont jamais joué, en ce qui concerne la technologie de l'information quantique. Anticipant ce jour où la technologie quantique trouvera sa place, il sera bon pour nous de continuer à poursuivre l'analyse asymptotique, en tant que ligne d'investigation dans la performance des algorithmes quantiques.

$O\left(f\left[N\right]\right)$$N$

$10^{10}$

$\approx300$

Vous ne pouvez pas ignorer les facteurs constants lorsque vous comparez le calcul quantique au calcul classique. Ils sont trop grands.

Par exemple, voici une image de quelques diapositives que j'ai présentées l'année dernière:

Les choses en bas sont des usines d'État magiques. Ils ont une empreinte de 150 000 qubits physiques. Étant donné que la porte ET utilise 150 000 qubits pendant 0,6 milliseconde, nous supposons que le volume d'espace-temps d'une porte ET quantique est de l'ordre de 90 secondes-qubit.

L'un des objectifs de mes collègues est d'utiliser 1 processeur pour 100 qubits lors de la correction d'erreurs. On pourrait donc dire que 90 secondes de qubit nécessitent 0,9 seconde de processeur. Nous avons rendu les constructions quantiques plusieurs fois plus efficaces depuis la création de l'image ci-dessus, appelons-la plutôt 0,1 cpu secondes.

(Il y a beaucoup d'hypothèses qui entrent dans ces estimations. Quel type d'architecture, taux d'erreur, etc. J'essaie seulement de transmettre une idée d'ordre de grandeur.)

Il faut 63 portes ET pour effectuer un ajout 64 bits. 63 * 0,1 cpu secondes ~ = 6 cpu secondes. Quantiquement, un ajout 64 bits coûte plus qu'une seconde CPU. Classiquement, un ajout 64 bits coûte moins cher qu'une nanoseconde CPU. Il y a facilement une différence de facteur constante de 10 milliards ici. Si vous comparez avec une machine classique parallèle, comme un GPU, les chiffres s'aggravent encore. Vous ne pouvez pas ignorer des facteurs constants avec autant de chiffres.

Par exemple, considérons l'algorithme de Grover, qui nous permet de rechercher une entrée satisfaisante pour une fonction dans les évaluations sqrt (N) de la fonction au lieu de N évaluations. Ajoutez le facteur constant de 10 milliards et déterminez où l'ordinateur quantique commence à nécessiter moins d'évaluations:

L'algorithme de Grover ne peut pas paralléliser les évaluations, et les évaluations nécessitent au moins une porte ET, donc fondamentalement, vous ne commencez à voir les avantages en termes de temps processeur que lorsque la recherche prend des dizaines de millions d'années.

À moins que nous améliorions beaucoup les facteurs constants, personne n'utilisera jamais la recherche Grover pour quelque chose d'utile. À l'heure actuelle, la situation quantique vs classique est un avantage exponentiel ou un effondrement.

Bien que d'autres réponses fournissent de bons points, je pense que je suis toujours en désaccord. Je partagerai donc mes propres réflexions sur ce point.

En bref, je pense que présenter la constante «en l'état» est au mieux une opportunité perdue. C'est peut-être le meilleur que nous puissions obtenir pour l'instant, mais c'est loin d'être idéal.

Mais d'abord, je pense qu'une brève excursion est nécessaire.

Quand avons-nous un algorithme efficace?

Quand Daniel Sank m'a demandé ce que je ferais s'il y avait un algorithme pour factoriser les nombres premiers avec un $10^6$accélération du facteur sur un ensemble de tests d'instances graves, j'ai d'abord répondu que je doute que cela soit dû à des améliorations algorithmiques, mais à d'autres facteurs (soit la machine, soit la mise en œuvre). Mais je pense que j'ai une réponse différente maintenant. Permettez-moi de vous donner un algorithme trivial qui peut factoriser de très grands nombres en quelques millisecondes et est néanmoins très inefficace :

1. Prenez un ensemble $P$ de (assez gros) nombres premiers.
2. Calculer $P^2$, l'ensemble de tous les composites avec exactement deux facteurs de $P$. Pour chaque composite, stockez la paire de nombres premiers utilisée pour le construire.
3. Maintenant, quand on lui donne une instance de $P^2$, il suffit de regarder la factorisation dans notre tableau et de la rapporter. Sinon, signalez «erreur»

J'espère qu'il est évident que cet algorithme est des ordures, car il ne fonctionne correctement que lorsque notre entrée est en $P^2$. Cependant, pouvons-nous voir cela lorsque l'algorithme est présenté sous la forme d'une boîte noire et que "par coïncidence" teste uniquement avec les$P$? Bien sûr, nous pouvons essayer de tester de nombreux exemples, mais il est très facile de faire$P$ très grand sans que l'algorithme soit inefficace sur les entrées de $P^2$ (peut-être que nous voulons utiliser une carte de hachage ou quelque chose).

Donc, il n'est pas déraisonnable que notre algorithme de détritus semble coïncider avec des accélérations «miraculeuses». Maintenant, bien sûr, il existe de nombreuses techniques de conception d'expériences qui peuvent atténuer le risque, mais peut-être des algorithmes «rapides» plus intelligents qui échouent encore dans de nombreux cas, mais pas assez d'exemples peuvent nous tromper! (Notez également que je suppose qu'aucun chercheur n'est malveillant , ce qui aggrave encore les choses!)

Donc, je répondrais maintenant: "Réveillez-moi quand il y a une meilleure mesure de performance".

Comment pouvons-nous faire mieux alors?

Si nous pouvons nous permettre de tester notre algorithme de «boîte noire» dans tous les cas, nous ne pouvons pas nous laisser berner par ce qui précède. Cependant, cela est impossible pour des situations pratiques. (Cela peut être fait dans des modèles théoriques!)

Ce que nous pouvons faire à la place est de créer une hypothèse statistique pour un certain temps d'exécution paramétré (généralement pour la taille d'entrée) pour tester cela, peut-être adapter notre hypothèse et tester à nouveau, jusqu'à ce que nous obtenions une hypothèse que nous aimons et rejeter le null semble raisonnable. (Notez qu'il y a probablement d'autres facteurs impliqués que j'ignore. Je suis pratiquement mathématicien. La conception d'expériences ne fait pas partie de mon expertise)

L'avantage de tester statistiquement un paramétrage (par exemple notre algorithme $O(n^3)$? ) est que le modèle est plus général et qu'il est donc plus difficile d'être «triché» comme dans la section précédente. Ce n'est pas impossible, mais au moins les affirmations statistiques sur le caractère raisonnable de cette décision peuvent être justifiées.

Alors, que faire des constantes?

Je pense que dire "$10^9$ speedup, wow! "est une mauvaise façon de traiter cette affaire. Mais je pense aussi que le fait de ne pas tenir compte de ce résultat est également mauvais.

Je pense qu'il est très utile de considérer la constante curieuse comme une anomalie , c'est-à-dire que c'est une affirmation qui en soi mérite une enquête plus approfondie. Je pense que créer des hypothèses basées sur des modèles plus généraux que simplement «notre algorithme prend X fois» est un bon outil pour le faire. Donc, même si je ne pense pas que nous puissions simplement prendre le contrôle des conventions CS ici, ignorer complètement le «dédain» pour les constantes est également une mauvaise idée.