Que sait-on de l'efficacité d'un calcul fiable?

14

Dans quelle mesure le problème suivant a-t-il été étudié dans TCS? (Je m'excuse si l'énoncé du problème vous semble vague!)

Étant donné un modèle de calcul MC (Turing Machine, Cellular Automata, Kolmogorov-Uspenskii Machine ... etc.) et un modèle de bruit qui pourraient affecter le calcul de MC, existe-t-il un moyen de récupérer des erreurs causées par ce bruit dans un moyen efficace ? Par exemple, supposons qu'un certain type de bruit affecte une machine de Turing M, pourrait-on imaginer une machine de Turing M 'qui simule M sans coût majeur et est fiable (ce qui signifie que M' est tolérant à ce bruit)?

Il semble que certains modèles de calcul soient meilleurs que d'autres pour ce faire: les automates cellulaires par exemple. Des résultats si le bruit est remplacé par un modèle adversaire?

Désolé pour la balise! Je n'ai pas assez de réputation pour mettre une étiquette appropriée (informatique fiable, informatique tolérante aux pannes ... etc.)

user2471
la source
5
Je pense que vous demandez essentiellement ce qui se fait dans le domaine de l'informatique à tolérance de pannes.
Tsuyoshi Ito,

Réponses:

14

Bien qu'il existe certaines techniques qui peuvent être appliquées à la tolérance aux pannes pour tous les modèles, la résistance d'un modèle de calcul à la tolérance aux pannes dépend du modèle. Par exemple, Peter Gacs a fait pas mal de recherches sur la tolérance aux pannes sur les automates cellulaires, et il montre que (avec beaucoup de travail) vous pouvez construire des automates cellulaires tolérants aux pannes.

Von Neumann a prouvé qu'en utilisant la redondance, vous pouviez construire un ordinateur fiable à partir de composants peu fiables en utilisant uniquement des frais généraux logarithmiques.

Pour le calcul quantique, les circuits quantiques peuvent être rendus tolérants aux pannes avec un surdébit polylogarithmique ( surdébit, où la recherche de la valeur correcte de c est toujours ouverte). Une autre question ouverte pour le calcul quantique est de savoir si le calcul quantique adiabatique peut être rendu tolérant aux pannes d'une manière physiquement raisonnable (physiquement raisonnable signifie qu'il est possible que la méthode mène à un ordinateur quantique adiabatique évolutif; par exemple, vous n'êtes pas autorisé à prendre le température à 0 lorsque la taille du calcul augmente).logcnc

Peter Shor
la source
Merci Peter! Je pense que Gacs a réussi à construire un boîtier extrêmement compliqué en 1 dimension qui présente une tolérance aux pannes (réf. Cs.bu.edu/faculty/gacs/papers/long-ca-ms.pdf ). Quant à Von Neumann, la surcharge logarithmique est-elle dans le nombre de composants ou les fils dans chaque composant?
user2471
Pour von Neumann, vous devriez pouvoir l'arranger dans les deux sens. Je pense cependant qu'il parlait du nombre de composants. Pour le résultat Gacs à 1 dimension, il présente certains aspects de la tolérance aux pannes, mais je n'appellerais pas cela une vraie tolérance aux pannes.
Peter Shor
Pourquoi n'appeleriez-vous pas l'exemple 1 Gacs tolérant aux pannes?
user2471
J'ai probablement mal parlé. L'exemple unidimensionnel de Gacs est capable de se souvenir d'un bit. Il s'agit peut-être d'une mémoire à tolérance de pannes, mais ce n'est pas un calcul à tolérance de pannes. De plus, si je me souviens bien, ce 1 bit ne reste pas vraiment au même endroit dans l'exemple de Gacs, mais est codé par un nombre toujours croissant de cellules.
Peter Shor
Je peux me tromper, mais Gacs n'utilise-t-il pas un certain temps de calcul sur les données encodées (sans avoir besoin de décoder / encoder à chaque fois)? ref cs.bu.edu/faculty/gacs/papers/long-ca-ms.pdf section 5.2 Stockage d'informations et calcul dans diverses dimensions
user2471
2

Je pense que le travail lié à l' auto-stabilisation est proche de l'esprit de votre question.

Un système auto-stabilisant récupère de toute corruption de la RAM.

Jukka Suomela
la source
2

La question posée est "Existe-t-il un moyen de se remettre des erreurs causées par le bruit [quantique] de manière efficace?" et la réponse de Peter Shor couvre admirablement un moyen efficace de répondre à cette question, à savoir la conception d'ordinateurs quantiques tolérants aux pannes.

Un autre moyen efficace est très couramment rencontré dans la pratique de l'ingénierie. Nous raisonnons "Si le bruit est suffisamment grand pour qu'aucun calcul quantique ne soit possible, alors peut-être que la dynamique du système peut être simulée avec des ressources classiques en P."

En d'autres termes, nous pouvons souvent «récupérer de manière efficace» du bruit en reconnaissant que le bruit nous fournit un service important, en réduisant de façon exponentielle la complexité informatique de la simulation des systèmes classiques et quantiques.

La littérature sur les approches de simulation dynamique centrées sur le bruit est vaste et croissante; une référence récente dont les théorèmes sont à la fois physiquement motivés et agréablement rigoureux, et qui comprend de nombreuses références à la littérature plus large, est les limites supérieures de Plenio et Virmani sur les seuils de tolérance aux pannes des ordinateurs quantiques bruyants basés sur Clifford. (arXiv: 0810.4340v1).

Les dynamiques classiques utilisent un langage très différent dans lequel les mécanismes de bruit s'appellent le nom technique des thermostats ; Frenkel et Smit comprennent la simulation moléculaire: des algorithmes aux applications (1996) fournit une introduction mathématique de base.

Lorsque nous transcrivons des thermostats classiques et quantiques dans le langage de la dynamique géométrique, nous constatons (sans surprise) que les méthodes classiques et quantiques pour exploiter le bruit pour augmenter l'efficacité de la simulation sont essentiellement identiques; que leurs littératures respectives se référent si rarement les unes aux autres est en grande partie un accident de l'histoire qui a été soutenu par des obstructions de notation.

Moins rigoureusement mais plus généralement, les résultats ci-dessus mettent en lumière les origines de la théorie de l'information quantique d'une règle heuristique largement adoptée par les chimistes, les physiciens et les biologistes, selon laquelle tout système classique ou quantique en contact dynamique avec un bain thermal est susceptible de prouver simulable avec des ressources de calcul en P à toutes fins pratiques (FAPP).

Les exceptions à cette heuristique, à la fois classiques et quantiques, représentent d'importants problèmes ouverts. Leur nombre diminue de façon frappante d'année en année; l' évaluation critique biennale de la prévision des structures (CASP) fournit une mesure objective de cette amélioration.

Les limites fondamentales de ce progrès "plus que Moore" entraîné par le bruit et sur plusieurs décennies sont actuellement mal connues. Inutile de dire qu'à long terme, notre compréhension constante de ces limites nous rapprochera de la construction d'ordinateurs quantiques, tandis qu'à court terme, ces connaissances nous aident grandement à simuler efficacement des systèmes qui ne sont pas des ordinateurs quantiques. Quoi qu'il en soit, ce sont de bonnes nouvelles.

John Sidles
la source
2

Il semble que Gacs soit en train de construire une machine Turing tolérante aux pannes. Jetez un œil à ceci: http://arxiv.org/abs/1203.1335

user8719
la source
1

Les modèles de calcul quantique traitent explicitement du bruit et des moyens de rendre les calculs résistants aux erreurs introduites par ce vecteur. Le calcul quantique, curieusement, peut être fait en avant et en arrière (par la nature des transformations de QM Hadamard et l'indépendance temporelle de l'hamiltonien) - le "non-calcul" est une technique utilisée pour endiguer le flot de telles erreurs.

Sur les «vrais» ordinateurs - serveurs d'entreprise - il y a une petite mais réalisable chance qu'un peu de RAM soit lu de manière incorrecte. La théorie de la détection et de la correction des codes d'erreur peut être appliquée au niveau du mot machine pour détecter et corriger de telles erreurs de 1 bit (sans trop de surcharge). Et en fait, de nombreux serveurs d'entreprise qui ont des opérations critiques invitent un petit bit de parité sur chaque mot de RAM.

Bien que loin d'être une preuve, il me semble que les schémas de codage de correction d'erreur standard pourraient fonctionner avec presque tous les automates théoriques (les automates cellulaires sont suspects) avec seulement un ralentissement polynomial (en fait linéaire?).

Ross Snider
la source
il existe certainement des modèles de calcul où la correction d'erreur arbitraire n'est pas possible (c'est-à-dire où un théorème de tolérance aux pannes ne peut pas être prouvé). N'est-ce pas la raison pour laquelle nous étudions rarement les ordinateurs analogiques?
Artem Kaznatcheev
5
Les ordinateurs analogiques sont parfaitement capables de calculer de manière tolérante aux pannes, mais pour autant que je sache uniquement en simulant des ordinateurs numériques (ou pensiez-vous que votre ordinateur contient de vrais bits, et non des électrons et des tensions?).
Peter Shor
Permettez-moi d'ajouter une mise en garde à mon commentaire précédent. Je suis sûr qu'il est possible de faire un modèle restreint de calcul analogique où la tolérance aux pannes n'est pas possible, donc Artem a en effet un bon point sur la tolérance aux pannes qui ne s'applique pas à tous les modèles de calcul.
Peter Shor
1
Au niveau classique et quantique, aucune conception informatique n'est tolérante aux pannes contre toutes les classes de bruit, d'imprécision et d'instabilité. De plus, l'histoire de la technologie fournit de nombreux exemples dans lesquels l'offre de mécanismes naturels de bruit a été sous-estimée; la "Liste des instabilités du plasma" hébergée sur Wikipedia en 56 points est un résumé d'une page des raisons pour lesquelles les feuilles de route de l'énergie de fusion des années 1950 et 1990 ont échoué. Alors que les architectures de calcul classique et quantique fusionneront dans les prochaines décennies, il sera très intéressant de voir la liste des mécanismes connus de bruit, d'imprécision et d'instabilité s'allonger.
John Sidles
1

Il existe un certain travail sur les structures de données et algorithmes dits "résilients" (arbres de recherche, compteurs, dictionnaire). Le modèle est celui d'une RAM avec l'hypothèse que jusqu'àkles bits peuvent être modifiés par un adversaire à tout moment. De nombreux registres ne peuvent constamment pas être modifiés par l'adversaire. Selon le paramètrek, vous pouvez obtenir des algorithmes qui fonctionnent toujours correctement et dont la durée d'exécution dépend de k c'est mieux que de courir kcopies indépendantes d'un algorithme. Un récent discours invité de G. Italiano devrait donner un aperçu: Algorithmes résilients et structures de données (je viens de trouver cet article et je ne l'ai pas encore lu moi-même, mais je suis convaincu que c'est un bon pointeur).

Riko Jacob
la source