L’information c’est physiqueou comment exorciser les Démons

David PoulinDépartement de physique et DIRO

Université de Montréal

1. Introduction

Physique InformationManipulation

•États quantiques•Craie•Feynman: problème quantique, info quantique•Ordinateur analogique

Physique InformationPrédictions

•Méthode d’entropie maximale•Thermodynamique = minimiser I avec contraintes macroscopiques

Physique Information

Information -i

i. Information ??? intuition.

Gauchers Droitiers Prob.Yeux bleus PGB PDB 1/3Yeux verts PGV PDV 2/3 Prob. 1/3 2/3 1

But: Déterminer les 4 variables Pab.

À notre disposition: 4 équations linéaires dont 3 indépendantes.

Solution: Choisir celle qui introduit le moins d’information. scontrainte|)(min abP

PIab

Multiplicateurs de Lagrange.

Il nous reste à trouver I !!!

Information -2

2. InformationInformation contenue en moyenne dans un message An {Ai}i=1..N ?

Pr(An) = pn,

N

iip

11

Cas extrêmes

1) pn=1 , pi=0 , i j

Information=0

2) pi= , i=1..N

Information maximale

Cas général (Entropie de Shannon, 1949)

N1

N

iiiNii ppkpI

1..1 ln}{

k > 0 (k =1 et ln = log2 bits)

Information -3

Information = # minimal de bits par message

Exemple trivial:Message Probabilité

(fréquance)Représentation # de bits

A 1/4 00 2B 1/4 01 2C 1/4 10 2D 1/4 11 2

24ln41ln

414 I

2l

Exemple moins trivial:Message Probabilité Représentation # de bits

A 1/2 0 1B 1/4 10 2C 1/8 110 3D 1/8 111 3

47

81ln

81

81ln

81

41ln

41

21ln

21 I

Information -4

On trouve bien <l> = 7/4. On est contraint à trouver une représentation qui ne présente aucune ambiguïté:1 0 1 1 0 1 0 0 1 1 1 0 ... B C B A D A

De façon générale, 1 IlI

Jaynes, 1954. Faire de la thermodynamique, c’esttrouver les probabilités pi, associées à chaque étatmicroscopique i, qui minimisent l’information Itout en respectant les contraintes macroscopiquestels le volume, la pression, ...

Les résultats obtenus sont identiques aux résultatsétablis depuis longtemps ...

Thermodynamique -5

3. Thermodynamique

Les lois de la thermodynamique:

0. L’équilibre thermodynamique existe.1. L’énergie est conservée.2. L’entropie ne peut qu’augmenter.3. L’entropie tend vers une constante quand T 0.

1. You cannot win, you can only get even.2. You can only get even at absolute zero.3. You cannot reach absolute zero!

L’impossibilité de construire une machine à mouvement perpétuel est une conséquence des3 lois.

Machines à vapeur (thermiques)•Centrales nucléaires•Moteurs à combustion•Disque dur (but de l’exposé!)

Thermodynamique -6

Toutes les machines à vapeur ont le même principede fonctionnement:

T1

T2

W

Q1

Q2

Par conservation de l’énergie: Q1 = Q2 + WNote: Si W <0, c’est un réfrigérateur!

Définition opérationnelle de l’ENTROPIE:

TQS S est connue à une constante

additive près.

Chaud

Froid

Thermodynamique -7

De la deuxième loi, on obtient

1

2

1

2

2

2

1

1

e

0

)(2 0

TT

QQTQ

TQ

loiS

L’efficacité d’une machine thermique est

1

2

1

2

1

21

111

TT

QQ

QQQ

QW

“=“ S = 0 Réversible.

Une efficacité de 1 signifie que toute la chaleur Q1

tirée du réservoir chaud sert à faire un travail W.

loi) (3 Impossible 0 Impossible :1

e2

1

TT

Entropie -8

Carnot 1830 & Clausius 1850

Boltzmann ~1870-80

4. Entropie

TQS

Gibbs ~1910

= # d’états accessibles

1ln

iiiB ppkS

La formulation de Boltzmann est un cas particulierde la forme générale de Gibbs:

ln1ln1 1BBi kkSp

Entropie -9

C’est la même formule mathématique que l’information de Shannon!!! Coïncidence?

Note1.Pourquoi une constante additive?

lnBkS

’= n

nkknk

kS

BB

B

B

lnln ln

'ln'

La mécanique quantique nous indique commentséparer correctement l’espace de phase: on compteles états orthogonaux.

Entropie -10

Note 2. 2121 )()( tttStS

Pourtant, les équations de la physique sont parfaitement symétriques dans le temps: t -t

2

2

2

2

)()('' )'(

dtxd

tddx

tddmmaFtt

dtxdmmaF

La deuxième loi de la thermodynamique est laseule loi de la physique qui introduit une asymétriedu temps.

Un réfrigérateur ne diffère d’une machine à vapeur que par le sens de l’écoulement du temps.

Le Démon de Maxwell -11

5. Le Démon de Maxwell

Illustration Darling et Hulburt:

T1 T2

Q1 Q2

