Entropie et complexité de calcul

12

Il y a un chercheur montrant que l'effacement d'un bit doit consommer de l'énergie, maintenant y a-t-il des recherches sur la consommation moyenne d'énergie d'un algorithme avec une complexité de calcul ? Je suppose que la complexité de calcul F ( n ) est corrélée à la consommation moyenne d'énergie, j'espère pouvoir obtenir une réponse ici.F(n)F(n)

cc.complexity-theory reference-request it.information-theory quantum-information statistical-physics XL _At_Here_There
la source
Un lien avec le document en question améliorerait cette question.
Stella Biderman
@StellaBiderman merci, mais je n'ai trouvé aucun lien dans votre commentaire.
XL _At_Here_There
Je ne sais pas de quel papier / chercheur vous parlez. Je suggère que vous fournissiez I
Stella Biderman le
1
@StellaBiderman J'ai mal compris vos commentaires, en fait je viens de lire un texte expliquant "l'effacement du bit doit consommer de l'énergie" dans la complexité de Kolmogorov et son application par Viatanyi et Li. Je pense que je n'ai pas lu d'autres articles et livres sur le sujet
XL _At_Here_There

Réponses:

16

Oui, mais la plupart des travaux jusqu'à présent (sauf très récemment, voir ci-dessous) ont porté sur la transformation de calculs irréversibles en calculs réversibles, espérant ainsi éviter toute génération d'entropie. (Remarque: il existe une différence importante entre l' énergie nécessaire pour exécuter un calcul et l' entropie générée par le calcul et rejetée dans l'environnement, généralement sous forme de chaleur.)

kTln⁡(2)

Plus récemment,

Demaine, Lynch, Mirano et Tyagi. Algorithmes écoénergétiques , 2016.

étudié des algorithmes partiellement réversibles - c'est-à-dire, si vous êtes prêt à payer une certaine entropie, pour des tâches algorithmiques standard, on peut améliorer les simulations générales irréversibles à réversibles mentionnées ci-dessus. L'informatique réversible a toute une communauté de chercheurs qui s'y consacrent, à savoir. la conférence sur l' informatique réversible , qui en est à sa dixième année.

ln⁡(2)

Kolchinsky & Wolpert, Dependence of dissipation on the initial distribution over states . J. Stat. Mech. 2017 ( lien arXiv )

(et références y contenues).

Nous avons organisé un atelier à ce sujet au Santa Fe Institute en août 2017 (où vous pouvez voir les noms de certains chercheurs et parler de titres pertinents), et cela soulève un tout nouvel ensemble de questions en physique et en complexité de calcul thermodynamique.

Joshua Grochow
la source
La thèse de Turing Machine ou Church-Turing peut être régie ou restreinte par la loi physique, de sorte que la possibilité d'implémenter le calcul quantique ou la communication quantique peut être déduite de la loi de physique, comme la deuxième loi de la mécanique statistique, la relativité générale. Donc, je suppose que s'il y a un résultat sur le lien entre la thèse et la loi de physique
XL _At_Here_There
Et il semble que le site de physique ne s'intéresse pas aux sujets de ce genre.
XL _At_Here_There
@XL_at_China: Il y a une "thèse de Church-Turing physique", mais cela n'a pas grand-chose à voir avec la deuxième loi, car la thèse de Church-Turing et sa version physique sont à peu près ce qui est calculable, pas n'importe quel type d'estimations quantitatives , mais la deuxième loi est une déclaration quantitative. De plus, bien qu'il n'y ait peut-être pas encore eu une tonne de publications à ce sujet, à notre atelier, les physiciens semblaient définitivement intéressés.
Joshua Grochow
J'avais essayé de trouver le lien il y a plusieurs années, mais je n'ai obtenu aucun résultat. Intuitivement, la calculabilité semble devoir être liée à la deuxième loi thermodynamique. Et considérant Turing Machine en terme de relativité générale, le problème devient intéressant. Mais je ne connais aucun physicien intéressé par un tel problème.
XL _At_Here_There
Et pourrions-nous publier une question connexe sur la physique du site et en discuter avec un physicien?
XL _At_Here_There