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
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...