Les ordinateurs analogiques et la thèse de Church-Turing

J'aimerais citer Nielsen & Chuang, Quantum Computation and Quantum Information, édition du 10e anniversaire, page 5 (c'est moi qui souligne):

Une classe de défis à la forte thèse de Church-Turing vient du domaine du calcul analogique. Au cours des années qui se sont écoulées depuis Turing, de nombreuses équipes différentes de chercheurs ont remarqué que certains types d'ordinateurs analogiques peuvent résoudre efficacement des problèmes qui ne semblent pas avoir de solution efficace sur une machine Turing. À première vue, ces ordinateurs analogiques semblent violer la forme forte de la thèse de Church-Turing. Malheureusement pour le calcul analogique, il s'avère que lorsque des hypothèses réalistes sur la présence de bruit dans les ordinateurs analogiques sont faites, leur puissance disparaît dans tous les cas connus; ils ne peuvent pas résoudre efficacement les problèmes qui ne peuvent pas être résolus efficacement sur une machine de Turing.Cette leçon - que les effets du bruit réaliste doivent être pris en compte dans l'évaluation de l'efficacité d'un modèle de calcul - a été l'un des grands premiers défis du calcul quantique et de l'information quantique, un défi relevé avec succès par le développement d'une théorie de l'erreur quantique -correction des codes et calcul quantique tolérant aux pannes. Ainsi, contrairement au calcul analogique, le calcul quantique peut en principe tolérer une quantité finie de bruit et conserver ses avantages de calcul.

S'agit-il d'une déclaration selon laquelle le bruit évolue plus rapidement qu'une puissance de la taille du problème, ou quelqu'un peut-il m'orienter dans la bonne direction pour que je puisse savoir si ces limites de mise à l'échelle sont fondamentales ou simplement un «problème d'ingénierie»?

Pour être clair, je demande si les ordinateurs analogiques ne peuvent pas battre les machines Turing en termes d'efficacité en raison du bruit.

Tout d'abord, les auteurs semblent confondre deux thèses différentes: la thèse Church – Turing et la thèse Cook – Karp. Le premier concerne ce qui est calculable et le second concerne ce qui est calculable efficacement .

Selon la thèse de Cook – Karp, tous les modèles de calcul raisonnables «forts» sont polynomialement équivalents, en ce sens qu'ils se simulent tous polynomialement. De manière équivalente, chaque modèle de calcul raisonnable peut être simulé polynomialement par une machine de Turing. Les ordinateurs quantiques sont un contre-exemple de cette thèse, car ils semblent être exponentiellement plus efficaces que les ordinateurs classiques. Cependant, ils ne sont pas un contre-exemple de la thèse de Church-Turing, c'est-à-dire qu'en utilisant des ordinateurs quantiques, vous ne pouvez pas calculer tout ce que vous ne pouvez pas déjà calculer avec une machine de Turing. Nous pouvons également formuler une thèse de Cook – Karp mise à jour, déclarant que tous les modèles de calcul physiquement réalisables sont simulés polynomialement par des ordinateurs quantiques.

Plusieurs modèles physiques de calculs ont été proposés comme contestant ces thèses, mais à l'examen, ils semblent tous ne pas violer la thèse de Church-Turing, ou ne pas être plus puissants que le calcul quantique. Scott Aaronson propose de considérer cette situation comme une "loi de la nature". Cependant, pour autant que je sache, il n'y a pas d'arguments théoriques soutenant ces thèses autres que l'argument inductif selon lequel tous les modèles qui ont été proposés se sont révélés conformes à ces thèses.

ce passage (écrit il y a plus d'une décennie) est en effet essentiel et invoque pas mal de connaissances de base et anticipe très bien certaines orientations de recherche futures. il fait allusion au domaine de l' hypercalcul qui est parfois en marge du TCS, car il étudie des modèles de calcul prétendument "plus puissants" que les machines de Turing. le point intéressant à propos des machines de Turing ici est qu'elles n'ont aucun bruit, donc dans un sens l'informatique est fondée sur cette idéalisation qui à certains égards est physiquement irréaliste. et les systèmes électroniques imitent ce silence en tant que principe de conception, il est toujours présent dans la dynamique des puces de bas niveau mais très efficacement résumé dans les conceptions de niveau supérieur qui limitent tous les signaux électriques à des bits idéaux de 0/1. re ceci:

Cette leçon - que les effets du bruit réaliste doivent être pris en compte dans l'évaluation de l'efficacité d'un modèle de calcul - a été l'un des grands premiers défis du calcul quantique et de l'information quantique, un défi relevé avec succès par le développement d'une théorie de l'erreur quantique -correction des codes et calcul quantique tolérant aux pannes.

il semblerait que certaines de leurs affirmations semblent rétrospectivement prématurément optimistes. il est vrai que de grandes quantités de théorie ont été conçues dans les codes de correction d'erreur QM. cependant, très peu a été testé et vérifié expérimentalement. il y a des scientifiques / experts qui soupçonnent / émettent l'hypothèse qu'il peut y avoir des lois physiques qui exigent que le bruit soit mis à l'échelle d'une «mauvaise» manière pour les grands systèmes quantiques à n bits. c'est donc un domaine de recherche active et de controverse. en fait, il s'agit d'un domaine clé de discorde pour deux conceptions / approches informatiques QM de premier plan, l'une par les systèmes DWave et l'autre par le groupe Martinis UCSB / Google .

Pour être clair, je demande si les ordinateurs analogiques ne peuvent pas battre les machines Turing en termes d'efficacité en raison du bruit.

c'est la grande question n'est-ce pas? pour essayer de répondre à cela, considérons qu'il existe des systèmes analogiques classiques et les systèmes quantiques plus récemment envisagés . pour les systèmes classiques, le consensus général est tel que souligné par Nielsen / Chuang, qu'il existe des modèles théoriques qui "semblent" plus puissants mais quand le bruit est correctement pris en compte, cet "avantage" théorique "fond". en d'autres termes, proposer l'existence de systèmes informatiques analogiques "fondamentalement plus rapides théoriquement" que les systèmes électroniques déjà construits semble presque violer les lois de la physique / thermodynamique.

Cependant, la question de l'informatique QM est beaucoup plus une question ouverte et dépend (comme ils l'anticipent quelque peu) de la nature du bruit QM et de sa capacité à être expérimentalement / contrôlé, comme cela a été supposé et fait l'objet d'une enquête active.

il y a une analyse plus approfondie de ces questions dans le document Aaronsons NP-complete Problems and Physical Reality . l'aperçu sceptique se trouve dans Dyakonov Prospects for quantum computing: extrêmement douteux .