Comme aucune réponse n'a été donnée, un indicateur a été défini pour demander que cette question soit convertie en wiki communautaire.
Les commentaires d'Aaron Sterling, Sasho Nikolov et Vor ont été synthétisés dans la résolution suivante, qui est ouverte à la discussion wiki communautaire:
Résolu: En ce qui concerne les algorithmes classiques qui produisent des nombres, des échantillons ou des trajectoires de simulation, une logique mathématique stricte exige que les quatre propositions suivantes soient acceptées, ou aucune d'entre elles:
- Nous pouvons exclure un algorithme classique à temps polynomial pour générer des nombres aléatoires. [1]
- "Nous pouvons exclure un algorithme classique en temps polynomial pour échantillonner la distribution de sortie d'un ordinateur quantique, sous la seule hypothèse que la hiérarchie polynomiale est infinie." [2]
- "Nous ne pouvons pas simuler [une trajectoire mécanique quantique] de la manière habituelle ... il y a trop de variables." [3]
- La thèse de Church-Turing étendue (ECT) est exclue, pour la raison rigoureuse que les algorithmes classiques ne peuvent pas générer de nombres aléatoires. [4]
Pour lancer la discussion, voici des réponses affirmatives et négatives qui, bien que défendables, sont délibérément exagérées. Un argument fortement affirmatif pourrait être:
Affirmatif: Ces quatre énoncés reflètent des théorèmes qui, pour respecter la rigueur, nous obligent à ne jamais parler d'algorithmes classiques qui génèrent des nombres aléatoires, des échantillons aléatoires ou des simulations quantiques, mais plutôt à ne parler que d'algorithmes classiques qui génèrent des nombres pseudo-aléatoires et (par extension) des échantillons pseudo-aléatoires et des simulations pseudo-quantiques.
Ceci étant compris, les quatre affirmations sont vraies. De plus, pour éviter toute ambiguïté et éviter toute confusion, les mathématiciens devraient encourager les scientifiques et les ingénieurs à apposer le préfixe "pseudo-" sur presque tous les usages de "aléatoire", "échantillon" et "simulation quantique".
Un argument fortement négatif pourrait être:
Négatif: ces déclarations (et leurs théorèmes formels associés) sont des panneaux de signalisation qui nous dirigent vers un quartier mathématique de «feu rouge» de style Lakatos où nous sommes invités à embrasser avec enthousiasme (ce que l'on pourrait appeler) les disciplines du pseudo-aléatoire , pseudo-échantillonnage et pseudo-simulation… des pratiques mathématiques amusantes pour une raison délicieusement pécheresse: elles produisent des effets mathématiques qui, selon la logique formelle, sont impossibles. Par conséquent, quoi de plus magique et de plus amusant que cette conclusion: les quatre déclarations de la résolution sont chacune formellement vraies, mais pratiquement fausses?
Ceci étant entendu, les quatre déclarations sont fausses. De plus, comme la plupart des pratiques du "hasard", de "l'échantillonnage" et de la "simulation quantique" se produisent dans cet environnement magique - dans lequel les problèmes associés à la complexité de Kolmogorov et aux évaluations oraculaires sont délibérément négligés - ce sont les mathématiciens qui devraient modifier leur utilisation.
De façon réaliste, cependant, comment les théoriciens de la complexité devraient-ils formuler leurs conclusions concernant le caractère aléatoire, l'échantillon et la simulation… d'une part, en vue de maintenir un équilibre raisonnable de clarté, concision et rigueur… et d'autre part, en vue vers le maintien d'une communication à faible bruit avec d'autres disciplines STEM? Ce dernier objectif est particulièrement important, car les capacités pratiques augmentent régulièrement dans des domaines tels que la cryptographie, les tests statistiques, l'apprentissage automatique et la simulation quantique.
Il serait très utile (et agréable aussi) de lire des réponses bien motivées, affirmatives ou négatives.
La question posée est
Quel (s) est (sont) le (s) rôle (s) généralement accepté (s) de la vérification dans les définitions théoriques de la complexité associées à l'échantillonnage, à la simulation et au test de la thèse de Church-Turing étendu (ECT)?
La réponse préférée est des références à des articles, des monographies ou des manuels qui traitent de ces questions en profondeur.
Si cette documentation s'avérait rare ou insatisfaisante, alors (après deux jours) je convertirais cette question en un wiki communautaire demandant:
Quel (s) rôle (s) raisonnable (s) et approprié (s) de vérification dans les définitions théoriques de la complexité associées à l'échantillonnage, à la simulation et au test de la thèse de Church-Turing étendu (ECT)?
Contexte
La question posée est motivée par le récent fil de discussion "Qu'est-ce que cela signifierait de réfuter la thèse de Church-Turing?" , en particulier les réponses (excellentes IMHO) données par Gil Kalai et par Timothy Chow
Dans la question posée, l'expression "définitions théoriques de la complexité appropriées et / ou acceptées" doit être interprétée comme empêchant Alice de prétentions invraisemblables comme les suivantes:
Alice: Voici mon échantillon expérimental de chiffres binaires vraiment aléatoires calculés par mon réseau optique linéaire (un photon).
Bob: Voici mon échantillon simulé de chiffres pseudo-aléatoires calculés par une machine de Turing classique.
Alice: Désolé Bob ... votre échantillon est compressible algorithmiquement, et le mien ne l'est pas. Par conséquent, mes données expérimentales démontrent que l'ECT est faux! "
En l'absence de toute association de vérification à l'échantillonnage, le raisonnement d'Alice est irréprochable. En d'autres termes, les théoriciens de la complexité devraient-ils considérer l'ECT comme ayant déjà été officiellement réfuté… il y a des décennies?
D'un point de vue pratique, les méthodes de simulation associées à l'échantillonnage de trajectoire quantique sur les espaces d'état variétaux sont de plus en plus utilisées dans de nombreuses disciplines de la science et de l'ingénierie. C'est pourquoi les définitions théoriques de la complexité de l'échantillonnage qui respectent le rôle central de la vérification (qui est indissociable de la réplicabilité) en science et en ingénierie seraient les bienvenues pour les scientifiques et les ingénieurs en exercice… surtout si ces définitions étaient accompagnées de théorèmes décrivant la complexité de calcul des échantillonnage vérifié.
Ajouté Edit: Grâce à une collaboration entre l'Université de Genève et la société id Quantique , il est parfaitement possible de réaliser cet exercice en réalité.
Voici 1024 bits aléatoires certifiés par id Quantique comme étant incompressibles sur le plan algorithmique:
0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011
Faut-il maintenant accepter la revendication: "La thèse d'ECT est réfutée"?
Sinon, quels motifs devrions-nous donner?
Réponses:
L'essentiel de la question est, étant donné que la probabilité quantique est une source de véritable hasard, comment cela affecte-t-il la thèse de Church-Turing étendue (ou efficace, ou à temps polynomial)?
La réponse est que, par conjecture, cela ne l'affecte pas. Les gens conjecturent que BPP = P, c'est-à-dire que les algorithmes randomisés peuvent être dérandomisés avec des générateurs de nombres pseudo-aléatoires avec une surcharge polynomiale. La foi dans les PRNG en remplacement du vrai hasard est une raison pour laquelle les gens croiraient la thèse étendue de Church-Turing si ce n'était pour le calcul quantique.
la source