Cela faisait quelque temps que je voulais m'initier à l'informatique quantique. Je n'ai donc pas hésité quand Hannu Rajaniemi, mon auteur de science-fiction finlandais préféré, a fait l'éloge de ce livre. A priori, la pertinence de devoir remonter jusqu'à Démocrite sur ce sujet semble faible. Scott Aaronson parvient pourtant à montrer que les questionnements du philosophe sont toujours d'actualités pour les physiciens contemporains. Le titre est surtout révélateur du ton de l'ouvrage, plein d'esprit et amusant. L'auteur emploie souvent l'auto-dérision à propos de ses obsessions de chercheur en informatique théorique, toujours prêt à ramener n'importe quelle question à la comparaison entre deux classes de complexité.

L'ouvrage à l'ambition de montrer que, contrairement aux idées reçues, il est possible de comprendre la physique quantique. L'idée est de ne pas l'aborder par l'angle de la physique, mais par les concepts fondamentaux. La mécanique quantique est alors présentée comme une généralisation de la théorie des probabilités. En proba, la distance classique est la norme 1, la version quantique consiste à utiliser la norme 2. Limpide, n'est-t-il pas ?

Le livre est tiré d'un cours que l'auteur a donné en 2006 à l'université de Waterloo. Il commence par établir quelque pré-requis. Les premiers chapitres sont dédiés aux fondements des mathématiques : logique de premier ordre, axiomes de Peano de l'arithmétique, axiomes de Zermelo-Fraenkel de la théorie des ensembles, cardinalités, axiome du continu, axiome du choix, théorèmes de complétude et d'incomplétude de Gödel, machines de Turing, calculabilité, problème de l'arrêt, théorie de la complexité, le problème P vs NP... L'auteur n'hésite pas à donner les démonstrations, avec des arguments imparables genre « Si vous n'avez jamais vu cette démonstration, il faut que je vous la montre ! » L'avantage, c'est qu'en quelques chapitres vous avez un cours assez costaud sur les bases de l'informatique théorique. Le défaut c'est que ça va un peu vite. Pour moi une bonne partie était déjà connue et le rappel ne faisait pas de mal, surtout aussi bien présenté et avec ce ton joueur.

Enfin, nous arrivons à la mécanique quantique, vue comme une extension des probabilités. Le chapitre suivant est sur l'informatique quantique et sur ses possibilités. La classe des problèmes qu'un ordinateur quantique peut résoudre rapidement est nommée BQP. Elle contient par exemple la factorisation des nombres premiers. Même si rien n'est encore démontré, on conjecture fortement que P est strictement incluse dans BQP elle-même strictement incluse dans NP. Ce qui veut dire qu'un ordinateur quantique ne peux pas résoudre efficacement les problèmes dits NP-complets comme le voyageur de commerce ou le problème de savoir s'il y a une solution à une série d'équations logiques données.

Une fois que nous avons assimilé tout cela, l'auteur en profite pour démonter les arguments de Roger Penrose sur l'origine quantique de la conscience. J'ai toujours trouvé cette théorie peu convaincante, un article de Max Tegmark la critique déjà très fortement sur le plan de la physique. Ici Scott Aaronson pointe exactement là où est la faille dans l'utilisation du théorème de Gödel par Penrose.

L'auteur traite ensuite tout un tas de sujets passionnants, entre autres l'apprentissage, le principe anthropique, le libre-arbitre, le voyage dans le temps et la cosmologie. Pour chacun de ces sujets, il montre comment l'aborder du point de vue de l'informatique théorique classique et ensuite ce qu'apporte la mécanique quantique. Bluffant !

"Quantum Computing Since Democritus" est passionnant à lire. Je voudrais pouvoir le conseiller à tous mais ça risque quand même d'être difficile si les maths ne sont pas votre truc. Je dois aussi avouer que je n'ai pas essayé de comprendre en détail les chapitres où ça part dans les arcanes supérieures, mais même là j'ai pu entrevoir une partie du raisonnement. Donc si le sujet vous intéresse, donnez-vous une chance.

http://www.scottaaronson.com/democritus/