Chapitre 1.
Atomes et espace vide
Chapitre 2.
ensemble
Chapitre 3.
Gödel, Turing et leurs camarades
Chapitre 4.
Esprit et machine
Chapitre 5.
théorie de la complexité du Paléozoïque
Chapitre 6.
P et NP, leurs camarades
Chapitre 7.
l'aléatoire
Chapitre 8.
Cryptage
Chapitre 9.
quantum
Chapitre 10.
Informatique quantique
Chapitre 11.
Penrose
Chapitre 12.
Perte de connexion et variables cachées
Chapitre 13.
preuve
Chapitre 14.
Quelle est la taille d'un état quantique ?
Chapitre 15.
Scepticisme à l'égard de l'informatique quantique
Chapitre 16.
apprentissage
Chapitre 17.
Preuves interactives, bornes inférieures des circuits et quelques autres sujets
Chapitre 18.
Jouer avec le principe anthropique
Chapitre 19.
libre volonté
Chapitre 20.
voyage dans le temps
Chapitre 21.
Cosmologie et complexité
Chapitre 22.
Posez n'importe quelle question

Public cible de ce livre

Il est facilement accessible aux lecteurs ayant une formation scientifique ou aux étudiants se spécialisant en physique, en informatique, en mathématiques ou en philosophie.

Structure de ce livre

Le chapitre 1 remonte aussi loin que possible jusqu'aux « origines » et commence par une histoire sur le philosophe grec antique Démocrite.
Pour résumer les idées de Démocrite, telles qu'elles ressortent des documents qui nous sont parvenus, tous les phénomènes naturels résultent principalement d'interactions complexes entre quelques types de minuscules « atomes » qui tourbillonnent dans l'espace vide.

Les chapitres 2 et 3 déplacent brièvement l'attention de la discussion et expliquent les mathématiques, la connaissance la plus profonde que nous possédions, qui ne repose pas sur des « faits inconnus » concernant le monde physique.
Nous commencerons par examiner la théorie des ensembles, la logique et la théorie de la calculabilité, qui sont les domaines des mathématiques qui ont été jusqu'à présent les moins influencés par la physique.
Dans ce cours, nous présentons les grandes découvertes de Cantor, Frege, Gödel, Turing, Church et Cohen, qui vous aideront à comprendre le domaine du raisonnement mathématique.
De plus, en démontrant pourquoi tous les domaines des mathématiques ne peuvent pas être réduits à une « certaine procédure mécanique », il explique dans quelle mesure la réduction est possible et ce que signifie exactement l'expression « procédure mécanique ».

Le chapitre 4 examine le débat fastidieux sur la question de savoir si l'esprit humain suit lui aussi une « procédure régulière et mécanique ».
Le chapitre 5 présente la théorie de la complexité computationnelle, une cousine moderne de la théorie de la calculabilité.
Cette théorie joue un rôle important dans les chapitres suivants.
Nous montrerons notamment comment la complexité computationnelle peut être utilisée pour transformer de « profonds mystères philosophiques » tels que les limites de la perception en défis mathématiques incroyablement difficiles qui reflètent bon nombre des choses mêmes que nous considérons comme des limites de la perception.
Des énigmes mathématiques comme celles-ci peuvent contenir la plupart des informations que nous souhaitons obtenir.
Un exemple représentatif de cette transformation est le problème P contre NP.
Ceci est expliqué au chapitre 6.


Le chapitre 7 présente diverses utilisations de l'aléatoire classique dans la complexité computationnelle ainsi que dans d'autres domaines, en guise d'échauffement pour l'informatique quantique.
Le chapitre 8 présente l'histoire de la façon dont le concept de complexité computationnelle a été appliqué à la théorie et aux applications de la cryptographie au début des années 1970, ce qui a conduit à des résultats révolutionnaires.
Le chapitre 9 présente le point de vue de l'auteur selon lequel la mécanique quantique est une « théorie généralisée des probabilités ».
Le chapitre 10 présente les fondements de la théorie quantique du calcul, qui est le domaine d'expertise de l'auteur et qui est né de la combinaison de la mécanique quantique et de la théorie de la complexité computationnelle.