Q1+Q2=0 (1ere loi)

! 011

211

2

2

1

1

TTQ

TQ

TQS

2121 0 TTQQ

Le Démon enfrein la seconde loi, il peut donc construire une machine à mouvement perpétuel !

Trouver la faille -12

6. Trouver la faille

Szilard 1929 Pour être efficace, la Démon doit prendre une mesure sur le système.

Ansatz: La mesure augmente l’entropie du systèmeDémon-Boîte de kBln2 J/K.

Machine de Szilard:

W

Particule dans une boîte.

Met une cloisonet mesure.

Extrait du travaildu système.

État initial.

S=kB ln

S=kB ln( /2 ) +Sm

=kB (ln - ln2 + ln2)

S = 0

C’est une machine de Carnot !!! Réversible.

Irréversibilité logique -13

Brillouin 1950 L’entropie augmente lors de l’acquisition (mesure) d’information.S = I. Trouve des exemples pour justifier.

7. Irréversibilité logique

Landauer Les opérations logiquement irréversiblesont un coût thermodynamique.

01=0 -1(0)=(?,?)

L’information, peu importe sa forme et son contenu, doit être supportée (représentée) par un système physique.

•Disque dur: moments magnétiques.•Mémoire humaine: neurones.•Signaux lumineux: amplitude, fréquence, ...•etc.

Irréversibilité logique -14

Exemple d’opération logiquement irréversible:remise à 0 ou “reset”.

Support physique: particule dans une boîte.

0 = 1 =

1. Si la boîte ne contient pas d’information, c’estparce que nous savons, avec probabilité 1, où setrouve la particule. i.e. Notre cerveau possède une copie du contenu. L’effacer n’est donc pas irréversible.

0 Laisse tel quel.

1

Aucun coût thermodynamique.

Irréversibilité logique -15

2. Si la boîte contient de l’information (on ignoreson contenu), on doit utiliser un piston afin de contraindre la particule à se situer dans la partiede gauche.

?W

? lnBkS

2lnln2

ln BBB kkkS

Je fournis un travail2lnTkB

Une opération logiquement irréversible coûteau moins kBT ln2 J d’énergie.

Cet exemple est généralisable à tout systèmephysique, le volume devient l’espace de phase.

Irréversibilité logique -16

Bennett 1982, Pour en revenir au Démon ...

?W

Mémoire Gain Système

? ?

W

0

0

0

kBT ln2

-kBT ln2

0?

Complexité algorithmique -17

8. Complexité algorithmiqueKolmogorov, Solomonoff, Chaitin.

DéfinitionSoit ,1,0 nx

.)(:min)( xpUpxKp

alors

•U est une machine de Turing universelle.•p est une chaîne de 0 et de 1 servant de programme.•|p| est la longueur de p.•U(p) est le résultat de l’exécution de p sur U.

La complexité d’une chaîne x est la longueur duplus petit programme qui donne x lorsqu’exécutésur une machine de Turing universelle.

K est donc défini à une constante additive près.

Définition x est aléatoire K(x) = |x|.

Complexité algorithmique -18

Exemple x = 00000...0 (1,267 1030 fois)

p: BEGIN PROGRAM DO I=1,1.126E30 WRITE 0 END DOEND PROGRAM

|p|100 = longueur binaire de 1,267 1030 =2100.

100 << 1,267 1030 , non aléatoire.

Exemple x = 001101010011101011110...

p: BEGIN PROGRAM WRITE 00110101001110...END PROGRAM

|p||x| , x est aléatoire.

Complexité algorithmique -19

Exemple x = 1100100100001111110110...

Est-ce-que x est aléatoire?

NON, x = , un simple programme peut le générer.

K est bien défini, mais incalculable la plupart du temps.

Connaître p = connaître xI(p) = I(x)Possibilité de compresser réversiblement x.

Le Démon peut encore enfreindre la seconde loi si:

• il possède une mémoire pouvant storer N >1 bits.• il répète N fois

Mesure la particuleExtrait du travail

• compresse sa mémoire• efface la mémoire compressée

Gain = 0)(2ln xKNkB

Complexité algorithmique -20

Zurek 1984 L’entropie physique est la somme del’entropie de Gibbs (thermodynamique) et de lacomplexité algorithmique du système.

KSH

Il existe beaucoup plus de chaînes aléatoires que de chaînes algorithmiquement simples dans la nature.

Grossièrement, l’information de Shannon estl’équivalent de la complexité pour un systèmestatistique. Puisque l’information de Shannon est une fonction de la distribution de probabilité, ellene peut pas être calculée pour une seul objet, on utilise donc la complexité

Pour un ensemble statistique:

KI

L’information c’est physique -21

9. L’information c’est physiqueShumacher

T1

01101010

T2

01101010

Information

Eextraie Erequise

Esurplux

Démon lecteur Démon effaceur

02ln)( 21 TTNkEEE Brequiseextraiesurplux

2

11TT

EE

extraie

surplux Machine de Carnot

L’énergie est envoyé par un fil électrique etl’entropie par un fil téléphonique...