{"id":16154,"date":"2018-07-26T08:28:51","date_gmt":"2018-07-26T07:28:51","guid":{"rendered":"http:\/\/www.oezratty.net\/wordpress\/?p=16154"},"modified":"2018-07-31T17:10:44","modified_gmt":"2018-07-31T16:10:44","slug":"comprendre-informatique-quantique-complexite","status":"publish","type":"post","link":"https:\/\/www.oezratty.net\/wordpress\/2018\/comprendre-informatique-quantique-complexite\/","title":{"rendered":"Comprendre l’informatique quantique – complexit\u00e9"},"content":{"rendered":"

Dans la partie pr\u00e9c\u00e9dente<\/a> de cette s\u00e9rie estivale sur l\u2019informatique quantique, nous avons fait le tour des principaux algorithmes quantiques connus, de leurs domaines d\u2019applications et de leur performance relative.<\/p>\n

Le calcul quantique est parfois pr\u00e9sent\u00e9 comme \u00e9tant une solution miracle aux limites du calcul sur supercalculateurs. Il permettrait de r\u00e9soudre des probl\u00e8mes dits \u201cintractables\u201d sur des ordinateurs classiques. Mais au juste, quelle est la nature des probl\u00e8mes qui peuvent \u00eatre r\u00e9solus avec un ordinateur quantique et qui ne peuvent pas l\u2019\u00eatre avec des ordinateurs classiques ? Et surtout, quelles sont les limites des ordinateurs quantiques ? Comment se situent-elles par rapport aux limites de l\u2019intelligence artificielle ?<\/p>\n

Nous allons voir que ces limites sont plut\u00f4t floues et mouvantes. Elles sont trait\u00e9es dans un champ complet et m\u00e9connu de la science, celui des th\u00e9ories de la complexit\u00e9<\/strong>. C\u2019est un monde on ne peut plus abstrait o\u00f9 les sp\u00e9cialistes parlent un langage abscons fait de P, NP, BQP et autres compl\u00e9tudes. Ils gambergent depuis pr\u00e8s d\u2019un demi-si\u00e8cle pour d\u00e9terminer si P = NP ou pas<\/strong>, une question aussi importante que le r\u00f4le exact du nombre 42 dans le fonctionnement de l\u2019Univers. C\u2019est la science des classes de complexit\u00e9 de probl\u00e8mes. Derri\u00e8re ces math\u00e9matiques de la complexit\u00e9 se cachent des consid\u00e9rations techniques mais aussi philosophiques fondamentales pour l\u2019Homme et son d\u00e9sir de toute puissance.<\/p>\n

Les classes de complexit\u00e9 de probl\u00e8mes sont des poup\u00e9es russes plus ou moins emboit\u00e9es les unes dans les autres. Elles tournent surtout autour de la question de la mont\u00e9e en charge du temps de r\u00e9solution des probl\u00e8mes en fonction de leur taille.<\/p>\n

On ne sait r\u00e9soudre dans un temps raisonnable que les probl\u00e8mes dits polynomiaux ou plus simples que les polynomiaux. Un temps polynomial est proportionnel \u00e0 une puissance donn\u00e9e de N, N \u00e9tant la dimension du probl\u00e8me \u00e0 r\u00e9soudre. L\u2019informatique quantique permet dans certaines conditions de r\u00e9soudre certains probl\u00e8mes dits exponentiels, qui croissent de mani\u00e8re exponentielle avec leur taille. Au-del\u00e0 se situent divers probl\u00e8mes inaccessibles qui rel\u00e8vent souvent de simulations complexes ou de r\u00e9solutions par force brute. Bref, les ordinateurs quantiques ne pourront pas r\u00e9soudre tous les probl\u00e8mes qui nous passeront par la t\u00eate, m\u00eame le jour o\u00f9 l\u2019on pourra aligner des gazillions de qubits avec un taux d\u2019erreur infinit\u00e9simal.<\/p>\n

Ces limites ont un impact indirect sur les pr\u00e9visions concernant la cr\u00e9ation d\u2019intelligences artificielles omniscientes capables de transcender le raisonnement humain et de r\u00e9soudre tous les probl\u00e8mes. Ces hypoth\u00e9tiques AGI (Artificial General Intelligence) seront limit\u00e9es par les donn\u00e9es et concepts qui les alimentent et par l\u2019impossibilit\u00e9 de r\u00e9soudre certains probl\u00e8mes complexes, notamment ceux qui rel\u00e8vent de la pr\u00e9vision et de la simulation et qui reposent sur la force brute plut\u00f4t sur des astuces algorithmiques permettant d\u2019aboutir rapidement \u00e0 la solution.<\/p>\n

Le calcul ultime n\u2019existe donc pas encore et l\u2019Homme continuera \u00e0 faire face \u00e0 l\u2019impossible et ne pourra pas r\u00e9soudre tous les probl\u00e8mes complexes qu\u2019il rencontrera ! Bref, le calcul quantique ne permet pas de dominer la nature et de mettre en \u00e9quation l\u2019Univers et d\u2019en pr\u00e9voir le fonctionnement au quantum pr\u00e8s. Le hasard, l\u2019impr\u00e9vu et le libre arbitre continueront de jouer un r\u00f4le dans un monde tr\u00e8s ind\u00e9terministe et c\u2019est tant mieux comme cela. C\u2019est une petite le\u00e7on d\u2019humilit\u00e9 pour l\u2019Homme que de passer son temps \u00e0 d\u00e9couvrir des limites scientifiques \u00e0 ses besoins de contr\u00f4le !<\/p>\n

Classes de complexit\u00e9 de probl\u00e8mes<\/strong><\/p>\n

Pour rentrer dans ce sujet, il faut en passer par d\u00e9finir les grandes classes de probl\u00e8mes par niveau de complexit\u00e9. Elles font partie d\u2019un champ entier de la logique et des math\u00e9matiques qui agite un petit monde de sp\u00e9cialistes. Me voil\u00e0 donc une fois encore amen\u00e9 \u00e0 devoir simplifier la complexit\u00e9, et cette fois-ci, au sens litt\u00e9ral du terme.<\/p>\n

Dans la pratique, les classes de complexit\u00e9 d\u00e9crivent des probl\u00e8mes que l\u2019on r\u00e9sout par force brute en testant plusieurs combinatoires. Ils ne rel\u00e8vent pas d\u2019\u00e9quations math\u00e9matiques simples que l\u2019on r\u00e9sout avec des formules permettant d\u2019aboutir directement \u00e0 la solution comme on le fait pour pr\u00e9dire la position des plan\u00e8tes en s\u2019appuyant sur les lois de la m\u00e9canique newtonienne.<\/p>\n

Les classes de probl\u00e8mes font appel \u00e0 une notion de machines d\u00e9terministes et non d\u00e9terministes de Turing. De quoi s\u2019agit-il ? Les machines de Turing sont les mod\u00e8les conceptuels d\u2019ordinateurs cr\u00e9\u00e9s par Alan Turing avant la seconde guerre mondiale. Elles mod\u00e9lisent les traitements informatiques en s\u2019appuyant sur la notion de programmes et de donn\u00e9es, incarn\u00e9es par des rouleaux de papier continus, le premier pour le programme, le second pour les donn\u00e9es en entr\u00e9e et le troisi\u00e8me pour g\u00e9n\u00e9rer les r\u00e9sultats (sch\u00e9ma ci-dessous<\/em>, source<\/a>). Des \u00e9tudiants d\u2019un master de l\u2019ENS Lyon ont r\u00e9alis\u00e9 une machine de Turing en Lego en 2012 \u00e0 l\u2019occasion du centenaire de la naissance d\u2019Alan Turing (vid\u00e9o<\/a>) et ce n\u2019\u00e9tait pas la seule du genre (vid\u00e9o<\/a>) ! Un Anglais en a aussi r\u00e9alis\u00e9 une en bois en 2015 (vid\u00e9o<\/a>). Voil\u00e0 de quoi s\u2019\u00e9duquer ludiquement !<\/p>\n

\"Machine<\/a><\/p>\n

Le mod\u00e8le th\u00e9orique de Turing est utilis\u00e9 depuis longtemps pour d\u00e9finir les classes de probl\u00e8mes que l\u2019on peut r\u00e9soudre ou pas avec un ordinateur. Les ordinateurs sont tous m\u00e9taphoriquement des machines de Turing, reproduisent cette logique en lisant des instructions de programmes et en g\u00e9rant les donn\u00e9es en m\u00e9moire vive (RAM) ou en stockage persistent (disque dur, SSD, \u2026). Est associ\u00e9e \u00e0 la notion de machine de Turing celle de la th\u00e8se de Church-Turing<\/strong>, des noms d\u2019Alonzo Church et Alan Turing selon laquelle il existe une \u00e9quivalence entre probl\u00e8mes de calcul r\u00e9alisable \u00e0 la main et avec des ressources non limit\u00e9es, ceux qui sont traitables avec une machine de Turing et les ceux qui peuvent \u00eatre r\u00e9solus avec des fonctions dites r\u00e9cursives.<\/p>\n

Dans une machine d\u00e9terministe, la s\u00e9quence des actions \u00e0 r\u00e9aliser est pr\u00e9d\u00e9finie et s\u00e9quentielle. Dans le mod\u00e8le conceptuel de machine de Turing non d\u00e9terministe, les r\u00e8gles de calcul peuvent imposer de r\u00e9aliser plusieurs op\u00e9rations diff\u00e9rentes pour chaque situation \u00e9valu\u00e9e. En gros, en explorant plusieurs voies en parall\u00e8le et en cherchant une r\u00e9ponse positive \u00e0 une composante d\u2019algorithme et en fermant des boucles de tests parall\u00e8les une fois les sous-solutions trouv\u00e9es.<\/p>\n

\"Non<\/a><\/p>\n

C\u2019est plus ou moins le mod\u00e8le de navigation dans l\u2019arbre de d\u00e9cision de la version 2017 d\u2019AlphaGo, dite AlphaGo Zero<\/a>, qui \u00e9value dans un r\u00e9seau de neurones diff\u00e9rents sc\u00e9narios de jeu. Bref, une machine non d\u00e9terministe augmente la combinatoire de calcul par rapport \u00e0 une machine d\u00e9terministe. Et cette combinatoire passe de polynomiale \u00e0 exponentielle. La force d\u2019AlphaGo Zero est d\u2019utiliser des r\u00e9seaux de neurones en quelque sorte r\u00e9cursif pour r\u00e9duire le nombre de branches de l\u2019arbre de d\u00e9cision \u00e0 tester pour sortir partiellement de la fatalit\u00e9 exponentielle de ce jeu.<\/p>\n

Les classes de complexit\u00e9 g\u00e9n\u00e9riques<\/strong><\/p>\n

Le niveau de complexit\u00e9 s\u2019entend vis \u00e0 vis du temps de calcul n\u00e9cessaire et de l\u2019espace m\u00e9moire n\u00e9cessaire pour ces calculs. En r\u00e8gle g\u00e9n\u00e9rale, on est bloqu\u00e9 par le temps de calcul avant de l\u2019\u00eatre par la capacit\u00e9 m\u00e9moire. L\u2019association d\u2019un probl\u00e8me \u00e0 une classe de complexit\u00e9 est li\u00e9e \u00e0 la performance du meilleur algorithme connu pour r\u00e9soudre ledit probl\u00e8me.<\/p>\n

Les niveaux de classes de probl\u00e8mes dans les th\u00e9ories de la complexit\u00e9 reposent souvent sur des mod\u00e8les de boite noire ou d\u2019oracles \u00e0 qui un syst\u00e8me pose des questions et obtient des r\u00e9ponses en fonctions des donn\u00e9es fournies. C\u2019est une logique de \u201cforce brute\u201d et de scan d\u2019hypoth\u00e8ses. La combinatoire \u00e0 tester est plus ou moins grande selon les classes de probl\u00e8mes.<\/p>\n

\"\"<\/a><\/p>\n

Voici donc ces classes par niveau croissant de complexit\u00e9 sachant que nous passerons le plus de temps sur les classes NP et NP Complet.<\/p>\n

L<\/strong> : ou LSPACE, ou DLOGSPACE, qui d\u00e9finit la classe des probl\u00e8mes que l\u2019on peut r\u00e9soudre \u00e0 une \u00e9chelle logarithmique de m\u00e9moire consomm\u00e9e et sur une machine de Turing d\u00e9terministe. Bref, sur un ordinateur traditionnel. C\u2019est le genre de classe id\u00e9ale ! La complexit\u00e9 de calcul diminue rapidement avec la taille du probl\u00e8me. Malheureusement, tr\u00e8s peu de probl\u00e8mes complexes sont dans cette classe l\u00e0. On y trouve notamment les requ\u00eates dans des bases de donn\u00e9es relationnelles pr\u00e9alablement index\u00e9es, les recherches de s\u00e9quences d\u2019ADN et d\u2019une mani\u00e8re g\u00e9n\u00e9rale les techniques de recherche utilisant des pointeurs et qui optimisent l\u2019utilisation de la m\u00e9moire des ordinateurs.<\/p>\n

NL<\/strong> : la classe des probl\u00e8mes r\u00e9solus \u00e0 une \u00e9chelle logarithmique sur une machine non-d\u00e9terministe. Les logiciens cherchent toujours \u00e0 savoir si si L=NL ! Cela pourrait durer quelque temps. Cela les occupe moins que P=NP.<\/p>\n