Le chapitre 11 prend le temps de critiquer les idées de Sir Roger Penrose.
Lord Penrose est célèbre pour avoir soutenu que le cerveau humain n'est pas seulement un ordinateur quantique, mais un ordinateur gravitationnel quantique.
Ainsi, les humains peuvent résoudre des problèmes incalculables par Turing, et le théorème d'incomplétude de Gödel est présenté comme la base de cette capacité.
Dans ce processus, nous examinerons si nous pouvons trouver une part de vérité dans la conjecture de Penrose.


Le chapitre 12 examine, un par un, ce que l'auteur considère comme les problèmes fondamentaux des concepts de la mécanique quantique.
Le problème n'est pas que l'avenir soit indéterministe (bien que cela soit acceptable), mais que le passé l'est également.
Examinons deux réactions contrastées à cela.
L'une est la plus courante chez les physiciens, invoquant la décohérence et la flèche effective du temps dans la deuxième loi de la thermodynamique, et l'autre repose sur des « théories à variables cachées » telles que la dynamique de Bohm.
Même si vous n'adhérez pas à la théorie des variables cachées, je pense qu'elle soulève des questions mathématiques très intéressantes.

Le chapitre 13 introduit de nouveaux concepts en matière de preuve mathématique (tels que la preuve probabiliste et la preuve à divulgation nulle de connaissance).
Et nous appliquons cela pour comprendre la complexité computationnelle de la théorie des variables cachées.
Au chapitre 14, nous estimons la taille des états quantiques.
Autrement dit, nous examinons s'il encode une quantité exponentielle d'informations classiques.
Examinons cette question dans le cadre du débat sur l'interprétation quantique et des recherches récentes en théorie de la complexité sur la preuve quantique et le conseil quantique.

Le chapitre 15 examine les arguments sceptiques contre l'informatique quantique.
Les sceptiques ne disent pas que construire un ordinateur quantique pratique est difficile (ce que tout le monde reconnaît comme vrai), mais plutôt que c'est fondamentalement impossible pour plusieurs raisons fondamentales.
Le chapitre 16 présente le problème de l'induction de Hume.
Ceci nous amène à discuter des dernières découvertes de la recherche sur la théorie de l'apprentissage quantique et l'apprentissage des états quantiques.

Le chapitre 17 introduit plusieurs résultats novateurs liés aux versions classiques et quantiques des systèmes de preuve interactifs (par exemple, IP = PSPACE, QIP = PSPACE), mais se concentre sur les bornes inférieures des circuits non relativisants qui peuvent éclairer le problème P vs. NP.
Le chapitre 18 présente le célèbre principe anthropique et l'argument de l'apocalypse.
(Comme prévu) il commence par un sujet très philosophique et progresse vers l'informatique quantique post-sélection et PostBQP = PP.

Le chapitre 19 examine le paradoxe de Newcomb et le libre arbitre.
Ce sujet se poursuit avec une explication du « théorème du libre arbitre » de Conway-Cohen et une méthode pour générer des « nombres aléatoires certifiés par Einstein » à l'aide de l'inégalité de Bell.
Le chapitre 20 traite du voyage dans le temps.
La discussion suit un schéma désormais familier, commençant par diverses discussions philosophiques et se concluant par une preuve qu'un ordinateur classique ou quantique avec une courbe temporelle fermée possède une puissance de calcul totalement équivalente à celle de PSPACE (des contre-arguments intéressants à cette preuve sont possibles et seront longuement discutés).

Le chapitre 21 présente la cosmologie, l'énergie sombre, la limite de Bekenstein et le principe holographique.
Bien entendu, tous ces sujets sont abordés sous l'angle de leur signification au regard des limites du calcul.
Par exemple, combien de bits peuvent être stockés ou récupérés sans utiliser suffisamment d'énergie pour créer un trou noir, et combien d'opérations peuvent être effectuées sur ces bits ?

