Le weblogue de Matthieu Walraet

Page d'acceuil | Aller au contenu | Aller au menu | Aller à la recherche

Quantum Computing Since Democritus - Scott Aaronson

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/

Comment terminer un tournoi de poker avec classe

Je viens de jouer un petit sit&go de Texas Hold'em no limit, une table de dix, 5.5$ pour participer, 25$ pour le gagnant.

C'est toujours agréable de gagner un tournoi, d'habitude je n'aurais pas pris la peine de m'en vanter. Là c'est un peu spécial: quinteflush.png

Je m'en veux de ne pas avoir fait le screenshot avec les cartes sur la table ! En général, gagner sur une quinte flush, cela ne se voit qu'au cinéma.

EGC 2007

Cet été j'ai participé au Congrès Européen de Go, à Villach en Autriche.

Il a rassemblé environ 600 joueurs de go. Le principal évènement est un tournoi en dix ronde, une par jour. J'y ai obtenu un bon résultat, six victoires, ce qui me redonne un niveau de 3 kyu.

Arnaud en a fait un compte rendu agrémenté de ses photos : http://arnaud.knippel.free.fr/photos/egc2007/

Réveil de blog

Je n'ai jamais dit que j'allais régulièrement écrire quelque chose ici, si ?

Ce n'est pas qu'il ne se passe rien dans ma vie, mais bon je ne vais pas tout raconter non plus. Par exemple ce soir, je suis allé à mon club de go (le COP). J'ai joué une partie à égalité contre un joueur strasbourgeois en visite et j'ai perdu du komi. J'étais content quand même, c'était une partie sympa, et cela faisait un bail que je n'avais pas joué au go.

La minute de 61 secondes

Cette nuit, nous avons porté un toast à minuit, 59 minutes et 60 secondes, pour célébrer un évènement très court : la seconde intercalaire. La précedente avait eu lieu le 1er janvier 1999.

Merci à Romain de nous avoir prévenu à temps. N'oubliez pas de reculer vos horloges d'une seconde, ou vous risquez d'arriver en avance à tous vos rendez-vous.

Au fait, bonne année 2006 !

Gounki en série !

Vous connaissez tous le Gounki ?

Si vous avez fait gaffe à mes photos de congrès de go(unki) : Tuchola et Prague.

Il y a une petite différence. Non ?

Et oui, l'Association des Joueurs de Gounki a lancé la production du jeu en série : tada !

Congrès Européen de go à Prague

J'ai participé au Congrès Européen de Go qui c'est tenu du 23 juillet au 6 août à Prague. Bien entendu, j'en ai aussi profité pour visiter la République Tchèque.

L'ambiance était très conviviale. C'était l'occasion de jouer au go (je ne le fais pas assez durant le reste de l'année) et de rencontrer des amis venant d'un peu partout en europe et dans le monde. Point de vue résultat, je m'en tire honorablement avec six parties gagnées sur dix au tournoi principal.

Ah oui, voici mes photos.

Voyage en chine

G

En avril, j'ai fait avec Cyrille un voyage de trois semaine en chine.

C'est un pays étonnant, par sa taille, la richesse de son histoire et de sa culture, le contraste entre la campagne archaïque et les villes ultra-moderne.

Voici les photos.

Wow !

Voila, j'ai fini par craquer...

Depuis cette semaine je me suis mis à World of Warcraft.

Faut dire que j'ai beaucoup joué à Warcraft 1, 2 & 3. Je n'ai pas résisté à l'envie de jouer un mage pour pouvoir transformer mes adversaires en mouton.

Je joue sur le serveur Garona. Zardor, mage humain tailleur et enchanteur. Contre 9 tissus de lin, je vous fais un petit sac. Je peux aussi enchanter vos bracelets, prix à débattre.

Crèmes brûlées

Papa utilise un ustensile de cuisine que Mamie a retrouvé à St-Mesmes. Il date d'avant guerre et n'a pas du servir beaucoup ces dernières décennies.

Pour bien faire, il aurait fallu le chauffer sur les braises dans la cheminée mais avec la cuisinière à gaz c'était très bien aussi.

Il faut aimer la fumée...

Voilà. C'était très bon !

Greg Egan : Multiverse Opera.

J'ai écrit il y a un peu plus d'un an cette revue de "Diaspora" et "Schild's ladder", deux romans de Greg Egan qui ne sont pas encore traduits en français.

Cet article est paru dans la revue PDE.

lire la suite

Ubuntu

Je suis passé à Linux !

J'ai installé la distribution Ubuntu à partir d'un CD que Thomas m'a donné.

Le plus difficile a été d'installer un nouveau disque dur, je n'avais plus trop de place sur l'ancien et je préfère garder ma partition Fat32/Windows 98 intacte. (Hé oui, je partais de loin.)

J'ai eu un petit problème de clavier, il n'était pas configuré en azerty dans l'environnement graphique alors que je l'avais indiqué au cour de l'installation. Je me suis voulu d'avoir choisi un mot de passe compliqué !

A part cela pas de soucis. J'ai installé Thunderbird en utilisant le gestionnaire de paquets Synaptic. Comme j'utilisais déjà Firefox et Thunderbird, cela ne me change pas trop.

Je ne peux pas dire que je suis un utilisateur de base, mais cette distrib m'a semblé particulièrement simple à installer et à utiliser.

Usine à gaz

Qu'est ce que vous foutez sur mon site ?

C'est ce que je me demande quand je vois qu'il y a une quarantaine de visites par jour et que je compare cela à l'intérêt de son contenu.

Depuis que j'ai accès aux logs, j'ai la réponse. La plupart de mes visiteurs déboulent ici en faisant une recherche sur "Usine à gaz". Pour cette requète, je suis en deuxième position sur Google.

Cela mène à une des pages décrivant l'automate cellulaire Wireworld. Je cherchais un titre pour un circuit un peu compliqué, j'ai mis cela.

Voilà, maintenant je me demande pourquoi donc tant de monde fait une recherche sur "usine à gaz".

Enfin le blog que le monde attendait

...mais, qu'est-ce que je vais bien pouvoir écrire dedans ?