Entropia: Introdução à teoria matemática da informação, Notas de estudo de Engenharia Química

Baixe Entropia: Introdução à teoria matemática da informação e outras Notas de estudo em PDF para Engenharia Química, somente na Docsity! Entropia: introdução à Teoria Matemática da (des)Informação 1 Bernardo N. B. Lima, Leandro Martins Cioletti, Marcelo de O. Terra Cunha, Gastão A. Braga Departamento de Matemática - UFMG CP 702 - Belo Horizonte - 30123-970 15 de outubro de 2004 1Minicurso a ser apresentado na II Bienal da SBM - UFBa - Salvador - 25 a 29/10/2004 v O texto No segundo semestre de 2003 os autores deste texto, junto com Ricardo Falcão e Daniel Cavalcanti, realizaram seminários no intuito de buscar linguagem comum e conhecimento em Teoria Quântica da Informação. O texto base para isso foi [5]. No ińıcio de 2004, contando ainda com a participação de Paulo Cupertino de Lima, chegamos ao conceito de entropia, onde ficava claro que a bagagem de cada um trazia visões complementares sobre o assunto. Por outro lado, não é comum encontrar essa bagagem reunida. Entropia aparece como conceito nos livros das diferentes teorias, mas só em alguns poucos textos é o fio condutor. Surgiu assim a idéia de preparar um texto como o aqui apresentado, imediatamente pensado para a apresentação de um mini-curso na II Bienal de Matemática, exigindo do público alvo apenas o conhecimento comum ao ciclo básico de ciências exatas: cálculo de funções de várias variáveis e álgebra linear. Como o pano de fundo é a noção de probabilidade, o primeiro caṕıtulo que se segue apre- senta essa teoria na sua visão moderna, sem a necessidade de pré-requisitos sofisticados. O preço que se paga é restringir a teoria a espaços amostrais finitos , mas houve a pre- ocupação ao longo do texto de, sempre que posśıvel, manter a discusão em termos mais gerais, embora as definições e exemplos diretamente trabalhados obedeçam tal restrição. O caṕıtulo seguinte traz a teoria clássica da informação, apresentando algumas pro- priedades importantes das diversas entropias que seguem da primeira definição (noções como entropia conjunta, entropia relativa e informação mútua), e culminando com o Teo- rema de Shannon, onde surge a relação entre entropia de uma distribução e a possibilidade de compactar dados apresentados segundo esta distribuição. O caṕıtulo 3 trata do conceito de entropia em teoria quântica da informação. É natural, no esṕırito deste texto, fazer uma introdução dos ingredientes necessários para o tratamento do assunto, assim os conceitos básicos de mecânica quântica são apresentados, assumindo apenas que o leitor conhece álgebra linear de espaços vetoriais com dimensão finita. É claro que não cabe aqui a discussão de detalhes da teoria, mas alguns dos seus pontos mais curiosos são tocados ao longo do texto. O caṕıtulo traz as generalizações naturais dos conceitos clássicos, mas aponta também algumas das importantes diferenças entre a teoria clássica e a quântica. O caṕıtulo se encerra com o Teorema de Schumacher, a perfeita tradução do Teorema de Shannon para este contexto. O caṕıtulo 4 trata da mecânica estat́ıstica de equiĺıbrio em redes finitas. Este é o cenário onde se torna mais elementar obter resultados rigorosos, cuja extensão a redes infinitas e a modelos mais gerais é ainda, em grande parte, objeto de pesquisa atual. Neste caṕıtulo vi INTRODUÇÃO demonstramos que para cada valor de uma certa energia livre, o estado de equiĺıbrio é aquele que maximiza a entropia sujeito a tal restrição. O texto é auto-contido, e assume apenas os pré-requisitos já comentados, além de dis- posição. Os exerćıcios são considerados parte indispensável do texto. Vários desejos foram abandonados em nome da premência de tempo: não inclúımos um apêndice sobre crip- tografia quântica, não escrevemos um caṕıtulo sobre entropia em sistemas dinâmicos e não conseguimos passar o texto antes para um número considerável de colegas que pudessem nos ajudar a ter um texto mais definitivo. Nesse sentido, vemos estas notas como uma primeira versão de algo que pode se tornar mais completo. Ainda assim, achamos que servem bem como convite ao estudo de um conceito naturalmente interdisciplinar, e es- peramos que o leitor tenha prazer nas páginas que se seguem. Sumário Introdução iii Entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii O texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 Noções de Probabilidade 1 1.1 Espaços de Probabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Probabilidade Condicional e Independência . . . . . . . . . . . . . . . . . . 3 1.3 Variáveis Aleatórias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Esperança e Lei dos Grandes Números . . . . . . . . . . . . . . . . . . . . 8 2 Entropia e Teoria Clássica da Informação 13 2.1 Definições e primeiros exemplos . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Concavidade de H(X) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Entropia Relativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 A Entropia Conjunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 vii 2 CAPÍTULO 1. NOÇÕES DE PROBABILIDADE ii) Se A ∈ A, então Ac ∈ A; iii) Se A1, . . . , An, . . . ∈ A, então ∪∞i=1Ai ∈ A. Definição 1.2 (Axiomas de Kolmogorov) Um Espaço de Probabilidades é uma tripla ordenada (Ω,A, P ), onde Ω é um conjunto qualquer não-vazio, denominado Espaço Amostral, A é uma σ-álgebra de subconjuntos de Ω e P é uma função P : A → R satisfazendo: i) P (A) ≥ 0, ∀ A ∈ A; ii) P (Ω) = 1; iii) Se A1, . . . , An, . . . ∈ A e são dois a dois disjuntos , então P (∪∞i=1Ai) = ∑∞ i=1 P (Ai). Neste caso, dizemos que a função P é uma medida de probabilidade,( ou simplesmente probabilidade) e os elementos de A, o domı́nio de P , serão chamados de eventos. Durante todo o texto, iremos apenas considerar Espaços de Probabilidade em que o Espaço Amostral seja um conjunto finito (para uma definição precisa de conjunto finito, veja o caṕıtulo 2 de [4]). No caso Ω finito, podemos sempre tomar a σ-álgebra A como sendo P(Ω), o conjunto das partes de Ω (i.e., aquele formado por todos os subconjuntos de Ω). Exerćıcio 1.1 Denotando por #Ω, a cardinalidade do conjunto Ω, mostre que se #Ω = n, então #P(Ω) = 2n. Se Ω = {ω1, . . . , ωn}, então associamos a toda medida de probabilidade P , de modo biuńıvoco, um vetor de probabilidade, ou vetor de distribuição de probabilidade, (p1, . . . , pn), onde pi ≥ 0, i = 1, . . . n, e p1 + · · ·+ pn = 1. Neste caso, temos que P (A) = ∑ i;ωi∈A pi, ∀ A ∈ P(Ω) (1.1) e pi é a probabilidade de ocorrência do evento {ωi}. Em termos menos formais, se formos realizar um sorteio onde Ω seja um conjunto que contenha todas as posśıveis realizações do nosso sorteio, considerar uma distribuição de probabilidade dada pelo vetor (p1, . . . , pn) equivale a assumir que pi é a probabilidade do resultado do sorteio ser ωi. Exerćıcio 1.2 Verifique que P , definida por (1.1) é de fato uma medida de probabilidade! 1.2. PROBABILIDADE CONDICIONAL E INDEPENDÊNCIA 3 Um caso particular de extrema importância é quando assumimos que todos os posśıveis resultados do nosso sorteio são equiprováveis, isto é, pi = 1 n , i = 1, . . . n. Neste caso, temos que a probabilidade de qualquer evento A pertencente a P(Ω) é dada por P (A) = #A #Ω , ou seja, o problema do cálculo de uma probabilidade se resume a um problema de con- tagem, já que a probabilidade de ocorrência de qualquer evento (conjunto) A é dada pela proporção entre o número de elementos de A e o número de elementos do Espaço Amostral. Exerćıcio 1.3 i) n pessoas participam de um “amigo oculto”, isto é, existe uma urna contendo n bolas com os nomes de cada um dos n participantes e cada um dos parti- cipantes sorteia, sem repor, uma bola com o nome do seu “amigo oculto”; deste modo, cada participante terá um único “amigo oculto”e será “amigo oculto”de uma única pessoa. Calcule a probabilidade de haver pelo menos uma pessoa que sorteou a si próprio como “amigo oculto”. ii) Mostre que o limite da resposta do ı́tem anterior quando n→ +∞ é 1− e−1. 1.2 Probabilidade Condicional e Independência Sejam (Ω,A, P ) um espaço de probabilidade, A e B eventos tais que P (B) 6= 0. Definimos a probabilidade condicional do evento A, dado o evento B, como: P (A|B) = P (A ∩B) P (B) . Intuitivamente, podemos pensar em P (A|B) como a proporção que o evento A∩B ocupa no evento B. A seguir enunciaremos os principais resultados sobre probabilidades condi- cionais: Teorema 1.1 (Teorema da Multiplicação) Sejam A1, A2, . . . , An eventos quaisquer. Então: P (A1 ∩ A2 ∩ · · · ∩ An) = P (A1)× P (A2|A1)× · · · × P (An|A1 ∩ An−1). Demonstração: O caso n = 2 segue da definição de probabilidade condicional. Para os demais valores de n, a prova segue facilmente por indução finita. 4 CAPÍTULO 1. NOÇÕES DE PROBABILIDADE Definição 1.3 Seja P = {A1, . . . , An} um conjunto de eventos. Dizemos que o conjunto P é uma partição do espaço amostral Ω se: i) Ai ∩ Aj = ∅, ∀ i 6= j, isto é, os elementos de P são conjuntos dois a dois disjuntos; ii) ∪ni=1Ai = Ω. Seja P = {A1, . . . , An} uma partição do espaço amostral Ω e B um evento qualquer. Então temos os seguintes resultados: Teorema 1.2 (Teorema da Probabilidade Total) P (B) = n∑ i=1 P (Ai)× P (B|Ai). Demonstração: Como P é uma partição do espaço amostral Ω, podemos escrever B como a seguinte união disjunta B = (A1 ∩B) ∪ (A2 ∩B) ∪ · · · ∪ (An ∩B) Portanto, P (B) = n∑ i=1 P (Ai ∩B) = n∑ i=1 P (Ai)× P (B|Ai). Corolário 1.1 (Fórmula de Bayes) P (Ai|B) = P (Ai)× P (B|Ai)∑n j=1 P (Aj)× P (B|Aj) , ∀ i = 1, . . . , n. Definição 1.4 Sejam A e B dois eventos quaisquer em um mesmo espaço de probabili- dades. Dizemos que A e B são independentes se P (A ∩B) = P (A)× P (B). Se A e B são independentes com P (A) 6= 0 e P (B) 6= 0 podemos ver facilmente que P (B|A) = P (B) e P (A|B) = P (A), isto é, a ocorrência do evento A não afeta a ocorrência do evento B e vice-versa. 1.3. VARIÁVEIS ALEATÓRIAS 7 Exerćıcio 1.6 Sejam IA e IB as funções indicadoras dos eventos A e B. Mostre que as variáveis aleatórias IA e IB são independentes se, e somente se, os eventos A e B são independentes. Exemplo 1.4 Sejam X1, . . . , Xn variáveis aleatórias de Bernoulli (coletivamente) inde- pendentes e com a mesma distribuição. Considere a variável aleatória S = X1 + · · ·+Xn, que mede o número de sucessos ocorridos durante a repetição de n ensaios independentes de Bernoulli. Dizemos que S possui distribuição binomial com parâmetros n e p, ou S ∼ b(n, p), onde p é a probabilidade de ”sucesso”em cada ensaio de Bernoulli. Exerćıcio 1.7 Verifique que P (S = i) = n! i!(n− i)! pi(1− p)n−i, ∀ i = 0, . . . , n. O exemplo anterior, e muitas outras situações importantes em Probabilidade, diz respeito a propriedades de seqüências de variáveis aleatórias independentes. Dentre os diversos tipos de dependência que podem ser introduzidos, definiremos abaixo o que é conhecido como Cadeias de Markov. Definição 1.9 i) Seja (Xn)n∈N, Xn : Ω → Λ uma seqüência de variáveis aleatórias (é claro que #Λ <∞). Dizemos que tal seqüência forma uma Cadeia de Markov se P (Xn+1 = xn+1|Xn = xn, . . . , X1 = x1) = P (Xn+1 = xn+1|Xn = xn) para todo n ∈ N e para toda seqüência (xi)n+1i=1 tal que xi ∈ Λ. ii) Tal seqüência forma uma Cadeia de Markov homogênea (no tempo), se P (Xn+1 = y|Xn = x) = P (X2 = y|X1 = x), ∀ n ∈ N, ∀ x, y ∈ Λ. Em palavras, em uma Cadeia de Markov homogênea quaisquer que sejam os estados x e y, a probabilidade condicional, de uma variável aleatória da seqüência assumir no tempo futuro (n + 1) o estado y dada toda a seqüência de estados passados e presente (até o tempo n) assumidos pela seqüência de variáveis aleatórias, depende apenas dos estados presente e futuro, x e y, não dependendo da posição (temporal), n, e nem dos estados passados. Exerćıcio 1.8 Mostre que a seqüência de variáveis aleatórias (X, Y, Z) forma uma Cadeia de Markov homogênea se, e somente se, a seqüência (Z, Y,X) também é uma Cadeia de Markov homogênea. 8 CAPÍTULO 1. NOÇÕES DE PROBABILIDADE 1.4 Esperança e Lei dos Grandes Números Definição 1.10 Seja X : Ω → Λ ⊂ R uma variável aleatória, onde Λ = {λ1, . . . , λm}. A Esperança da variável aleatória X, E(X), é E(X) = m∑ i=1 λi · P (X = λi). Exemplo 1.5 Para os exemplos da seção anterior, pode-se verificar (exerćıcio!) que i) Se X = IA, a função indicadora do evento A, então E(X) = P (A); ii) Se X : Ω → Λ tem distribuição uniforme, ou equiprovável, em Λ, então E(X) = λ1+···+λm m , a média aritmética dos valores de Λ; iii) Se X ∼ b(n, p), então E(X) = np. Teorema 1.3 i) Sejam X, Y : Ω → R variáveis aleatórias. Então E(aX + bY ) = aE(X) + bE(Y ), ∀ a, b ∈ R. ii) Se X e Y são independentes, então E(XY ) = E(X)E(Y ). Demonstração:i) Sejam X = ∑n i=1 xiIAi e Y = ∑m j=1 yjIBj , onde Ai = (X = xi), i = 1, . . . , n e Bj = (Y = yj), j = 1, . . . ,m. Logo E(aX + bY ) = E( n∑ i=1 m∑ j=1 (axi + byj)IAi∩Bj) = n∑ i=1 m∑ j=1 (axi + byj)P (Ai ∩Bj) = = a n∑ i=1 xiP (Ai) + b m∑ j=1 yjP (Bj) = aE(X) + bE(Y ). i i) E(XY ) = E( n∑ i=1 xiIAi × m∑ j=1 yjIBj) = E( n∑ i=1 m∑ j=1 xiyjIAi∩Bj) = = n∑ i=1 m∑ j=1 xiyjP (Ai ∩Bj) = n∑ i=1 m∑ j=1 xiyjP (Ai)P (Bj) = E(X)E(Y ) 1.4. ESPERANÇA E LEI DOS GRANDES NÚMEROS 9 Exemplo 1.6 Seja X a variável aleatória que assume os valores 0, π 2 e π com proba- bilidade 1 3 . Sejam Y e Z variáveis aleatórias definidas como Y = sinX e Z = cosX. O leitor deve verificar que E(Y Z) = E(Y )E(Z); porém Y e Z não são independentes pois P (Y = 1, Z = 1) 6= P (Y = 1)P (Z = 1). Logo, a rećıproca da parte ii) do teorema anterior é falsa. Sejam X e Y variáveis aleatórias. Definimos a covariância entre X e Y como cov(X, Y ) = E(XY )− E(X)E(Y ). A variância da variável aleatória X é definida como V (X) = cov(X,X) = E(X2)− [E(X)]2 = E[X − E(X)]2. Exerćıcio 1.9 Mostre que i)V (X1 + · · · + Xn) = ∑n i=1 V (Xi) + 2 ∑ 1≤i<j≤n cov(Xi, Xj). Em particular, se (Xi) n i=1 são dois a dois independentes V ( ∑n i=1Xi) = ∑n i=1 V (Xi). ii) Se X ∼ b(n, p), então V (X) = np(1− p). Agora estamos prontos para enunciar (e provar!) um dos resultados mais importantes da Teoria da Probabilidade: a Lei dos Grandes Números. Em palavras, ela diz que sob certas hipóteses, ao realizarmos n repetições independentes de uma certa variável aleatória X, a média aritmética das n observações realizadas se aproxima de E(X) quando o número de observações n cresce para o infinito. Há diversas versões para a Lei dos Grandes Números. A que provaremos é uma versão da Lei Fraca dos Grandes Números que será suficiente para o que virá a seguir. Na demostração, a seguinte desigualdade será necessária. Teorema 1.4 (Desigualdade de Chebyshev) Seja X : Ω → R uma variável aleatória não negativa. Então P (X ≥ ) ≤ E(X)  , ∀  > 0. Demonstração: Novamente, seja X da forma X = n∑ i=1 xiIAi , 12 CAPÍTULO 1. NOÇÕES DE PROBABILIDADE Caṕıtulo 2 Entropia e Teoria Clássica da Informação Este caṕıtulo começa com a definição de nosso conceito central: entropia. Depois de explorar o caso de um único sistema, passamos a diversos conceitos naturais sobre sis- temas compostos: entropia conjunta, entropia relativa e informação mútua são definidas e várias de suas propriedades são exploradas. O caṕıtulo se encerra com o resultado cen- tral da teoria clássica da informação, o Teorema de Shannon, que relaciona entropia com compressão de dados. 2.1 Definições e primeiros exemplos Definição 2.1 Seja X uma variável aleatória com vetor de probabilidade (p1, . . . , pn). Definimos a entropia de Shannon da variável aleatória X como H(X) = − n∑ i=1 pi log pi. (2.1) Como o leitor pode notar a entropia de Shannon da variável aleatória X, depende somente da distribuição de X. Portanto, em alguns casos podemos simplesmente nos referir a entropia de Shannon associada a uma distribuição de probabilidades, e denotar H (pi). Para que a entropia de Shannon faça sentido mesmo se pi = 0 para algum i, definimos (veja 13 14 CAPÍTULO 2. ENTROPIA E TEORIA CLÁSSICA DA INFORMAÇÃO Exerćıcio 2.1) 0 log 0 como sendo 0. Aqui log denota logaritmo na base 2, mais adequada para aplicações da entropia à teoria da informação, motivação original de Shannon. Exerćıcio 2.1 Mostre que limx→0+ x lnx = 0. A grandeza H(X) pode ser interpretada como uma medida da nossa incerteza sobre o valor da variável aleatória X, antes de observá-la, ou como a quantidade de informação sobre X que foi ganha depois de realizar a observação. Em particular, se X assume algum valor ω com probabilidade 1 então nenhuma informação é ganha após a observação de X (já que com probabilidade 1, X assume o valor ω). Neste caso, podemos verificar direta- mente da definição de entropia que H (X) é zero. Por outro lado, se X tem distribuição equiprovável, pi = 1/n para todo i, então H(X) é exatamente log n. H(X) é sempre não-negativa e limitada superiormente de maneira uniforme. Os exerćıcios a seguir mostram este resultado. Exerćıcio 2.2 i) Mostre que podemos eliminar os valores de p identicamente nulos da soma (2.1) sem que se altere o valor de H(X), isto é, H(X) = − ∑ {i : pi>0} pi log pi. ii) Usando o item i) e definindo M(X) ≡ max{i : pi>0} | log pi|, mostre que 0 ≤ H(X) ≤M(X). Exemplo 2.1 (entropia binária) Seja X uma variável de Bernoulli com parâmetro p. Então H(X) = −p log p− (1− p) log(1− p). (2.2) Exerćıcio 2.3 Mostre que a entropia binária, quando vista como função de p, tem um máximo em p = 1/2 e que seu valor máximo é 1. Conclua então que H(X) ≤ 1 para qualquer v.a. X com distribuição binária. No exerćıcio 2.3 fica clara a comodidade do logaritmo ser tomado na base 2. Com a escolha de outra base teŕıamos log 2 como valor máximo. Observe que a cota superior dada pelo Exerćıcio 2.3 é uniforme em X, ao contrário da cota M(X) do Exerćıcio 2.2, que depende da distribuição de probabilidade de X. O Exerćıcio 2.3 pode ser generalizado, como mostramos a seguir. 2.3. ENTROPIA RELATIVA 17 Exerćıcio 2.10 Mostre que H(X‖Y ) = −H(X)− ∑ i pi ln qi. Exerćıcio 2.11 Se p1 = 1 e p2 = 0, q1 = q > 0 e q2 = 1− q, calcule H(X‖Y ) e H(Y ‖X) e verifique que H(X‖Y ) 6= H(Y ‖X). A entropia relativa nos permitirá quantificar, num certo sentido, o quão distintas estão as duas distribuições de probabilidade (pi) n i=1 e (qi) n i=1. Contudo, a entropia relativa não poderia nos fornecer uma noção de distância pois, como o Exerćıcio 2.11 nos mostra, ela não é simétrica. A entropia relativa, vista como uma medida da proximidade entre duas distribuições, será um conceito um pouco mais fraco do que o de distância. Contudo, a entropia relativa permeará resultados importantes no decorrer do texto. Exerćıcio 2.12 Mostre que lnx ≤ x − 1 para todo x > 0 e que a igualdade vale se, e somente se, x = 1. Teorema 2.3 (Positividade da entropia relativa) Sejam X e Y duas variáveis ale- atórias com distribuições (pi) n i=1 e (qi) n i=1, respectivamente. Então H(X‖Y ) ≥ 0 e a igualdade ocorre se, e somente se, (pi) n i=1 = (qi) n i=1. Prova: Da definição de entropia relativa e do o Exerćıcio 2.12, nós obtemos H(X‖Y ) = ∑ i pi ln ( pi qi ) = − ∑ i pi ln ( qi pi ) ≥ ∑ i pi ( 1− qi pi ) = 0. É claro que se pi = qi para todo i então H(X‖Y ) = 0. Por outro lado, se H(X‖Y ) = 0 então segue da seqüência de desigualdades acima que 0 = − ∑ i pi ln ( qi pi ) ≥ ∑ i pi ( 1− qi pi ) = 0. Equivalemente ∑ i pi [( qi pi − 1 ) − ln ( qi pi )] = 0, e usando o Exerćıcio 2.12 nós conclúımos que pi = qi para todo i. Uma bela aplicação da entropia relativa é uma outra prova do Teorema 2.1, como o próximo exerćıcio mostra. 18 CAPÍTULO 2. ENTROPIA E TEORIA CLÁSSICA DA INFORMAÇÃO Exerćıcio 2.13 Use a positividade da entropia relativa e o Exerćıcio 2.10 com X tendo distribuição equiprovável para obter uma outra prova do Teorema 2.1. Usaremos freqüentemente esta técnica de encontrar expressões para quantidades entrópicas em termos da entropia relativa, tanto no contexto de informação clássica quanto quântica. 2.4 A Entropia Conjunta Definição 2.8 (Distribuição Conjunta) Sejam X, Y : Λ → Ω variáveis aleatórias com distribuições pi = P (X = ωi) e qj = P (Y = ωj). A distribuição conjunta do vetor aleatório (X, Y ) é caracterizada pelo vetor de probabilidades pij = P (X = ωi, Y = ωj). Podemos verificar que pi = ∑ j pij, qj = ∑ i pij e que quando X e Y são independentes pij = piqj. Definição 2.9 (Entropia Conjunta) Dado o vetor aleatório (X,Y ), definimos sua en- tropia conjunta por H (X, Y ) = − ∑ ij pij log pij, (2.5) onde pij é a distribuição conjunta de (X,Y ). Exerćıcio 2.14 Mostre que, se X e Y são independentes, H (X, Y ) = H (X) +H (Y ). O Exerćıcio 2.14 diz que, se X e Y são independentes, uma variável não carrega infor- mação sobre a outra, ou seja o total da informação no par é a soma das informações em cada uma. A seguir obteremos que em geral a entropia é subaditiva, ou seja, o total de informação no par é menor que a soma da informação em seus constituintes. Teorema 2.4 (Subaditividade da Entropia de Shannon) Sejam X e Y variáveis aleatórias com distribuições pi e qj, respectivamente. Então H(X,Y ) ≤ H(X) +H(Y ), com a igualdade sendo válida se, e somente se, X e Y são independentes. 2.5. ENTROPIA CONDICIONAL E INFORMAÇÃO MÚTUA 19 Prova: Sejam Z = (X,Y ) e W = (W1,W2) vetores aleatórios com distribuições conjun- tas (pij)i,j e (piqj)i,j, respectivamente (isto é, W é um vetor aleatório cuja distribuição conjunta seria a de Z caso X e Y fossem independentes). Segue então H (Z‖W ) = ∑ ij pij log pij piqj = ∑ ij pij log pij − ∑ ij pij log pi − ∑ ij pij log qj = ∑ ij pij log pij − ∑ i pi log pi − ∑ j qj log qj = −H (Z) +H (X) +H (Y ) . Pelo teorema 2.3 temos H (Z‖W ) ≥ 0 valendo a igualdade se, e só se, Z e W têm a mesma distribuição, ou seja, pij = piqj,∀i, j, logo X e Y são independentes. 2.5 Entropia Condicional e Informação Mútua A subaditividade sugere que pode haver correlação entre as variáveis, que ao aprender sobre uma podemos também ganhar informação sobre a outra. Uma pergunta natural então é saber quanta informação sobre X não está dispońıvel em Y . Definição 2.10 A entropia condicional de X dado o conhecimento de Y é definida por H(X|Y ) = H(X, Y )−H(Y ). (2.6) Podemos interpretar a entropia condicional como a medida da incerteza que temos do valor de X dado que conhecemos o valor de Y . Pelo exerćıcio 2.14 vemos que, se X e Y são independentes, H (X|Y ) = H (X), ou seja, o conhecimento de Y não traz informação sobre X. Uma outra quantidade que podemos definir é a informação mútua contida no par X e Y , com objetivo de medirmos quanta informação elas têm em comum. Suponhamos que adicionemos a informação contida emX, H(X), à informação contida em Y . A informação comum existente em X e Y será contada duas vezes nesta soma, enquanto a informação que não é comum será contada apenas uma vez. Se subtrairmos a informação conjunta de (X, Y ), H(X,Y ), da soma feita anteriormente obteremos a informação comum ou a informação mútua de X e Y . 22 CAPÍTULO 2. ENTROPIA E TEORIA CLÁSSICA DA INFORMAÇÃO i) Dada a seqüência de variáveis aleatórias (Xi), defina a seqüência (Yi) como Yi (ω) = − log pj se Xi (ω) = xj. Neste caso, como a seqüência (Xi) é iid, a seqüência (Yi) também o é. Logo, pela Lei dos Grandes Números (teorema 1.5) temos que ∀ε > 0, lim n→∞ P (∣∣∣∣∑ni=1 Yin − EY ∣∣∣∣ ≤ ε) = 1. Observando que EY = H (X) temos a seguinte igualdade entre os conjuntos{∣∣∣∑ni=1 Yin − EY ∣∣∣ ≤ ε} = {n (H (X)− ε) ≤∑ni=1 Yi ≤ n (H (X) + ε)} = {n (H (X)− ε) ≤ − log (p1 · · · pn) ≤ n (H (X) + ε)} = T (n, ε) . ii) Como 1 ≥ P (T (n, ε)) = ∑ (x1,...,xn)∈T (n,ε) P (Xi = xi) ≥ (#T (n, ε)) 2−n(H(X)+ε), temos #T (n, ε) ≤ 2n(H(X)+ε), ∀n ∈ N. Pelo item i), como limn→∞ P (T (n, ε)) = 1, dado δ > 0, ∃no ∈ N tal que P (T (n, ε)) > 1− δ, ∀n > no. Então 1− δ ≤ P (T (n, ε)) ≤ (#T (n, ε)) 2−n(H(X)−ε), logo #T (n, ε) ≥ (1− δ) 2n(H(X)−ε). iii) Dado R < H (X), tome ε > 0 tal que H (X)− R − ε > 0. Denotando S = S (n) e T = T (n, ε), podemos escrever∑ (x1,...,xn)∈S P (Xi = xi, i = 1, . . . , n) = = ∑ (x1,...,xn)∈S∩T P (Xi = xi, i = 1, . . . , n) + ∑ (x1,...,xn)∈S∩T c P (Xi = xi, i = 1, . . . , n) . Pelo item i), dado ε > 0 existe n1 ∈ N tal que P (T (n, ε)) > 1− δ 2 , ∀n > n1, logo ∑ (x1,...,xn)∈S∩T c P (Xi = xi, i = 1, . . . , n) < δ 2 . 2.6. COMPACTAÇÃO DE DADOS E O TEOREMA DE SHANNON 23 Por outro lado, pela própria definição de seqüência t́ıpica,∑ (x1,...,xn)∈S∩T P (Xi = xi, i = 1, . . . , n) ≤ (#S (n)) 2−n(H(X)−ε) ≤ 2−n(H(X)−R−ε), como H (X)−R−ε > 0, existe n2 ∈ N tal que 2−n(H(X)−R−ε) < δ2 , ∀n > n2. Fazendo no = max {n1, n2} segue o resultado. Agora já temos todos os resultados que nos permitirão demonstrar o Teorema de Shannon. Falta apenas entender o que chamamos um sistema de Compressão-Descompressão, como usado por um computador para “zipar” um arquivo. Vamos manter o exemplo de um arquivo fotográfico em mente, embora o Teorema originalmente estivesse preocupado com a transmissão de dados. Nosso arquivo original contém a cor de cada pixel. Se usamos k bits para designar uma cor, e o reticulado possui m posições, devemos registrar n = mk bits. Se considerarmos cada bit como uma variável aleatória iid1, podemos pensar na entropia dessa distribuição. No nosso exemplo do coqueiro, há grande predomı́nio de poucas cores, o que diz que a entropia é pequena, comparada ao máximo valor que ela poderia assumir se tivéssemos muitas cores na foto. Um sistema de compressão- descompressão com razão R (com 0 < R < 1) é um par de funções C e D, onde C leva n bits em Rn bits, enquanto D faz o caminho contrário. É claro que C e D não podem ser rigorosamente inversas, pois C não tem como ser injetora. Um sistema de compressão- descompressão será dito confiável se P (D ◦ Cx = x) > 1−δ, ou seja, se a possibilidade de falha puder ser controlada por um δ arbitrário. Em sua essência, o Teorema de Shannon diz que um sistema de compressão-descompressão precisa cuidar das seqüências t́ıpicas se quiser ser confiável. Teorema 2.6 (Teorema de Shannon) Suponha que {Xi} seja uma seqüência iid de variáveis de Bernoulli com entropia H(X). Suponha que R > H(X). Então existe um esquema confiável de compressão com razão R para os dados desta fonte. Reciprocamente, se R < H(X) qualquer esquema de compressão não é confiável. Prova: Suponha que R > H(X). Escolha ε > 0 tal que H(X) + ε < R. Considere o conjunto T (n, ε) das seqüências ε-t́ıpicas. Para qualquer δ > 0 e suficientemente grande, existem no máximo 2n(H(X)+ε) < 2nR tais seqüências e a probabilidade da fonte produzir uma tal seqüência é no mı́nimo 1− δ. O método de compressão é simplesmente examinar agrupamentos de n dados de sáıda da fonte para ver se ele é ε-t́ıpico. Escolhida uma enumeração das t́ıpicas, associamos cada seqüência a seu valor; se a seqüência não for 1O que é uma simplificação, mas que pode ser melhor contornada. 24 CAPÍTULO 2. ENTROPIA E TEORIA CLÁSSICA DA INFORMAÇÃO t́ıpica, a associamos a um número espećıfico entre 0 e nR que será para nós como um registro que indica falha. A descompressão destes tipos de seqüência será simplesmente uma outra seqüência gerada pela fonte aleatoriamente. E isto nos fornece um esquema eficiente de compressão de dados (pois quase toda seqüência é t́ıpica). Supondo que R < H(X). A combinação das operações compressão-descompressão tem no máximo 2nR posśıveis sáıdas, logo no maximo 2nR das seqüências fornecidas pela fonte podem sofrer a operação citada acima sem a ocorrência de erro. Pelo teorema das seqüências t́ıpicas, para n suficientemente grande a probabilidade de uma seqüência fornecida pela fonte estar num conjunto de 2nR seqüências tende a zero, se R < H(X). Assim qualquer esquema de compressão não é confiável. 3.1. NOÇÕES RÁPIDAS DE MECÂNICA QUÂNTICA 27 Exerćıcio 3.5 (Combinações Convexas) Mostre que combinações covexas de oper- adores densidade são também operadores densidade. O que se conclui sobre o conjunto dos operadores densidade? Exerćıcio 3.6 (Estados Puros) Mostre que os pontos extremais do conjunto de oper- adores densidade correspondem a projetores ortogonais sobre subespaços unidimensionais de V . Tais pontos extremais são denominados estados puros. Em probabilidades, a distribuição de uma variável aleatória se refere às probabilidades de obter cada resultado posśıvel em sorteios independentes dessa variável. É importante distinguir a noção de sorteio independente da realização de duas observações subseqüentes do mesmo sistema. Para descrever o resultado de sorteios da Mega-Sena, por exemplo, devemos acreditar que cada número é sorteado com a mesma probabilidade e indepen- dentemente, o que leva a todas as combinações de seis dezenas serem equiprováveis, ex- clúıdas as repetições proibidas pela regra do jogo. Assim, a maneira de descrevermos o resultado de um concurso ainda não realizado é através da distribuição equiprovável no conjunto de todas as combinações permitidas. O problema muda de figura quando tratamos de um sorteio já realizado. Se alguém perguntar “qual o resultado do concurso 600 da Mega-Sena?”, e não tivermos informação alguma a esse respeito, ainda temos a distribuição equiprovável associada a ele. Mas se alguém nos informar que o resultado é {16, 18, 31, 34, 39, 54}, passamos a descrever tal variável “aleatória” por uma distribuição concentrada neste resultado agora conhecido. Qualquer nova observação da variável “con- curso 600 da Mega-Sena” dará o mesmo resultado. Em mecância quântica estas duas situações também aparecem. Em termos f́ısicos, é comum dizer que um operador densidade caracteriza (o resultado de) um processo de preparação. Sistemas igualmente preparados são caracterizados pelo mesmo operador densidade, que permite associar a cada processo de medição a distribuição de uma variável aleatória. A definição a seguir nos ensina a fazer essa associação. Definição 3.3 (Processo de Medição) Sejam V o espaço de estados e ρ o operador densidade. Um processo de medição é dado por um conjunto de operadores de medição {Mi}ni=1 sobre V , com a propriedade n∑ i=1 M †i Mi = I, (3.1) onde I denota o operador identidade e A† o adjunto de A. Os diferentes resultados do 28 CAPÍTULO 3. ENTROPIA E TEORIA QUÂNTICA DA INFORMAÇÃO processo serão indexados por i, e cada posśıvel resultado tem probabilidade pi = Tr ( MiρM † i ) . (3.2) Exerćıcio 3.7 Mostre que a eq. (3.2) define uma distribuição de probabilidade. Exemplo 3.1 (Observáveis e medições projetivas) Seja A um operador auto-adjun- to sobre V . Pelo teorema da decomposição espectral, A = n∑ i=1 aiPi, com ai reais e distintos, Pi projetores ortogonais com PiPj = δijPj. O conjunto {Pi} determina um processo de medição, com os resultados dados por {ai}. O operador A é dito um observável. O processo de medição aqui descrito é chamado medição projetiva. Da mesma forma que ao “concurso 600 da Mega-Sena” já sorteado, e cujo resultado já conhecemos, associamos uma variável aleatória com distribuição diferente daquela que o caracterizava antes do sorteio, em mecânica quântica associaremos um novo operador densidade a um sistema após sua medição. Definição 3.4 Sejam ρ operador densidade e {Mi}ni=1 operadores de medição. Se o re- sultado da medição for dado pelo ı́ndice i, o estado do sistema após a medição será dado por ρapós,i = MiρM † i Tr ( MiρM † i ) . (3.3) Exerćıcio 3.8 Mostre que ρapós,i é um operador densidade. O que acontece com a definição 3.4 quando o denominador se anula? Exerćıcio 3.9 Que operador densidade devemos associar a um sistema sobre o qual foi realizado um processo de medição, mas cujo resultado não conhecemos? Como isso se compara com o caso de um sorteio da Mega-Sena já realizado, mas cujo resultado descon- hecemos? 3.1. NOÇÕES RÁPIDAS DE MECÂNICA QUÂNTICA 29 3.1.1 Notação de Dirac Existe uma notação bastante comum nos textos de mecância quântica, chamada notação de Dirac. Vamos introduzi-la aqui por dois motivos: primeiro para fazer uso subseqüente dela, segundo para que ela não se torne um obstáculo para aqueles que desejem ler outros textos sobre mecânica quântica. Tal notação é válida para espaços vetoriais V com pro- duto escalar. Parece um tanto artificial, mas mostra-se de muita valia quando se opera com ela. Tudo começa com Definição 3.5 Um vetor v ∈ V será denotado |v〉. Como temos um produto escalar em mãos, a cada |v〉 ∈ V podemos associar um funcional linear dado por “fazer produto escalar com |v〉”. Tais funcionais constituem um espaço vetorial, chamado dual de V , e denotado V ∗. Em notação de Dirac, temos: Definição 3.6 Denotamos 〈v| o seguinte funcional linear: 〈v| : V −→ C w 7−→ (v, w) . Vale realçar que o produto escalar que está sendo considerado deve ser linear na segunda variável, e semi-linear na primeira, ao contrário da maioria dos textos de álgebra linear. A motivação da notação vem justamente do fato que o produto escalar entre dois vetores é agora denotado 〈v | w〉, e como em inglês teŕıamos o braket dos vetores v e w, em notação de Dirac dizemos que 〈v| é um “bra” (ou ainda, o bra v) e que |w〉 é um “ket” (o ket w). Exemplo 3.2 (Projetores) Seja |v〉 um vetor normalizado. O operador dado em nota- ção de Dirac por |v〉 〈v| é o projetor ortogonal sobre o subespaço unidimensional gerado por |v〉, usualmente chamado projetor sobre |v〉. Exerćıcio 3.10 (Decomposição ortonormal) Mostre que, dado um operador auto- adjunto A, podemos escolher uma base {|i〉}di=1, tal que A = ∑ i ai |i〉 〈i|. Exemplo 3.3 (Qubit em notação de Dirac) No importante caso de um qubit, é co- mum denotar por {|0〉 , |1〉} uma base convenientemente escolhida. Esta base é chamada base computacional, em referência aos valores computacionais de um registrador binário. 32 CAPÍTULO 3. ENTROPIA E TEORIA QUÂNTICA DA INFORMAÇÃO 1. A entropia de von Neumann é não-negativa. A entropia é zero se, e somente se, o estado é puro. 2. Num espaço d−dimensional a entropia é no máximo log d. Este valor é atingido se, e somente se, o sistema é um estado de mistura máxima, I/d. 3. Suponha que pi são probabilidades e que os operadores densidade ρi têm suporte em subespaços ortogonais. Então S (∑ i piρi ) = H(pi) + ∑ i piS(ρi). (3.11) Prova: (1) Segue diretamente da definição. (2) Da desigualdade de Klein (teorema 3.1), temos 0 ≤ S(ρ‖I/d) = −S(ρ) + log d. (3) Sejam λji e |e j i 〉 autovalores e correspondentes autovetores de ρi. Observe que piλ j i e |eji 〉 são autovalores e autovetores de ∑ i piρi e assim S ( ∑ i piρi) = − ∑ ij piλ j i log piλ j i = − ∑ i pi log pi − ∑ i pi ∑ j λ j i log λ j i = H(pi) + ∑ i piS(ρi). Como interpretações, (1) novamente traz a interpretação de um quantificador das surpre- sas que podemos ter ao fazer medições, ou ainda, de quanta desordem há no estado ρ; (2) justifica que I/d seja o análogo quântico da distribuição equiprovável de probabilidades; (3) mostra como as entropias de Shannon e von Neumann se complementam - para mel- hor apreciar a importância da hipótese de suportes ortogonais, recomendamos voltar ao exerćıcio 3.12. 3.3 Entropia e Medições Classicamente, quando é realizado um sorteio de uma variável aleatória podemos con- siderar duas situações: quando ainda não sabemos o resultado, continuamos a descrevê- la pela mesma distribuição de probabilidade de antes do sorteio; quando ganhamos in- formação sobre o resultado (que pode ser o próprio resultado, ou apenas uma informação parcial), refazemos nossa descrição desta nova variável. Como ganhamos informação nesse processo, a nova distribuição tem menos entropia que a anterior. Quanticamente, uma 3.3. ENTROPIA E MEDIÇÕES 33 medição da qual não sabemos o resultado já modifica o sistema, como vimos no exerćıcio 3.9. Além disso, pode haver medições que diminuem a entropia mesmo sem que saibamos seu resultado (exerćıcio 3.14)! Começamos então pela situação de medições projetivas das quais não sabemos o resultado: Teorema 3.3 (Medições projetivas aumentam entropia) Suponha que {Pi} deter- mina uma medição projetiva e que ρ é um operador densidade. Então a entropia do estado ρ′ = ∑ i PiρPi, que descreve o sistema após a medição, obedece S(ρ′) ≥ S(ρ), (3.12) valendo a igualdade se, e só se, ρ = ρ′. Prova: Pela desigualdade de Klein temos 0 ≤ S(ρ‖ρ′) = −S(ρ)− Tr(ρ log ρ′). (3.13) Usando que ∑ i Pi = I, P 2 i = Pi, e a propriedade ćıclica do traço, obtemos −Tr(ρ log ρ′) = −Tr ( ∑ i Piρ log ρ ′) = −Tr ( ∑ i Piρ log ρ ′Pi) . Como ρ′Pi = PiρPi = Piρ ′, Pi comuta com log ρ ′. Segue que −Tr(ρ log ρ′) = −Tr ( ∑ i PiρPi log ρ ′) = −Tr(ρ′ log ρ′) = S(ρ′). A eq. (3.13) conclui a prova. O exerćıcio seguinte mostra que medições generalizadas, das quais não sabemos o resul- tado, podem diminuir a entropia. Exerćıcio 3.14 Suponha que um qubit num estado ρ é medido usando os operadores de medição, M1 = |0〉〈0| e M2 = |0〉〈1|. Se o resultado da medição não é conhecido, após esta medição temos o sistema no estado M1ρM † 1 +M2ρM † 2 . Mostre que este procedimento pode diminuir a entropia do qubit. Como você interpretaria este processo? É natural pensar que ao ganharmos informação através de uma medição, a entropia do estado após a medição seja menor que a anterior. Mas será que essa “intuição clássica” vale no mundo quântico? 34 CAPÍTULO 3. ENTROPIA E TEORIA QUÂNTICA DA INFORMAÇÃO Exerćıcio 3.15 (Medições Projetivas diminuem a Entropia) Mostre que se {Pi} determina uma medição projetiva e ρ o estado do sistema, então S(ρi,após) ≤ S (ρ) para todo i. Exerćıcio 3.16 Considere um qubit descrito pelo estado ρ = 1 2 |0〉 〈0|+ 1 4 (|0〉+ |1〉) (〈0|+ 〈1|) , sujeito a um processo de medição dado por M1 = 1√ 3 [ 1 −1 0 1 ] e M2 = 1√ 3 [ 1 0 1 1 ] . O que acontece com a entropia de ρ nesse processo, para cada posśıvel resultado? 3.4 Sistemas quânticos compostos Nosso objetivo é chegar ao análogo quântico do teorema de Shannon. Para isso deveremos considerar várias cópias de um sistema quântico. Precisamos antes aprender a tratar com sistemas quânticos compostos , ou seja, aqueles formados por várias partes. O primeiro exemplo de sistema quântico composto são os sistemas bipartites . Seja A um sistema quântico descrito pelo espaço de estados V , e seja B outro sistema com espaço de estados W . Quando descrevemos conjuntamente os sistemas A e B (denotado AB), é claro que se |v〉 ∈ V e |w〉 ∈W descrevem cada parte, o par (|v〉 , |w〉) descreverá o estado do sistema composto. Mas a linearidade da mecânica quântica exige que associemos um espaço de estados a cada sistema. Assim, devemos considerar o espaço vetorial gerado pelos pares (|v〉 , |w〉). Matematicamente este espaço é o produto tensorial V ⊗W , para o qual damos uma definição construtiva: Definição 3.9 (Produto tensorial de espaços) Sejam V e W espaços vetoriais (de dimensão finita) e {|vi〉}mi=1 e {|wj〉} n j=1 respectivas bases ortonormais. Constrúımos o espaço V ⊗W declarando |vi, wj〉 = (|vi〉 , |wj〉) uma base ortonormal desse espaço. Exerćıcio 3.17 Qual a dimensão de V ⊗W? Definição 3.10 (Produto tensorial de operadores) Sejam A : V → V e B : W → W . O produto tensorial de A e B, A⊗B : V ⊗W → V ⊗W , é definido na base produto por A⊗B |vi, wj〉 = A |vi〉 ⊗B |vj〉 e estendido por linearidade. 3.5. ENTROPIA EM SISTEMAS COMPOSTOS 37 Exerćıcio 3.21 (Decomposição Polar) Seja A um operador em V . Então A†A é um operador positivo, e podemos definir J = √ A†A. Mostre que existe U unitária tal que A = UJ , e que U é única se, e só se, A é invert́ıvel. Esta é chamada (uma) decomposição polar à esquerda do operador A. Compare com a decomposição polar de números complexos para entender a nomenclatura. Além disso, mostre a existência de uma decomposição polar à direita. Sugestão: considere K = √ AA†. Exerćıcio 3.22 (Decomposição a valor singular) Seja M matriz quadrada. Mostre que existem U e V unitárias e D diagonal com elementos não-negativos tais que M = UDV. Sugestão: considere uma decomposição polar e diagonalize o operador positivo. Exerćıcio 3.23 (Decomposição de Schmidt geral) Escreva a demonstração do caso geral da Decomposição de Schmidt. Uma interessante conseqüência da Decomposição de Schmidt é a idéia de purificação. Se ρ = ∑ i pi |i〉 〈i| é um operador densidade de um estado misto sobre um espaço V , podemos considerar um outro espaço auxiliar V ′ e o estado puro |Ψ〉 = ∑ i √ pi |i〉⊗ |i′〉 em V ⊗V ′, tal que, quando o segundo subespaço é ignorado, reobtemos o estado de mistura de onde começamos. Esse processo é chamado uma purificação de ρ, e mostra-se bastante útil para várias definições e demonstrações. 3.5 Entropia em sistemas compostos Um primeiro resultado, bastante importante, é conseqüência direta da Decomposição de Schmidt e do fato da entropia de von Neumann só depender dos autovalores de ρ: Teorema 3.5 Se AB é um sistema composto descrito por um estado puro ρAB = |Ψ〉 〈Ψ|, então S ( ρA ) = S ( ρB ) . Outra propriedade interessante segue do item (3) do teorema 3.2: 38 CAPÍTULO 3. ENTROPIA E TEORIA QUÂNTICA DA INFORMAÇÃO Teorema 3.6 (Entropia Conjunta) Suponha que pi são probabilidades, |i〉 são estados ortogonais para um sistema A, e ρi qualquer conjunto de operadores para um outro sistema B. Então S (∑ i pi|i〉〈i| ⊗ ρi ) = H(pi) + ∑ i piS(ρi). (3.15) Exerćıcio 3.24 (Entropia de um produto tensorial) Use o teorema da entropia con- junta, para mostrar que S(ρ⊗σ) = S(ρ)+S(σ). Prove também este resultado diretamente da definição de entropia de von Neumann. Em analogia com a entropia de Shannon é posśıvel definir no contexto de entropia de von Neumann as entropias conjunta e condicional e também a informação mútua para sistemas quânticos compostos. A entropia conjunta (do estado ρAB) de um sistema AB será dada por S(A,B) ≡ S ( ρAB ) = −Tr(ρAB log(ρAB)). Dáı definimos, respectivamente, a entropia condicional e a informação mútua por: S(A|B) ≡ S(A,B)− S(B) = S ( ρAB ) − S ( ρB ) , (3.16) S(A : B) ≡ S(A) + S(B)− S(A,B) = S ( ρA ) + S ( ρB ) − S ( ρAB ) . (3.17) Exerćıcio 3.25 Calcule S (A|B) e S (A : B) para os estados do exerćıcio 3.20. Com- pare com as propriedades de H (A|B) e H (A : B) estudadas no caṕıtulo anterior. Tente interpretar seu resultado. Deve ser claro então que buscar cotas e relações envolvendo estas diversas entropias nos permite entendê-las melhor. Um bom exemplo está aqui: Teorema 3.7 (Subaditividade) Sejam A e B dois sistemas quânticos distintos de- scritos pelo estado conjunto ρAB. Então a entropia conjunta deste sistema satisfaz a desigualdade S(A,B) ≤ S(A) + S(B), (3.18) com a igualdade valendo apenas se ρAB = ρA ⊗ ρB. Prova: Pela desigualdade de Klein temos, S(ρ) ≤ −Tr(ρ log σ). Definindo ρ ≡ ρAB e σ = ρA ⊗ ρB temos as seguintes identidades −Tr(ρ log σ) = −Tr(ρAB(log ρA + log ρB)) = −Tr(ρA log ρA)− Tr(ρB log ρB) = S(A) + S(B). 3.5. ENTROPIA EM SISTEMAS COMPOSTOS 39 Usando então a desigualdade de Klein temos S(A,B) ≤ S(A) + S(B). Da condição de igualdade de desigualdade de Klein, segue a última afirmação. Queremos agora mostrar que a entropia de von Neumann é uma função côncava no con- junto dos operadores densidade, ou seja, dada uma distribuição de probabilidades pi e correspondentes operadores densidade ρi, a entropia satisfaz a desigualdade S (∑ i piρi ) ≥ ∑ i piS(ρi). (3.19) Para isso, suponhamos que ρi são estados de um sistema A e consideremos um sistema auxiliar B cujo espaço de estados tenha uma base ortonormal {|i〉}. Consideremos o estado ρAB ≡ ∑ i piρi ⊗ |i〉〈i| para o sistema composto. Obtemos as seguintes identidades S(A) = S ( ∑ i piρi) , S(B) = S ( ∑ i pi|i〉〈i|) = H(pi), S(A,B) = H(pi) + ∑ i piS(ρi). Finalmente, usando a subaditividade de S(A,B), temos (3.19). Exerćıcio 3.26 Prove que vale a igualdade em (3.19) se, e somente se, a combinação convexa for trivial. Exerćıcio 3.27 Mostre que existe um conjunto de matrizes unitárias {Uj} e um vetor de probabilidade (pj) tais que, para qualquer matriz A,∑ i piUiAU † i = Tr(A) I d , onde d é a dimensão do espaço onde A esta definida. Use esta informação e a concavidade estrita da entropia para dar outra demonstração de que a entropia atinge seu máximo na matriz I d . Exerćıcio 3.28 Seja P um projetor e Q = I − P o projetor complementar. Prove que existem operadores unitários U1 e U2 e um parâmetro p ∈ [0, 1] tais que para todo ρ, PρP+QρQ = pU1ρU † 1 +(1−p)U2ρU † 2 . Use esta observação para dar uma prova alternativa do teorema 3.3. 42 CAPÍTULO 3. ENTROPIA E TEORIA QUÂNTICA DA INFORMAÇÃO Exerćıcio 3.29 Seja ρ = ρ⊗n1 como acima. Faça o traço parcial em n − 1 qubits para obter o estado do qubit restante. Use seu resultado para justificar a afirmativa que esta é a generalização natural de iid. Vamos introduzir agora as idéias da versão quântica das seqüências t́ıpicas. Suponha que o operador densidade ρ1 tenha uma decomposição ortonormal ρ1 = ∑ x p(x)|x〉〈x|, (3.21) onde {|x〉} é um conjunto ortonormal e (p(x)) um vetor de probabilidades (no caso de qubits, x = 0, 1, mas a definição pode considerar dimensão arbitrária; é importante notar que os vetores |x〉 são determinados pela diagonalização de ρ1). Podemos definir sequências ε-t́ıpicas {x1, . . . , xn} como sendo as seqüências para as quais se verifica a desigualdade ∣∣∣∣ 1n log ( 1 p(x1) . . . p(xn) ) − S(ρ) ∣∣∣∣ ≤ ε, onde a única diferença para o caso clássico é a entropia utilizada. Um estado ε-t́ıpico é um estado |x1〉|x2〉 . . . |xn〉 para o qual a seqüência {x1, . . . , xn} é ε-t́ıpica. Definimos o subespaço ε-t́ıpico como sendo o subespaço gerado por todos os estados ε-t́ıpicos. Deno- taremos o subespaço ε-t́ıpico por T (n, ε) e o projetor neste subespaço por P (n, ε). Note que P (n, ε) = ∑ {xi}ni=1 ε-t́ıpica |x1〉〈x1| ⊗ |x2〉〈x2| ⊗ . . .⊗ |xn〉〈xn|. Teorema 3.9 (Teorema do Subespaço T́ıpico) Seja ρ operador densidade sobre V , com P (n, ε) e T (n, ε) definidos acima. 1. Dado ε > 0, temos lim n→∞ Tr(P (n, ε)ρ⊗n) = 1. Em palavras, o traço da restrição de n cópias de ρ ao subespaço ε-t́ıpico tende a 1 quando n vai para infinito. 2. Dados ε > 0 e δ > 0, existe no ∈ N tal que (1− δ)2n(S(ρ)−ε) ≤ dim (T (n, ε)) ≤ 2n(S(ρ)+ε), ∀n > no. 3. Sejam 0 < R < H (ρ) um número real e Π (n) um projetor sobre um subespaço de V ⊗n com dim (Π (n)) ≤ 2nR. Então, dado δ < 0, existe no ∈ N tal que Tr(Π (n) ρ⊗n) < δ, ∀n > no. 3.7. TEOREMA DE SCHUMACHER 43 Prova: Para provar (1) basta observar que Tr(P (n, ε)ρ⊗n) = ∑ {xi}ni=1 ε-t́ıpica p(x1) . . . p(xn) e usar o primeiro item do Teorema 2.5. (2) Segue diretamente do segundo item do Teorema 2.5. (3) Vamos fazer o traço separadamente no subespaço ε-t́ıpico e no seu complemento ortogonal, Tr(Π(n)ρ⊗n) = Tr(Π(n)ρ⊗nP (n, ε)) + Tr(Π(n)ρ⊗n(I − P (n, ε))), e cotar cada termo. Para o primeiro termo observe que ρ⊗nP (n, ε) = P (n, ε)ρ⊗nP (n, ε), já que P (n, ε) é um projetor que comuta com ρ⊗n. Mas Tr(Π(n)P (n, ε)ρ⊗nP (n, ε)) ≤ 2nR2−n(S(ρ)−ε), já que os autovalores de P (n, ε)ρ⊗nP (n, ε) são limitados superiormente por 2−n(S(ρ)−ε). Assim, existe n1 tal que Tr ( Π (n) ρ⊗nP (n, ε) ) ≤ δ 2 , ∀n > n1. Para o segundo termo note que I − Π (n) é operador positivo. Já que Π(n) e ρ⊗n(I − P (n, ε)) são ambos operadores positivos segue que 0 ≤ Tr ( Π(n)ρ⊗n(I − P (n, ε) ) ≤ Tr(ρ⊗n(I − P (n, ε)), e pelo item (1) exite n2 tal que Tr ( Π(n)ρ⊗n(I − P (n, ε)) ) ≤ δ 2 , ∀n > n2. Basta tomar no > max {n1, n2} para demonstrar o resultado. Dos ingredientes básicos, ainda precisamos definir um processo de compressão-descom- pressão e buscar a noção adequada de confiável . Um processo de compressão (de n cópias do estado, ou ainda, de um “bloco” de tamanho n) será uma aplicação Cn : V ⊗n → V nc , onde V nc é o chamado espaço de compressão. Um processo de descompressãov (para n cópias) é uma aplicação Dn : V nc → V ⊗n. Um processo de compressão-descompressão é uma seqüência de processos {Cn,Dn}∞n=1. A taxa de compressão do processo é dado pelo 44 CAPÍTULO 3. ENTROPIA E TEORIA QUÂNTICA DA INFORMAÇÃO limite limn→∞ log dim(V nc ) n , com a mesma interpretação que no caso clássico: a razão entre a quantidade de qubits necessária para armazenar de maneira confiável a informação contida em n qubits caracterizados pelo estado ρ e esse número total de qubits, n. É importante enfatizar que em aplicações práticas simplesmente toma-se n “suficientemente grande”, mas na sua descrição teórica aparecem as seqüências e os limites acima. Por fim, confiabilidade. A idéia deve ser clara: queremos que Dn ◦ Cn seja “efetivamente” próxima da identidade. É claro que se dim (Vc) < 2 n, tal composição não pode ser rigorosamente a identidade. Mas não precisamos disso. O que precisamos é ter Dn ◦ Cnρ⊗n ≈ ρ⊗n. Mas ainda falta dizer o que significa “≈” nessa expressão. Para isso, usaremos a noção de fidelidade de um processo quântico. Inspirado nos processos de medição, podemos definir: Definição 3.13 (Processos Quânticos) Um processo quântico E será definido por um conjunto de operadores {Ei} tais que ∑ i Tr ( E†iEi ) = 1 pela seguinte operação ρ 7−→ ∑ i EiρEi. (3.22) Definição 3.14 (Fidelidade) Se um processo quântico E é dado pelos operadores {Ei}, a fidelidade de E quando aplicado ao estado ρ é dada por F (E , ρ) = ∑ i |Tr (ρEi)|2 . (3.23) Agora sim temos os ingredientes para a noção de confiável: para δ > 0, um par (Cn,Dn) é dito δ-confiável se F ( Dn ◦ Cn, ρ⊗n ) > 1− δ. Dizemos que um processo de compressão é confiável se, dado δ > 0, existe no tal que para todo n > no os pares (Cn,Dn) são δ-confiáveis. Teorema 3.10 (Teorema de Schumacher) Seja ρ um operador densidade em V . Se R > S(ρ) então existe um esquema de compressão confiável de razão R. Se R < S(ρ) então qualquer sistema de compressão de razão R não é confiável. Caṕıtulo 4 Entropia e Mecânica Estat́ıstica O objetivo deste caṕıtulo é fazer uma breve introdução à Mecânica Estat́ıstica do Equiĺı- brio a volume finito (veja a Seção 4.1) com o intuito de provar o Teorema 4.2. Este teorema é o equivalente, no equiĺıbrio, do Teorema H de Boltzmann. O Teorema H de Boltzmann afirma que a entropia H de um gás de part́ıculas, que está sob a ação de uma força externa atenuante e dependente do tempo, tende a crescer à medida que o tempo passa. Por outro lado, a Segunda Lei da Termodinâmica afirma que os sistemas f́ısicos isolados tendem ao equiĺıbrio ao longo do tempo. Assim sendo, somos levados a concluir do teorema, juntamente com a Segunda Lei, que os estados de equiĺıbrio de um sistema f́ısico são aqueles de maior entropia. No jargão popular, os sistemas f́ısicos fora do equiĺıbrio evoluem para o estado de maior entropia. O Teorema 4.2 é a manifestação deste comportamento, supondo de antemão que o sistema já esteja em equiĺıbrio termodinâmico. Em poucas palavras, o teorema afirma que o máximo da entropia, vista como função das probabilidades que descrevem o sistema, é atingido quando a probabilidade é aquela fornecida pelo regra de Gibbs (ou Boltzmann), veja a Definição 4.1. Este caṕıtulo é auto-contido. Contudo, caso o leitor queira se aprofundar no assunto, sugerimos a leitura das referências [3, 7, 8], de onde foi retirado o material para escrever estas notas. 47 48 CAPÍTULO 4. ENTROPIA E MECÂNICA ESTATÍSTICA 4.1 Definições Preliminares No que se segue, Λ representará um hipercubo em Zd, como definido a seguir: dado N ∈ N, seja Λ ≡ [−N,N ]d ∩ Zd. Contudo, deve-se ter em mente que Λ poderia ser um subconjunto arbitrário de Zd. A escolha do hipercubo é feita somente para facilitar a exposição. O conjunto Λ depende de N e é chamado de rede. Os seus elementos são chamados de śıtios. Denotaremos por |Λ| a cardinalidade de Λ, isto é, o número de śıtios em Λ. Neste texto trabalharemos somente com redes finitas (|Λ| <∞). As questões aqui tratadas podem ser reformuladas no limite termodinâmico (isto é, no limite |Λ| → ∞), mas nós não faremos isto pois os pré-requisitos para entendê-las são bem mais avançados. Exerćıcio 4.1 Para N = 1 e d = 1, 2 e 3, faça um desenho da rede Λ e calcule |Λ|. Deduza que, em geral, |Λ| = (2N + 1)d. A cada śıtio i ∈ Λ nós associamos uma variável aleatória σi ∈ {−1, 1}, chamada de spin, com distribuição uniforme. Um ponto σ ∈ Ω ≡ {−1, 1}|Λ| é uma configuração de spins e Ω é o espaço das configurações. Exerćıcio 4.2 Para N = 1 = d, determine todas as posśıveis configurações de spin. Para valores arbitrários de N e d, mostre que a cardinalidade de Ω é igual a 2|Λ|. Exerćıcio 4.3 Se S ∈ Z+ é dado e se σ é uma variável aleatória assumindo valores em {−S,−S + 1, · · · ,−1, 0,+1, · · · , S − 1, S}, determine Ω e |Ω|. A cada configuração σ ∈ Ω nós associamos uma energia (ou Hamiltoniano) EΛ(σ). Então EΛ(σ) é uma função de Ω em R. Exerćıcio 4.4 Se N = 1 = d, calcule os posśıveis valores de EΛ(σ), onde EΛ(σ) ≡ −(σ0σ1 + σ0σ−1). A expressão da energia como função de σ é parte importante dos chamados modelos em mecânica estat́ıstica. Para a compreensão das próximas seções deste caṕıtulo, não 4.1. DEFINIÇÕES PRELIMINARES 49 é importante entender modelos espećıficos, embora sejam importantes exemplos (nesse contexto você será convidado a resolver o Exerćıcio 4.7). Denotaremos por β ao inverso de K T , onde K > 0 é a constante de Boltzmann e T é a temperatura. Veremos β como um parâmetro, sendo introduzido na teoria via o fator de Gibbs da configuração σ e−βEΛ(σ). Sobre Ω nós definimos uma medida de probabilidade µΛ,β(·), também chamada de medida de Gibbs a volume finito (associada à energia EΛ e com parâmetro β) µΛ,β(σ) = e−βEΛ(σ) ZΛ(β) , (4.1) onde ZΛ(β) é um fator de normalização tal que µΛ,β(Ω) = 1. ZΛ(β) é a função partição e ela só depende dos parâmetros da teoria. A construção da medida 4.1 é o que chamamos de Ensemble Canônico. Se tivéssemos olhado para configurações de energia constante, teŕıamos o Ensemble Microcanônico. Exerćıcio 4.5 Da definição de µΛ,β(·), conclua que ZΛ(β) = ∑ σ∈Ω e−βEΛ(σ). Se f é uma função das configurações σ ∈ Ω, então sua esperança, ou seu valor esperado, ou ainda seu valor médio (com respeito a µΛ,β(·)) é 〈f〉Λ = ∑ σ∈Ω f(σ)µΛ,β(σ). (4.2) É também comum representar o valor esperado de f por µΛ,β(f). Definição 4.1 (Hamiltoniano de Ising) O Hamiltoniano EΛ(σ) ≡ − ∑ 〈i,j〉 σiσj − h ∑ i∈Λ σi, (4.3) onde a primeira soma é feita sobre pares de śıtios vizinhos dentro do volume Λ, onde σ = ±1 e onde h ∈ R, é chamado de“Hamiltoniano de Ising com campo magnético externo h e com condições de contorno livres”. 52 CAPÍTULO 4. ENTROPIA E MECÂNICA ESTATÍSTICA Teorema 4.1 (O Prinćıpio Variacional) Fixados Λ, β e EΛ, seja µΛ,β(·) a medida de Gibbs a volume finito Λ associada à energia EΛ e com parâmetro β. Então sup µ∈M pΛ,β (µ) = H(µΛ,β)− βµΛ,β(EΛ), (4.7) e µΛ,β(·) é a única medida em M onde ocorre o supremo. Prova: Para qualquer µ ∈M, a pressão pΛ,β(µ) pode ser reescrita como pΛ,β(µ) = H(µ)− βµ(EΛ) = − ∑ σ µ(σ) lnµ(σ)− β ∑ σ EΛ,β(σ)µ(σ) = − ∑ σ µ(σ) [lnµ(σ) + βEΛ,β(σ)] = ∑ σ µ(σ) ln ( e−βEΛ,β(σ) µ(σ) ) . Usando agora que lnx é uma função estritamente côncava e que vale uma desigualdade de Jensen para funções côncavas (veja Exerćıcio 2.7), conclúımos que pΛ,β(µ) ≤ ln (∑ σ µ(σ) ( e−βEΛ,β(σ) µ(σ) )) = lnZΛ(β) = pΛ,β(µΛ,β). Portanto, o máximo da pressão a volume finito é atingido em µ = µΛ,β ∈ M. Com isto, provamos a existência do ponto de máximo. Para a unicidade, observe que, ainda pelo Exerćıcio 2.7, a desigualdade acima torna-se uma igualdade se e somente se a razão e−βEΛ,β(σ) µ(σ) é constante para todo σ ∈ Ω. Como µ é uma medida de probabilidade, é fácil concluir que, neste caso, a constante de proporcionalidade tem que ser necessariamente a função partição. Dito de outra forma, a desigualdade acima torna-se uma igualdade se e somente se e−βEΛ,β(σ) ZΛ(β) = µ(σ) ∀ σ ∈ Ω. Exerćıcio 4.9 Prove o Teorema 4.1 usando multiplicadores de Lagrange. Para isto, con- sidere a pressão a volume finito como função das 2|Λ| variáveis µ(σ), σ ∈ Ω. Determine o seu ponto de máximo, estando ela sujeita à restrição ∑ σ µ(σ) = 1. 4.2. O PRINCÍPIO VARIACIONAL 53 Definição 4.3 (Estado de Equiĺıbrio) Uma medida de probabilidade µ ∈ M é um estado de equiĺıbrio associado à energia EΛ se o supremo de (4.6) é atingido em µ. Observação: Segue então do Teorema 4.1 e da Definição 4.3 que toda medida de Gibbs a volume finito, associada à energia EΛ, é um estado de equiĺıbrio. Em Termodinâmica definem-se os potenciais termodinâmicos ou energias livres. Toda a descrição termodinâmica de um sistema f́ısico é dada a partir do conhecimento do potencial termodinâmico adequado. Dentre eles destacamos a energia livre de Gibbs FΛ,T (µ) = µ(EΛ)−KTH(µ). (4.8) É claro que podemos reformular o Prinćıpio Variacional 4.1 em termos desta energia livre: a medida de Gibbs µΛ,β minimiza a energia livre de Gibbs, sendo a única medida minimizante, isto é FΛ,T (µ) ≥ FΛ,T (µΛ,β) = −KT lnZΛ(β). Usando a definição da função partição a volume finito Λ e com energia EΛ(σ) (veja Exerćıcio 4.5) e usando a regra da cadeia, podemos deduzir as seguintes relações para as derivadas da pressão a volume finito da medida de Gibbs µΛ,β: Exerćıcio 4.10 Mostre que, para qualquer valor de β ∈ R, valem as indentidades: d dβ lnZΛ(β) = −µΛ,β(EΛ), d2 dβ2 lnZΛ(β) = µΛ,β(E 2 Λ)− [µΛ,β(EΛ)]2. (4.9) Exerćıcio 4.11 Usando que |Ω| < ∞, que µΛ,β(Ω) = 1 e a desigualdade de Cauchy- Schwartz em R|Ω|, conclua que µΛ,β(E 2 Λ)− [µΛ,β(EΛ)]2 ≥ 0. Em particular, conclua que a pressão a volume finito de uma medida de Gibbs é uma função convexa (côncova) de β (de T ). Exerćıcio 4.12 (Entropia-Energia) Mostre que d dT H(µΛ,β) = 1 KT d dT µΛ,β(EΛ) (4.10) e conclua, novamente, que a pressão a volume finito é uma função côncova de T . 54 CAPÍTULO 4. ENTROPIA E MECÂNICA ESTATÍSTICA Observação: A identidade (4.10) é a forma mais clara de se exprimir uma relação in- finitesimal muito conhecida em Termodinâmica: dS = dQ T . Essa relação exprime o fato que a realização de trabalho vem sempre acompanhado de um aumento de entropia. O Exerćıcio 4.12 mostra que esta relação pode ser obtida, de certa maneira, das definições dadas anteriormente. O Teorema 4.1 tem o seguinte corolário Teorema 4.2 (Entropia Maximal) Seja E∗ um número real entre o mı́nimo e o máxi- mo da energia EΛ(σ), σ ∈ Ω. Existe um único valor β∗ de β tal que a medida de Gibbs a volume finito, associada à energia EΛ(σ) e com valor de pârametro β ∗, satifaz à condição µΛ,β∗(EΛ) = E ∗ e tal que µΛ,β∗(·) maximiza a entropia em M. Prova: O valor médio µΛ,β(EΛ) é, claramente, uma função cont́ınua de β pois, pelas relações (4.1) e (4.2), o valor médio é a razão de duas funções cont́ınuas, sendo que o denomindor nunca se anula pois ele é uma soma finita de exponenciais. Pelos ex- erćıcios 4.10 e 4.11, µΛ,β(EΛ) é uma função decrescente de β. Portanto, existem os limites limβ→−∞ µΛ,β(EΛ) e limβ→+∞ µΛ,β(EΛ). É claro que as desigualdades limβ→−∞ µΛ,β(EΛ) ≤ maxσEΛ(σ) e limβ→+∞ µΛ,β(EΛ) ≥ minσEΛ(σ) são satisfeitas. Na verdade, vale sempre a igualdade pois, como tanto o numerador quanto o denominador são somas finitas en- volvendo exponenciais de β, o limite da razão é determinado pelo termo exponencial dominante (exp[−βmaxσEΛ(σ)] se β → −∞ e exp[−βminσEΛ(σ)] se β → +∞). Portanto, seja E∗ um número real tal que minσEΛ(σ) < E ∗ < maxσEΛ(σ). Pela con- tinuidade e monotonicidade de µΛ,β(EΛ) como função de β, existe um valor β ∗ tal que µΛ,β∗(EΛ) = E ∗. Agora, seja µ ∈ M tal que µ(EΛ) = E∗. Então, pelo Prinćıpio Varia- cional teremos que H(µ)− β∗E∗ = H(µ)− β∗µ(EΛ) ≤ H(µΛ,β∗)− β∗µΛ,β∗(EΛ) ≤ H(µΛ,β∗)− β∗E∗. Conseqüentemente, H(µ) ≤ H(µΛ,β∗) para qualquer µ ∈M satisfazendo µ(EΛ) = E∗.