Le chapitre 22 fait office de dessert.
Les informations présentées ici sont basées sur les réponses de l'auteur aux questions posées par les étudiants lors du dernier cours du module « L'informatique quantique depuis Démocrite ».
Cet ouvrage aborde l'échec de la mécanique quantique, les trous noirs et les fuzzballs, la pertinence des résultats d'oracles pour la complexité computationnelle, la NP-complétude et la créativité, les corrélations « super-quantiques », la dérandomisation des algorithmes aléatoires, la nature de la science, de la religion et de la raison, et explique pourquoi l'informatique n'est pas une branche de la physique.

Note de l'auteur

En 2013 encore, seule une très petite minorité considérait la mécanique quantique comme une théorie de l'information et des probabilités.
Si vous prenez n'importe quel livre de physique, qu'il s'agisse d'un livre populaire ou d'un manuel, vous constaterez que (1) la physique moderne est pleine de toutes sortes de phénomènes apparemment contradictoires, comme les ondes étant des particules ou les particules étant des ondes, (2) si vous y regardez de plus près, personne ne comprend vraiment ces termes, (3) il faut des années de recherche intensive rien que pour l'exprimer mathématiquement, et (4) finalement, le point de vue atomique est non seulement correct, mais c'est le seul qui compte.

Tout ce que je veux savoir, c'est :
Pourquoi les choses ne correspondent pas à mon intuition, comment corriger ma pensée pour qu'elle corresponde aux résultats expérimentaux, et comment raisonner sur le fonctionnement du monde réel sans être confus.
Je peux vous assurer qu'aucun physicien ne sait comment corriger son intuition pour que le comportement des particules subatomiques ne paraisse pas insensé.
En fait, il se peut qu'il n'y ait absolument aucun moyen.
Le fait que le mouvement subatomique soit uniformément aléatoire restera peut-être une vérité gênante.
Il n'y a rien d'autre à dire que : « Vous pouvez trouver la réponse en utilisant cette formule. »


Heureusement, comme en témoignent les recherches menées ces dernières décennies sur l'informatique quantique et les principes fondamentaux de la physique quantique, je crois que nous pouvons désormais mieux expliquer la mécanique quantique que de la considérer simplement comme un fait inconnu.
Pour bien comprendre la conclusion, voici le point de vue adopté dans cet ouvrage.

La mécanique quantique est une généralisation élégante des lois des probabilités.
On peut la considérer comme une généralisation basée sur les nombres complexes plutôt que sur les nombres réels positifs, avec deux nombres au lieu d'un.
Les applications de la mécanique quantique peuvent être menées indépendamment de l'étude de la mécanique quantique elle-même.
Cette théorie des probabilités généralisée peut naturellement servir de base au développement d'un nouveau modèle de calcul appelé modèle de calcul quantique.
C’est précisément ce modèle qui a remis en question la notion conventionnelle de calcul comme quelque chose qui pouvait autrefois être connu à l’avance, et que les informaticiens théoriciens essayaient de développer à leurs propres fins.
Cette direction n'a peut-être en réalité rien à voir avec la physique.
En résumé, la mécanique quantique a émergé il y a un siècle pour résoudre des problèmes spécifiques en physique, mais elle peut désormais être expliquée de manière satisfaisante d'un point de vue totalement différent.
C’est-à-dire, dans le cadre de l’histoire des idées, les limites de la perception à travers les mathématiques, la logique, l’informatique et la philosophie.

Si je me suis intéressé à l'informatique quantique, ce n'est pas par curiosité pour les capacités des ordinateurs quantiques, mais par curiosité pour l'impact que leur faisabilité aurait sur notre vision du monde.
Soit un ordinateur quantique pratique est réalisable et les limites de la perception ne sont pas celles que nous pensons, soit nous ne pouvons pas construire un tel ordinateur et devrons modifier les principes de la mécanique quantique, soit nous découvrons un moyen de simuler efficacement la mécanique quantique sur un ordinateur classique auquel nous n'avons pas encore pensé.
Ces trois possibilités peuvent paraître des conjectures plutôt bizarres, mais au moins l'une d'entre elles est vraie.
Donc, quel que soit le résultat, si vous plagiez une publicité qui plagie mes notes de cours, vous pourrez dire : « C'est intéressant. »