Departamento de Ciência da Computação Instituto de Matemática e Estatı́stica Universidade de São Paulo Computação Quântica: Complexidade e Algoritmos Carlos H. Cardonha Marcel K. de Carli Silva Cristina G. Fernandes (orientadora) Iniciação Cientı́fica: Agosto/2003 a Dezembro/2004 Apoio Financeiro da FAPESP 03/13236-0 e 03/13237-7 Sumário Introdução I 5 Aspectos Algorı́tmicos 10 1 Bits, registradores e circuitos quânticos 1.1 Bits quânticos . . . . . . . . . . . . . . . . . 1.1.1 ? Representação gráfica de um qubit 1.1.2 ? Decomposição de matrizes unitárias 1.2 Registradores quânticos . . . . . . . . . . . . 1.3 Reversibilidade . . . . . . . . . . . . . . . . 1.4 Circuitos quânticos . . . . . . . . . . . . . . 1.5 Teorema do no-cloning . . . . . . . . . . . . 1.6 Emaranhamento quântico . . . . . . . . . . 2 Algoritmos quânticos 2.1 Paralelismo quântico . . . . . 2.2 Medida do consumo de tempo 2.3 O problema de Deutsch . . . . 2.4 O problema de Deutsch-Jozsa 2.5 O problema de Simon . . . . . . . . . . . . . . . . . . . . 3 O algoritmo de fatoração de Shor 3.1 Visão geral do algoritmo . . . . . . 3.2 Redução à busca do perı́odo . . . . 3.3 Busca do perı́odo . . . . . . . . . . 3.4 A transformada quântica de Fourier 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 11 13 15 19 23 24 26 28 . . . . . 30 30 33 34 37 40 . . . . 43 43 44 47 50 II Resultados de Complexidade 54 4 Máquinas de Turing 4.1 Máquina de Turing determinı́stica . . . . 4.2 Máquinas de Turing não-determinı́sticas 4.3 Máquina de Turing probabilı́stica . . . . 4.4 Máquina de Turing quântica . . . . . . . 4.5 Recursos e linguagens . . . . . . . . . . . . . . . . 55 55 57 58 58 59 . . . . . 63 63 65 65 70 71 . . . . . 74 74 80 80 80 81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Máquinas de Turing universais 5.1 Máquina de Turing determinı́stica universal . . . . . . . . 5.2 Máquina de Turing quântica universal . . . . . . . . . . . 5.2.1 Decomposição de uma transformação unitária . . . 5.2.2 Cálculo de transformações quase-triviais . . . . . . 5.2.3 Descrição da máquina de Turing quântica universal 6 Classes de complexidade 6.1 Classes de complexidade do modelo clássico 6.2 Classes quânticas de complexidade . . . . . 6.3 Recursos e linguagens no modelo quântico . 6.4 As classes EQP e BQP . . . . . . . . . . . 6.5 Relações envolvendo as classes quânticas . . III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Apêndices 85 A Espaços de Hilbert A.1 Espaços vetoriais, produto interno e norma . . . . A.2 Espaço de Hilbert conjugado . . . . . . . . . . . . A.3 Bases ortonormais . . . . . . . . . . . . . . . . . . A.4 Operadores lineares . . . . . . . . . . . . . . . . . A.5 Autovalores, autovetores e representação espectral A.6 Produto tensorial . . . . . . . . . . . . . . . . . . . . . . . . 86 86 89 89 91 92 94 B Mecânica quântica B.1 Axiomas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.1 Estados quânticos . . . . . . . . . . . . . . . . . . . . . . 96 96 96 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.2 Observáveis e medições . . . . . . . . . . . . . . . . . . . B.2 Experimento com polarização de fótons . . . . . . . . . . . . . . C Teoria dos números C.1 Divisibilidade e primalidade . . C.2 Teoria dos grupos . . . . . . . . C.3 Teorema do resto chinês . . . . C.4 Equações modulares . . . . . . C.5 Considerações computacionais . C.5.1 O algoritmo de Euclides C.5.2 Exponenciação modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 98 100 100 103 108 110 112 113 115 D Testes de primalidade e Criptografia RSA 117 D.1 Os problemas da primalidade e da fatoração . . . . . . . . . . . 117 D.2 O Teste de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . 120 D.3 O sistema de criptografia RSA . . . . . . . . . . . . . . . . . . . 125 E Circuitos clássicos E.1 Portas universais . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Complexidade de circuitos . . . . . . . . . . . . . . . . . . . . . E.3 Computação reversı́vel . . . . . . . . . . . . . . . . . . . . . . . 129 130 131 132 Referências bibliográficas 134 Índice remissivo 142 4 Introdução Em 1900, em uma palestra marcante no Congresso Internacional de Matemáticos realizado em Paris, Hilbert postulou 23 problemas matemáticos, que tratam de temas diversos em matemática e áreas afins. O décimo problema na lista de Hilbert (determination of the solvability of a diophantine equation) pergunta se é possı́vel determinar se uma equação diofantina arbitrária tem ou não solução por meio de um “processo finito”: Given a diophantine equation with any number of unknown quantities and with rational numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. Esse problema pode ser postulado em uma linguagem mais atual como o seguinte: existe um algoritmo que, dada uma equação diofantina, determina se esta tem ou não solução? Note que a questão postulada por Hilbert precede de décadas a invenção de computadores. Foi apenas nos anos 30 que tais questões foram formuladas e tratadas dentro do que ficou depois conhecido como teoria da computabilidade. Esta é a parte da teoria da computação especializada em lidar com esse tipo de questão. Foi nos anos 30, após um trabalho de Gödel em lógica, que a idéia de algoritmo começou a ser formalizada. Gödel [Göd31] introduziu o conceito de função primitiva recursiva como uma formalização dessa idéia. Church [Chu33, Chu36] introduziu o λ-cálculo e Kleene [Kle36] definiu o conceito de funções recursivas parciais e mostrou a equivalência entre esse e o λ-cálculo. Turing [Tur36, Tur37] por sua vez propôs a sua formalização da idéia de algoritmo: as chamadas máquinas de Turing. Nesses trabalhos, Turing mostrou também a equivalência do conceito de máquinas de Turing e de funções recursivas parciais. Vale mencionar que o conceito de máquinas de Turing foi independentemente proposto por Post [Pos36], um professor de colegial de Nova Iorque. Cada uma dessas propostas diferentes do conceito de algoritmo é chamada de modelo de computação. 5 Foi Kleene [Kle52] quem chamou de tese de Church a afirmação de que todo modelo de computação razoável é equivalente ao da máquina de Turing. A afirmação é propositalmente vaga, pois visa capturar mesmo modelos que ainda venham a ser propostos, e cuja natureza não podemos prever. Por razoável entende-se um modelo que seja realista, no sentido de poder (mesmo que de maneira aproximada) ser construı́do na prática. A teoria da computabilidade no fundo diferencia os problemas decidı́veis (para os quais existe um algoritmo) dos indecidı́veis (para os quais não existe um algoritmo). O surgimento dos computadores nas décadas de 30 e 40 aos poucos evidenciou uma diferença entre os problemas decidı́veis: muitos parecem ser bem mais difı́ceis que outros, no sentido de que se conhece apenas algoritmos extremamente lentos para eles. Com isso, surgiu a necessidade de refinar a teoria de computabilidade para tentar explicar essas diferenças. Foi apenas nos anos 60 que a teoria de complexidade, que trata de tais questões, tomou corpo, com a formalização da idéia de algoritmo eficiente, independentemente introduzida por Cobham [Cob65] e Edmonds [Edm65], e a proposta de reduções eficientes entre problemas, feita por Karp [Kar72]. Foi nessa época que surgiram as definições das classes de complexidade P e NP e do conceito de NP-completude, que captura de certa maneira a dificuldade de se conseguir algoritmos eficientes para certos problemas. Grosseiramente, um problema em NP é dito NP-completo se qualquer outro problema da classe NP pode ser reduzido eficientemente a ele. A mais famosa questão na área de teoria da computação é se P é ou não igual a NP. Se for mostrado que algum problema NP-completo está em P, então tal questão é resolvida e fica provado que P = NP. Um marco na teoria de complexidade é o teorema de Cook [Coo71, Lev73], que prova a existência de problemas NP-completos. Cook mostrou que o problema conhecido como sat, de decidir se uma fórmula booleana em forma normal conjuntiva é ou não satisfatı́vel, é NP-completo. Após o teorema de Cook e o trabalho de Karp [Kar72], que mostrou que vários outros problemas conhecidos são NP-completos, essa teoria se desenvolveu amplamente, tendo estabelecido a dificuldade computacional de problemas das mais diversas áreas, como mostram Garey e Johnson [GJ79]. Um dos problemas mais famosos cuja complexidade continua em aberto, mesmo após várias décadas de esforço da comunidade no sentido de resolvê-lo, é o problema da fatoração de inteiros: dado um inteiro, determinar a sua fatoração em números primos. Recentemente, o seu parente próximo, o problema de decidir se um número inteiro é primo ou não, chamado de problema da primalidade, teve sua complexidade totalmente definida, com o algoritmo aks, de Agrawal, Kayal e Saxena [AKS02a, AKS02b]. Esse algoritmo mostra que o pro6 blema da primalidade está na classe P, resolvendo com isso uma questão em aberto há anos. Não se sabe até hoje, no entanto, se há um algoritmo eficiente para resolver o problema da fatoração de inteiros! Na verdade, a dificuldade computacional do problema da fatoração de inteiros tem sido usada de maneira crucial em alguns sistemas criptográficos bemconhecidos. Se for descoberto um algoritmo eficiente para resolver o problema da fatoração, vários sistemas criptográficos importantes seriam quebrados, incluindo o famoso sistema rsa de chave pública, criado por Rivest, Shamir e Adleman [RSA78]. O assunto de nossa iniciação cientı́fica — Computação Quântica — trata de um novo modelo de computação, o modelo quântico, que vem levantando questões intrigantes dentro da teoria de complexidade, e pode ter impactos práticos dramáticos no mı́nimo na área de criptologia. O modelo quântico de computação não infringe a validade da tese de Church, porém questiona a validade de uma versão mais moderna dessa, a chamada tese de Church estendida, que diz que todo modelo de computação razoável pode ser simulado eficientemente por uma máquina de Turing. Pode-se dizer que a teoria de computação quântica iniciou-se nos anos 80, quando Feynman [Fey82] observou que um sistema quântico de partı́culas, ao contrário de um sistema clássico, parece não poder ser simulado eficientemente em um computador clássico, e sugeriu um computador que explorasse efeitos da fı́sica quântica para contornar o problema. Desde então, até 1994, a teoria de computação quântica desenvolveu-se discretamente, com várias contribuições de Deutsch [Deu85, Deu89], Bernstein e Vazirani [BV97], entre outros, que colaboraram fundamentalmente para a formalização de um modelo computacional quântico. Foi apenas em 1994 que a teoria recebeu um forte impulso e uma enorme divulgação. Isso deveu-se principalmente ao algoritmo de Shor [Sho94, Sho97], um algoritmo quântico eficiente para o problema da fatoração de inteiros, considerado o primeiro algoritmo quântico combinando relevância prática e eficiência. O algoritmo de Shor é uma evidência de que o modelo computacional quântico proposto pode superar de fato o modelo clássico, derivado das máquinas de Turing. O resultado de Shor impulsionou tanto a pesquisa prática, objetivando a construção de um computador segundo o modelo quântico, quanto a busca por algoritmos criptográficos alternativos e algoritmos quânticos eficientes para outros problemas difı́ceis. Essas e várias outras questões, relacionadas tanto com a viabilidade do modelo quântico quanto com as suas limitações, têm sido objeto de intensa pesquisa cientı́fica. Do ponto de vista prático, busca-se descobrir se é ou não viável construir um computador segundo o modelo quântico que seja capaz de manipular núme7 ros suficientemente grandes. Tal viabilidade esbarra em uma série de questões técnicas e barreiras fı́sicas e tecnológicas. Já se tem notı́cia de computadores construı́dos segundo o modelo quântico, mas todos ainda de pequeno porte. Em 2001, por exemplo, foi construı́do um computador quântico com 7 qubits (o correspondente aos bits dos computadores tradicionais). Nesse computador, foi implementado o algoritmo de Shor que, nele, fatorou o número 15. Uma parte dos cientistas da computação acredita que a construção de computadores quânticos de maior porte será possı́vel, enquanto outra parte não acredita nisso. Do ponto de vista de teoria de complexidade, busca-se estabelecer a relação entre as classes de complexidade derivadas do modelo quântico e as classes de complexidade tradicionais. Também busca-se, claro, estabelecer a complexidade no modelo quântico de problemas bem conhecidos, ou seja, busca-se por algoritmos quânticos eficientes para outros problemas relevantes. Organização do texto Este texto está dividido em três partes. A primeira concentra-se nos resultados algorı́tmicos da área, a segunda, nos tópicos de teoria de complexidade computacional e a terceira consiste em uma coleção de apêndices, cada um sobre um assunto que é um pré-requisito ou é relacionado aos tratados nas duas partes principais. A parte algorı́tmica começa descrevendo os componentes básicos de um computador quântico e a formalização de suas operações básicas. Alguns algoritmos quânticos simples são apresentados e finalmente o algoritmo de Shor é descrito e analisado. A formalização de um computador quântico utiliza fortemente espaços de Hilbert e algumas noções de mecânica quântica. O apêndice A trata de espaços de Hilbert e o apêndice B, de mecânica quântica. Esses apêndices podem ser ignorados, lidos ou consultados esporadicamente dependendo da bagagem prévia do leitor. Para a compreensão do algoritmo de Shor, vários resultados básicos de teoria dos números são necessários. O apêndice C apresenta todos os resultados relevantes de teoria dos números para o estudo do algoritmo de Shor e testes de primalidade ou algoritmos de fatoração em geral. Além disso, esse apêndice contém também a descrição e análise de várias rotinas básicas que são usadas na descrição de testes de primalidade e, em particular, no algoritmo de Shor. O apêndice D está também relacionado ao algoritmo de Shor, porém não como um pré-requisito, mas como uma curiosidade ou paralelo. Para leitores com menos familiaridade com ciência da computação, recomendamos a sua leitura. Nele, são apresentados e discutidos alguns resultados tradicionais de teste de 8 primalidade. Uma seção curta deste apêndice comenta também o sistema RSA e sua relação com testes de primalidade e algoritmos de fatoração. A segunda parte do texto trata de resultados de complexidade computacional. Ela começa apresentando as máquinas de Turing tradicionais e a máquina de Turing quântica. Um resultado bastante complexo porém importante é apresentado a seguir: a descrição de uma máquina de Turing quântica universal. Depois disso, são introduzidas as várias classes de complexidade envolvidas e são apresentados vários resultados de complexidade entre essas classes. Esses resultados mostram algumas das técnicas usadas na simulação de máquinas de Turing quânticas, e ressalta as dificuldades nessas simulações frente às simulações tı́picas do modelo clássico. Esperamos com esse texto dar uma visão geral desta nova e intrigante área, tanto do ponto de vista algorı́tmico quanto do ponto de vista de teoria de complexidade. 9 Parte I Aspectos Algorı́tmicos 10 Capı́tulo 1 Bits, registradores e circuitos quânticos A apresentação dos resultados algorı́tmicos dessa área depende da formalização de alguns conceitos básicos. Introduziremos os conceitos de bits e registradores quânticos, que são os blocos fundamentais de um computador quântico, bem como a noção de circuitos quânticos, que correspondem ao conceito de algoritmo no modelo tradicional. 1.1 Bits quânticos Seja H2 um espaço de Hilbert de dimensão 2. Fixe uma base ortonormal B2 := |0i, |1i de H2 . Um qubit ou bit quântico é um vetor unitário em H2 , isto é, um vetor |φi ∈ H2 é um qubit se |φi = α0 |0i + α1 |1i, (1.1) com α0 , α1 ∈ C e |α0 |2 +|α1 |2 = 1. Dizemos que os vetores |0i e |1i são os estados básicos e que o qubit |φi está numa superposição de estados básicos (contraste isto com o modelo clássico, onde um bit assume apenas um dos valores 0 ou 1). Chamamos ao coeficiente complexo αj de amplitude do estado básico |ji, para j = 0, 1. No modelo clássico, se tivermos em mãos um bit b, podemos descobrir sem problemas se b vale 0 ou 1 e isso em nada afeta o valor de b. Já no modelo quântico, não é possı́vel determinar o valor de um qubit |φi. Se tentarmos, o que observamos é o resultado de um evento probabilı́stico que tem como efeito colateral a alteração irreversı́vel do valor de |φi. Mais precisamente, ao medirmos o estado de um qubit |φi dado pela equação (1.1), enxergaremos 11 o “valor” |0i com probabilidade |α0 |2 e o “valor” |1i com probabilidade |α1 |2 . Se o “valor” observado for |0i, o estado do qubit |φi, imediatamente após a medição, será |0i, e analogamente se o estado observado for |1i. Note então que, apesar de um qubit armazenar uma superposição de estados, usando medições, só conseguimos obter dele um dos estados da superposição. Existem apenas duas portas lógicas operando sobre um bit clássico: a porta identidade e a negação. No modelo quântico de computação, qualquer transformação unitária em H2 é uma porta quântica. Uma matriz U ∈ C n×n é dita unitária se U ∗ U = U U ∗ = I, onde I é a matriz identidade e U ∗ é a transposta conjugada de U . Para trabalharmos com tais transformações, convencionamos que um qubit |φi dado pela equação (1.1) tem a seguinte representação na base B2 : α0 = |φi = α0 |0i + α1 |1i. (1.2) α1 Assim, a matriz de Hadamard 1 H := √ 2 1 1 1 −1 (1.3) transforma o qubit |0i no qubit 1 1 1 1 1 1 H|0i = =√ = √ |0i + |1i . 1 −1 0 2 1 2 (1.4) Como no caso de circuitos tradicionais, será útil convencionarmos uma representação gráfica para circuitos quânticos, indicando a ordem de aplicação de portas e medições. Por exemplo, o circuito ilustrado na figura 1.1 indica que a matriz de Hadamard H deve ser aplicada ao qubit |φi e depois o qubit resultante deve ser medido para obtermos o qubit |φ0 i. Se |φi for inicializado com |0i, então |φ0 i será |0i ou |1i equiprovavelmente, de acordo com a equação (1.4). |φi 76 01M54 23 H |φ0 i Figura 1.1: Um circuito quântico. É interessante observar como as medições afetam o comportamento do circuito. Por exemplo, se inicializarmos |φi com |0i, então |φ0 i no circuito quântico da figura 1.2 sempre será |0i. Já no circuito da figura 1.3, o estado |φ0 i será |0i ou |1i equiprovavelmente. 12 |φi H 76M23 54 01 H |φ0 i Figura 1.2: Mais um circuito. |φi H 76 01M54 23 H 76 01M54 23 |φ0 i Figura 1.3: Circuito com medição intercalada. 1.1.1 ? Representação gráfica de um qubit Vamos apresentar uma possı́vel representação gráfica para um qubit, que nos ajudará mais tarde a visualizar algumas operações sobre estes. Esta subseção é opcional e só utilizamos os resultados aqui encontrados na subseção 1.1.2, também opcional. Proposição 1.1. Sejam θ ∈ R e A uma matriz tal que A2 = I. Então eiθ = cos θ + i sen θ e eiθA = cos(θ)I + i sen(θ)A. Demonstração. Primeiro notamos que as expansões em séries de Taylor das funções ex , sen x e cos x são x e ∞ X xk xk x2 x3 + + ··· + + ··· = = 1+x+ 2! 3! k! k! k=0 ∞ 2k+1 X x2k+1 x3 x5 k x + + · · · + (−1) + ··· = (−1)k sen x = x − 3! 5! (2k + 1)! (2k + 1)! k=0 ∞ 2k 2k X x2 x4 k x k x cos x = 1 − + + · · · + (−1) + ··· = . (−1) 2! 4! (2k)! (2k)! k=0 Mas então temos (iθ)2 (iθ)3 (iθ)4 (iθ)5 + + + + ··· 2! 3! 4! 5! θ2 θ3 θ4 θ5 = 1 + iθ − −i + + i + ··· 2! 3! 4! 5! 2 4 θ θ θ3 θ5 = 1− + + ··· + i θ − + + ··· 2! 4! 3! 5! = cos θ + i sen θ. eiθ = 1 + iθ + 13 Similarmente, se expandirmos eA como eA := I + A + A2 A3 Ak + + ··· + + ···, 2! 3! k! teremos (iθA)2 (iθA)3 (iθA)4 (iθA)5 + + + + ··· 2! 3! 4! 5! θ3 θ4 θ5 θ2 = I + iθA − I − i A + I + i A + · · · 2! 3! 4! 5! 2 4 θ θ θ3 θ5 = 1− + + ··· I + i θ − + + ··· A 2! 4! 3! 5! = cos(θ)I + i sen(θ)A. eiθA = I + iθA + Note então que, dado z ∈ C, com |z| = 1, existe θ ∈ R tal que z = eiθ . Para encontrarmos um θ satisfazendo essa igualdade, sejam a e b tais que z = a + bi. Note que os sinais de a e b determinam o quadrante em que θ se encontra. Em particular, se a = 0, é óbvio que θ só pode ser π/2 ou −π/2, de acordo com o sinal de b. Se a 6= 0, então θ é dado pelo ângulo arctg b/a no respectivo quadrante. Proposição 1.2. Seja |ψi um qubit. Então existem γ, φ, θ ∈ R tais que |ψi = θ iγ e cos 2 |0i + eiφ sen 2θ |1i . Demonstração. Seja |ψi := α|0i + β|1i um qubit. Então temos que α, β ∈ C e |α|2 + |β|2 = 1. Segue que |α|2 ≤ 1 e portanto 0 ≤ |α| ≤ 1. Se |α| = 0, então temos α = 0 e |β| = 1. Neste caso, existe φ ∈ R tal que β = eiφ . Tome γ := 0 e θ := π e estamos feitos. Se |α| = 1, então temos β = 0 e existe γ ∈ R tal que α = eiγ . Tome φ := 0 e θ := 0 e estamos feitos. Senão, temos 0 < |α| < 1 e 0 < |β| < 1. Tome θ := 2 arccos |α|, de modo que cos(θ/2) = |α|. Como |α|2 + |β|2 = 1, segue que |β|2 = sen2 (θ/2) e portanto |β| = sen(θ/2). Tome α0 := α/ cos(θ/2) e β 0 := β/ sen(θ/2). Pelo que foi visto acima, temos |α0 | = |β 0 | = 1. Então existem γ, δ ∈ R tais que α0 = eiγ e β 0 = eiδ . Mas então |ψi = α|0i + β|1i = α0 cos(θ/2)|0i + β 0 sen(θ/2)|1i = eiγ cos(θ/2)|0i + eiδ sen(θ/2)|1i θ θ iγ i(δ−γ) = e cos |0i + e sen |1i . 2 2 14 Tome φ := δ − γ e estamos feitos. De acordo com os axiomas da mecânica quântica, apresentados na seção B.1, um bit quântico é simplesmente um estado quântico num sistema quântico representado por um espaço de Hilbert bidimensional. Vemos então, na proposição acima, que eiγ é um fator de fase global. Podemos então reenunciar este resultado de acordo com nossa discussão sobre estados quânticos indistingüı́veis, feita na subseção B.1.1: Proposição 1.3. Seja |ψi um qubit. Então existem ϕ, θ ∈ R tais que |ψi = cos 2θ |0i + eiϕ sen 2θ |1i. Diante desta maneira de escrever um qubit |ψi, podemos representar graficamente |ψi na esfera de Bloch (também chamada esfera de Poincaré), uma esfera de raio unitário. Como pode ser visto na figura 1.4, se ~r é a representação de |ψi, então a projeção de ~r sobre o plano xy forma um ângulo de ϕ com o eixo x e θ é o ângulo de ~r com o eixo z. Figura 1.4: Representação de |ψi := cos 2θ |0i + eiϕ sen 2θ |1i na esfera de Bloch. 1.1.2 ? Decomposição de matrizes unitárias Desenvolvemos nesta seção um resultado sobre decomposições de matrizes unitárias em C2×2 que mostra os “blocos fundamentais” de construção destas matrizes. Esta subseção é opcional e depende dos resultados encontrados na subseção 1.1.1, também opcional. 15 Considere as seguintes matrizes, denominadas matrizes de Pauli: 0 1 0 −i 1 0 σx := σy := σz := . 1 0 i 0 0 −1 (1.5) Vamos mostrar que os “blocos fundamentais”, que definimos a seguir, de construção de matrizes unitárias em C2×2 são gerados pelas matrizes de Pauli. Seja θ ∈ R. Definimos, para w = x, y, z, a matriz de rotação de θ sobre o eixo w como θ Rw (θ) := ei 2 σw , onde as matrizes σx , σy e σz foram definidas em (1.5) (observe que σx2 = σy2 = σz2 = I). Como indicado pelo nome, essas matrizes representam, na esfera de Bloch, uma rotação no sentido horário de um certo ângulo θ sobre um determinado eixo. Note que tais matrizes de fato são unitárias, já que θ θ θ ∗ θ ∗ cos I + i sen σw [Rw (θ)] Rw (θ) = cos I − i sen σw 2 2 2 2 θ θ θ θ = cos2 I + i cos sen (σw − σw∗ ) + sen2 I = I, 2 2 2 2 pois σw∗ = σw para w = x, y, z. Expandindo Rw (θ) para os três eixos, obtemos: cos 2θ i sen 2θ cos 2θ sen 2θ Rx (θ) = Ry (θ) = i sen 2θ cos 2θ − sen 2θ cos 2θ θ Rz (θ) = 0 ei 2 −i θ2 0 e ! . Essas transformações são importantes na decomposição de matrizes unitárias de dimensão 2 e recebem nomes especiais. Seguindo a terminologia estabelecida em Barenco et al. [BBC+ 95], definimos as seguintes transformações sobre H2 : cos 2θ sen 2θ • Rot(θ) := Ry (θ) = , uma rotação de θ; − sen 2θ cos 2θ iα e2 0 α • Ph(α) := Rz (α) = , uma mudança de fase de α; 0 e−i 2 iδ e 0 iδ • Scal(δ) := e I = , uma “escala” de δ. 0 eiδ 16 Além disso, a matriz σx também é chamada de “negação”. Com isso, estamos chamando de rotação apenas a rotação sobre o eixo y. A rotação sobre z muda tão somente a fase de um vetor e por isso recebe o nome de mudança de fase (phase shift). Já a operação de “escala” apenas altera o fator de fase global. Valem as seguintes propriedades, facilmente verificadas: 1. Rot(θ1 ) Rot(θ2 ) = Rot(θ1 + θ2 ); 2. Ph(α1 ) Ph(α2 ) = Ph(α1 + α2 ); 3. Scal(δ1 ) Scal(δ2 ) = Scal(δ1 + δ2 ); 4. σx Rot(θ) σx = Rot(−θ); 5. σx Ph(α) σx = Ph(−α). Com isso, podemos provar o seguinte: Teorema 1.4. Seja U ∈ C2×2 uma matriz unitária. Então existem α, β, γ, θ ∈ R tais que iα iβ e 0 cos θ i sen θ e 0 iγ U =e . (1.6) 0 e−iα i sen θ cos θ 0 e−iβ Demonstração. Vamos apresentar uma prova construtiva da existência da fatoração (1.6). Seja u11 u12 U= u21 u22 uma matriz unitária. Então suas colunas, que denotamos por U1 e U2 , bem como suas linhas, são ortonormais. Logo temos que hU1 |U1 i = u∗11 u11 + u∗21 u21 = kU1 k2 = 1. Portanto |u11 |2 + |u21 |2 = 1. (1.7) Similarmente, a primeira linha e a segunda coluna têm norma 1: |u11 |2 + |u12 |2 = 1 |u12 |2 + |u22 |2 = 1 (1.8) (1.9) e as colunas U1 e U2 são ortogonais, de forma que hU1 |U2 i = 0, ou seja, u∗11 u12 + u∗21 u22 = 0. 17 (1.10) Por (1.7), temos que |u11 |2 ≤ 1. Segue que 0 ≤ |u11 | ≤ 1. Se |u11 | = 0, então u11 = 0. Além disso, por (1.7), |u21 | = 1; por (1.8), |u12 | = 1; finalmente, por (1.9), |u22 | = 0 e portanto u22 = 0. Então existem a, b ∈ R tais que u21 = eia e u12 = eib . Tome α := 0, β := (a − b)/2, γ := (a + b − π)/2 e θ := π/2 e estamos feitos. Se |u11 | = 1, então por (1.7) temos |u21 | = 0 e imediatamente u21 = 0. Além disso, por (1.8), |u12 | = 0 de forma que u12 = 0; por (1.9), |u22 | = 1. Então existem a, b ∈ R tais que u11 = eia e u22 = eib . Tome α := 0, β := (a − b)/2, γ := (a + b)/2 e θ := 0 e estamos feitos. Senão, 0 < |u11 | < 1. Tome θ := arccos |u11 |, de forma que cos θ = |u11 | e 0 < θ < π/2. Por (1.7), |u21 |2 = 1 − cos2 θ = sen2 θ. Logo, |u21 | = | sen θ|. Semelhantemente, por (1.8), |u12 | = | sen θ| e, por (1.9), |u22 | = | cos θ|. Note também que, como 0 < θ < π/2, então cos θ 6= 0 6= sen θ. Tome a11 := u11 /(cos θ), a21 := u21 /(i sen θ), a12 := u12 /(i sen θ) e a22 := u22 /(cos θ). Note que |a11 | = 1/| cos θ| |u11 | = 1, |a21 | = 1/|i sen θ| |u21 | = 1, |a12 | = 1/|i sen θ| |u12 | = 1 e |a22 | = 1/| cos θ| |u22 | = 1. Então existem A11 , A12 , A21 , A22 ∈ R tais que aij = eiAij para 1 ≤ i, j ≤ 2. Agora tome α := −(A21 −A11 )/2, β := −(A12 −A11 )/2 e γ := (A12 +A21 )/2. Vamos verificar que essa fatoração de U é válida. Multiplicando todos os fatores de (1.6), obtemos i(γ+α+β) e cos θ ei(γ+α−β) i sen θ , ei(γ−α+β) i sen θ ei(γ−α−β) cos θ de modo que precisamos verificar que a11 = ei(γ+α+β) , a12 = ei(γ+α−β) , a21 = ei(γ−α+β) e a22 = ei(γ−α−β) . Veja que γ+α+β = A12 + A21 A21 − A11 A12 − A11 − − = A11 2 2 2 e então a11 = eiA11 = ei(γ+α+β) . É semelhantemente fácil verificar que α, β e γ também satisfazem as igualdades para a12 e a21 . Para a22 , primeiro note que γ−α−β = u∗11 A12 + A21 A21 − A11 A12 − A11 + + = A12 + A21 − A11 . (1.11) 2 2 2 Agora vamos substituir em (1.10) os valores que temos para U , isto é, = e−iA11 cos θ, u12 = eiA12 i sen θ, u∗21 = (eiA21 i sen θ)∗ = (ei(A21 +π/2) sen θ)∗ = 18 e−i(A21 +π/2) sen θ = −e−iA21 i sen θ e u22 = eiA22 cos θ: ⇒ ⇒ ⇒ ⇒ (e−iA11 cos θ)(eiA12 i sen θ) + (−e−iA21 i sen θ)(eiA22 cos θ) = 0 i cos θ · sen θ(ei(A12 −A11 ) − ei(A22 −A21 ) ) = 0 ei(A12 −A11 ) = ei(A22 −A21 ) , pois i cos θ · sen θ 6= 0 ei(A12 −A11 ) eiA21 = eiA22 ei(A12 +A21 −A11 ) = eiA22 . Mas então, de (1.11), ei(γ−α−β) = ei(A12 +A21 −A11 ) = eiA22 = a22 e estamos feitos. Ou seja, toda matriz unitária de dimensão 2 pode ser escrita como uma composição de rotações sobre determinados eixos, mais uma mudança no fator de fase global. Mais especificamente, como eiγ Rz (α)Rx (θ)Rz (β). Seguindo os mesmos passos desta demonstração, podemos provar outra forma geral dessas matrizes: Teorema 1.5. Seja U ∈ C 2×2 uma matriz unitária. Então existem α, β, γ, θ ∈ R tais que U = Scal(γ) Ph(α) Rot(θ) Ph(β). Esses resultados reforçam nossa intuição de que matrizes unitárias representam “rotações gerais” sobre um espaço vetorial. No caso, estamos afirmando que qualquer rotação na esfera de Bloch pode ser decomposta em rotações em eixos individuais. Tais rotações, geradas pelas matrizes de Pauli, são os “blocos fundamentais” de construção de matrizes unitárias em C2×2 . 1.2 Registradores quânticos Seja H2n um espaço de Hilbert de dimensão 2n . Denote por {0, 1}n o conjunto das cadeias de caracteres de comprimento n sobre o alfabeto {0, 1} e n fixe B2n := |xi : x∈ {0, 1} uma base ortonormal de H2n . Por exemplo, para n = 2 temos B4 = |00i, |01i, |10i, |11i . Um registrador quântico de n qubits é um vetor unitário em H2n , isto é, um vetor |φi ∈ H2n é um registrador quântico de n qubits se X αx |xi, (1.12) |φi = x∈{0,1}n com αx ∈ C para todo x ∈ {0, 1}n e X |αx |2 = 1. x∈{0,1}n 19 (1.13) A nomenclatura para qubits se estende para os registradores: os estados |xi com x ∈ {0, 1}n são os estados básicos, o qubit |φi é dito uma superposição de estados básicos e o coeficiente complexo αx é chamado de amplitude do estado básico |xi para todo x ∈ {0, 1}n . Será conveniente expressarmos o estado (1.12) como |φi = n −1 2X αx |xi, (1.14) x=0 onde estamos substituindo as cadeias de caracteres de {0, 1}n pelos valores numéricos que essas cadeias representam, se interpretadas como representação binária de números. Por exemplo, para n = 2, temos |φi = α|00i + β|01i + γ|10i + δ|11i = α|0i + β|1i + γ|2i + δ|3i. Continuando a estender a notação de qubits para registradores, a representação na base B2n do registrador quântico dado por (1.14) é α0 n −1 2X α1 αx |xi. .. = |φi = . x=0 α2n −1 A seguinte questão surge naturalmente: se |φi é um registrador cujos qubits, de menos para mais significativos, são |φ0 i, |φ1 i, . . . , |φn−1 i, qual é o estado quântico do registrador |φi, dados os estados de cada um dos qubits? A resposta é: |φi = |φn−1 i ⊗ |φn−2 i ⊗ · · · ⊗ |φ0 i, onde ⊗ denota o produto tensorial, que definimos a seguir. Sejam a11 · · · a1n b11 · · · b1q .. .. A = ... e B = ... . . . ... . . am1 · · · amn bp1 · · · bpq matrizes. O produto tensorial de A e B, denotado por A ⊗ B, é definido como a11 B · · · a1n B .. . .. A ⊗ B := ... (1.15) . . am1 B · · · amn B 20 Assim, um registrador |φi cujos qubits são |φ1 i e |φ0 i, com |φ1 i := α0 |0i + α1 |1i e |φ0 i := β0 |0i + β1 |1i, está no estado α β 0 0 α0 β1 α0 β0 |φi = |φ1 i ⊗ |φ0 i = ⊗ = α1 β0 α1 β1 α1 β1 e, portanto, |φi = α0 β0 |00i + α0 β1 |01i + α1 β0 |10i + α1 β1 |11i = α0 β0 |0i + α0 β1 |1i + α1 β0 |2i + α1 β1 |3i. (1.16) Outra questão natural é a inversa da anterior: se |φi é um registrador cujos qubits, de menos para mais significativos, são |φ0 i, |φ1 i, . . . , |φn−1 i, quais são os estados quânticos de cada um dos qubits, dado o estado do registrador |φi? Postergamos esta discussão para a seção 1.6. A medição de um registrador quântico funciona de modo semelhante à medição de qubits: se medirmos um registrador quântico |φi dado por (1.14), obtemos o estado básico |xi com probabilidade |αx |2 e, imediatamente após a medição, o estado do registrador será |xi. Ou seja, a superposição que existia anteriormente foi irreversivelmente perdida. Não é necessário, porém, medirmos todos os qubits do registrador: pode-se medir qubits individuais ou grupos de qubits. Por exemplo, se medirmos apenas o qubit |φ1 i do registrador |φi descrito acima na equação (1.16), existem duas possibilidades de resposta: • O valor observado é |0i. Esse evento ocorre com probabilidade |α0 β0 |2 + |α0 β1 |2 = |α0 |2 . Neste caso, o estado do registrador |φi, imediatamente após a medição, será |φ0 i = α0 β0 |00i + α0 β1 |01i , |α0 |2 ou seja, projetou-se o estado |φi no subespaço gerado por |00i e |01i, normalizando-se o resultado para obtermos um vetor unitário. • O valor observado é |1i. Esse evento ocorre com probabilidade |α1 β0 |2 + |α1 β1 |2 = |α1 |2 . Neste caso, o estado do registrador |φi, imediatamente após a medição, será |φ0 i = α1 β0 |10i + α1 β1 |01i , |α1 |2 ou seja, projetou-se o estado |φi no subespaço gerado por |10i e |11i, normalizando-se o resultado para obtermos um vetor unitário. 21 Para o caso geral, suponha que seu registrador quântico com n qubits está no estado dado pela equação (1.12) e que você está medindo o qubit |φj i, onde o qubit menos significativo é |φ0 i e o mais significativo é |φn−1 i. Para cada cadeia de caracteres x ∈ {0, 1}n , escreva x = xn−1 · · · x0 , com xk ∈ {0, 1} para todo k. Existem duas possibilidades para o resultado da medição de |φj i: • O valor observado é |0i. A probabilidade de ocorrência desse evento é X p0 := |αx |2 : x ∈ {0, 1}n e xj = 0 . Neste caso, o estado do registrador, imediatamente após a medição, será P αx |xi : x ∈ {0, 1}n e xj = 0 0 , |φ i = p0 onde p0 é simplesmente um fator de normalização. • O valor observado é |1i. A probabilidade de ocorrência desse evento é X p1 := |αx |2 : x ∈ {0, 1}n e xj = 1 . Neste caso, o estado do registrador, imediatamente após a medição, será P n α |xi : x ∈ {0, 1} e x = 1 x j |φ0 i = , p1 onde p1 é simplesmente um fator de normalização. O mecanismo de medição de um número arbitrário de qubits de um registrador é análogo. Exibimos apenas um exemplo: suponha que seu registrador quântico |φi está no estado dado por (1.12) e que ele tem n ≥ 2 qubits, com os qubits |φ0 i, . . . , |φn−1 i ordenados como acima. Suponha que os qubits medidos são |φj i e |φk i. Existem quatro possibilidades para o resultado de uma medição: • Os valores observados são ambos |0i. A probabilidade de ocorrência desse evento é X p00 := |αx |2 : x ∈ {0, 1}n e xj = xk = 0 . Neste caso, o estado do registrador, imediatamente após a medição, será P αx |xi : x ∈ {0, 1}n e xj = xk = 0 0 |φ i = . p00 22 • Os valores observados são |0i para |φj i e |1i para |φk i. A probabilidade de ocorrência desse evento é X p01 := |αx |2 : x ∈ {0, 1}n e xj = 0 e xk = 1 . Neste caso, o estado do registrador, imediatamente após a medição, será P αx |xi : x ∈ {0, 1}n e xj = 0 e xk = 1 0 |φ i = . p01 • Os valores observados são |1i para |φj i e |0i para |φk i. A probabilidade de ocorrência desse evento é X p10 := |αx |2 : x ∈ {0, 1}n e xj = 1 e xk = 0 . Neste caso, o estado do registrador, imediatamente após a medição, será P αx |xi : x ∈ {0, 1}n e xj = 1 e xk = 0 0 |φ i = . p10 • Os valores observados são ambos |1i. A probabilidade de ocorrência desse evento é X p11 := |αx |2 : x ∈ {0, 1}n e xj = xk = 1 . Neste caso, o estado do registrador, imediatamente após a medição, será P αx |xi : x ∈ {0, 1}n e xj = xk = 1 0 |φ i = . p11 1.3 Reversibilidade Falemos agora de portas quânticas operando sobre mais de um qubit. Uma porta quântica sobre n qubits é uma função bijetora de V2n para V2n , onde V2n é o conjunto de vetores unitários de H2n . Em outras palavras, uma porta quântica é uma matriz unitária em H2n . Essa restrição reflete o fato de que, de acordo com as leis da mecânica quântica, toda transformação num estado quântico é reversı́vel. Assim, toda porta quântica é reversı́vel, isto é, existe uma bijeção entre o domı́nio e a imagem da função correspondente. Por exemplo, suponha que temos uma porta quântica U e um registrador |φi com dimensões compatı́veis. Se aplicarmos U a |φi para obtermos |φ0 i := U |φi, então podemos obter o estado original |φi a partir de |φ0 i através da aplicação da porta quântica U ∗ 23 (claramente U ∗ é unitária), pois U ∗ |φ0 i = U ∗ U |φi = I|φi = |φi. Em outras palavras, a aplicação de U não causa “perda de informação”. Esse não é o caso, por exemplo, da porta lógica ∨, o “ou” lógico do modelo clássico: suponha que temos dois bits clássicos a e b e que aplicamos a porta ∨ nesses bits, obtendo c := a ∨ b. Se tivermos c = 1, não temos como obter os valores de a e b, pois podia valer que a = 1 e b = 0, ou que a = 0 e b = 1, ou ainda, que a = 1 e b = 1. Dizemos, por esse motivo, que a porta ∨ não é reversı́vel. Não é difı́cil, porém, construirmos uma “versão” da porta “ou” que seja reversı́vel. Considere a função f : {0, 1}3 −→ {0, 1}3 dada por f (x, y, z) := x, y, z ⊕ (x ∨ y) , onde ⊕ denota a operação lógica “ou exclusivo”. Em outras palavras, a aplicação da função f muda o valor do bit z se, e somente se, x ∨ y = 1. Além disso, é trivial obtermos os valores originais de x, y e z, pois x e y fazem parte dos valores que saem da porta. É evidente que f é uma bijeção, de modo que f é reversı́vel. A única diferença é que estamos armazenando informações a mais, o suficiente para sermos capazes de obter x e y (e z) a partir de f (x, y, z). Então existe uma matriz unitária Uf que “implementa” a função f . Dado um registrador |φi := |xi ⊗ |yi ⊗ |zi, onde |xi, |yi e |zi são qubits, a porta Uf leva |φi ao estado |φ0 i = |xi ⊗ |yi ⊗ z ⊕ (x ∨ y) . Será mais conveniente usarmos a seguinte notação: dado um registrador |φi := |x, y, zi, a aplicação de Uf a |φi leva o estado deste registrador a |φ0 i = x, y, z ⊕ (x ∨ y) . Veja que estamos simplesmente separando os qubits individuais por vı́rgulas. Na verdade, podemos utilizar essa notação para separar grupos arbitrários de qubits num registrador, quando isso for conveniente. O “truque” de carregar informações a mais nas aplicações de portas lógicas pode ser utilizado para transformar qualquer porta lógica do modelo clássico numa porta reversı́vel e que, portanto, pode ser implementada por uma matriz unitária no modelo quântico. Na verdade, Bennett [Ben73] mostrou que qualquer circuito no modelo clássico pode ser convertido em reversı́vel, ou seja, num circuito cujas portas são todas reversı́veis, e mostrou que isso pode ser feito com um aumento no máximo polinomial no tamanho do circuito, isto é, no número de portas utilizadas. Para mais detalhes, consulte o apêndice E. 1.4 Circuitos quânticos A notação para circuitos apresentada na seção sobre qubits se estende facilmente para circuitos operando sobre múltiplos qubits. Por exemplo, a figura 1.5 24 mostra um circuito operando sobre 3 qubits e com uma única porta, dada pela matriz Uf implementando a versão reversı́vel da operação lógica “ou”. De acordo 0 0 0 com nossa especificação de Uf , temos |x i = |xi, |y i = |yi e |z i = z ⊕ (x ∨ y) . |x0 i |xi |yi Uf |y 0 i |z 0 i |zi Figura 1.5: Circuito com porta “ou” reversı́vel. Considere agora o circuito ilustrado na figura 1.6. Veremos tal circuito mais adiante quando apresentarmos o problema de Deutsch. Por enquanto, vamos apenas analisar o estado do registrador a cada aplicação de porta. Considere o registrador |φi de 2 qubits formado pelos qubits |xi e |yi. Suponha que o estado inicial de |φi, antes da aplicação do circuito, é |φi = |xi ⊗ |yi. Após a aplicação da primeira “camada” de portas do circuito, isto é, após a aplicação de H a cada um dos qubits, o estado do registrador será |φ0 i := H|xi ⊗ H|yi = (H ⊗ H) |xi ⊗ |yi = (H ⊗ H)|φi, pelas propriedades do produto tensorial. Podemos resumir isso informalmente: se numa dada “camada” do circuito tivermos várias portas, cada uma operando sobre um certo conjunto de qubits, então a transformação unitária aplicada ao registrador é dada pelo produto tensorial de cada uma das portas. Agora aplicamos a segunda “camada” de portas ao registrador, obtendo o estado |φ00 i := Uf |φ0 i. Finalmente, após a aplicação da terceira “camada”, isto é, após a aplicação de H ao qubit |xi, o estado do registrador será |φ000 i := (H ⊗ I)|φ00 i. Resumindo: se, numa camada, nenhuma porta opera sobre um dado qubit, então o termo do produto tensorial referente a tal qubit é a matriz identidade. |xi H H |x000 i Uf |yi |y 000 i H Figura 1.6: Circuito para o problema de Deutsch. Seja Vf ∈ C2×2 uma matriz unitária. Então a notação utilizada no circuito da figura 1.7 indica que o operador Vf deve ser aplicado ao qubit |yi se, e somente se, |xi = |1i. Em outras palavras, o circuito da figura 1.7 é equivalente 25 ao circuito da figura 1.8, onde 1 0 0 0 0 1 0 0 Vf0 := 0 0 v11 v12 0 0 v21 v22 e Vf := v11 v12 v21 v22 . A porta indicada no circuito da figura 1.7 é chamada porta Vf controlada por |xi. |xi • |x0 i |yi Vf |y 0 i Figura 1.7: Circuito com porta Vf controlada por |xi. |x0 i |xi Vf0 |y 0 i |yi Figura 1.8: Circuito equivalente ao da figura 1.7. 1.5 Teorema do no-cloning Não existe uma transformação que copia (clona) o estado de qualquer qubit para outro. Note que, se isso fosse possı́vel, poderı́amos copiar o estado desse qubit antes de realizarmos uma medição, de modo que terı́amos uma medição do qubit e ainda assim terı́amos uma cópia intacta. Mais que isso, se tivéssemos um número ilimitado de cópias de um qubit desconhecido, poderı́amos determinar seu estado quântico com precisão arbitrária. Teorema 1.6 (No-cloning). Não existe uma transformação unitária U tal que U |ψ, 0i = |ψ, ψi para qualquer qubit |ψi. Demonstração. Suponha que tal U existe. Sejam |αi, |βi qubits √ ortogonais. Temos U |α, 0i = |α, αi e U |β, 0i = |β, βi. Seja |γi = |αi + |βi / 2. Então 1 1 U |γ, 0i = U √ |α, 0i + |β, 0i = √ U |α, 0i + U |β, 0i 2 2 1 = √ |α, αi + |β, βi . 2 26 Porém, temos também U |γ, 0i = |γ, γi = 21 |α, αi + |α, βi + |β, αi + |β, βi . Como |αi e |βi são vetores ortogonais, os elementos do conjunto B := |α, αi, |α, βi, |β, αi, |β, βi são mutuamente ortogonais (lembre-se que hφ, ψ|φ0 , ψ 0 i = hφ|φ0 ihψ|ψ 0 i) e então B é uma base para H4 , de modo que todo vetor deste espaço pode ser escrito de uma única forma como combinação linear dos elementos de B. Mas então 1 U |γ, 0i = √ |α, αi + |β, βi 2 1 6= |α, αi + |α, βi + |β, αi + |β, βi = U |γ, 0i, 2 uma contradição. Vamos provar uma limitação acerca de transformações “de cópia”: Proposição 1.7. Sejam U uma transformação unitária e |ψi, |φi qubits distintos. Se U |ψ, 0i = |ψ, ψi e U |φ, 0i = |φ, φi, então hψ|φi = 0. Demonstração. Primeiro notamos que hψ, ψ|φ, φi = hψ|φi2 . Além disso, temos ∗ hψ, ψ|φ, φi = U |ψ, 0i U |φ, 0i = |ψ, 0i∗ U ∗ U |φ, 0i = |ψ, 0i∗ |φ, 0i = hψ, 0|φ, 0i = hψ|φih0|0i = hψ|φi. Com isso, hψ|φi2 = hψ|φi e portanto hψ|φi só pode ser 0 ou 1. Porém, como kψk = kφk = 1, o produto interno de |ψi e |φi só pode ser 1 se |ψi = |φi. Como esse não é o caso, segue que hψ|φi = 0. É importante observar que tipo de cópia o teorema do no-cloning proı́be. Por exemplo, é possı́vel clonar um estado quântico conhecido. O que o teorema nos afirma é que é impossı́vel que uma transformação copie um estado quântico arbitrário. Proposição 1.8. Seja |ψi um qubit. Então existe uma operação unitária U|ψi tal que U|ψi |ψ, 0i = |ψ, ψi. Demonstração. Seja |ψi := α|0i + β|1i. É fácil ver que α −β ∗ U|ψi = I ⊗ β α∗ é unitária e satisfaz a afirmação. 27 1.6 Emaranhamento quântico Considere um registrador de 2 qubits |ψi no estado 1 |Φ+ i := √ |00i + |11i . 2 Se fizermos uma medição do primeiro qubit em relação à base padrão, obteremos |0i com probabilidade 1/2 e |1i com probabilidade 1/2. No primeiro caso, |ψi passa a valer |00i e, no segundo, |11i. Com isso, uma posterior medição no segundo qubit já tem seu resultado determinado, isto é, com probabilidade 1 obteremos |0i no primeiro caso e |1i no segundo. Os qubits neste estado não são independentes ou não têm identidade própria. Isso não ocorre, entretanto, se |ψi estivesse no estado 1 |00i + |01i + |10i + |11i , 2 isto é, o resultado de uma medição do primeiro qubit não afeta o resultado de medições no segundo qubit realizadas posteriormente. Em geral, se o estado de |ψi puder ser escrito como o produto tensorial de dois qubits, então estes “têm identidade própria”. Suponha que |ψi = |ψ1 i⊗|ψ2 i, onde |ψ1 i = α0 |0i + α1 |1i e |ψ2 i = β0 |0i + β1 |1i são qubits. Se medirmos o primeiro qubit com relação à base padrão, obtemos |0i com probabilidade |α0 β0 |2 + |α0 β1 |2 = |α0 |2 e o novo estado de |ψi será |0i ⊗ |ψ2 i; obtemos |1i com probabilidade |α1 β0 |2 + |α1 β1 |2 = |α1 |2 e |ψi passa a ser |1i ⊗ |ψ2 i. Já se |ψi não puder ser escrito como produto tensorial de dois qubits, eles demonstram um comportamento semelhante ao caso de |Φ+ i mostrado acima. Note que |Φ+ i não pode ser escrito como produto tensorial de dois qubits. Nn n := Seja |ψi um registrador com n qubits, isto é, |ψi ∈ H 2 i=1 H2 . Se |ψi Nn não pode ser escrito na forma |ψi = i=1 |ψi i, onde |ψi i é um qubit para 1 ≤ i ≤ n, então |ψi é chamado de estado emaranhado (entangled state). Exemplo 1.9 Tome a seguinte matriz de dimensão 2n , para n > 1: 1 I S , E := √ 2 S −I onde I é a matriz identidade de dimensão 2n−1 e S é a matriz de mesma dimensão contendo 0’s em todas as entradas exceto na diagonal secundária, onde S tem 1’s. 28 É fácil ver que E é unitária: 1 I ∗ S∗ I S ∗ E E = S −I 2 S ∗ −I ∗ 2 1 I +S 1 2I 0 0 = = , 0 I + S2 0 2I 2 2 que é justamente a matriz identidade de dimensão 2n . Agora observe que E, |0n i, gera o estado ema aplicada no vetor básico 1 n n n ranhado √2 |0 i + |1 i . Já aplicada em |1 i, gera o estado emaranhado √1 |0n i − |1n i . 2 Um registrador de 2 qubits no estado |Φ+ i é dito um estado EPR, ou par EPR, onde EPR é uma abreviação para Einstein, Podolsky e Rosen, fı́sicos que contestaram a validade desta formulação da teoria quântica, já que esta possibilitava situações aparentemente paradoxais, que violam princı́pios fundamentais da teoria da relatividade. A existência de estados quânticos emaranhados é a principal razão pela qual computadores quânticos não podem ser facilmente simulados eficientemente por computadores clássicos (mesmo no modelo probabilı́stico). De fato, se todo registrador quântico com n qubits pudesse sempre ser escrito como o produto tensorial de n qubits, então bastaria armazenar classicamente 2n números complexos por registrador quântico. Entretanto, é uma conseqüência da existência de estados emaranhados que nem sempre podemos dividir um estado quântico em suas “partes componentes” e operar nestas separadamente. Assim, para armazenar classicamente o estado de um registrador quântico de n qubits, parece ser necessário armazenar 2n números complexos. 29 Capı́tulo 2 Algoritmos quânticos Estudaremos agora conceitos fundamentais sobre algoritmos no modelo quântico. Começamos mostrando o paralelismo quântico, técnica essencial para o projeto de algoritmos eficientes. A seguir, formalizamos o conceito de medida de tempo consumido por um algoritmo neste novo modelo de computação. Finalmente, apresentamos alguns exemplos simples de algoritmos, como os que resolvem os problemas de Deutsch, de Deutsch-Jozsa e de Simon. 2.1 Paralelismo quântico Considere um registrador com n qubits no estado |φi := n −1 2X αi |ii. i=0 A aplicação de uma matriz unitária U de dimensão 2n sobre este registrador produz ! 2n −1 n −1 2X X |φ0 i = U |φi = U αi |ii = αi U |ii, i=0 i=0 isto é, uma única aplicação de U realiza um número exponencial de operações em estados básicos. Este fenômeno é chamado de paralelismo quântico (quantum parallelism). Usualmente, a matriz de Hadamard, dada por (1.3), é utilizada para gerar num registrador um estado quântico contendo a superposição de todos os estados básicos, todos com a mesma amplitude. Nn Seja Hn := j=1 H, onde H é a matriz de Hadamard, como definimos em (1.3). Chame Hn de matriz de Hadamard de ordem 2n . Note que a aplicação 30 de Hn a um registrador é feita simplesmente pela aplicação de H a cada qubit individual do registrador. Abaixo ilustramos o uso dessa transformação. Exemplo 2.1 Seja f : {0, . . . , 2n − 1} −→ {0, . . . , 2m − 1} uma função. Considere um registrador |φi com n + m qubits, formado por dois sub-registradores, um com n qubits contendo |ai, para algum 0 ≤ a < 2n , e outro com m qubits contendo |bi, para algum 0 ≤ b < 2m , ou seja, |φi é o produto tensorial de |ai e |bi: |φi = |a, bi. Seja Uf uma matriz unitária de dimensão 2n+m tal que Uf |a, bi = a, b ⊕ f (a) . Denote por Im a matriz identidade de ordem 2m . Partindo do registrador |φi inicializado com o estado básico |0, 0i, aplicamos Hn sobre o primeiro subregistrador, isto é, aplicamos o operador Hn ⊗Im sobre o registrador |φi, obtendo (Hn ⊗ Im )|0, 0i = Hn |0i ⊗ Im |0i . Não é difı́cil ver que n Hn |0 i = n O ! H j=1 n O j=1 ! |0i = n O H|0i j=1 n 1 O 1 = √ |0i + |1i = √ n 2 j=1 2n X |xi x∈{0,1}n n 2 −1 1 X = √ |xi. 2n x=0 (2.1) Então (Hn ⊗ Im )|0, 0i = ! 2n −1 2n −1 1 X 1 X √ |xi ⊗ |0i = √ |x, 0i. 2 x=0 2 x=0 Agora aplicamos Uf a |φi uma única vez, para obter ! 2n −1 2n −1 1 X 1 X Uf √ |x, 0i = √ Uf |x, 0i 2 x=0 2 x=0 n n 2 −1 2 −1 1 X 1 X x, 0 ⊕ f (x) = √ x, f (x) . = √ 2 x=0 2 x=0 Observe que, com uma única aplicação de Uf o valor de f (x) foi calculado para todo 0 ≤ x < 2n . Vale lembrar que a medição de um registrador como descrito acima causa o colapso deste em um único estado básico, justamente o que é obtido na medição. 31 Desta forma, apesar de o estado do registrador conter o valor de f (x) para todo 0 ≤ x < 2m , podemos obter um único valor da função. Além disso, não podemos nem escolher para qual x obteremos f (x), já que o resultado da medição é probabilı́stico. É preciso então desenvolver operações unitárias que manipulem de forma inteligente as amplitudes dos estados básicos para que se possa usar eficientemente o paralelismo quântico. Exemplo 2.2 (Mudança de sinal) Sejam f e Uf como no exemplo acima e tome m = 1. Seja |xi um registrador com n qubits. Vamos mostrar como realizar a operação Vf dada por Vf |xi = (−1)f (x) |xi, que muda o sinal da amplitude dos estados básicos |xi para os quais f (x) = 1. Para tanto, utilizaremos um qubit adicional, no estado √12 |0i − |1i , que é facilmente obtido através da aplicação da transformação de Hadamard ao estado básico |1i. Este qubit é “concatenado” ao registrador |xi através do produto tensorial, formando 1 1 |xi ⊗ √ |0i − |1i = √ |x, 0i − |x, 1i . 2 2 Aplicando Uf a este estado obtemos i 1 h 1 Uf √ |x, 0i − |x, 1i = √ x, f (x) − x, 1 ⊕ f (x) . 2 2 Se f (x) = 0, o estado anterior é i 1 h 1 √ |x, 0i − |x, 1 ⊕ 0i = √ |x, 0i − |x, 1i 2 2 1 0 = (−1) |xi ⊗ √ |0i − |1i . 2 Já se f (x) = 1, i 1 h 1 √ |x, 1i − |x, 1 ⊕ 1i = − √ |x, 0i − |x, 1i 2 2 1 1 = (−1) |xi ⊗ √ |0i − |1i . 2 Ou seja, 1 1 f (x) Uf |xi ⊗ √ |0i − |1i = (−1) |xi ⊗ √ |0i − |1i , 2 2 como querı́amos. 32 (2.2) 2.2 Medida do consumo de tempo Para medirmos o consumo de tempo de um algoritmo no modelo quântico, vamos analisar o circuito equivalente à sua execução para cada instância possı́vel. Essa formulação baseada em circuitos é igualmente válida para o modelo clássico. Mais adiante discutimos alguns aspectos de precisão que surgem apenas no modelo quântico. Suponha que um algoritmo A resolve um certo problema e seja I uma instância desse problema. Seja n o tamanho de I, isto é, suponha que I pode ser codificada com n qubits. A execução de A sobre I equivale a um circuito C que tem os qubits de I como entrada. Precisamos fazer algumas exigências acerca de C. Fixe um inteiro k ≥ 2. Exigimos que: (i) dado I, exista um algoritmo polinomial em n capaz de construir o circuito C equivalente à execução de A sobre I; (ii) cada porta do circuito C opere sobre, no máximo, k qubits. Satisfeitas essas exigências, diremos que o consumo de tempo do algoritmo A para a instância I é o tamanho de C, isto é, o número de portas do circuito. A exigência (i) apenas impede que o algoritmo usado para construir o circuito C utilize tempo superpolinomial. De fato, se não impuséssemos limitações para o consumo de tempo desse algoritmo de construção, o tamanho do circuito C poderia ser até mesmo constante. Já a exigência (ii) garante que cada passo da computação é feito localmente. Em outras palavras, cada porta do circuito opera sobre O(1) qubits. Como o consumo de tempo do algoritmo é o número de portas do circuito, estamos simplesmente dizendo que cada passo do algoritmo “custa” O(1). Tudo que foi discutido até aqui pode ser aplicado ao modelo clássico. Mas, no modelo quântico, pode surgir a seguinte questão: dentre todas as portas que operam sobre no máximo k qubits, quais delas podemos utilizar no circuito, ou seja, quais delas são fisicamente realizáveis? Esse problema não aparece no modelo clássico pois o número de portas que opera sobre no máximo k bits é finito. Porém, no modelo quântico, o número de portas operando sobre no máximo k qubits não só é infinito, como também é não-enumerável. A resposta para essa questão vem da existência de portas quânticas universais. Em outras palavras, existe um conjunto de portas quânticas, que chamaremos de famı́lia universal de portas quânticas, capaz de “simular” a aplicação de qualquer matriz unitária. Vamos formalizar melhor esse conceito. Seja U uma matriz unitária operando sobre no máximo k qubits. Ou seja, a dimensão de U é m := 2l , com l ≤ k. Então para todo > 0 existe um circuito quântico, utilizando somente as portas de uma famı́lia universal de 33 portas quânticas, cuja aplicação equivale à transformação unitária U 0 , sendo que kU − U 0 k < . Ademais, tal circuito tem tamanho polinomial em 1/. Em outras palavras, se tivermos em mãos um computador quântico equipado com uma famı́lia universal de portas quânticas, podemos simular com precisão arbitrária qualquer transformação unitária operando sobre no máximo k qubits. Não vamos considerar a influência de erros a cada passo do algoritmo. Para mais detalhes, veja as notas de aula de Preskill [Pre04] e o artigo de Bernstein e Vazirani [BV97]. Portanto, podemos utilizar qualquer porta quântica operando sobre no máximo k qubits. 2.3 O problema de Deutsch Dizemos que uma função f é dada como uma caixa preta se só podemos obter informações acerca de f através de sua aplicação a elementos de seu domı́nio. O problema de Deutsch, também conhecido como problema XOR de Deutsch, consiste no seguinte: Problema 2.3 (XOR de Deutsch) Seja f : {0, 1} −→ {0, 1} uma função dada como uma caixa preta. Determine se f (0) = f (1) ou se f (0) 6= f (1). Se f (0) = f (1), dizemos que f é constante. Já se f (0) 6= f (1), dizemos que f é balanceada. Para se resolver o problema com certeza no modelo clássico, são necessárias duas aplicações de f : é preciso usar a caixa preta de f duas vezes, para as entradas 0 e 1. Já no modelo quântico, este problema pode ser resolvido satisfatoriamente utilizando-se apenas uma chamada à caixa preta. Primeiro mostramos a solução original dada por Deutsch, que dá a resposta certa com probabilidade 1/2 e não dá resposta alguma com probabilidade 1/2. Depois mostramos uma solução melhorada, dada por Cleve, Ekert, Macchiavello e Mosca [CEMM98], que sempre dá a resposta certa. Solução 2.4 (Deutsch) Seja Uf a transformação unitária de dimensão 4 que leva |x, yi a x, y ⊕ f (x) . No modelo quântico, Uf é a nossa caixa preta. Tome um registrador |φ0 i com 2 qubits inicializado com |0, 0i e aplique a transformação de Hadamard no primeiro qubit, obtendo |φ1 i := H ⊗ I |0i ⊗ |0i 1 1 √ |0i + |1i ⊗ |0i = √ |0, 0i + |1, 0i . = 2 2 34 Com uma única aplicação da caixa preta Uf a |φ1 i, obtemos o estado 1 √ |φ2 i := Uf |φ1 i = 0, f (0) + 1, f (1) . 2 Aplicamos agora H2 sobre |φ2 i para obter |φ3 i. Lembrando que 1 1 1 1 1 1 −1 1 −1 , H2 = 1 −1 −1 2 1 1 −1 −1 1 temos 1 1 |φ3 i = √ |0, 0i + (−1)f (0) |0, 1i + |1, 0i + (−1)f (0) |1, 1i 2 2 1 f (1) f (1)+1 + |0, 0i + (−1) |0, 1i − |1, 0i + (−1) |1, 1i , 2 e portanto 1 1 (−1)f (0) + (−1)f (1) |0, 1i |φ3 i = √ |0, 0i + 2 2 1 f (0) f (1)+1 + (−1) + (−1) |1, 1i . 2 Assim, se f é constante, então f (0) = f (1) e f (0) 6≡ f (1) + 1 (mod 2), de modo que 1 |φ3 i = √ |0, 0i + (−1)f (0) |0, 1i . 2 Já se f é balanceada, então f (0) 6≡ f (1) (mod 2) e f (0) ≡ f (1) + 1 (mod 2), de forma que 1 |φ3 i = √ |0, 0i + (−1)f (0) |1, 1i . 2 Fazemos agora uma medição do segundo qubit. Se obtivermos |0i, perdemos nossos cálculos. Mas com probabilidade 1/2 obteremos |1i. Neste caso, ocorre um colapso no registrador, que estará no estado |0, 1i se f é constante ou no estado |1, 1i se f for balanceada. Assim, uma medição do primeiro qubit nos fornece o resultado correto. Solução 2.5 (Cleve, Ekert, Macchiavello e Mosca) Considere novamente a transformação Uf como nossa caixa preta e um registrador |φ0 i com 2 qubits inicializado com |0, 1i. 35 |0i H H f (0) ⊕ f (1) Uf |1i |x0 i H Figura 2.1: Circuito para o problema de Deutsch O circuito quântico ilustrado na figura 2.1 mostra o algoritmo que resolve o problema de Deutsch. Acompanhe a seguir o funcionamento do algoritmo: Primeiro aplicamos a transformação de Hadamard aos 2 qubits do registrador, obtendo 1 |0i + |1i ⊗ |0i − |1i |φ1 i := H2 |φ0 i = H|0i ⊗ H|1i = 2 1 1 |0i ⊗ |0i − |1i + |1i ⊗ |0i − |1i . = 2 2 Neste ponto a caixa preta Uf é aplicada a |φ1 i para obtermos |φ2 i: ( ( ) ) 1 1 Uf |0i ⊗ |0i − |1i Uf |1i ⊗ |0i − |1i |φ2 i := Uf |φ1 i = + . 2 2 Já vimos em (2.2) do exemplo da página 32 que a aplicação de Uf a um regis trador contendo |φi = |xi ⊗ |0i − |1i , onde x ∈ {0, 1}, resulta em (−1)f (x) |φi. Assim, ( ( ) ) 1 1 (−1)f (0) |0i ⊗ |0i − |1i (−1)f (1) |1i ⊗ |0i − |1i |φ2 i = + 2 2 1 f (0) f (1) (−1) |0i + (−1) |1i ⊗ |0i − |1i = 2 1 f (0) f (1) f (0) f (0) = (−1) |0i + (−1) (−1) (−1) |1i ⊗ |0i − |1i 2 (−1)f (0) f (0)⊕f (1) = |0i + (−1) |1i ⊗ |0i − |1i 2 ( ) 1 1 √ |0i + (−1)f (0)⊕f (1) |1i ⊗ √ |0i − |1i = (−1)f (0) . 2 2 Agora podemos aplicar a transformação de Hadamard ao primeiro qubit de |φ2 i para obter ( ) 1 |φ3 i := (H ⊗ I)|φ2 i = (−1)f (0) f (0) ⊕ f (1) ⊗ √ |0i − |1i . 2 36 Uma medição do primeiro qubit de |φ3 i fornece agora o valor de f (0) ⊕ f (1) e portanto o algoritmo descobre com certeza se f é constante ou balanceada através de uma única aplicação da caixa preta. 2.4 O problema de Deutsch-Jozsa Deutsch e Jozsa propuseram mais tarde uma generalização do problema de Deutsch, que descrevemos a seguir. Seja f : {0, 1}n −→ {0, 1} uma função. Dizemos que f é constante se f (x) =f (y) para todos x, y ∈{0, 1}n e que f é balanceada se |F0 | = |F1 |, onde Fz := x ∈ {0, 1}n : f (x) = z para z = 0, 1. O problema de Deutsch-Jozsa consiste no seguinte: Problema 2.6 (Deutsch-Jozsa) Seja f : {0, 1}n −→ {0, 1} uma função dada como uma caixa preta, com a garantia de que f é constante ou balanceada. Determine se f é constante ou balanceada. A solução original proposta por Deutsch e Jozsa faz duas chamadas à caixa preta Uf , que é a transformação que leva |x, yi a x, y⊕f (x) . Vamos apresentar um algoritmo devido a Cleve, Ekert, Macchiavello e Mosca [CEMM98], que faz apenas uma chamada à caixa preta Uf para resolver o problema. O algoritmo segue de perto a solução exata do problema XOR. Começamos com um registrador |φ0 i de n+1 qubits inicializado com |0n , 1i, ou seja, os n primeiros qubits valem |0i e apenas o último tem o valor |1i. Aplicamos a transformação de Hadamard a cada um dos n + 1 qubits de |φ0 i, obtendo |φ1 i := (Hn ⊗ H)|φ0 i = Hn |0i ⊗ H|1i # " n −1 2X 2n −1 1 X 1 √ = |xi ⊗ |0i − |1i = √ |xi ⊗ |0i − |1i . 2n x=0 2n x=0 Agora aplicamos a caixa preta Uf a |φ1 i: 2n −1 1 X |φ2 i := Uf |φ1 i = √ Uf |xi ⊗ |0i − |1i 2n x=0 2n −1 1 X f (x) = √ (−1) |xi ⊗ |0i − |1i . 2n x=0 Observe que novamente utilizamos o que foi mostrado em (2.2) no exemplo da página 32. 37 Temos assim 2n −1 1 X f (x) |φ2 i = √ |xi ⊗ |0i − |1i (−1) 2n x=0 " # 2n −1 1 X √ = (−1)f (x) |xi ⊗ |0i − |1i . 2n x=0 A partir deste ponto passamos a ignorar o último qubit do registrador, e consideraremos apenas n 2 −1 1 X (−1)f (x) |xi. |φ2 i = √ n 2 x=0 Aplicamos a transformação de Hadamard a cada um dos n primeiros qubits de |φ2 i para obter n 2 −1 1 X 1 |φ3 i := Hn |φ2 i = √ (−1)f (x) Hn |xi = √ 2n x=0 2n X (−1)f (x) Hn |xi. x∈{0,1}n Não é difı́cil ver que, para qualquer x ∈ {0, 1}n , temos 1 Hn |xi = √ 2n X (−1)x·y |yi, (2.3) y∈{0,1}n L onde x · y = n−1 j=0 xj yj e ⊕ é a operação ou-exclusivo. Desta forma, temos X X 1 1 |φ3 i = √ (−1)f (x) √ (−1)x·y |yi 2n x∈{0,1}n 2n y∈{0,1}n X 1 (−1)f (x)⊕(x·y) |yi. = n 2 n x,y∈{0,1} Observe que a amplitude α0 do vetor básico |0i é α0 = X x∈{0,1}n (−1)f (x) . 2n Assim, se f é constante, então α0 = (−1)f (0) e portanto |φ3 i = (−1)f (0) |0i. Já se f é balanceada, então α0 = 0. Podemos então medir os n qubits de |φ3 i 38 para descobrir se f é balanceada ou constante: se todos os qubits do registrador valerem |0i, então f é constante; caso contrário, f é balanceada. O algoritmo apresentado acima resolve o problema de Deutsch-Jozsa com apenas uma chamada à caixa preta de f . É claro que, para um computador determinı́stico resolver o mesmo problema exatamente, são necessárias no pior caso 2n−1 + 1 chamadas a f e portanto esse problema não pode ser resolvido em tempo polinomial no modelo determinı́stico. Entretanto, no modelo probabilı́stico, existe um algoritmo, descrito a seguir, que resolve o problema em tempo polinomial se for permitido um erro unilateral arbitrariamente pequeno. Considere um algoritmo probabilı́stico que inicialmente sorteia n números inteiros x1 , . . . , xn tais que 0 ≤ xi < 2n para todo i. Depois são feitas n chamadas à caixa preta: para cada i, fazemos yi = f (xi ). Finalmente, verificamos se yi = yi+1 para i = 1, . . . , n − 1. Se este for o caso, então o algoritmo responde que f é constante. Caso contrário, o algoritmo responde que f é balanceada. Note que, se o algoritmo afirma que f é balanceada, então f com certeza é balanceada. Entretanto, pode ser que o algoritmo afirme que f é constante mesmo que f seja balanceada. Vamos medir a probabilidade de ocorrência desse evento, ou seja, de o algoritmo responder que f é constante sendo que f é balanceada. Fixada uma função f balanceada, temos uma bipartição {F0 , F1 } de {0, 1}n com |F0 | = |F1 |, como na definição de função balanceada acima. Para i = 1, . . . , n, defina a variável aleatória Xi com valor 0 se xi ∈ F0 e 1 se xi ∈ F1 . É claro que P [Xi = 0] = P [Xi = 1] = 1/2 para todo i, já que |F0 | = |F1 |. A probabilidade de o algoritmo responder que f é constante é q := P [X1 = 0, X2 = 0, . . . , Xn = 0] + P [X1 = 1, X2 = 1, . . . , Xn = 1] n n Y Y 1 1 1 = P [Xi = 0] + P [Xi = 1] = n + n = n−1 , 2 2 2 i=1 i=1 de modo que q ≤ 1/2 se n ≥ 2 e portanto o problema de decidir se f é balanceada está na classe de complexidade RP, que será apresentada na parte II deste texto. Vamos mostrar agora uma variante do problema de Deutsch-Jozsa proposta por Bernstein e Vazirani [BV93]. Dado a ∈ {0, 1}n , considere a função fa : {0, 1}n −→ {0, 1} dada por fa (x) := x · a. Suponha que a função fa é dada como uma caixa preta. O problema consiste em determinar a. Note que fa é constante se a = 0n e fa é balanceada caso contrário (mas não é verdade que, se f é garantidamente constante ou balanceada, então f é igual a fa para algum a ∈ {0, 1}n ). A solução dada por Cleve, Ekert, Macchiavello e Mosca [CEMM98] para 39 essa variante do problema é quase idêntica ao algoritmo que resolve o problema de Deutsch-Jozsa. Em particular, o algoritmo faz uma única chamada à caixa preta Ufa . Considere o registrador |φ3 i obtido como naquele algoritmo: X X 1 1 |φ3 i = n (−1)f (x)⊕(x·y) |yi = n (−1)(x·a)⊕(x·y) |yi 2 2 n n x,y∈{0,1} = 1 2n X x,y∈{0,1} (−1)x·(a⊕y) |yi. x,y∈{0,1}n Observe que a amplitude do estado básico |ai é 1 X (−1)x·0 = 1 n 2 n x∈{0,1} e portanto |φ3 i = |ai. Portanto, basta medir os n qubits do registrador para se obter a. 2.5 O problema de Simon Seja f : {0, 1}n −→ {0, 1}n uma função. Dizemos que f é dois-para-um se existe um vetor s ∈ {0, 1}n , s 6= 0n , tal que, para quaisquer x, x0 ∈ {0, 1}n , x 6= x0 , tivermos f (x) = f (x0 ) se, e somente se, x0 = x ⊕ s. O problema de Simon, também conhecido como problema XOR de Simon, consiste no seguinte: Problema 2.7 (Simon) Seja f : {0, 1}n −→ {0, 1}n uma função dada como uma caixa preta, com a garantia de que f é bijetora ou dois-para-um. Determine se f é bijetora ou dois-para-um. Caso f seja dois-para-um, determine também o vetor s como especificado na definição acima. A solução proposta por Simon [Sim97] resolve o problema em tempo esperado polinomial. O algoritmo consiste essencialmente em algumas repetições do procedimento Hadamard-twice, que descrevemos a seguir. Seja |φ0 i um registrador de 2n qubits inicializado com 0n , 0n . Aplique a transformação de Hadamard a cada um dos n primeiros qubits de |φ0 i, para obter X 1 x, 0n . |φ1 i := (Hn ⊗ In )|φ0 i = √ 2n x∈{0,1}n Aplicamos agora a caixa preta Uf , que leva |x, yi a x, y ⊕ f (x) , a |φ1 i: X 1 x, f (x) . |φ2 i := Uf |φ1 i = √ 2n x∈{0,1}n 40 Mais uma vez aplicamos a transformação de Hadamard a cada um dos n primeiros qubits, obtendo, de acordo com (2.3) da página 38, X 1 |φ3 i := (Hn ⊗ In )|φ2 i = n (−1)x·y y, f (x) . 2 n x,y∈{0,1} Faça agora uma medição de |φ3 i para obter um par y, f (x) . O procedimento Hadamard-twice devolve então o vetor y observado. Antes de descrever o algoritmo de Simon, vamos calcular as amplitudes dos estados básicos no vetor |φ3i acima. Suponha que f é bijetora. Então todos os possı́veis estados y, f (x) da superposição |φ3 i são distintos e têm a mesma amplitude, que é 1/2n . Agora considere o caso em que f é dois-para-um e seja s o vetor tal que 0 0 f (x) = f (x ) ⇔ x = x ⊕ s. Então os estados y, f (x) e y, f (x ⊕ s) são idênticos e, portanto, sua amplitude total é 1 α(x, y) = n (−1)x·y + (−1)(x⊕s)·y . 2 Se s · y ≡ 0 (mod 2), então (x ⊕ s) · y ≡ (x · y) ⊕ (s · y) (mod 2) e, portanto, (x ⊕ s) · y ≡ x · y (mod 2), de modo que α(x, y) = ±1/2n−1 . Caso contrário, é óbvio que α(x, y) = 0. Assim, um vetor y devolvido pelo procedimento Hadamardtwice com certeza satisfaz s · y ≡ 0 (mod 2). O algoritmo de Simon repete o procedimento Hadamard-twice até obter vetores y1 , . . . , yn−1 linearmente independentes. Após a obtenção de vetores y1 , . . . , yn−1 linearmente independentes, o algoritmo resolve o sistema de equações s · yi ≡ 0 (mod 2) para todo 1 ≤ i ≤ n − 1. O subespaço das soluções deste sistema tem dimensão 1 (consulte [MK01] para um estudo mais detalhado acerca de espaços vetoriais definidos sobre corpos finitos) e portanto contém um único vetor não-nulo. O algoritmo encontra tal vetor s∗ e, se f (0n ) = f (s∗ ), devolve a resposta “dois-para-um”; senão, devolve “bijetora”. Resta provarmos agora que o número esperado de repetições do procedimento Hadamard-twice é polinomial em n. Vamos fazer a análise do caso em que f é dois-para-um. A análise do caso em que f é bijetora é completamente análoga. Para cada 1 ≤ i ≤ n − 1, defina a variável aleatória Xi da seguinte forma. Suponha que y1 , . . . , yi−1 são os vetores linearmente independentes obtidos até um dado instante. Então o valor de Xi é o número de vezes que o procedimento Hadamard-twice é chamado até que se obtenha um vetor yi que não seja combinação linear P de y1 , . . . , yi−1 . É claro então que a variável aleatória X definida como i Xi é justamente o número total de chamadas ao procedimento Hadamard-twice até a obtenção de n − 1 vetores linearmente independentes. 41 Fixe i. É claro que Xi segue a distribuição geométrica com parâmetro p, onde p é a probabilidade do vetor devolvido por Hadamard-twice não ser combinação linear de y1 , . . . , yi−1 . Já observamos que o espaço amostral dos vetores que podem ser devolvidos pelo procedimento é S := {y ∈ Zn2 : s · y ≡ 0 (mod 2)} e que a distribuição de probabilidade nesse espaço é uniforme. Como s 6= 0n e S é justamente o subespaço das soluções do sistema s · y ≡ 0 (mod 2), então S tem dimensão n − 1 e, portanto, 2n−1 elementos. É claro também que o conjunto de todos os vetores de S que são combinação linear de y1 , . . . , yi−1 tem cardinalidade 2i−1 (note que {y1 , . . . , yi−1 } ⊆ S). Desta forma, temos que p := 2i−1 (2n−i − 1) 2n−1 − 2i−1 = = 2i−n (2n−i − 1). 2n−1 2n−1 Mas então E Xi = 1/p = 2n−i ≤ 2, 2n−i − 1 pois 1 ≤ i ≤ n − 1. É imediato que n−1 n−1 hX i X E X =E E Xi = O(n). Xi = i=1 i=1 Portanto o tempo esperado de execução do algoritmo de Simon é O nTf (n) + nG(n) , onde Tf (n) é o tempo de execução da caixa preta Uf e G(n) é o tempo necessário para se resolver um sistema linear com n incógnitas e n − 1 equações, sobre o espaço vetorial Zn2 . Observe que estamos contabilizando o tempo para verificar se um conjunto é ou não linearmente independente através da função que resolve sistemas lineares. É evidente que o algoritmo pode nunca terminar. Mas é muito fácil convertêlo em um algoritmo que sempre termina, mas que dá a resposta com uma probabilidade limitada de erro. Basta fixar o número de chamadas ao procedimento Hadamard-twice e, caso não se obtenha n − 1 vetores linearmente independentes com este número de chamadas, dar uma resposta qualquer. Brassard e Høyer [BH97] apresentaram um algoritmo que sempre produz a resposta certa para o problema de Simon e cujo tempo de execução é polinomial no pior caso. 42 Capı́tulo 3 O algoritmo de fatoração de Shor O algoritmo de Shor resolve o problema da fatoração de inteiros em primos e consome tempo polinomial no tamanho da entrada. Apresentamos a seguir os detalhes fundamentais do funcionamento deste algoritmo. 3.1 Visão geral do algoritmo O algoritmo de Shor [Sho97] é um algoritmo quântico que, dado um inteiro n composto ı́mpar que não é potência de primo, devolve um fator de n com probabilidade limitada de erro. As restrições para o valor de n não representam problema algum. De fato, é trivial encontrar um fator de um número par. Além disso, é fácil desenvolver um algoritmo eficiente que decide se n = ak , para inteiros a e k > 1, e que devolve a e k neste caso. Podemos, por exemplo, utilizar a idéia ingênua de, para cada k desde lg n até 2, usar busca binária para determinar se existe um inteiro r tal que rk = n. Uma análise superficial mostra que o consumo de tempo deste algoritmo 6 é O (lg n) , que é polinomial em lg n. Existem algoritmos muito melhores para resolver este problema, como o apresentado por Bernstein [Ber98]. Ademais, podemos verificar em tempo polinomial se n é composto, utilizando o algoritmo aks. Outra opção é executar testes de primalidade probabilı́sticos um número suficiente de vezes. Na prática, isso é mais eficiente, pois os testes probabilı́sticos são, em geral, mais simples e rápidos que o aks. O teste de Miller-Rabin, apresentado na seção D.2, é uma ótima escolha para esta veri ficação, por ser de fácil implementação e ter complexidade de tempo O lg3 n , com uma constante pequena escondida pela notação assintótica. Como n é produto de no máximo lg n inteiros, o algoritmo de Shor pode ser utilizado para resolver o problema da fatoração em tempo polinomial no 43 tamanho da entrada. O algoritmo de Shor baseia-se numa redução do problema da busca de um fator de n ao problema da busca do perı́odo de uma seqüência. Como a redução utiliza aleatorização, é possı́vel que ela falhe, isto é, que nenhum fator de n seja encontrado. Porém, a probabilidade de ocorrência deste evento é limitada. Na seção 3.2 apresentamos essa redução e limitamos a probabilidade de falha. Na seção 3.3, apresentamos um algoritmo quântico eficiente para a busca do perı́odo da seqüência gerada pela redução. Esse algoritmo utiliza a transformada quântica de Fourier, que pode ser implementada eficientemente, como mostramos na seção 3.4. O algoritmo de busca de perı́odo apresentado na seção 3.3 pode ser facilmente generalizado para buscar eficientemente o perı́odo de qualquer seqüência. Mais formalmente, dado um oráculo Uf que computa uma função f de {0, . . . , 2m − 1} em {0, . . . , 2a − 1} com perı́odo r, a generalização do algoritmo faz uma única chamada a Uf e usa um circuito quântico de tamanho polinomial em m para descobrir r com probabilidade limitada de erro. 3.2 Redução à busca do perı́odo Seja n um inteiro composto ı́mpar que não é potência de primo. Vamos mostrar como reduzir o problema de encontrar um fator de n ao problema de encontrar o perı́odo de uma função. Essa redução utiliza aleatorização, de modo que precisaremos limitar a probabilidade de falha do procedimento. Algoritmo Shor (n) 1 escolha um inteiro 1 < x < n aleatoriamente 2 se mdc(x, n) > 1 3 então devolva mdc(x, n) 4 seja r o perı́odo da função f (a) = xa mod n 5 se r for ı́mpar ou xr/2 ≡ −1 (mod n) 6 então o procedimento falhou 7 devolva mdc(xr/2 + 1, n) O algoritmo de Shor utiliza um único passo quântico: o cálculo do perı́odo da função na linha 4. Os demais passos podem ser efetuados em tempo polinomial no modelo tradicional, e portanto também no modelo quântico. 44 Agora vamos mostrar que, se a redução devolve uma resposta, ela está correta. Depois vamos delimitar superiormente a probabilidade de falha deste procedimento, isto é, a probabilidade de o algoritmo terminar na linha 6. Começamos observando que, se o algoritmo executa a linha 3, então o valor devolvido de fato é um fator de n. Já se mdc(x, n) = 1, então x está em Z∗n , o grupo multiplicativo módulo n, de modo que o corolário C.22 nos garante que a função f (a) = xa mod n é periódica com perı́odo dado pela ordem de x, módulo n. Isto é, o perı́odo r é o tamanho do subgrupo de Z∗n gerado por x. Pelo teorema C.21, r é o menor inteiro positivo tal que xr ≡ 1 (mod n). (3.1) Observe que, se r é par e xr/2 6≡ −1 (mod n), então xr/2 é uma raiz quadrada não-trivial de 1, módulo n. Não precisamos verificar se xr/2 ≡ 1 (mod n), pois r é o menor inteiro positivo tal que xr ≡ 1 (mod n), como já foi notado. Aplicando o teorema C.38, vemos que mdc(xr/2 + 1, n) e mdc(xr/2 − 1, n) são ambos fatores de n. Assim, o valor devolvido na linha 7 é, de fato, um fator de n. Resta limitarmos a probabilidade de falha do procedimento, ou seja, dado um inteiro 1 < x < n escolhido aleatoriamente com probabilidade uniforme, precisamos limitar a probabilidade de que r, a ordem de x, módulo n, seja ı́mpar ou satisfaça xr/2 ≡ −1 (mod n) se for par. Q ki Suponha que a fatoração de n em primos é dada por n = m i=1 pi , onde pi é primo e ki ≥ 1 para todo i e m > 1, já que n não é potência de primo. Para cada i, seja ni := pi ki , de modo que n = n1 · · · nm . Sejam 1 < x < n um inteiro, r a ordem de x, módulo n, e ri a ordem de x, módulo ni , para i = 1, . . . , m. Pelo corolário C.31 ao teorema do resto chinês, a equação xr ≡ 1 (mod n) é equivalente ao sistema xr ≡ 1 xr ≡ 1 (mod n1 ) (mod n2 ) .. . xr ≡ 1 (mod nm ). (3.2) Conforme o teorema C.21, a ordem ri de x, módulo ni , é o menor inteiro positivo tal que xri ≡ 1 (mod ni ). Pelo corolário C.22, temos xr ≡ xri (mod ni ) se, e 45 somente se, r ≡ ri (mod ri ). Então r é múltiplo de ri para todo i. Segue de (3.1) que r = mmc(r1 , . . . , rm ). (3.3) Sejam ci e qi tais que ri = 2ci qi , com qi ı́mpar, (3.4) para i = 1, . . . , m. É fácil ver que r é ı́mpar se, e somente se, ri é ı́mpar para todo i, isto é, se, e somente se, ci = 0 para todo i. Suponha agora que ri é par para algum i. Então r é par. Vamos descobrir em que condições temos xr/2 ≡ −1 (mod n). Novamente, pelo corolário C.31 ao teorema do resto chinês, a equação xr/2 ≡ −1 (mod n) é equivalente ao sistema xr/2 ≡ −1 xr/2 ≡ −1 (mod n1 ) (mod n2 ) .. . xr/2 ≡ −1 (3.5) (mod nm ). Suponha que existam i, j ∈ {1, . . . , m} tais que ci > cj . Então r = 2rj u para algum inteiro u, pela equação (3.3). Segue que xr/2 ≡ xrj u (mod nj ). Mas então temos xr/2 ≡ 1 (mod nj ), de modo que xr/2 6≡ −1 (mod n). Portanto, para que r seja par e xr/2 ≡ −1 (mod n), é necessário que c1 = c2 = · · · = cm > 0. Estabelecemos assim que, se o procedimento falha, então c1 = · · · = cm . Vamos limitar a probabilidade de ocorrência desse evento, dada a escolha aleatória de x. Pelo teorema C.29 chinês do resto, existe uma bijeção entre Zn e o produto cartesiano Zn1 × · · · × Znm : Zn 3 x ←→ (x1 , . . . , xm ) ∈ Zn1 × · · · × Znm . (3.6) Assim, escolher um inteiro 0 ≤ x < n aleatoriamente é equivalente a escolher, independentemente para cada 1 ≤ i ≤ m, um inteiro 0 ≤ xi < ni . Vamos supor que mdc(x, n) = 1, já que a redução não se aplica se mdc(x, n) > 1. Então x ∈ Z∗n . É fácil ver que x ∈ Z∗n se, e somente se, xi ∈ Z∗ni para todo i. Portanto estamos escolhendo aleatoriamente um xi ∈ Z∗ni , independentemente, para cada i = 1, . . . , m: Z∗n 3 x ←→ (x1 , . . . , xm ) ∈ Z∗n1 × · · · × Z∗nm . (3.7) Para cada i = 1, . . . , m, o grupo Z∗ni é cı́clico, conforme o teorema C.28, pois ni = pi ki com pi primo. Seja gi um gerador de Z∗ni , para cada i. Temos que xi = gili , com 0 ≤ li < φ(ni ), para i = 1, . . . , m. 46 (3.8) Estamos então escolhendo aleatoriamente um 0 ≤ li < φ(ni ) para cada i, independente e uniformemente: lm ) ∈ Z∗n1 × · · · × Z∗nm , Z∗n 3 x ←→ (g1l1 , . . . , gm (3.9) Para i = 1, . . . , m, sejam di e si tais que φ(ni ) = 2di si , com si ı́mpar, e lembre-se que ri = 2ci qi é a ordem de xi , módulo ni , com qi ı́mpar. Note que φ(ni ) = φ pki i = pki i −1 (pi − 1), conforme o teorema C.32, e portanto di > 0, pois pi é ı́mpar. Pelo teorema C.17 de Lagrange, ri divide φ(ni ), e portanto ci ≤ di . Pelo teorema C.21, ri é o menor inteiro positivo tal que gili ri ≡ 1 (mod ni ). Segue do corolário C.22 que li ri = 2ci qi li é múltiplo de φ(ni ) = 2di si . Se li é ı́mpar, então devemos ter ci = di , pois qi li é ı́mpar. Já se li é par, então necessariamente teremos ci < di : se ci = di , então ri /2 também é inteiro e li ri /2 também é múltiplo de φ(ni ), um absurdo. Portanto, a probabilidade de que ci = c, para qualquer c, é limitada por 1/2, já que 0 ≤ li < φ(ni ) e φ(ni ) é par. Concluı́mos então que a probabilidade de falha dessa redução, ou, na verdade, a probabilidade de que c1 = · · · = cm é, no máximo, 1 − 1/2m−1 ≤ 1/2, pois m > 1 e a escolha de cada ci é independente de todas as outras. 3.3 Busca do perı́odo Seja n um inteiro composto ı́mpar que não é potência de primo e seja 1 < x < n um inteiro relativamente primo a n. Vamos apresentar um algoritmo quântico que descobre, com probabilidade limitada de erro, a ordem de x, módulo n, que, de acordo com o teorema C.21 e o corolário C.22, é o perı́odo da seqüência hx0 mod n, x1 mod n, x2 mod n, . . .i. (3.10) Seja β := blg nc + 1 o número de bits da representação binária de n e seja q = 2l a única potência de 2 tal que n2 ≤ q < 2n2 . Vamos precisar de um registrador |φi com l + β qubits. Os l primeiros qubits formam o primeiro sub-registrador. Os β qubits restantes farão parte do segundo sub-registrador. Todos os qubits do registrador |φi devem ser inicializados com |0i. 47 Após a aplicação da transformação de Hadamard a cada um dos qubits do primeiro sub-registrador, o estado do registrador |φi será q−1 1 X |a, 0i. √ q a=0 (3.11) Seja Uf a transformação unitária que, para todo 0 ≤ a < q, leva um estado básico |a, 0i, ao estado |a, xa mod ni. No apêndice C, mostramos um algoritmo para exponenciação modular que consome O(β 3 ) operações sobre bits. Então, para todo n, existe um circuito com O(β 3 ) portas, cada uma operando sobre no máximo um número fixo de qubits, que efetua a transformação Uf . Em outras palavras, Uf pode ser implementada eficientemente (veja o artigo de Shor [Sho97] para mais detalhes). Aplicando a transformação Uf ao registrador |φi, obtemos o estado q−1 1 X |a, xa mod ni. √ q a=0 (3.12) Medindo o estado do segundo sub-registrador, obtemos algum xb mod n, onde 0 ≤ b < q. Com isso, o estado do registrador |φi colapsa para uma superposição dos estados básicos de (3.12) cujos β qubits menos significativos representam xb mod n. Seja r a ordem de x, módulo n. Então os valores de 0 ≤ a < q tais que xa ≡ xb (mod n) são da forma a0 + jr, com 0 ≤ a0 < r, já que, pelo corolário C.22, a seqüência (3.10) é periódica com perı́odo r. A medição do segundo subregistrador em (3.12) selecionará os seguintes valores de a, no primeiro subregistrador: a0 , a0 + r, a0 + 2r, . . . , a0 + (A − 1)r, onde A = dq/re. O estado do registrador |φi será então A−1 1 X √ |a0 + jr, xb mod ni. A j=0 De agora em diante, vamos ignorar o segundo sub-registrador. Então o estado de |φi será A−1 1 X √ |a0 + jri. (3.13) A j=0 Note que os estados básicos de |φi que podem ser obtidos numa medição estão uniformemente espaçados a partir de a0 , com espaço r. 48 Seja Mq a transformação unitária dada por q−1 1 X Mq : |xi −→ √ exp(2πixy/q)|yi. q y=0 (3.14) Vamos mostrar, na seção 3.4, que esta transformação, conhecida como matriz de Vandermonde, pode ser implementada eficientemente por um circuito quântico. A aplicação de Mq ao registrador |φi, dado por (3.13), gera o estado " # q−1 A−1 1 X 1 X exp 2πi(a0 + jr)y/q |yi |φi = √ √ q y=0 A j=0 " # q−1 A−1 X 1 X exp{2πia0 y/q} exp{2πijry/q}|yi . = √ qA y=0 j=0 Então a amplitude de um estado básico |yi é A−1 X 1 √ exp{2πia0 y/q} exp{2πijry/q}, qA j=0 (3.15) de modo que a probabilidade de obtenção de |yi numa medição de |φi é 2 A−1 X 1 py = exp{2πijry/q} . qA (3.16) j=0 Aqui vamos apenas analisar o caso em que r é uma potência de 2, de modo que A = q/r. Os demais casos seguem a mesma idéia porém são mais técnicos. Suponha que y não é múltiplo de A. Então ry/q não é inteiro, de modo que exp{2πiry/q} = 6 1. Pela fórmula da soma de uma progressão geométrica, temos A−1 X j=0 exp{2πijry/q} = A−1 X j exp{2πiry/q} j=0 A exp{2πiry/q} − 1 = exp{2πiry/q} − 1 exp{2πiy} − 1 = = 0, exp{2πiry/q} − 1 pois A = q/r. 49 Suponha agora que y é um múltiplo de A. Então ry/q é inteiro, de modo que exp{2πijry/q} = 1 para todo 0 ≤ j < A. Então A−1 X exp{2πijry/q} = A. j=0 Concluı́mos que a probabilidade de obtenção de |yi na medição do registrador |φi no estado (3.15) é 1/r, se y é múltiplo de q/r py = (3.17) 0, caso contrário. Assim, uma medição de |φi nos fornece um y = cq/r, com 0 ≤ c < r escolhido equiprovavelmente. Teremos então um valor de y satisfazendo y/q = c/r, onde c e q são conhecidos. Se mdc(c, r) = 1, então basta obter a fração irredutı́vel correspondente a y/q para chegarmos ao perı́odo r. A probabilidade de obtenção de um 0 ≤ c < r com mdc(c, r) = 1 é φ(r)/r. Pode-se provar [HW54] que existe uma constante δ tal que φ(r)/r > δ/ log log r. Assim, a probabilidade de falha deste procedimento é, no máximo, 1 − δ/ log log r. Se repetirmos o procedimento acima z := log log r/δ vezes, a probabilidade de falha passará a ser (1 − 1/z)z ≤ 1/e, de modo que a probabilidade de sucesso é, no mı́nimo, 1 − 1/e, uma constante. Portanto, obtemos o perı́odo r com probabilidade limitada inferiormente por uma constante. 3.4 A transformada quântica de Fourier Vamos ver agora que a transformação unitária Mq , dada por (3.14), pode ser implementada eficientemente sempre que q for uma potência de 2. Ou seja, para todo q = 2m , vamos mostrar que existe um circuito de tamanho polinomial em m, utilizando apenas portas quânticas que operam sobre um número fixo de qubits, cuja aplicação a um registrador com m qubits é equivalente à aplicação da matriz Mq . Primeiro vamos escrever o estado q−1 1 X exp(2πixy/q)|yi √ q y=0 (3.18) de uma forma mais conveniente. Considere q = 2m , com m um inteiro positivo. Denotaremos (xm−1 · · · x0 )2 a representação binária de 0 ≤ x < 2m , ou seja, Pm−1 por x = j=0 xj 2j , com xj ∈ {0, 1} para todo j. Além disso, utilize (0. x1 · · · xp )2 50 P para denotar a representação binária de 0 ≤ x < 1, isto é, x = pj=1 xj 2−j , com xj ∈ {0, 1} para todo j. Então o estado (3.18) não é emaranhado e pode ser fatorado como 1 √ |0i + exp 2πi(0. x0 )2 |1i ⊗ 2 1 √ |0i + exp 2πi(0. x1 x0 )2 |1i ⊗ · · · ⊗ (3.19) 2 1 √ |0i + exp 2πi(0. xm−1 · · · x0 )2 |1i . 2 Para mostrar que o estado quântico (3.18) é o mesmo que o estado (3.19), vamos mostrar que, para todo estado básico |ym−1 · · · y0 i, temos exp{2πixy/2m }|ym−1 · · · y0 i = exp 2πi(0. x0 )2 ym−1 |ym−1 i ⊗ exp 2πi(0. x1 x0 )2 ym−2 |ym−2 i ⊗ · · · ⊗ exp 2πi(0. xm−1 · · · x0 )2 y0 |y0 i , (3.20) onde o lado direito da equação (3.20) mostra como se forma o estado básico |yi = |ym−1 · · · y0 i em (3.19). Será então suficiente mostrar que exp{2πixy/2m = exp 2πi(0. x0 )2 ym−1 exp 2πi(0. x1 x0 )2 ym−2 · · · exp 2πi(0. xm−1 · · · x0 )2 y0 (3.21) n = exp 2πi (0. x0 )2 ym−1 + (0. x1 x0 )2 ym−2 + · · · + o (0. xm−1 · · · x0 )2 y0 . Observe que " # m−1 " m−1 # m−1 m−1 X X X yx 1 X xk 2k = yj xk 2k−m+j . = m yj 2j 2m 2 j=0 j=0 k=0 k=0 (3.22) Na equação (3.21), o termo xy/2m aparece multiplicando 2πi. Então apenas a parte fracionária de xy/2m é relevante: se xy/2m = u + r, com 0 ≤ r < 1 e u ∈ Z, então exp(2πixy/2m ) = exp(2πir). Na equação (3.22), para k ≥ m − j, o valor 2k−m+j é inteiro, de modo que podemos reescrever (3.22) como " # m−j−1 m−1 X X yx = y j uj + y j xk 2k−m+j , (3.23) 2m j=0 k=0 51 onde uj é um inteiro. É fácil verificar agora que m−j−1 X xk 2k−m+j = (0. xm−j−1 · · · x0 )2 . k=0 Mas então xy/2m = u + ym−1 (0. x0 )2 + ym−2 (0. x1 x0 )2 + · · · + y0 (0. xm−1 · · · x0 )2 , (3.24) onde u é um inteiro. A equação (3.21) segue imediatamente da equação (3.24), de modo que fica provado que o estado (3.18) pode ser fatorado como (3.19). Considere o circuito quântico apresentado na figura 3.1, referente ao caso em que m = 4. |x3 i |x2 i |x1 i |x0 i H S2,3 S1,3 |y0 i S0,3 • S1,2 H • • • |y1 i S0,2 H • |y2 i S0,1 • H |y3 i Figura 3.1: Circuito para a transformada quântica de Fourier, com m = 4. Nesta figura, a matriz Sj,k , para j < k é definida por 1 0 Sj,k = . 0 exp{2πi/2k−j+1 } (3.25) É muito fácil ver como este circuito se estende para qualquer m. Para cada qubit |xk i, aplicamos a matriz de Hadamard, seguida de k portas controladas por Sj,k , para todo 0 ≤ j < k, onde a porta controlada por Sj,k opera sobre os qubits |xk i e |xj i. Para ver que esse circuito de fato calcula a transformada quântica de Fourier, vamos analisar sua operação sobre o qubit |x3 i na figura 3.1. Após a aplicação da matriz de Hadamard, o estado deste qubit será |0i + exp 2πi(0. x3 )2 |1i. √ Note que estamos desprezando o fator de normalização 1/ 2, para maior clareza. Depois da aplicação da porta controlada por S2,3 , o estado passa a ser |0i + exp 2πi(0. x3x2 )2 |1i. Aplicando agora a porta controlada por S1,3 , teremos |0i + exp 2πi(0. x3 x2 x1 )2 |1i e, por fim, após S0,3 o estado será 52 |0i + exp 2πi(0. x3 · · · x0 )2 |1i. Mas isso é justamente |y0 i, conforme a equação (3.19). Repetindo esses cálculos com os outros qubits, obteremos os estados desejados, de acordo com a equação (3.19). Note que os qubits da saı́da deste circuito estão na ordem inversa. É óbvio que isso não representa qualquer problema para nós. Observe também que o circuito utiliza m(m+1)/2 portas, o que é quadrático em m. Assim, a transformada quântica de Fourier pode ser implementada por um circuito de tamanho O(m2 ). 53 Parte II Resultados de Complexidade 54 Capı́tulo 4 Máquinas de Turing Agora mudamos de assunto, nos voltando à teoria de complexidade computacional. Os resultados dessa área são usualmente apresentados por meio do mais tradicional modelo de computação — a máquina de Turing (MT), que nada mais é que um computador bastante rudimentar com memória infinita. Vamos apresentar três variantes desse modelo: a máquina de Turing determinı́stica, a não-determinı́stica e a probabilı́stica. Depois disso, apresentamos a segunda formalização do modelo quântico de computação, a máquina de Turing quântica, fazendo um paralelo com o modelo clássico de computação. Como observamos na introdução, essa segunda formalização é equivalente à primeira. A demonstração desse fato não é trivial e não será mostrada nesse texto. 4.1 Máquina de Turing determinı́stica Uma máquina de Turing determinı́stica (MTD) é composta por uma central de controle, uma cabeça de leitura e uma fita dividida em células. Essa fita tem um final à esquerda e contém infinitas células à direita. Cada célula da fita armazena um sı́mbolo pertencente a um conjunto finito Σ. O conjunto Σ é chamado de alfabeto da máquina e contém, entre outros, dois sı́mbolos especiais: o sı́mbolo t, chamado de branco, e o sı́mbolo B, que fica armazenado o tempo todo na célula mais à esquerda da fita. A cabeça de leitura da máquina é um apontador móvel para uma determinada célula da fita. O conteúdo dessa célula pode ser lido e alterado pela máquina. A cada instante, a central de controle da máquina está em um dos estados de um conjunto finito Q de estados. No instante inicial, a máquina começa em um estado particular de Q, chamado de estado inicial e denotado por s. Existe 55 ainda um conjunto especial de estados H ⊆ Q, chamados de estados finais. Uma MTD funciona da seguinte maneira. Ela recebe como entrada uma ∗ cadeia de caracteres em Σ \ {t, B} . Inicialmente a cabeça de leitura aponta para a célula mais à esquerda da fita, e a partir da célula seguinte está armazenada a entrada da máquina, seguida por brancos. A máquina efetua uma seqüência de passos até terminar a execução. Se q é o estado corrente da máquina e q está em H, então ela termina a execução. Do contrário, ela realiza três ações, determinadas pelo par (q, σ), onde σ é o sı́mbolo de Σ contido na célula que está sob a cabeça de leitura. A primeira ação consiste na alteração do estado da máquina de q para um estado q 0 em Q. A segunda ação é a escrita de um sı́mbolo σ 0 na célula que está sob a cabeça de leitura. A terceira ação consiste no deslocamento da cabeça de leitura, que pode se mover uma posição para a esquerda, uma posição para a direita ou pode continuar apontando para a mesma célula. A cabeça de leitura sempre desloca-se para a direita quando atinge a célula mais à esquerda e nunca altera o conteúdo dessa posição da fita. Por conveniência, assume-se que a máquina não pode escrever o sı́mbolo B em qualquer posição da fita que não seja a célula mais à esquerda. A cadeia de caracteres escrita na fita quando a máquina termina a execução, ignorando-se o sı́mbolo B e os brancos à direita, é a saı́da da máquina para a entrada em questão. Formalmente, define-se uma máquina de Turing determinı́stica como uma quı́ntupla M := (Q, Σ, δ, s, H), onde Q é o conjunto de estados, Σ é o alfabeto de sı́mbolos, δ é uma função de (Q \ H) × Σ em Q × Σ × {←, ↓, →}, s ∈ Q é o estado inicial e H ⊆ Q é o conjunto de estados finais. O conjunto {←, ↓, →} descreve os possı́veis movimentos da cabeça de leitura da máquina. A função δ, chamada usualmente de função de transição, descreve um passo arbitrário da máquina e satisfaz as restrições mencionadas acima. Suponha que a máquina esteja num estado q em Q \ H e que sob a cabeça de leitura esteja o sı́mbolo σ. Se δ(q, σ) = (q 0 , σ 0 , d), o próximo estado será q 0 , o sı́mbolo σ 0 será escrito no lugar de σ e a cabeça de leitura de M moverá de acordo com d. A configuração atual de M é uma tripla (w1 , q, w2 ) ∈ Σ∗ ×Q×Σ∗ , onde w1 é a palavra que aparece na fita à esquerda da cabeça de leitura, q é o estado atual e w2 é a palavra à direita da cabeça de leitura ignorando-se brancos à direita. A cabeça de leitura aponta para a posição que contém o último sı́mbolo de w1 . A configuração inicial é a tripla (B, s, x), onde x é a entrada para a máquina. Dizemos que uma configuração (w1 , q, w2 ) produz em k passos uma configuração (w10 , q 0 , w20 ), denotado por (w1 , q, w2 ) `kM (w10 , q 0 , w20 ), se a máquina sai da primeira configuração e vai para a segunda em exatos k passos. 56 4.2 Máquinas de Turing não-determinı́sticas A máquina de Turing não-determinı́stica (MTND) é uma generalização da máquina de Turing determinı́stica. Essa máquina tem um papel fundamental na teoria de complexidade pois está na base da definição da classe NP, conforme será mostrado posteriormente. A maior parte das definições e idéias envolvidas na descrição das MTDs também se aplica às MTNDs. A diferença entre a MTND e a MTD está na função de transição e na maneira como as transições são feitas a cada passo. Nas máquinas determinı́sticas, existe uma única transição possı́vel a partir de uma dupla (q, σ), onde q é um estado não-final e σ é um sı́mbolo em Σ. Já nas máquinas não-determinı́sticas, pode existir mais de uma transição válida a partir de uma dupla (q, σ). Em cada passo da MTND, uma transição válida é escolhida arbitrariamente e é executada. O número de transições válidas a partir de uma dupla (q, σ) é limitado superiormente por 3 × |Σ| × |Q|. Logo, o número de configurações que podem ser produzidas a partir de cada configuração também é limitado superiormente por 3 × |Σ| × |Q|. A transição numa MTND é portanto uma relação e não necessariamente uma função. Formalmente, uma máquina de Turing não-determinı́stica é uma quı́ntupla M := (Q, Σ, ∆, s, H), onde Q é o conjunto de estados, Σ é o alfabeto de sı́mbolos, ∆ é uma relação de (Q \ H) × Σ em Q × Σ × {←, ↓, →}, s ∈ Q é o estado inicial e H ⊆ Q é o conjunto de estados finais. É evidente que as MTDs são casos particulares de MTNDs em que ∆ é uma função, já que toda função é uma relação. Uma transição (q 0 , σ 0 , d) em ∆(q, σ), onde q ∈ Q e σ ∈ Σ, é interpretada como antes. Assim, q 0 será o próximo estado da máquina, σ 0 deve ser escrito no lugar de σ e d indicará o deslocamento da cabeça de leitura. Tal transição será válida somente se (q 0 , σ 0 , d) ∈ ∆(q, σ). A definição de configuração é igual à que usamos na definição da máquina de Turing determinı́stica. Para MTNDs, dizemos que uma configuração (w1 , q, w2 ) produz a configuração (w10 , q 0 , w20 ) em k passos se, estando a máquina na primeira configuração, após k passos ela pode estar na segunda a partir de uma seqüência de transições válidas. A existência de várias transições possı́veis para cada par (q, σ) numa MTND permite a ocorrência de computações distintas para uma mesma entrada. Como as MTNDs podem ter várias computações válidas possı́veis para uma mesma entrada, elas podem produzir saı́das diferentes para uma mesma entrada. Comentaremos mais sobre isso quando falarmos das linguagens decididas por uma máquina de Turing. 57 4.3 Máquina de Turing probabilı́stica Uma máquina de Turing probabilı́stica (MTP) é uma MTND que funciona de maneira diferente. A cada passo, em vez de uma transição ser escolhida arbitrariamente dentre todas as transições aplicáveis, escolhe-se uma com probabilidade uniforme. Assim, pode-se falar na probabilidade da MTP produzir, numa computação para uma certa entrada, uma saı́da especı́fica. Todas as definições dadas para as MTNDs aplicam-se de maneira natural a uma MTP. Observe que uma MTD é uma MTP em que, a cada passo, há apenas uma transição aplicável. Uma MTP corresponde à formalização do conceito de um computador acoplado a um gerador de sı́mbolos aleatórios. É possı́vel descrever o funcionamento de uma MTP postergando as escolhas aleatórias para o final. Ou seja, pode-se calcular a probabilidade de se estar em uma configuração especı́fica a cada passo e só ao final fazer um único sorteio para determinar a configuração em que a máquina termina. 4.4 Máquina de Turing quântica A definição de uma máquina de Turing quântica (MTQ) assemelha-se à de uma MTP. Uma máquina de Turing quântica é uma MTND M = (Q, Σ, ∆, s, H) com a relação ∆ substituı́da por uma função α : Q × Σ × Q × Σ × {←, ↓, →} −→ C tal que, para cada (q, σ) em Q × Σ, vale que X 2 |α(q, σ, q 0 , σ 0 , d)| = 1, (q 0 ,σ 0 ,d)∈T onde T := Q × Σ × {←, ↓, →}. Cada número α(q, σ, q 0 , σ 0 , d) é chamado de amplitude. Note que α determina uma distribuição de probabilidade nas possı́veis transições aplicáveis a um par (q, σ). Define-se superposição de configurações como uma combinação linear de configurações, onde o coeficiente de uma configuração c é um número complexo P 2 αc e c |αc | = 1, sendo que o somatório é sobre todas as configurações c que estão na superposição. O coeficiente αc é a amplitude da configuração c. A primeira diferença no funcionamento de uma MTQ frente às máquinas anteriores é que esta, a cada instante, encontra-se numa superposição de configurações. Para que a transição de uma MTQ esteja bem definida, é preciso 58 que a máquina satisfaça a seguinte propriedade: se, numa superposição obtida depois de k passos a partir da configuração inicial, há uma configuração com amplitude não-nula num estado final, então todas as configurações com amplitude não-nula nessa superposição estão num estado final. Se todas as configurações da MTQ com amplitude não-nula forem finais, a MTQ termina a execução. Caso contrário, ela efetua uma transição, que P consiste no seguinte. Digamos que ψ := tj=1 αj cj é a superposição corrente, P onde tj=1 |αj |2 = 1 e αj 6= 0 para todo j. Para cada j, seja Cj o conjunto das configurações que podem ser obtidas de cj em um passo por meio de uma transição cuja amplitude é não-nula. Para cada c em Cj , seja αcj a amplitude correspondente à transição dePcj paraPc. Então, temos que a superposição resultante da transição é ψ 0 = tj=1 αj c∈Cj αcj c. Quando uma mesma configuração c aparece em mais de um conjunto Cj 2 P P 2 e j:c∈Cj αj αcj 6= j:c∈Cj |αj αcj | , dizemos que houve interferência. A interferência é negativa se o lado esquerdo é menor que o direito e positiva caso contrário. O fenômeno de interferência é o principal responsável pela diferença entre uma MTQ e uma MTP. A segunda diferença no funcionamento de uma MTQ frente às máquinas anteriores é que, ao final de suaPexecução, a MTQ efetua o que chamamos de t medição. Digamos que ψ := j=1 αj cj é a superposição final da máquina. Uma medição consiste na escolha aleatória de uma configuração c = cj com probabilidade |αj |2 , e na transição da superposição ψ para a superposição ψ 0 := c, ou seja, para a superposição em que apenas a configuração c tem amplitude não-nula (mais exatamente, c tem amplitude 1 em ψ 0 ). A saı́da da MTQ é o que está escrito na fita após a medição. Assim como uma MTP, uma MTQ pode produzir diferentes saı́das para uma mesma entrada, cada uma com uma probabilidade. Chamamos de paralelismo quântico à capacidade da MTQ estar numa superposição de configurações, e, num passo, efetuar transições múltiplas, envolvendo diversas configurações. Potencialmente é possı́vel explorar o fenômeno de interferência bem como o paralelismo quântico para se obter algoritmos quânticos eficientes para problemas considerados difı́ceis no modelo clássico de computação. 4.5 Recursos e linguagens Apresentamos algumas definições do modelo clássico de computação com o intuito de estabelecer um paralelo durante a apresentação dos correspondentes quânticos desses resultados e definições. 59 Para isso, definiremos o significado de tempo e espaço consumido nas máquinas do modelo clássico. Em seguida, falaremos das linguagens decididas por cada uma dessas máquinas. Tempo consumido pelas máquinas de Turing Durante a descrição da MTD, foi definido que (w1 , q, w2 ) `kM (w10 , q 0 , w20 ) se a máquina M sai da primeira configuração e vai para a segunda em exatos k passos. Se (w1 , q, w2 ) é a configuração inicial de M e q 0 é um de seus estados finais, então dizemos que k é o tempo consumido por M para a entrada w2 . Dada uma MTD M, se existe um polinômio p(n) : N −→ N tal que, para qualquer entrada x, o tempo consumido por M é limitado superiormente por p(|x|), onde |x| denota o comprimento da palavra x, então dizemos que M é polinomialmente limitada. Se M é uma MTND, o maior tempo consumido em uma computação válida de M para uma entrada determinada é considerado o tempo consumido por M para essa entrada. Analogamente, M é polinomialmente limitada se existe um polinômio p(n) : N −→ N tal que, para qualquer entrada x, o tempo consumido por M é limitado superiormente por p(|x|). Por fim, se M é uma MTP, valem as mesmas definições usadas para as MTNDs. Vale destacar que no caso das MTPs também aplica-se o conceito de tempo esperado de computação, que formalmente é a esperança do tempo consumido por uma computação de M para uma dada entrada x. Espaço consumido pelas máquinas de Turing Existem também classes de problemas que são definidas em função do espaço consumido pelas máquinas de Turing que os resolvem. Da mesma forma que no estudo do consumo de tempo, temos interesse especial nos problemas que podem ser resolvidos por máquinas de Turing que consomem espaço polinomial no tamanho da entrada. As diferenças entre as máquinas de Turing de naturezas distintas não são muito grandes no consumo de espaço. Mais adiante, ao enunciarmos um resultado de Savitch [Sav70], ficará mais claro o porquê dessa afirmação. Dizemos que o espaço consumido por uma MT é a maior quantidade de células distintas usadas pela máquina para realizar uma computação válida para uma determinada entrada. No caso das MTDs, é o número de células usadas na única computação possı́vel. Já para MTNDs e MTPs, é o maior número de células utilizadas em uma computação válida. 60 Como em toda MT a cabeça de leitura só pode se deslocar de uma célula a cada passo, claramente o espaço consumido em uma computação é limitado superiormente pelo número de passos utilizados pela máquina. Dizemos que uma MT consome espaço polinomial se o espaço consumido pela MT é limitado superiormente por um polinômio definido em função do tamanho da entrada. Linguagens e máquinas de Turing Ao definir as máquinas de Turing, utilizamos como parâmetro um alfabeto Σ. Esse alfabeto é um conjunto que contém todos os sı́mbolos reconhecidos pela máquina de Turing em questão. Logo, uma entrada válida para a máquina deve ser uma palavra composta apenas por sı́mbolos de Σ. Um conjunto de palavras cujas letras pertencem a um alfabeto Σ é chamado de linguagem. Geralmente estamos interessados em verificar se uma determinada palavra pertence ou não a uma particular linguagem L. Máquinas de Turing que devolvem respostas binárias podem ser usadas para efetuar essa tarefa. Uma das respostas indica que a palavra fornecida como entrada pertence à linguagem L (aceitação) e a outra que a palavra não pertence (rejeição). Em muitos casos, porém, deseja-se fornecer uma entrada para uma máquina de Turing para a obtenção de uma saı́da que não pode ser descrita apenas com duas respostas distintas. Por exemplo, uma máquina que recebe a representação binária de um número inteiro x qualquer como entrada e devolve como resposta a representação binária do número x + 2 claramente deve ser capaz de devolver mais do que duas respostas distintas. Nesse caso, dizemos que estamos lidando com um problema, e não com uma linguagem. Rigorosamente, existem diferenças entre problemas e linguagens, mas como podemos transformar uma coisa na outra de maneira razoavelmente simples, vamos falar de problemas e linguagens de maneira indistinta. Mostraremos agora as relações entre as linguagens e as máquinas de Turing determinı́sticas, não-determinı́sticas e probabilı́sticas. Se existe uma MTD M que, dada uma palavra x, responde se x pertence ou não a uma determinada linguagem L, então dizemos que M decide a linguagem L. As respostas são devolvidas por M através dos sı́mbolos 0 e 1, que indicam rejeição e aceitação, respectivamente, da palavra x. Esses sı́mbolos devem aparecer sozinhos na fita da máquina após a mesma ter parado, na segunda célula da esquerda para a direita. No caso das MTNDs, já vimos que podem existir várias computações e várias saı́das possı́veis para uma máquina e uma entrada. Assim, dizemos que uma MTND M decide uma linguagem L se toda palavra x em L é aceita por 61 M em pelo menos uma de suas computações, e se toda palavra x fora de L é rejeitada por M em todas as suas computações. Essa definição acaba mostrando a caracterı́stica das MTNDs que faz com que elas pareçam mais eficientes computacionalmente e menos realistas do que as MTDs. Por fim, a decisão de linguagens por MTPs têm um aspecto um pouco diferente das demais máquinas de Turing. Assim como as MTNDs, as MTPs também podem produzir respostas distintas para uma mesma entrada. Porém, nas MTPs, atribuı́mos a cada computação válida (e conseqüentemente a cada possı́vel resposta) uma determinada probabilidade. A decisão de uma linguagem por uma MTP envolve as probabilidades de obtenção das respostas. Em alguns casos estamos interessados em fixar uma probabilidade máxima para as rejeições incorretas, em outros para as aceitações incorretas e em outros para as duas simultaneamente. A decisão de linguagens em MTPs, portanto, não possui uma definição única como no caso das MTDs e das MTNDs. Logo, ao utilizar esse conceito mais adiante no texto, definiremos exatamente o significado adequado dentro do contexto. 62 Capı́tulo 5 Máquinas de Turing universais A descrição de máquinas de Turing dada no capı́tulo anterior indica que tais máquinas são modeladas para resolver um único problema. No entanto, os computadores atuais não estão restritos a executar uma única tarefa. Vamos descrever neste capı́tulo uma MTD chamada de universal, que tem um caráter mais geral, sendo capaz de efetuar qualquer tarefa executada por uma MTD. Depois disso, apresentaremos uma máquina de Turing quântica universal. 5.1 Máquina de Turing determinı́stica universal A descrição que apresentamos a seguir baseia-se na apresentação de Papadimitriou [Pap94]. Denotaremos por U a máquina de Turing universal que vamos construir. Essa máquina lê uma entrada e a interpreta como sendo a descrição de uma máquina de Turing M e uma entrada x para essa máquina. A máquina U deve funcionar de modo que, após sua parada, a saı́da produzida seja a mesma que M devolve ao ser executada tendo x como entrada. Vamos determinar agora o padrão de entrada a ser reconhecido por U . Sejam M = (Q, Σ, δ, s, H) a máquina que será simulada e x sua entrada. Cada sı́mbolo de Σ e cada estado de Q será descrito como um número na forma binária. Os sı́mbolos de Σ serão representados por números em {1, 2, . . . , |Σ|}, os estados de Q por números em {|Σ|+1, |Σ|+2, . . . , |Σ|+|Q|} e os números |Σ|+ |Q| + 1, . . . , |Σ| + |Q| + 5 representarão os sı́mbolos {←, ↓, →}, B e t. Todos os sı́mbolos serão representados usando a mesma quantidade de bits (serão usados zeros à esquerda quando necessário). O estado denotado por s é o estado inicial de M , e será representado pelo número |Σ| + 1. Na parte da entrada que corresponde a M , inicialmente serão fornecidos os 63 números |Q|, |Σ| e |H|. Em seguida, aparece a representação de |H| estados de M , indicando seus estados finais. Por fim, segue uma descrição de δ através de uma seqüência de pares na forma ((q, σ), (p, ρ, D)), onde cada sı́mbolo estará codificado na forma já descrita. Vamos assumir sem perda de generalidade que os parênteses e a vı́rgula pertencem ao alfabeto de U . Após a descrição da máquina, a fita de entrada de U vai conter o sı́mbolo “;” (que deverá pertencer ao alfabeto de U ), seguido pela descrição da entrada x para M , também devidamente codificada. Como cada sı́mbolo e estado é representado com o mesmo número de bits, não há ambigüidades na descrição da máquina ou da entrada. Tendo a entrada, U pode começar sua execução. Para facilitar a descrição, vamos supor que U utiliza 3 fitas, e que cada fita tem uma cabeça de leitura independente (ou seja, cada cabeça pode estar numa posição diferente das demais). Pode-se provar que uma MTD com uma fita pode simular qualquer MTD com k fitas e com k cabeças de leitura independentes para k > 1. Na primeira fita, U receberá a entrada e devolverá a saı́da. Na segunda fita, U vai guardar a configuração atual de M . A configuração estará no formato (w, q, u), com cada sı́mbolo codificado da maneira que descrevemos anteriormente. Inicialmente, a configuração inicial será (B, s, x). A terceira fita guardará a descrição da função de transição δ de M . Para simular M , no inı́cio de cada passo U percorre a segunda fita até descobrir o estado atual de M , localizando assim a posição da cabeça de leitura de M em sua fita. Em seguida, U percorre a terceira fita, procurando uma transição que tenha q como estado do domı́nio, onde q é o estado atual. Feito isso, U move a cabeça de leitura para a esquerda na segunda fita para identificar o sı́mbolo σ que está sob a cabeça de leitura de M e verificar se a transição que está sendo analisada atualmente tem como domı́nio o par (q, σ). Se não for esse o par, repete-se o processo até que ele seja encontrado. Após localizar a transição adequada, U faz as modificações na segunda fita, movimentando a cabeça, alterando o sı́mbolo na posição que estava anteriormente e mudando o estado atual, conforme a descrição da função de transição. Se o estado atingido pertence a H, a simulação de M pára. Caso contrário o processo se repete. Ao término da simulação, o conteúdo da segunda fita de U representará a configuração final de M após sua execução para a entrada x. Assim, U substitui o conteúdo da primeira fita pelo da segunda e termina sua execução. A construção dessa máquina utilizou uma série de recursos e ferramentas que facilitaram bastante nossa tarefa, como as fitas múltiplas e o movimento independente das cabeças de leitura dessas fitas. Nem todas essas ferramentas podem ser utilizadas no modelo quântico. Além disso, outros cuidados devem 64 ser tomados, e isso acaba resultando num aumento significativo da complexidade da correspondente construção. A partir da descrição mostrada, não é difı́cil deduzir que uma MTD pode simular também uma MTND ou uma MTP. Vale destacar, porém, que no caso de MTNDs ou MTPs, alguns detalhes e convenções devem ser ajustados pois essas máquinas podem produzir mais de uma saı́da para a mesma entrada. 5.2 Máquina de Turing quântica universal As operações realizadas por uma MTQ podem ser descritas como transformações unitárias sobre vetores de um espaço de Hilbert. Logo, o estudo dessas transformações facilita a compreensão das limitações e das ferramentas disponı́veis quando estudamos a computação quântica. Nesta seção, apresentamos alguns resultados de Bernstein e Vazirani [BV97]. Mostramos como uma dada tranformação unitária pode ser decomposta em transformações unitárias simples (ou quase-triviais), diretamente implementáveis em MTQs. Essas transformações simples são divididas em dois tipos: mudança de fase e rotação. O resultado apresentado é construtivo, mas envolve cálculos com números irracionais. A princı́pio, não consideramos as precisões das operações envolvidas, mas vamos mostrar como os ângulos utilizados nas operações de rotação e de mudança de fase podem ser obtidos com precisão consumindo tempo polinomial em 1/ a partir de um ângulo fixo. 5.2.1 Decomposição de uma transformação unitária Se uma MTQ com conjunto de estados Q e alfabeto Σ, durante uma computação, utiliza no máximo k células da fita, então ela admite que uma matriz unitária de dimensão k|Q||Σ|k descreva sua evolução. Logo, a dimensão do espaço considerado será d, onde d = k|Q||Σ|k . Denotamos por ei o vetor com todas as coordenadas nulas exceto a coordenada i, que vale 1. Uma matriz unitária M d × d é denominada quase-trivial se satisfaz uma das duas condições abaixo: 1. M é a matriz identidade a menos de uma de suas entradas na diagonal principal, que tem valor eiθ para algum θ ∈ [0, 2π). Ou seja, existe j tal que Mj,j = eiθ , Mk,k = 1 ∀k 6= j e Mk,l = 0 ∀k, l, k 6= l. 2. M é a identidade a menos da submatriz 2 × 2 determinada por um par de coordenadas distintas j e k, onde coincide com a rotação de um ângulo 65 cos θ − sen θ θ ∈ [0, 2π), dada pela matriz: . Ou seja, M é tal que sen θ cos θ existem θ e j 6= k tais que M ej = (cos θ)ej + (sen θ)ek , M ek = −(sen θ)ej + (cos θ)ek , e para ∀l 6= j, k, M el = el . Nesse ponto, nos referimos a M el como sendo a l-ésima coluna de M . Dizemos que uma transformação que satisfaz a primeira condição é uma mudança de fase quase-trivial, enquanto que uma transformação que satisfaz a segunda condição é uma rotação quase-trivial. Vamos usar a notação [j, j, θ] para representar uma mudança de fase de eiθ na coordenada j, e vamos usar a notação [j, k, θ] para denotar uma rotação de um ângulo θ entre as coordenadas j e k. Agora, mostramos uma tranformação que leva um vetor v em Cd em um vetor de mesmo módulo mas com apenas uma coordenada especı́fica não-nula. Esse resultado será utilizado no teorema que mostra a decomposição de uma matriz unitária em matrizes quase-triviais. Para isso, vamos definir duas funções sobre o conjunto dos números complexos. Se x ∈ C, Re(x) é o valor da parte real de x, e Im(x) é o valor da parte imaginária de x. Lema 5.1. Para todo vetor v ∈ Cd , existe um conjunto de 2d − 1 matrizes quase-triviais U1 , U2 , . . . , U2d−1 tais que U1 U2 . . . U2d−1 v = kvke1 . Demonstração. Inicialmente, transformamos o vetor v = (v1 , . . . , vd ) em um vetor de Rd utilizando mudanças de fase. Seja Pj = [j, j, φj ] a matriz quase-trivial que, aplicada na coordenada j, faz uma mudança de fase de um ângulo φj onde φj = 0 se vj = 0 ou φj = Re(v ) Re(v ) 2π − arccos |vj |j ou φj = arccos |vj |j , dependendo do sinal de Im(vj ). Assim, temos vj = |vj |eiθ = |vj |(cos θ + i sen θ) para algum θ, e aplicando Pj em vj 0 0 obtemos um vetor vj0 = eiθ tal que sen θ = 0. Feitas as mudanças de fase em todas as coordenadas, teremos um novo vetor 0 v = P1 · · · Pd v, com vj0 = |vj | para todo j. O próximo passo é fazer d − 1 rotações para mover todo o peso do vetor v 0 para a sua primeira coordenada. Assim, seja Rj = [j, j + 1, θj ] a matriz quasetrivial que aplica nas coordenadas j e j + 1 uma rotação de θj , onde |vj | θj = − arccos qP d k=j |vk |2 se a somatória no denominador for não-nula e θj = 0 caso contrário. Dessa forma, temos que R1 · · · Rd−1 P1 · · · Pd v = kvke1 . 66 Na rotação Rj , a (j + 1)-ésima e a j-ésima coordenadas serão alteradas, de modo que a primeira ficará com valor 0 e a segunda vai concentrar o peso que as duas tinham anteriormente. Como o vetor em questão tem dimensão d, serão necessárias exatamente d − 1 rotações para que o vetor resultante tenha todo o seu peso concentrado em sua primeira coordenada. Para facilitar a compreensão do lema acima, vejamos um exemplo. Exemplo 5.2 Seja v = (1 + i, i, 2) um vetor em C3 . Vamos mapear esse vetor em R3 . Para isso, serão necessárias três mudanças de fase: 1. Mudança na terceira coordenada: Em primeiro lugar, devemos obter o valor de φ3 . Como v3 = 2, temos: φ3 = arccos Re(v3 ) 2 = arccos = 0. |v3 | 2 Logo, temos que P3 é a transformação quase-trivial [3, 3, 0], e portanto P3 v = (1 + i, i, 2). 2. Mudança na segunda coordenada: Agora, devemos obter o valor de φ2 . Como v2 = i, temos: 0 π 3π Re(v2 ) = 2π − arccos = 2π − = . |v2 | 1 2 2 Logo, temos que P2 é a transformação quase-trivial 2, 2, 3π . Assim, como 2 P3 v = v, temos: φ2 = 2π − arccos e 3πi 2 v2 = e 3πi 2 πi e 2 = e2πi = cos 2π + i sen 2π = 1 e portanto P2 P3 v = (1 + i, 1, 2). 3. Mudança na primeira coordenada: Por fim, fazemos a conversão da primeira coordenada. O esquema é parecido com a conversão da terceira coordenada. Sendo v1 = 1 + i, temos: Re(v1 ) 1 π 7π = 2π − arccos √ = 2π − = . |v1 | 4 4 2 . Assim: Logo, temos que P1 é a transformação quase-trivial 1, 1, 7π 4 φ1 = 2π − arccos 67 √ √ √ πi e 4 = 2 e2πi = 2 (cos 2π + i sen 2π) = 2 √ e portanto P1 P2 P3 v = ( 2, 1, 2). e 7πi 4 v1 = √ 2e 7πi 4 Dessa forma, mapeamos v ∈ C3 em R3 . Agora, vamos fazer duas rotações para mover todo o peso do vetor P1 P2 P3 v para sua primeira coordenada. 1. Rotação entre a 3a e a 2a coordenada: Nesse primeiro passo, vamos mover todo o peso da 3a e da 2a coordenadas √ do vetor P1 P2 P3 v = ( 2, 1, 2) para a segunda coordenada. Para isso, vamos aplicar a rotação R2 = [2, 3, θ2 ] onde |v2 | θ2 = − arccos qP 1 = − arccos √ . 3 5 2 j=2 |vj | Deixamos a cargo do leitor verificar que a multiplicação √ √ da matriz que √ corresponde a R2 por ( 2, 1, 2) resulta no vetor ( 2, 5, 0). 2. Rotação entre a 2a e a 1a coordenada: √ √ Nesse último passo, movemos todo o peso de R2 P1 P2 P3 v = ( 2, 5, 0) para a primeira coordenada. Vamos aplicar a rotação R1 = [1, 2, θ1 ], onde |v1 | θ1 = − arccos qP 3 j=1 r = − arccos |vj |2 2 . 5 Mais uma vez, deixamos as contas a cargo do leitor, e afirmamos por fim √ √ que a multiplicação da matriz correspondente a R por ( 2, 5, 0) resulta 1 √ no vetor ( 7, 0, 0). Note que R1 R2 P1 P2 P3 v = kvke1 , conforme enunciado no lema. Vamos mostrar agora como o mapeamento de um vetor para uma determinada direção permite a decomposição de uma transformação unitária. Teorema 5.3. Para toda matriz unitária U de dimensão d, existem n matrizes quase-triviais U1 , . . . , Un de dimensão d, com n limitado por um polinômio em d, tais que U = Un · · · U1 . 68 Demonstração. Para determinar as matrizes U1 , . . . , Un , vamos determinar matrizes Q1 , . . . , Qd tais que Qd · · · Q1 U é a matriz identidade, onde cada matriz Qk pode ser facilmente convertida num produto de matrizes quase-triviais. Como a inversa de uma matriz quase-trivial também é quase-trivial, de Q1 , . . . , Qd é fácil obter as matrizes U1 , . . . , Un mencionadas no enunciado do teorema. Uma matriz d × d é k-simples se suas primeiras k linhas e suas primeiras k colunas são iguais as da identidade. A única matriz d × d d-simples é a identidade. É claro que o produto de duas matrizes k-simples também é uma matriz k-simples. As matrizes Q1 , . . . , Qd são obtidas seqüencialmente, de modo que Qk · · · Q1 U é uma matriz k-simples para k = 1, . . . , d (isso implica que Qd · · · Q1 U é a identidade). Suponha que a matriz S = Qk−1 · · · Q1 U é uma matriz (k − 1)-simples unitária. Queremos um produto de matrizes quase-triviais Qk tal que Qk S seja k-simples. Para obter a matriz Qk , vamos recorrer ao resultado mostrado no lema anterior. Seja Z a matriz obtida de S removendo-se as k − 1 primeiras linhas e colunas de S. Note que Z é uma matriz (d − k + 1)-dimensional. Vamos aplicar a transformação do lema anterior no vetor correspondente à primeira linha de Z, que denotaremos por Z1T . A saı́da fornecida pelo algoritmo será uma seqüência de matrizes unitárias quase-triviais V1 , V2 , . . . , V2d−2k+1 (d − k + 1)-dimensionais tais que V1 · · · V2d−2k+1 Z1T = kZ1T ke1 . Feito isso, estendemos cada Vi para transformá-la em uma matriz (k − 1)simples d-dimensional. Como S é unitária, temos que Qk S é uma matriz ksimples unitária. A cada passo, produzimos uma das matrizes Qk . Cada uma dessas matrizes é um produto de matrizes d-dimensionais quase-triviais. No final, a matriz Qd · · · Q1 U será a identidade de dimensão k. A partir do produto de matrizes quase-triviais que compõem as matrizes Qk , podemos obter as matrizes Uj do enunciado. Bernstein e Vazirani [BV97] apresentaram versões algorı́tmicas do lema 5.1 e do teorema 5.3. Observe que as provas do lema e do teorema são construtivas se ignorarmos o fato de que envolvem cálculos com números reais. Bernstein e Vazirani demonstraram variantes “aproximadas” destes resultados. Tais variantes mostram que, mesmo que os cálculos envolvidos sejam feitos com um certo erro de precisão, as conclusões, ajustadas adequadamente, valem. 69 5.2.2 Cálculo de transformações quase-triviais Agora, apresentamos um lema que mostra que podemos usar uma única rotação para aproximar eficientemente o valor de qualquer rotação. Ou seja, podemos aproximar qualquer ângulo a partir de um determinado ângulo fixo. P −2i Lema 5.4. Seja R = 2π ∞ . Então existe um algoritmo determinı́si=1 2 tico que, dados > 0 e um ângulo θ ∈ [0, 2π), produz um inteiro k limitado polinomialmente por 1/ tal que |kR − θ| mod 2π ≤ . 2π Demonstração. Seja n a menor potência de 2 tal que > 2n−1 . Aproximamos θ n o número 2π por uma fração de denominador 2 . Ou seja, encontramos um inteiro m ∈ [1, 2n ) tal que θ m 1 2π − 2n ≤ 2n . Dessa forma, podemos pegar k = m2n , pois m2n R mod 2π = = 2πm 2πm ∞ X ! n−2i 2 i=1 ∞ X mod 2π ! n−2i 2 mod 2π i=log n+1 = ∞ X 2πm i + 2πm 2n−2 n 2 i=log n+2 ! mod 2π, e como m ∞ X i 2n−2 ≤ m2n−4n+1 ≤ 2n−3n+1 ≤ 2−2n+1 , i=log n+2 temos que n 2πm |m2 R − θ| mod 2π ≤ m2 R − n mod 2π + 2 2π 2π 2π ≤ 2n−1 + n < n−1 < . 2 2 2 n 70 2πm − θ 2n O resultado acima, para ser utilizado em combinação com o teorema 5.3 apresentado nessa seção, precisa de uma adaptação, bem como o lema 5.1. Há ainda a necessidade de admitir que, em potenciais implementações de MTQs e na execução das transições, eventualmente aparecem erros de precisão. Bernstein e Vazirani [BV97] apresentam versões adaptadas do lema e do teorema que levam em consideração potenciais erros de precisão e a utilização da aproximação dada pelo último lema. A utilização das decomposições em resultados algorı́tmicos, como por exemplo na descrição de uma MTQ universal, envolvem ainda a questão de se tais decomposições aproximadas podem ser obtidas em tempo polinomial nos parâmetros envolvidos. A versão de Bernstein e Vazirani do teorema incorpora esses dois aspectos e é enunciado abaixo, após uma definição, para que fiquem um pouco mais claras as conseqüências do teorema. Uma matriz U é -próxima de unitária se existe uma matriz unitária Ũ tal que kU − Ũ k ≤ . Teorema 5.5 (Bernstein & Vazirani). Existe um algoritmo determinı́stico que tem como entrada um número real > 0 e uma matriz d × d complexa √ -próxima de unitária e que produz matrizes quase-triviais d-dimensionais 2(10 d)d U1 , . . . , Un , com n polinomial em d, tais que kU − Un · · · U1 k ≤ . O algoritmo consome tempo polinomial em log 1/ e no tamanho de U . 5.2.3 Descrição da máquina de Turing quântica universal Como na teoria clássica de complexidade, para apresentar uma MTQ universal, é necessário introduzir ferramentas que permitam a simulação de uma MTQ arbitrária por uma MTQ universal. Esse ferramental, apesar de técnico e importante, não apresenta grandes dificuldades, até por não envolver nada peculiar ao modelo quântico de computação. Por isso, optamos por omitir sua apresentação, concentrando-nos na apresentação dos conceitos principais. Na descrição da MTD universal, utilizamos uma máquina com várias fitas. Fitas múltiplas, porém, são de difı́cil trato no modelo quântico, e foram substituı́das por uma fita única com múltiplas “trilhas”, de efeito quase semelhante. Uma diferença está no fato de que, por ter uma única fita, a MTQ universal tem apenas uma cabeça de leitura. Ou seja, a MTQ universal lê todas as trilhas em uma mesma posição simultaneamente, ao contrário da MTD universal, que utilizava uma cabeça para cada fita. Esse ponto e a questão de sincronização, discutida a seguir, dificultam a simulação de uma MTQ e justificam o funcionamento da MTQ universal descrita na prova do próximo teorema. Para que uma MTQ universal possa simular as transições quânticas de uma 71 MTQ M , ela deve se manter sincronizada, ou seja, todas as configurações da superposição de M num determinado passo devem ser atingidas simultaneamente (não deve haver transições atrasadas ou adiantadas na simulação). A simulação realizada por uma MTQ universal não é exata, ao contrário do que acontece com a MTD universal. Alguns desses detalhes serão omitidos para que não prejudiquem a compreensão das idéias principais envolvidas na simulação. Para descrever a MTQ universal, vamos precisar do conceito de máquina unidirecional, que definimos a seguir. Uma MTQ M = (Q, Σ, α, s, H) é denominada unidirecional se cada estado pode ser acessado a partir de uma única direção. Em outras palavras, se α(p1 , q1 , p01 , q, d1 ) e α(p2 , q2 , p2 1, q, d2 ) são ambas não-nulas, então d1 = d2 . Bernstein e Vazirani [BV97] demonstraram que toda MTQ pode ser simulada por uma MTQ unidirecional em um número de passos no máximo 5 vezes maior que o da MTQ simulada. Mais do que isso, a descrição da MTQ unidirecional pode ser obtida da descrição da MTQ a ser simulada em tempo polinomial. Esse fato é usado na prova do teorema abaixo. Nesse texto, apresentamos apenas a idéia geral dessa prova, que envolve uma série de detalhes técnicos, que podem ser encontrado no artigo de Bernstein e Vazirani [BV97]. Teorema 5.6. Existe uma MTQ U que, dada a descrição de uma MTQ M , um número > 0 e um inteiro T ≥ 0, simula os T primeiros passos de M com com precisão em um número de passos polinomial em T e 1/. Idéia da demonstração: Seja U nossa MTQ universal, e seja M a máquina que queremos simular. Sabemos que existe uma MTQ M 0 = (Q, Σ, α, s, H) unidirecional que simula M consumindo tempo polinomial no número de passos de M . Vamos usar U para simular M 0 . As configurações de M 0 são guardadas em duas trilha da fita de U . Para simular M 0 , serão utilizadas log |Q × Σ| células de U por célula de M 0 . Cada um desses grupos de células contém um par ordenado (p, σ), onde σ ∈ [1, |Σ|] representa o conteúdo da célula correspondente em M 0 , e p ∈ [0, |Q|] representa o estado de M 0 se a cabeça está nessa célula e p = 0 se a cabeça estiver em outra célula de M 0 . Cada membro do par estará em duas trilhas da fita. Seja T o número de passos de M . O número de grupos de células utilizados para simular a fita de M 0 será 2T + 1. Sabemos que, ignorado o movimento da cabeça de leitura, α fornece uma transformação unitária V de dimensão d = |Q × Σ|. Para fazer a atualização da superposição de M 0 armazenada nas duas trilhas de U , inicialmente varremos a fita de U e fazemos uma cópia do estado corrente e do sı́mbolo sob a cabeça 72 de leitura de M 0 para um grupo de células fixo de U , especificamente reservado para isso. Com a cabeça de leitura de U sob esse grupo de células, aplicamos a transformação V , obtendo o novo estado e o novo sı́mbolo sob a cabeça de leitura de M 0 para cada uma das configurações de sua superposição corrente. De posse dessa informação, U varre novamente sua fita, atualizando o estado e o sı́mbolo na posição correta de sua fita. A partir do estado corrente, dado que M 0 é uma máquina unidirecional, U determina o movimento da cabeça de leitura de M 0 . Na verdade, a partir de α, podemos obter, em tempo polinomial, apenas uma aproximaçaão de V com erro . A necessidade de se fazer uma cópia do estado e do sı́mbolo sob a cabeça de leitura de M 0 vem do fato de que a cabeça de leitura das várias configurações de M 0 não estão na mesma posição e a transição de U deve ser feita simultaneamente em todas essas configurações. 73 Capı́tulo 6 Classes de complexidade 6.1 Classes de complexidade do modelo clássico As classes P e PSPACE A partir do conceito de máquinas de Turing polinomialmente limitadas, vamos definir as linguagens polinomialmente decidı́veis. Dizemos que uma linguagem é polinomialmente decidı́vel se existe uma máquina de Turing determinı́stica polinomialmente limitada que a decide. A classe P (polynomial-time) é o conjunto de todas as linguagens polinomialmente decidı́veis. Esta classe é extremamente importante, pois contém a maior parte dos problemas que podem ser resolvidos de maneira eficiente. Dizemos que um problema é resolvido de maneira eficiente se existe um algoritmo para resolvê-lo que consome tempo polinomial no tamanho da entrada. A classe P é fechada sob união, intersecção, concatenação e estrela de Kleene. Essas propriedades são importantes e suas provas são interessantes, mas serão omitidas nesse texto. De maneira parecida, podemos definir a classe PSPACE (polynomialspace). Vale ressaltar que, enquanto a primeira faz a classificação das linguagens em função do tempo consumido, a segunda o faz em função do espaço consumido. Dizemos que uma linguagem pertence à classe PSPACE se ela é decidida por uma máquina de Turing determinı́stica que consome espaço polinomial no tamanho da entrada. É fácil ver que P ⊆ PSPACE: como já observamos, toda MTD que consome tempo polinomial certamente consome espaço polinomial, já que, a cada passo, a cabeça de leitura da máquina só pode se mover de no máximo uma 74 célula à direita. Por outro lado, o inverso não é verdade. É fácil imaginar uma MTD que consome tempo superpolinomial mas espaço polinomial. Assim, é concebı́vel (e até de se esperar) que existam linguagens em PSPACE que não estejam em P. Surpreendentemente, não se sabe até hoje se este é o caso ou não. Ou seja, não se sabe se P = PSPACE. As classes NP e coNP As classes NP e coNP podem ser descritas de maneira parecida com a que descrevemos a classe P. Conforme explicaremos adiante, essas classes são muito importantes no estudo da teoria de complexidade clássica. Vamos definir NP (nondeterministic polynomial-time) e coNP em função das máquinas de Turing não-determinı́sticas polinomialmente limitadas. Dizemos que uma linguagem pertence à classe NP se ela pode ser decidida por uma máquina de Turing não-determinı́stica polinomialmente limitada. A classe das linguagens cujo complemento pertence a NP é denominada coNP, onde o complemento de uma linguagem L sob um alfabeto Σ é a linguagem Σ∗ \ L. De maneira geral, o complemento de uma classe de complexidade arbitrária C é denotado por coC e definido como o conjunto das linguagens cujo complemento está em C. Por exemplo, ao definir a classe P, também podemos definir a classe coP, seguindo o esquema acima. Nesse caso, temos uma classe que é igual ao seu complemento. Dada uma linguagem L em P ou em coP, e uma máquina M polinomialmente limitada que a decide, basta trocar aceitação por rejeição e vice-versa na descrição de M para obter uma máquina polinomialmente limitada que decide o complemento de L. As classes NP e coNP contêm vários problemas para os quais não se conhece algoritmo polinomial, e formam com a classe P a fronteira entre o que pode e o que não pode ser resolvido eficientemente no modelo clássico. Essas classes também são importantes porque contêm uma grande quantidade de problemas de interesse prático. Claramente, toda linguagem que está em P também está em NP e em coNP, visto que uma MTD é uma MTND. Porém, não sabemos muito mais a respeito da relação entre essas três classes. A questão mais importante e conhecida é se P é igual a NP. Se isso for verdade, saberemos que muitos problemas para os quais hoje não se conhecem algoritmos exatos razoáveis terão uma solução polinomial. Porém, são poucos os que acreditam nessa hipótese. 75 NP ⊆ PSPACE = NPSPACE Uma relação conhecida entre classes de complexidade é que NP ⊆ PSPACE. Isso significa que toda linguagem decidida por uma MTND limitada polinomialmente pode ser decidida por uma MTD que consome espaço polinomial. Vamos apresentar a prova de maneira razoavelmente informal, pois o que queremos mostrar é a idéia que está por trás da simulação de uma MTND por uma MTD. Dada uma MTND M polinomialmente limitada que decide uma linguagem L, queremos mostrar que essa máquina pode ser simulada por uma MTD M 0 que consome espaço polinomial e decide a mesma linguagem L. A diferença entre as máquinas M e M 0 é o não-determinismo. Sendo uma MTND, M requer apenas que uma de suas possı́veis computações aceite uma palavra da linguagem L, e também requer que todas as computações rejeitem as palavras que não estão em L. Logo, ao simular M , a máquina M 0 deve ser capaz de simular todas as computações possı́veis de M para poder rejeitar uma palavra corretamente. A conclusão de que uma palavra está na linguagem pode ser rápida (basta encontrar a primeira computação que aceita a palavra de entrada), mas em geral não é possı́vel determinar a priori quantas simulações precisam ser feitas. Assim, considerando o pior caso, é fácil ver que toda simulação de M por M 0 que consiste em testar cada uma das computações possı́veis pode consumir tempo exponencial no tamanho da entrada. Porém, sabemos que M é polinomialmente limitada. Logo, todas as suas computações consomem tempo, e portanto espaço, polinomial no tamanho da entrada. Assim, uma simulação de M por M 0 que testa cada computação possı́vel consumindo espaço polinomial e que sempre consegue reaproveitar esse espaço nas próximas computações é suficiente para mostrar que NP está contida em PSPACE. A construção da M 0 é razoavelmente simples. A idéia principal consiste numa espécie de busca em largura num grafo. Mais especificamente, M 0 simula todas as computações possı́veis de M com t passos antes de simular qualquer computação com t + 1 passos. Para representar as computações, M 0 pode indexar as transições das computações com números. Esses números serão obtidos a partir de um contador, que será representado na base binária. Logo, mesmo se o número de computações for exponencial, o espaço consumido por M 0 para armazenar tal contador será polinomial no tamanho da entrada. Em cada passo da simulação, M 0 incrementa seu contador e simula a com76 putação de M referente a seu valor. O conteúdo da fita de M para cada computação pode ser guardado numa fita auxiliar durante a simulação, e antes da próxima computação essa fita é apagada. Dessa forma, é claro que o espaço usado para guardar as computações também será polinomial no tamanho da entrada. Como toda transição de M pode ser simulada em tempo polinomial por M 0 , a simulação pode ser feita consumindo espaço polinomial no tamanho da entrada. Assim, NP ⊆ PSPACE. Analogamente, mostra-se que coNP ⊆ PSPACE. Dizemos que uma linguagem pertence à classe NPSPACE se ela é decidida por uma máquina de Turing não-determinı́stica que consome espaço polinomial no tamanho da entrada. Uma simulação semelhante a essa foi proposta por Savitch [Sav70] para mostrar que NPSPACE = PSPACE. As classes RP e coRP As classes discutidas a seguir envolvem computações probabilı́sticas e são de fundamental importância tanto no modelo clássico como no modelo quântico. Primeiro definimos a classe RP (randomized polynomial-time). Na literatura, essa classe é definida em função das máquinas de Turing Monte-Carlo. Infelizmente não há um consenso quanto a definição dessas máquinas (algumas fontes falam que elas devem ser limitadas polinomialmente, enquanto outras não estabelecem essa restrição). Logo, vamos fazer a definição da classe em função de suas propriedades principais. Para que uma linguagem L pertença à classe RP, deve existir uma MTP M limitada polinomialmente satisfazendo o seguinte: 1. Se uma palavra x dada na entrada não está na linguagem L, então a máquina M sempre rejeita x. 2. Se uma palavra x dada na entrada está na linguagem L, então a máquina M aceita x com probabilidade maior ou igual a 0,5. Essas duas propriedades caracterizam a máquina de Turing Monte-Carlo. Diz-se neste caso que M decide a linguagem L com probabilidade de aceitação 0,5. O valor da probabilidade de aceitação na definição de RP não é muito importante, no sentido de que qualquer outro valor em (0; 1] leva à mesma classe RP. Isso porque, de uma MTP limitada polinomialmente que decide uma linguagem L com probabilidade de aceitação p, para um valor p qualquer em (0, 1], é possı́vel obter uma MTP limitada polinomialmente que decide L com 77 probabilidade de aceitação 0,5. De fato, se p ≥ 0,5, não há nada a fazer. Se p < 0,5, executa-se k vezes, com k = d−1/ log pe, a máquina original e aceita-se a palavra se pelo menos uma vez a máquina original a aceitou. Do contrário, rejeita-se a palavra. Esse procedimento aumenta a probabilidade de aceitação para pelo menos 0,5. O uso da repetição da execução das máquinas de Turing Monte-Carlo limitadas polinomialmente é bastante útil, pois pode deixar a probabilidade de falsas rejeições arbitrariamente pequena. Por isso, esse recurso é bastante utilizado na prática, mesmo quando as probabilidades de rejeição incorreta são pequenas (menores que 0,5). A classe coRP, das linguagens cujo complemento está em RP, pode também ser vista como a classe das linguagens L para as quais existe uma MTP M limitada polinomialmente com as seguintes propriedades: 1. Se uma palavra x dada na entrada não está na linguagem L, então a máquina M rejeita x com probabilidade maior ou igual a 0,5. 2. Se uma palavra x dada na entrada está na linguagem L, então a máquina M nunca rejeita a palavra x. As definições deixam claro o caráter complementar das duas classes. Enquanto as linguagens que estão em RP admitem máquinas que fazem rejeições incorretas, as linguagens de coRP admitem máquinas que fazem aceitações incorretas. A classe RP claramente está contida em NP. Basta notar que uma máquina de Turing Monte-Carlo para uma linguagem L é uma máquina de Turing nãodeterminı́stica que decide L (existe pelo menos uma computação dessa máquina que aceita cada palavra que está em L e todas as computações rejeitam palavras que não estão em L). Um argumento análogo mostra que a classe coRP está contida na classe coNP. Também é claro que P está contida nessas duas classes, pois uma MTD é um caso especial de uma máquina de Turing Monte-Carlo, onde as palavras sempre são aceitas e rejeitadas corretamente. As classes ZPP e BPP Na última seção, vimos classes de linguagens que são decididas por MTPs limitadas polinomialmente que podem ou aceitar ou rejeitar erroneamente uma determinada palavra. Agora, vamos definir uma classe de linguagens que exige das máquinas que as respostas sejam corretas, mas que abre mão da certeza da polinomialidade 78 na execução. Para que uma linguagem L pertença à classe ZPP (zero-error probability polynomial-time), deve existir uma máquina de Turing probabilı́stica M que sempre aceita palavras que pertencem a L e sempre rejeita palavras que não pertencem a L, e cujo tempo esperado de execução para qualquer entrada é polinomial. Pela definição, podemos perceber que a classe ZPP é muito parecida com a classe P, diferindo apenas no fato de que as máquinas utilizadas podem consumir tempo superpolinomial em algumas computações. Outra definição possı́vel é a seguinte: ZPP é a classe das linguagens que pertencem tanto a RP como a coRP. Se uma linguagem está tanto em RP como em coRP, executa-se de maneira alternada cada uma das máquinas envolvidas até que uma delas obtenha uma resposta certamente correta. O número de passos desse algoritmo é indeterminado (não há sequer garantias de que ele vai parar em algum momento), mas a esperança do número de passos é um valor polinomial no tamanho da entrada, pois a probabilidade de obtenção de respostas erradas diminui exponencialmente a cada execução das máquinas. Outra classe de complexidade importante, que também pode ser relacionada com as demais classes probabilı́sticas já citadas, é a classe BPP (boundederror probabilistic polynomial-time), que contém as linguagens para as quais existem máquinas de Turing que devolvem respostas erradas (tanto rejeições como aceitações) com probabilidade estritamente menor que 0,5. Na verdade, qualquer delimitação da probabilidade no intervalo (0; 0,5) resultaria na mesma classe. Por outro lado, Papadimitriou [Pap94] mostrou que delimitações maiores ou iguais a 0,5 podem levar a uma classe diferente. A definição dessa classe é simétrica, pois rejeição e aceitação devem ser feitas corretamente na maioria absoluta das computações feitas por essas máquinas. Assim, utilizando um argumento análogo ao do resultado P = coP, obtemos que BPP = coBPP. Além disso, é fácil ver que RP ⊆ BPP. Dadas uma linguagem L em RP e uma máquina M associada, basta executar M com a entrada desejada duas vezes para que a probabilidade de falsa rejeição seja de no máximo 0,25. Como a probabilidade de falsa aceitação é zero, as condições necessárias para que L pertença a BPP estão satisfeitas. O argumento que mostra que coRP ⊆ BPP é análogo. Por fim, vale destacar que não sabemos ainda se a classe BPP está contida na classe NP. 79 6.2 Classes quânticas de complexidade Vamos agora apresentar as duas principais classes quânticas de complexidade e demonstrar alguns resultados que as relacionam com as classes clássicas. 6.3 Recursos e linguagens no modelo quântico Durante as discussões sobre o modelo clássico de computação, fizemos considerações sobre o consumo de tempo e de espaço pelas máquinas de Turing determinı́sticas, não-determinı́sticas e probabilı́sticas. O tempo consumido por uma MTQ com entrada x é o número de passos que a máquina efetua até terminar a execução. Essa definição é consistente, porque exigimos que, quando uma configuração da superposição atinge um estado final, todas as demais configurações também o fazem. O espaço consumido por uma MTQ M com entrada x é definido de maneira análoga ao espaço consumido por uma MTND. Dentre todas as configurações que durante a execução de M tiveram amplitude não-nula, seja c aquela com o maior número possı́vel de células em que M escreveu algo. O número de células utilizadas em c é o espaço consumido por M com a entrada x. No contexto de linguagens, estamos interessados em MTQs que, para cada entrada x, têm saı́da ou x1 ou x0 (MTQs devem ser reversı́veis, por isso a resposta usualmente binária é precedida pela entrada). Diz-se que uma MTQ M desse tipo decide de maneira exata uma linguagem L se, para todo x em L, a máquina M produz como saı́da x1, e, para todo x fora de L, a máquina M tem como saı́da x0. Por fim, para um número p entre 0 e 1, diz-se que uma MTQ M decide L com probabilidade p se M , com entrada x em L, produz x1 com probabilidade pelo menos p e, com entrada x fora de L, produz x0 com probabilidade pelo menos p. 6.4 As classes EQP e BQP As duas classes de complexidade que iremos introduzir aqui foram propostas por Bernstein e Vazirani [BV97]. A classe EQP é o conjunto das linguagens que são decididas de maneira exata por uma MTQ que consome tempo polinomial no tamanho da entrada. Essa classe corresponde à classe P do modelo clássico. A classe BQP é o conjunto das linguagens para as quais existem máquinas 80 de Turing quânticas que devolvem respostas erradas (tanto rejeições como aceitações) com probabilidade estritamente menor que 0,5. A classe correspondente no modelo clássico é BPP, e assim como no caso dela, a probabilidade de erro pode ser qualquer valor no intervalo (0; 0,5). A seguir, vamos mostrar algumas relações envolvendo essas classes e as classes tradicionais de complexidade. 6.5 Relações envolvendo as classes quânticas Inicialmente, vamos mostrar que P ⊆ EQP e que BPP ⊆ BQP, pois as demonstrações e as idéias envolvidas são mais simples. Em seguida, mostraremos que BQP ⊆ PSPACE. Seguem abaixo demonstrações breves das duas primeiras relações, apresentadas no artigo de Bernstein e Vazirani [BV97]. Teorema 6.1. P ⊆ EQP. Demonstração. Seja L uma linguagem que pertence à classe P. É fácil ver que existe uma MTD limitada polinomialmente que, para cada entrada x, produz como saı́da x1 se x ∈ L e x0 caso contrário. Para toda MTD polinomialmente limitada, existe uma MTD reversı́vel equivalente, que também é limitada polinomialmente. Para obtê-la, modifica-se a máquina original de modo que cada um de seus estados só possa ser atingido por movimentos da cabeça de leitura em uma única direção (as transições cujas triplas têm o mesmo estado devem fazer o mesmo deslocamento da cabeça de leitura da máquina). Isso pode ser feito por meio da duplicação dos estados da máquina. Desse modo, a função de transição torna-se bijetora quando a direção é ignorada, e a partir de uma configuração arbitrária da máquina, é possı́vel deduzir a configuração “anterior”. Ou seja, a máquina é reversı́vel. Além disso, o número de passos executados pela máquina até que ela pare é o mesmo da máquina original. Mas se uma MTD é reversı́vel, então essa máquina é uma MTQ onde cada superposição de configurações contém apenas uma configuração com amplitude não-nula. Logo, existe uma MTQ limitada polinomialmente que, para cada entrada x, devolve x1 como resposta sempre que x está em L, e devolve x0 sempre que x está fora de L. Então, L é decidida de maneira exata por uma MTQ, e portanto pertence a EQP. Concluı́mos assim que P ⊆ EQP. A demonstração a seguir mostra como uma MTQ engloba naturalmente um gerador de números aleatórios. 81 Teorema 6.2. BPP ⊆ BQP. Demonstração. Sejam L uma linguagem em BPP e M uma MTP para L dada pela definição de BPP. Para mostrar que L ∈ BQP, vamos descrever uma MTQ que simula M com um aumento apenas polinomial no consumo de tempo. Para simplificar, vamos assumir que M tem k opções de transição em cada um de seus passos, para algum k fixo. Se numa simulação de M por uma MTQ M 0 conseguimos, a cada passo, escolher aleatoriamente um sı́mbolo do alfabeto {1, . . . , k}, então M pode ser simulada por M 0 . Cada sı́mbolo do alfabeto é usado para definir qual transição se aplica no passo que está sendo simulado de M . Esses sı́mbolos podem ser gerados da seguinte maneira. A cada passo, se o estado atual não é final, a cabeça de leitura desloca-se para √ uma determinada posição da fita e escreve-se o sı́mbolo j com amplitude 1/ k, para j = 1, . . . , k, em uma única transição, que representa um sorteio aleatório. Feito isso, o conteúdo da célula é lido, a cabeça retorna para a posição original da fita e a transição representada pelo sı́mbolo lido é realizada. A célula utilizada no sorteio deve ser tal que não haja interferência no resto da fita. Como M é polinomialmente limitada, existem números c e e tais que qualquer computação de M não consome mais do que cne passos. Assim, basta inserir os caracteres dos sorteios seqüencialmente, começando na (cne+1 )-ésima célula da fita. √ k, então cada Como cada transição do passo de sorteio tem amplitude 1/ √ configuração no final terá amplitude (1/ k)t , onde t é o número de passos de M , lembrando que não ocorrerá interferência entre as configurações geradas. Logo, com a medição, a probabilidade de obtenção de um determinado resultado em M 0 será igual à da obtenção do mesmo resultado em M . Como M pode ser simulada por M 0 , a linguagem L pode ser decidida com a mesma probabilidade p > 0,5 por uma MTQ limitada polinomialmente. Logo, L ∈ BQP, e portanto temos que BPP ⊆ BQP. As duas provas mostradas acima servem para reforçar idéias que devem ser intuitivas após a leitura das definições envolvidas. Nosso objetivo agora é mostrar uma relação menos imediata e mais importante, que envolve o consumo de espaço na simulação de uma MTQ por uma MTD. Quando falamos em simulação de uma MTQ por uma MTD, estamos nos referindo a uma simulação onde queremos saber a probabilidade de cada saı́da possı́vel ser produzida. Não conhecemos nenhuma simulação de uma MTQ por uma MTD que consuma tempo polinomial no tempo consumido pela MTQ, porém o teorema abaixo mostra que é possı́vel fazer uma simulação utilizando espaço polinomial no espaço consumido pela MTQ. Nesse texto, mostraremos 82 apenas as linhas gerais da prova desse teorema. Teorema 6.3. BQP ⊆ PSPACE. Demonstração. Seja L ∈ BQP e M := (Q, Σ, α, s, H) uma MTQ polinomialmente limitada que decide L com probabilidade p maior que 0,5. Vamos descrever uma MTD M 0 que decide L em espaço polinomial no tempo consumido por M . A máquina M 0 calcula, para cada entrada x, a probabilidade px de M aceitar x (ou seja, de M produzir x1 como saı́da). No final, M 0 aceita ou rejeita x de acordo com o valor de px . Dizemos que uma configuração (w1 , q, w2 ) tem tamanho k se a cadeia de caracteres w1 w2 tem k caracteres. Dadas duas configurações c1 e c2 , denotamos por α(c1 , c2 ) o valor da amplitude correspondente à transição de M que leva c1 a c2 . Se não há nenhuma transição que leva c1 a c2 , então α(c1 , c2 ) = 0. Seja c0 := (B, s, x) a configuração inicial. A máquina M 0 , para cada inteiro t a partir de |x|, simula t passos de M e calcula a probabilidade px de M produzir, em t passos, a saı́da x1. Essa probabilidade é dada por 2 X Y px = α(ci−1 , ci ) , c1 ,...,ct i onde o somatório é sobre todas as configurações c1 , . . . , ct de tamanho no máximo t onde ct = (B, h, x1 ), para algum h em H. Note que o número de termos no somatório é no máximo T = t|Σ|2t |Q|. A máquina M 0 deve portanto calcular o somatório descrito acima. O primeiro problema que aparece é a incapacidade de M 0 fazer cálculos com números irracionais. MTDs só podem armazenar valores inteiros limitados, enquanto que cada α(ci−1 , ci ) pode nem mesmo ser racional. Logo, a simulação será uma aproximação, que deverá ter um erro tolerável. Por fim, vale destacar que cada um dos no máximo T termos do somatório terá t fatores. Se cada α(ci−1 , ci ) for representado com m bits tanto na parte inteira como na parte imaginária dos números, onde m é grande comparado a log T , o erro será pequeno (da ordem de 2−m ). Assim, a primeira dificuldade já foi eliminada. O que M 0 deve fazer é computar cada termo do somatório e guardar a soma dos termos. Como cada operação de adição usa pouco espaço auxiliar (ou seja, consome espaço polinomial em m) e só é necessário guardar a cada operação a soma atual, podemos garantir que o espaço necessário para efetuar o somatório é polinomial. No caso dos produtos, os mesmos comentários se aplicam. O que resta considerar agora é a obtenção de cada α(ci−1 , ci ). É fácil, em tempo polinomial nos comprimentos de ci−1 e ci , detectar se ci pode ou 83 não ser derivada de ci−1 em um passo. Se não pode, então α(ci−1 , ci ) = 0. Se pode, então ao mesmo tempo pode-se determinar a transição (q1 , σ1 , q, σ, d) em Q × Σ × Q × Σ × {←, ↓, →} que, quando aplicada a ci−1 , leva a ci . A máquina M 0 então aciona uma “subrotina” que recebe um número m e devolve, em espaço polinomial em m, o valor de α(q1 , σ1 , q, σ, d) com precisão 2−m . O valor devolvido pela subrotina é a aproximação desejada de α(ci−1 , ci ). Mostrar que de fato há uma MTD que efetua tal subrotina e consome espaço polinomial em m não é tarefa trivial e envolve uma série de etapas. Omitiremos essa prova nesse texto. É importante notar que o número de tais subrotinas não depende da entrada, mas apenas da máquina M . Assim M 0 está bem definida, desde que existam MTDs que executem tais subrotinas. Mais do que isso, cada etapa que M 0 executa consome espaço polinomial (assumindo que as subrotinas consumam espaço polinomial), portanto de fato BQP ⊆ PSPACE. Dos resultados acima, temos que BPP ⊆ BQP ⊆ PSPACE. Assim, não é possı́vel mostrar que BPP 6= BQP sem resolver a clássica questão de se P está propriamente contido em PSPACE ou não. Por outro lado, no mesmo artigo, Bernstein e Vazirani [BV97] mostram um oráculo em relação ao qual BPP 6= BQP. Outros resultados nessa linha, porém direcionados à questão “P 6= NP?”, foram provados por Bennet et al. [BBBV97]. Por exemplo, Bennet et al. mostraram que, em relação a um oráculo, NP 6⊆ BQP. 84 Parte III Apêndices 85 Apêndice A Espaços de Hilbert Os espaços de Hilbert fornecem o formalismo apropriado para o estudo de conceitos da mecânica quântica e, portanto, da computação quântica. Neste capı́tulo definimos espaços de Hilbert, estabelecemos nossas notações e listamos algumas propriedades importantes. A.1 Espaços norma vetoriais, produto interno e Definição A.1. Um espaço vetorial S, com um conjunto H sobre K, é uma álgebra S = hH, +, −1 , 0, K, +f , ×f , 0, 1, ·i tal que hH, +, −1 , 0i é um grupo comutativo, K = hK, +f , ×f , 0, 1i é um corpo, e · : K × H −→ H é uma multiplicação escalar satisfazendo os seguintes axiomas para quaisquer a, b ∈ K e quaisquer φ, ψ ∈ H: • a · (φ + ψ) = a · φ + a · ψ, • a · (b · φ) = (a ×f b) · φ (a +f b) · φ = a · φ + b · φ • 1 · φ = φ. Feita esta definição, a partir de agora não faremos mais distinção entre os operadores + e +f , · e ×f , exceto quando necessário. Além disso, escreveremos φ − ψ no lugar de φ + ψ −1 . Definição A.2. Um espaço com produto interno complexo H é um espaço vetorial com um conjunto H sobre o corpo dos números complexos, munido de um produto interno h·|·i : H ×H −→ C satisfazendo os seguintes axiomas. Para quaisquer φ, φ0 , ψ ∈ H e quaisquer a, b ∈ C: 86 • hψ|φi = hφ|ψi∗ • hψ|ψi ≥ 0, com hψ|ψi = 0 se, e somente se, ψ = 0 • hψ|aφ + bφ0 i = ahψ|φi + bhψ|φ0 i. Definição A.3. Sejam S um espaço com p produto interno complexo e φ, ψ ∈ S. A norma de φ é definida por kφk := hφ|φi. A distância entre os vetores φ e ψ é dada por dist(φ, ψ) := kφ − ψk. Se tivermos H = C n e o produto interno definido como n X (x1 , . . . , xn ) (y1 , . . . , yn ) = x∗i yi , i=1 então falamos sobre o espaço com produto interno complexo n-dimensional. Neste texto adotamos a notação de Dirac, de modo que nos referimos a um elemento ψ de um espaço com produto interno complexo por |ψi, que é chamado um vetor ket. Como pode ser visto no restante do texto e deste capı́tulos, tal notação é bastante conveniente. Considere um espaço com produto interno complexo H. Para quaisquer vetores φ, ψ ∈ H e qualquer c ∈ C, valem as seguintes propriedades: (a) hcφ|ψi = c∗ hφ|ψi (b) kcφk = |c| kφk (c) |hφ|ψi| ≤ kφkkψk (desigualdade de Cauchy-Schwarz) (d) kφ + ψk ≤ kφk + kψk (desigualdade triangular) (e) kφ + ψk2 + kφ − ψk2 = 2kφk2 + 2kψk2 (lei do paralelogramo) Demonstração. (a) Utilizando os axiomas do produto interno, temos: ∗ hcφ|ψi = hψ|cφi∗ = chψ|φi = c∗ hψ|φi∗ = c∗ hφ|ψi. (b) Utilizando a propriedade (a) provada acima, temos: p p √ p kcφk = hcφ|cφi = c∗ chφ|φi = c∗ c hφ|φi = |c| kφk. 87 (c) Caso hφ|ψi = 0, a desigualdade se reduz a 0 ≤ kφkkψk e é trivialmente satisfeita. Senão, hφ|ψi = 6 0 e podemos assumir, sem perda de generalidade, que ψ 6= 0. Suponha então que ψ 6= 0 e hφ|ψi = 6 0. Para qualquer c ∈ C, temos hφ + cψ|φ + cψi ≥ 0. Expandindo essa expressão, temos hφ|φi+(chφ|ψi)∗ +chφ|ψi+c∗ chψ|ψi ≥ 0. Em particular, tome hφ|ψi∗ , com λ = λ∗ . c=λ |hφ|ψi| Então teremos λ2 hψ|ψi + 2λ|hφ|ψi| + hφ|φi ≥ 0. Como ψ 6= 0, g(λ) = λ2 hψ|ψi + 2λ|hφ|ψi| + hφ|φi é um trinômio do segundo grau em λ. Além disso, sabemos que g(λ) ≥ 0, e portanto seu discriminante deve ser não-positivo. Assim, |hφ|ψi| − hφ|φihψ|ψi ≤ 0, e a desigualdade de Cauchy-Schwarz segue imediatamente. (d) O resultado segue da desigualdade de Cauchy-Schwarz. Abaixo denotamos a parte real de um número complexo c por Re(c): kφ + ψk2 = = = ≤ hφ + ψ|φ + ψi hφ|φi + hφ|ψi + hψ|φi + hψ|ψi hφ|φi + 2 Re(hφ|ψi) + hψ|ψi hφ|φi + 2Re(hφ|ψi) + hψ|ψi ≤ kφk2 + 2kφkkψk + kψk2 , por (c) 2 = kφk + kψk . (e) Segue diretamente da expansão da norma, de acordo com a definição. Definição A.4. Dada uma seqüência infinita φ1 , φ2 , . . . ∈ H, onde H é um espaço com produto interno complexo, dizemos que ela converge para φ ∈ H se, para qualquer > 0, existir um número N () tal que kφi − φk < para todo i > N (). Além disso, tal seqüência infinita é chamada de seqüência de Cauchy se, para qualquer > 0, existir um número M () tal que kφi −φj k < para quaisquer i, j > M (). Se toda seqüência de Cauchy em H converge, dizemos que H é completo. Definição A.5. Um espaço de Hilbert é um espaço completo com produto interno complexo. 88 Não vamos nos deter nos detalhes topológicos, que são desnecessários aqui. Também não vamos definir independência linear, bases, conjuntos geradores e dimensão, pois esses conceitos já devem ser bem conhecidos. A partir de agora vamos nos referir sempre a H como um espaço de Hilbert. A.2 Espaço de Hilbert conjugado Definição A.6. Uma função f : H −→ C é dita linear se f (aφ + bψ) = af (φ) + bf (ψ), para quaisquer φ, ψ ∈ H e quaisquer a, b ∈ C. Dizemos também que f é um funcional. É possı́vel provar que para todo funcional f existe um único φf ∈ H tal que f (ψ) = hφf |ψi para todo ψ ∈ H. O conjunto de todos os funcionais de um espaço de Hilbert H é também um espaço de Hilbert (se definirmos a adição e a multiplicação da maneira usual). Tal espaço é denominado dual do espaço de Hilbert H ou espaço de Hilbert conjugado, denotado por H ∗ , com produto interno hf |gi = hφf |φg i para todo f, g ∈ H ∗ . Desta forma, estabelece-se uma bijeção entre H e H ∗ e portanto todo espaço de Hilbert é isomorfo ao seu dual. Dado um elemento φ ∈ H, ou |φi como vetor ket na notação de Dirac, o funcional correspondente é denotado por hφ|, denominado vetor bra. Para qualquer ψ ∈ H, temos hφ| |ψi = hφ|ψi. Se estivermos falando de um espaço de Hilbert n-dimensional, podemos pensar em |φi como um vetor coluna de dimensão n e hφ| como um vetor linha de mesma dimensão. Neste caso, a transformação |φi ↔ hφ| corresponde a uma transposição e conjugação. O produto externo |φihψ| equivale portanto a uma matriz de dimensão n, utilizando-se a definição usual de multiplicação de matrizes. O mesmo se aplica ao cálculo do produto interno. A.3 Bases ortonormais A ortogonalidade é um conceito de extrema importância para a computação quântica. Numa medição, só é possı́vel distingüir estados quânticos mutuamente ortogonais. Definição A.7. Dois vetores não-nulos φ, ψ ∈ H são ortogonais, o que se denota por φ ⊥ ψ, se hφ|ψi = 0. Um conjunto S ⊆ H é ortogonal se cada par de elementos distintos do conjunto forem ortogonais. Um conjunto ortogonal é chamado ortonormal se todos seus elementos têm norma 1. 89 Proposição A.8. Seja B ⊆ H um conjunto ortogonal com n elementos. Então os vetores de B são linearmente independentes. Demonstração. Seja B = {φ1 , . . . , φn }. Vamos provar que a única solução para a1 φ1 + . . . + an φn = 0 é a trivial, com ai = 0 para todo 1 ≤ i ≤ n, e portanto os vetores φ1 , . . . , φn são linearmente independentes. Dado i, temos que hφi |a1 φ1 + · · ·P + an φn i = hφi | 0i = 0. Porém, temos também que hφi |a1 φ1 + · · · + an φn i = nj=1 aj hφi |φj i = 0. Como B é ortogonal, hφi |φj i = 0 se i 6= j e portanto a soma anterior é simplificada para ai hφi |φi i = 0. Como hφi |φi i = 6 0, devemos ter ai = 0. Como i foi escolhido arbitrariamente, temos que ai = 0 para 1 ≤ i ≤ n e portanto os vetores de B são linearmente independentes. Definição A.9. Um conjunto ortonormal B ⊆ H é uma base ortonormal de H se todo vetor v ∈ H pode ser escrito como X aφ φ, v= φ ∈B com aφ ∈ C para todo φ ∈ B. Definição A.10. Seja B = {φi }ni=1 uma base para um espaço de Hilbert H e ψ ∈ H um vetor. Então ψ pode ser escrito como combinação linear dos elementos de B: ψ = a1 φ1 +· · ·+an φn . Chamamos (a1 , . . . , an ) a representação de ψ na base B. Pode-se provar que quaisquer espaços de Hilbert H1 e H2 de mesma dimensão são isomorfos. Assim, denotaremos um espaço de Hilbert d-dimensional por Hd . Dada uma base ortonormal B de um espaço de Hilbert H, é fácil verificar as seguintes propriedades, para quaisquer φ, ψ ∈ H: 1. |φi = P γ∈B hγ|φi|γi 2. Se hφ|γi = 0 para todo γ ∈ B, então φ = 0. P 3. hφ|ψi = γ∈B hφ|γihγ|ψi 4. kψk2 = P γ∈B hγ|ψi2 (identidade de Parseval) Vamos provar apenas o primeiro item. Todos os outros seguem imediatamente deste. 90 Demonstração. P Como B = {γ1 , . . . , γn } é uma base, existem a1 , . . . , an ∈ C tais que |φi = ni=1 ai |γi i. Dado i, temos que hγi |φi = n X ai hγi |γj i = ai hγi |γi i = ai · 1 = ai . j=1 Dado um subespaço W de um espaço de Hilbert H, existe um único subespaço W ⊥ de H tal que todo vetor de W é ortogonal a todo vetor de W ⊥ . Além disso, todo vetor ψ ∈ H pode ser escrito de forma única como ψ = φ1 + φ2 , com φ1 ∈ W e φ2 ∈ W ⊥ . Nesse caso dizemos que H é a soma direta de W e W ⊥ e denotamos por H = W ⊕ W ⊥ . Dizemos também que W e W ⊥ formam uma decomposição ortogonal de H. Podemos generalizar essa decomposição em subespaços ortogonais. Assim, H = W1 ⊕ · · · ⊕ Wn , onde hφi |φj i = 0 sempre que φi ∈ Wi e φj ∈ Wj , com i 6= j, onde Wi , 1 ≤ i ≤ n, são subespaços de H. Segue também que todo ψ ∈ H pode ser escrito de forma única como ψ = φ1 + · · · + φn com φi ∈ Wi , 1 ≤ i ≤ n. A.4 Operadores lineares Definição A.11. Um operador linear sobre um espaço de Hilbert H é uma função linear A : H −→ H. A aplicação de um operador linear A em um vetor |ψi é denotada por A|ψi. Além disso, A também é um operador linear de H ∗ , levando hφ| a hφ|A. Quando hφ|A é aplicado a algum vetor ψ, primeiro realiza-se a aplicação de A sobre ψ para depois aplicar hφ|. Um operador linear A é chamado positivo ou semi-definido, denotado por A ≥ 0, se, para qualquer |ψi ∈ H, tivermos hψ|Aψi ≥ 0. Fixada uma base enumerável B = |θi i : i ∈ I de H, qualquer operador linear A pode ser representado por uma matriz, indexada por elementos de I, tendo, como entrada (i, j), o valor hθi |Aθj i. Essa matriz é identificada com o próprio operador A e denotada da mesma forma, quando não houver perigo de confusões por conta de bases diferentes. Definição A.12. A norma kAk de um operador linear A é supkφk=1 kAφk. Um operador linear A é dito limitado se kAk < ∞. 91 Uma classe de operadores lineares de extrema importância são os projetores. Como foi visto anteriormente, se tivermos uma decomposição ortogonal de H em W1 e W2 , então todo vetor de ψ ∈ H tem uma representação única ψ = ψ1 + ψ2 , com ψi ∈ Wi , i = 1, 2. Os vetores ψ1 e ψ2 são as projeções de ψ nos subespaços W1 e W2 , respectivamente. Neste caso, o operador PWi que leva ψ a ψi é chamado projetor sobre o subespaço Wi . Se um subespaço é gerado apenas por um vetor φ, kφk = 1, escrevemos Pφ . Pode-se provar que Pφ = |φihφ|. Veja [TI97]. Também não é difı́cil provar que todo projetor é idempotente, ou seja, que 2 P = P. Definição A.13. O adjunto T ∗ de um operador linear T limitado é um operador tal que, para quaisquer φ, ψ ∈ H, hψ|T φi = hT ∗ ψ|φi. Um operador T tal que T ∗ = T é denominado auto-adjunto. Normalmente utilizaremos a notação hψ|T |φi, ao invés de hψ|T φi, de modo que hT ∗ ψ|φi = hψ|T |φi = hψ|T φi. Se tomarmos a matriz A correspondente ao operador linear T em relação a uma base qualquer, a matriz correspondente a T ∗ é simplesmente A∗ , a conjugada transposta de A. Uma matriz A é hermitiana se A = A∗ . A cada operador auto-adjunto T corresponde uma matriz hermitiana A. A.5 Autovalores, autovetores e representação espectral Definição A.14. Dado um operador A sobre o espaço de Hilbert Hn , λ ∈ C e φ ∈ Hn , se Aφ = λφ, então φ é um autovetor de A e λ é o autovalor associado a φ. O espectro de A é o conjunto de todos seus autovalores. Para um dado operador A, se tivermos Aφ = λφ, λ ∈ C, então A(cφ) = c(Aφ) = cλφ = λ(cφ) pela linearidade de A. Logo cφ também é um autovetor de A. Se Aφ1 = λφ1 e Aφ2 = λφ2 , com φ1 6= φ2 , segue da mesma forma que A(φ1 + φ2 ) = λ(φ1 + φ2 ), de modo que φ1 + φ2 também é autovetor de A. Como A · 0 = λ · 0, temos que o conjunto de todos os autovetores associados a λ é um subespaço de H, chamado de autoespaço de H e denotado por Hλ . Se os autovalores distintos de uma matriz Pmhermitiana A são λ1 , . . . , λm e a dimensão do autoespaço Hλi é m(i), então i=1 m(i) = n, ou seja, o subespaço gerado por todos os autovetores tem dimensão n. 92 Proposição A.15. O determinante de uma matriz é igual ao produto de seus autovalores. Além disso, o traço (soma dos elementos da diagonal) de uma matriz A, denotado por Tr(A), é igual à soma dos autovalores de A. A prova deste resultado pode ser vista em [TI97]. Proposição A.16. Todos os autovalores de uma matriz hermitiana A são reais. Além disso, autovetores de A correspondendo a autovalores diferentes são ortogonais. Demonstração. Seja φ um autovetor de A correspondendo ao autovalor λ. Temos então λhφ|φi = hφ|λφi = hφ|Aφi = hA∗ φ|φi = hAφ|φi = hλφ|φi = λ∗ hφ|φi. Como φ 6= 0, temos λ = λ∗ e assim λ ∈ R. Considere agora φ1 , φ2 dois autovetores de A, correspondentes aos autovalores λ1 , λ2 ∈ R, respectivamente, com λ1 6= λ2 . Temos então λ1 hφ1 |φ2 i = hλ1 φ1 |φ2 i = hAφ1 |φ2 i = hA∗ φ1 |φ2 i = hφ1 |Aφ2 i = hφ1 |λ2 φ2 i = λ2 hφ1 |φ2 i. Como λ1 6= λ2 , teremos necessariamente φ1 ⊥ φ2 . Considere um espaço de Hilbert Hn e uma matriz hermitiana A de dimensão n com autovalores λ1 , . . . , λm e respectivos autoespaços Hλ1 , . . . , Hλm . Existe uma base ortonormal Bλi para cada autoespaço Hλi , 1 ≤ i ≤ m. Então B = ∪m i=1 Bλi é uma base ortonormal de H, pelos resultados apresentados acima. Teorema A.17 (Representação Espectral). Seja A uma matriz hermitiana e λ1 , . . . , λk seus autovalores distintos. Então A= k X λi Pi , i=1 onde Pi é o projetor sobre o autoespaço correspondente a λi . Demonstração. Seja φ um vetor e considere φj = Pj φ, ou seja, φj é a projeção de φ sobre o autoespaço correspondente ao autovalor λj . Segue que P φ = kj=1 φj , pois os subespaços são ortogonais. Assim, ! k k k k X X X X Aφ = A φj = Aφj = λj φj = λ j Pj φ j=1 j=1 j=1 e isso completa a prova. 93 j=1 A.6 Produto tensorial Definição A.18. Sejam H1 , H2 espaços de Hilbert com respectivas bases ortonormais B1 = {|φ1 i, . . . , |φn i} e B2 = {|ψ1 i, . . . , |ψm i}. O produto tensorial de H1 e H2 , denotado por H1 ⊗H2 , é o espaço de Hilbert H gerado pelo conjunto n o B := B1 × B2 = |φi i, |ψj i : |φi i ∈ B1 , |ψj i ∈ B2 , e com produto interno entre |φi i, |ψj i e |φk i, |ψl i dado por hφi |φk ihψj |ψl i para quaisquer φi , φk ∈ B1 e ψj , ψl ∈ B2 . Da definição, os elementos de B são ortonormais, de forma que B, o conjunto gerador, é também uma base para H1 ⊗ H2 e, portanto, dim(H1 ⊗ H2 ) = dim H1 dim H2 . O produto interno entre quaisquer elementos de H1 ⊗ H2 é totalmente determinado pelo produto interno entre os elementos dessa base, que foi definido acima. Definição A.19. Sejam H P1m, H2 e B1 , B2 como na definição acima, φ = Pn j=1 dj |ψj i ∈ H2 . Definimos o produto tensorial i=1 ci |φi i ∈ H1 e ψ = de |φi e |ψi, pertencente a H1 ⊗ H2 , por |φi ⊗ |ψi := n X m X ci dj |φi i, |ψj i . i=1 j=1 Algumas vezes será mais conveniente escrevermos |φi|ψi ou |φψi ou |φ, ψi no lugar de |φi ⊗ |ψi, para |φi ∈ H1 e |ψi ∈ H2 , Como observado acima, o produto interno entre os elementos de B1 e B2 determina o produto interno entre quaisquer elementos de H1 ⊗H2 . Em particular, pode-se provar facilmente que o produto interno entre |φi ⊗ |ψi e |φ0 i ⊗ |ψ 0 i, isto é, hφ, ψ|φ0 , ψ 0 i, é dado por hφ|φ0 ihψ|ψ 0 i, para quaisquer |φi, |φ0 i ∈ H1 e |ψi, |ψ 0 i ∈ H2 . Seguem as seguintes propriedades do produto tensorial, para quaisquer vetores |φi ∈ H1 , |ψi ∈ H2 , |γi ∈ H3 e c ∈ C: 1. |φi ⊗ |ψi ⊗ |γi = |φi ⊗ |ψi ⊗ |γi (propriedade associativa) 2. c |φi ⊗ |ψi = c|φi ⊗ |ψi = |φi ⊗ c|ψi 3. |φi+|ψi ⊗|γi = |φi⊗|γi+|ψi⊗|γi (propriedade distributiva à esquerda) 4. |φi ⊗ |ψi + |γi = |φi ⊗ |ψi + |φi ⊗ |γi (propriedade distributiva à direita) 94 Sejam B1 , . . . , Bm bases ortonormais dos espaços de Hilbert H1 , . . . , Hm . Então o conjunto m O B1 ⊗ · · · ⊗ Bm = Bi = {φ1 ⊗ · · · ⊗ φm : φi ∈ Bi } i=1 é uma base para o espaço de Hilbert H1 ⊗ · · · ⊗ Hm = m O Hi . i=1 Exemplo 1.20 Considere o espaço de Hilbert bidimensional H2 com base B2 = {|0i, |1i}, onde 1 0 |0i := e |1i := . 0 1 Então o conjunto n O B2 = |x1 i ⊗ · · · ⊗ |xn i : x1 · · · xn ∈ {0, 1}n i=1 é uma base ortogonal do espaço de Hilbert n O H2n := H2 , i=1 n de dimensão 2 . Vamos estender o produto tensorial para as matrizes, correspondentes a operadores lineares. Considere as matrizes b11 · · · b1m a11 · · · a1n .. e B = .. .. . .. .. A = ... . . . . . an1 · · · ann bm1 · · · bmm O produto tensorial de A e B, denotado por A ⊗ B, é definido por a11 B · · · a1n B .. . ... A ⊗ B := ... . an1 B · · · ann B Seguem as seguintes propriedades: 1. (A ⊗ B) |φi ⊗ |ψi = A|φi ⊗ B|ψi 2. (A ⊗ B)(C ⊗ D) = AC ⊗ BD 3. (A ⊗ B)∗ = A∗ ⊗ B ∗ . 95 Apêndice B Mecânica quântica A seguir relacionamos os conceitos de espaços de Hilbert, vistos no capı́tulo anterior, com seus equivalentes na mecânica quântica. B.1 Axiomas Um sistema quântico é representado por um espaço de Hilbert H com a dimensão escolhida apropriadamente. Para nós, esta dimensão sempre será finita. Se tivermos dois sistemas quânticos com seus correspondentes espaços de Hilbert H1 e H2 , então o espaço de Hilbert correspondente à composição destes sistemas será H := H1 ⊗ H2 . B.1.1 Estados quânticos Antes de definirmos estados quânticos, precisamos introduzir o conceito de raios. Considere a relação ∼R em H definida da seguinte maneira: dados |φi, |ψi ∈ H, dizemos que |φi ∼R |ψi se, e somente se, |φi = α|ψi para algum α ∈ C. É muito fácil ver que a relação ∼R é reflexiva, simétrica e transitiva, e é portanto uma relação de equivalência em H. Então a relação ∼R induz naturalmente uma partição de H em classes de equivalência. Um raio (ray) de H é uma classe de equivalência de H induzida pela relação ∼R . Em outras palavras, um raio é uma classe de equivalência de vetores de H que diferem por um fator multiplicativo complexo. Dado um sistema quântico representado pelo espaço de Hilbert H, um estado quântico deste sistema é um raio de H. Como um raio é uma classe de equivalência induzida pela relação ∼R , podemos convencionar que utilizaremos como representantes de cada classe um vetor de norma unitária. De acordo com 96 esta convenção, se |φi é um representante de uma classe, então |ψi = eiθ |φi, para qualquer θ ∈ R, também é um representante da mesma classe, ou seja, ambos constituem o mesmo estado quântico. Neste caso, identificamos |φi com |ψi, já que eles são fisicamente indistingüı́veis, e chamamos o fator eiθ de fator de fase global. Como cada raio corresponde a um estado quântico possı́vel, dados dois estados quânticos |φi e |ψi, ortogonais entre si, podemos formar um novo estado |γi = α|φi + β|ψi, onde α, β ∈ C e kαk2 + kβk2 = 1. O estado |γi é uma superposição dos estados |φi e |ψi. Retomando a discussão anterior, os vetores |γi e eiθ |γi representam o mesmo estado quântico. Já se formarmos o estado |ϕi = α|φi + eiθ β|ψi, com θ ∈ (0, 2π), não podemos identificar |γi com |ϕi. O fator eiθ é chamado de fator de fase relativa entre |γi e |ϕi e, diferente do fator de fase global, é importante fisicamente. Fixada uma base ortonormal B de H, chamamos de estados básicos de H os estados desta base. Todo estado |ψi em H pode ser escrito como uma superposição de estados básicos, ou seja, X |ψi = αφ |φi, |φi∈B onde αφ ∈ C para todo |φi ∈ B. O fator αφ é chamado de amplitude do estado básico |φi em |ψi. A evolução de um estado quântico em H durante um certo intervalo de tempo é determinada por uma matriz unitária em H. Uma matriz U é unitária se U ∗ = U −1 . Uma matriz que define uma possı́vel evolução em um sistema quântico será chamada de operador. B.1.2 Observáveis e medições Informalmente, um observável é uma propriedade de um sistema quântico que pode ser medida. Formalmente, definimos um observável como um operator auto-adjunto em H. De acordo com o teorema A.17 da representação espectral, todo observável O pode ser escrito como X O= λPλ , (B.1) λ∈Λ onde Λ é o espectro de O e, para λ ∈ Λ, Pλ é o projetor sobre Wλ , o autoespaço associado a λ. A proposição L A.16 nos garante que os autoespaços de O são ortogonais, de modo que H = λ∈Λ Wλ . Algumas vezes será mais conveniente representarmos um observável pelo seu conjunto de autoespaços. Nesta nova representação, o observável O seria dado por {Wλ : λ ∈ Λ}. 97 Na mecânica quântica, medições são fundamentalmente diferentes de medições na fı́sica clássica: uma medição altera irreversivelmente o estado quântico observado. Além disso, o resultado das medições é probabilı́stico. Medições são feitas relativas a algum observável. O resultado numérico de uma medição com relação a um observável O é um autovalor de O. Considere a representação espectral de O, dada em (B.1). Para qualquer autovalor λ de O, a probabilidade de obtenção de λ como resultado da medição de um estado 2 quântico |ψi é dada por Pλ |ψi = hψ|Pλ |ψi. Se λ é o resultado obtido, então o estado quântico (normalizado) do sistema imediatamente após a medição será Pλ |ψi p hψ|Pλ |ψi , onde o denominador é simplesmente um fator de normalização. Se uma medição relativa ao mesmo observável for repetida imediatamente após a primeira medição, então o resultado será o mesmo, com probabilidade 1. B.2 Experimento com polarização de fótons Vamos exemplificar um experimento simples para nos familiarizarmos com alguns fenômenos quânticos. Os equipamentos utilizados são uma fonte de luz, como laser, e três polaróides (filtros de polarização) A, B e C, onde A é polarizado horizontalmente, B a 45◦ e C verticalmente. Eles devem ser dispostos como indicado na Figura B.1 (inicialmente não utilizaremos B): Figura B.1: Disposição do equipamento. Um fóton pode estar polarizado verticalmente (representado por | ↑ i), horizontalmente (representado por | →i), ou numa superposição destes estados, ou seja, α | ↑ i+β | →i, com α, β ∈ C. Assumindo que a luz gerada é aleatoriamente polarizada, cerca de metade dos fótons emitidos serão polarizados horizontalmente por A e o atravessam. Note que A não deixa passar apenas os fótons 98 com α = 0 e β = 1, senão apenas uma fração mı́nima dos fótons atravessaria A, o que não é o caso. Os fótons polarizados horizontalmente não passam pelo filtro vertical C. Porém, se adicionarmos B entre A e C, observaremos que 1/8 dos fótons emitidos pela fonte atravessam C (veja a Figura B.2). Figura B.2: Nova disposição, utilizando o polaróide B. A mecânica quântica explica esse fenômeno do seguinte modo. Em A, ocorre uma medição do fóton, de acordo com o observável OA = {E1 , E2 }, onde E1 e E2 são gerados, respectivamente, por | ↑ i e por | →i. Após a medição de um fóton no estado de polarização α | ↑ i + β | →i, ele estará no estado | ↑ i com probabilidade |α|2 e no estado | →i com probabilidade |β|2 . Apenas estes últimos, projetados sobre E2 , atravessam A. Em C ocorre uma medição de acordo com o mesmo observável O, porém apenas os fótons projetados sobre E1 pela medição atravessam o polaróide. Se B não estiver entre A e C, todos os fótons chegando a C são da forma 0 | ↑ i+1 | →i e portanto não é possı́vel que nenhum deles o atravesse. Entretanto, caso B seja interposto entre A e C, ele realizará uma medição de acordo com o observável O = {E10 , E20 }, onde E10 e E20 são gerados respectivamente por | % i e por | & i, onde 1 | % i := √ | ↑ i + | →i 2 e 1 | & i := √ | ↑ i − | →i . 2 Com isso, metade dos fótons polarizados horizontalmente que atingem B é projetada sobre E10 e o atravessa, enquanto a outra metade é projetada sobre E20 e é absorvida ou refletida. Agora √ os fótons que chegam a C não terão mais α = 0 e β = 1, e sim α = β = 1/ 2. Desta forma, metade deles será projetada sobre E1 e atravessará C e a outra metade é absorvida ou refletida. Assim, cerca de 1/8 do total de fótons emitidos atravessa A, B e C, como observado experimentalmente. 99 Apêndice C Teoria dos números Fazemos uma breve revisão de alguns conceitos e resultados básicos de teoria dos números. A familiarização com os tópicos aqui cobertos é fundamental para a compreensão do algoritmo de Shor. Alguns resultados serão enunciados sem prova. O leitor interessado pode consultar o capı́tulo 31 do livro de Cormen et al. [CLRS01], o capı́tulo 4 do livro de Graham et al. [GKP94], os capı́tulos 10 e 11 do livro de Papadimitriou [Pap94], e os livros de Fraleigh [Fra89], Rosen [Ros00], Coutinho [Cou00] e Bressoud [Bre89]. C.1 Divisibilidade e primalidade A divisibilidade de um inteiro por outro é um conceito que permeia toda a teoria dos números. Definição C.1. Sejam n e d inteiros. Dizemos que d divide n se existe um inteiro k tal que n = kd, e denotamos isso por d | n. Neste caso, dizemos também que n é divisı́vel por d e que n é um múltiplo de d. Se d | n e d ≥ 0, então dizemos que d é um divisor de n. Se d não divide n, isso é denotado por d 6 | n. É claro que todo inteiro n é divisı́vel por 1 e n, que são chamados de divisores triviais de n. Um divisor não-trivial de n é chamado de fator de n. O seguinte resultado é imediato da definição de divisibilidade: Proposição C.2. Sejam d, a, b inteiros. Se d divide a e b, então d divide ax+by para quaisquer x, y ∈ Z. Também é claro que, se a divide b, então |a| ≤ |b|. Assim, a | b e b | a implicam que a = ±b. 100 Os inteiros não-negativos que não têm nenhum fator são extremamente importantes: Definição C.3. Seja n > 1 um inteiro. Dizemos que n é primo se os únicos divisores de n são 1 e n. Caso contrário, dizemos que n é composto. Observe que 1 não é nem primo nem composto. O seguinte fato é conhecido desde os tempos de Euclides: Teorema C.4. Há infinitos números primos. Demonstração. Suponha que Q o conjunto P dos números primos é finito. Considere o inteiro M := 1 + p∈P p, ou seja, M é o produto de todos os primos, somado com 1. É óbvio que M 6∈ P , de modo que M deve ser composto, ou seja, M tem um fator primo. Seja p um primo. É claro que p não divide M , pois p divide M −1. Então M não tem nenhum fator primo, um absurdo. Segue que existem infinitos números primos. A operação de divisão e módulo pode ser formalizada para os inteiros através do seguinte resultado: Teorema C.5 (Divisão). Sejam m ≥ 0 e n > 0 inteiros. Então existem inteiros q e r satisfazendo m = qn + r e 0 ≤ r < n, e tais inteiros são únicos. No teorema acima, o valor q é chamado de quociente da divisão de m por n e é denotado por bm/nc e o número r é o resto da divisão de m por n, denotado por m mod n. É óbvio que n divide m se, e somente se, m mod n = 0. Definição C.6. Dados inteiros a, b, d, dizemos que d é divisor comum de a e b se d é divisor de a e de b. Se a 6= 0 ou b 6= 0, então o maior dos divisores comuns de a e b é chamado de máximo divisor comum de a e b e é denotado por mdc(a, b). Se mdc(a, b) = 1, então dizemos que a e b são relativamente primos ou primos entre si. Provamos a seguir algumas propriedades importantes sobre divisores comuns. Teorema C.7. Sejam a, b inteiros, não ambos nulos. Então mdc(a, b) é o menor elemento positivo do conjunto {ax + by : x, y ∈ Z} de combinações lineares inteiras de a e b. 101 Demonstração. Seja d o menor elemento positivo de I := {ax + by : x, y ∈ Z} e sejam x, y ∈ Z tais que d = ax + by. Vamos mostrar que mdc(a, b) ≥ d. Pelo teorema C.5 da divisão, existem inteiros q e r satisfazendo a = qd + r e 0 ≤ r < d. Mas então r = a − qd = a − q(ax + by) = a(1 − qx) + b(−qy) também é uma combinação linear inteira de a e b. Como d é o menor elemento positivo de I e 0 ≤ r < d, então r = 0. Segue que d | a. Analogamente provamos que d | b. Portanto mdc(a, b) ≥ d, pois d é divisor comum de a e b. Agora mostramos que mdc(a, b) ≤ d, completando a prova. Pela proposição C.2, mdc(a, b) divide d = ax + by. Como d > 0, então mdc(a, b) ≤ d, como querı́amos. Corolário C.8. Sejam a e b inteiros, não ambos nulos. Se d é um divisor comum de a e b, então d | mdc(a, b). Demonstração. Pelo teorema C.7, existem inteiros x, y tais que mdc(a, b) = ax + by, ou seja, mdc(a, b) é uma combinação linear inteira de a e b. Mas d | a e d | b, de modo que d | mdc(a, b), pela proposição C.2. O seguinte resultado fornece imediatamente um algoritmo para o cálculo do máximo divisor comum, como veremos posteriormente. Teorema C.9 (Recursão de Euclides). Sejam a ≥ 0 e b > 0 inteiros. Então mdc(a, b) = mdc(b, a mod b). (C.1) Demonstração. Seja d := mdc(a, b) e sejam q := ba/bc e r := a mod b. Vamos mostrar que mdc(a, b) | mdc(b, r) e que mdc(b, r) | mdc(a, b), de onde seguirá o teorema. É claro que d | a e d | b. Como r = a−bq é uma combinação linear inteira de a e b, segue da proposição C.2 que d | r. Então d | b e d | r, ou seja, d é um divisor comum de b e r. Pelo corolário C.8, d | mdc(b, r), ou seja, mdc(a, b) | mdc(b, r). O outro lado é análogo, pois a = qb + r é uma combinação linear inteira de b e r. Proposição C.10. Sejam d, a e b inteiros positivos e suponha que d | ab. Se mdc(d, a) = 1, então d | b. Demonstração. Como mdc(d, a) = 1, o teorema C.7 nos garante que existem inteiros x, y tais que dx + ay = 1. Multiplicando esta equação por b, temos bdx + aby = b. É óbvio que d | bdx, a primeira parcela. Por hipótese, d | aby, a segunda parcela. Mas então d | b pela proposição C.2, como querı́amos. 102 O seguinte resultado segue imediatamente da proposição C.10 acima. Teorema C.11. Sejam p um primo e a, b inteiros. Se p | ab, então p | a ou p | b. O teorema C.11 pode ser utilizado para provar o seguinte resultado, conhecido como Teorema Fundamental da Aritmética: Teorema C.12 (Fatoração única). Seja n > 1 um inteiro. Então existe um único modo de escrever n na forma n = pe11 pe22 · · · pekk , (C.2) onde k ≥ 1, os inteiros p1 < p2 < · · · < pk são primos e ei > 0 para todo i. Na equação (C.2), o lado direito é chamado de fatoração de n em primos. C.2 Teoria dos grupos Definição C.13. Sejam G ⊆ G0 conjuntos e ∗ : G0 × G0 −→ G0 uma função. Um grupo (G, ∗) é um conjunto G munido de uma função ∗ satisfazendo os seguintes axiomas: 1. Fechamento: a ∗ b ∈ G para todo a, b ∈ G. 2. Associatividade: (a ∗ b) ∗ c = a ∗ (b ∗ c) para todos a, b, c ∈ G. 3. Existência de identidade: Existe e ∈ G tal que a ∗ e = e ∗ a = a para todo a ∈ G. Tal elemento e é chamado de elemento identidade do grupo (G, ∗). 4. Existência de inversos: Para todo a ∈ G, existe b ∈ G tal que a ∗ b = b ∗ a = e. Tal elemento b é chamado de inverso de a e é denotado por a−1 . Se (G, ∗) é um grupo, então a função ∗ é chamada de operação binária do grupo. Se, além desses axiomas, o par (G, ∗) satisfizer a ∗ b = b ∗ a para todo a, b ∈ G, então dizemos que (G, ∗) é um grupo comutativo ou abeliano. Dizemos que um grupo (G, ∗) é finito se G é finito. Neste caso, a ordem de (G, ∗) é ord (G, ∗) := |G|. Acima, definimos um grupo como um par ordenado (G, ∗) formado por um conjunto G e uma operação binária ∗. Em alguns momentos abusaremos da notação e diremos que G é um grupo, quando a operação binária ∗ estiver implı́cita no contexto. 103 É óbvio que (Z, +) é um grupo comutativo, tendo 0 como identidade e −n como inverso de n para todo n ∈ Z. É claro também que (Z, ·) não é um grupo, pois, por exemplo, o elemento 2 não tem inverso multiplicativo nos inteiros. Vamos construir, para cada inteiro positivo n, dois grupos finitos, através das operações de adição e multiplicação módulo n. Fixe n um inteiro positivo. Considere a relação ∼n ⊆ Z × Z definida da seguinte maneira: dados a, b ∈ Z, dizemos que a ∼n b se, e somente se, n divide a − b. Se a ∼n b, então dizemos que a e b são congruentes módulo n. É muito fácil provar que a relação ∼n é reflexiva, simétrica e transitiva, e é portanto uma relação de equivalência em Z. Então a relação ∼n induz naturalmente uma partição de Z em classes de equivalência. Dados inteiros a, b, é fácil provar que a e b estão na mesma classe de equivalência se, e somente se, a mod n = b mod n, isto é, se a e b têm o mesmo resto na divisão por n. Portanto, a classe de equivalência contendo o inteiro a é [a]n := {a + kn : k ∈ Z}. Definimos Zn como o conjunto de classes de equivalência induzidas pela relação ∼n , ou seja, Zn := [a]n : 0 ≤ a < n . Podemos convencionar que o representante de uma classe [a]n é o único elemento não-negativo da classe que é estritamente menor que n. Mas é importante lembrar que cada elemento de Zn é uma classe de equivalência: quando nos referirmos, por exemplo, ao elemento −1 de Zn , estamos nos referindo à classe representada por n − 1, de acordo com a nossa convenção. Podemos definir agora as operações de adição e multiplicação módulo n. Seja +n : Zn × Zn −→ Zn definida da seguinte forma: dados [a]n , [b]n ∈ Zn , tomamos [a]n +n [b]n := [a + b]n . A multiplicação módulo n é definida de forma análoga: dados [a]n , [b]n ∈ Zn , tomamos [a]n ·n [b]n := [ab]n . Com as operações definidas deste modo, dados representantes a e b, para obtermos o representante da adição e multiplicação módulo n de a e b, basta aplicarmos a operação desejada sobre a e b, vistos como inteiros, e calcular o resto da divisão do resultado por n. É muito fácil provar o seguinte resultado: Proposição C.14. O par (Zn , +n ) é um grupo comutativo finito. Chamamos o grupo (Zn , +n ) de grupo aditivo módulo n. Escreveremos, de agora em diante, + no lugar de +n . Vamos definir agora o grupo multiplicativo módulo n. Considere o conjunto Z∗n := [a]n : mdc(a, n) = 1 . (C.3) Teorema C.15. O par (Z∗n , ·n ) é um grupo comutativo finito. 104 Demonstração. É fácil provar que valem as propriedades associativa, comutativa e de fechamento e que Z∗n é finito. A identidade é [1]n . Resta provarmos a existência de inversos. Seja [a]n ∈ Z∗n . Como mdc(a, n) = 1, o teorema C.7 nos garante que existem inteiros x, y tais que ax + ny = 1. Mas então ax ∼n 1, isto é, [a]n ·n [x]n = [1]n e portanto [x]n é o inverso de [a]n . De agora em diante passamos a escrever · no lugar de ·n ou simplesmente omitimos o sı́mbolo da operação, que ficará clara pela justaposição dos fatores. Escreveremos também a ≡ b (mod n) no lugar de a ∼n b e de [a]n = [b]n . Vamos abusar da notação e chamar Zn de grupo aditivo módulo n e Z∗n de grupo multiplicativo módulo n. A função φ(n) := |Z∗n | é chamada de função totiente de Euler e conta o número de inteiros entre 0 e n − 1, inclusive, que são relativamente primos a n. Mais adiante mostraremos uma forma de calcular φ(n) a partir dos divisores primos de n. Definimos a seguir o conceito de subgrupo: Definição C.16. Sejam (G, ∗) um grupo e H ⊆ G. Se (H, ∗) é um grupo, então (H, ∗) é chamado de subgrupo de (G, ∗). É claro que o grupo (2Z, +), onde 2Z := {2n : n ∈ Z} é o conjunto dos pares, é um subgrupo de (Z, +). Na verdade, para qualquer k ∈ Z, o grupo (kZ, +), onde kZ := {kn : n ∈ Z}, é subgrupo de (Z, +). O seguinte teorema é um poderoso resultado da álgebra. Sua demonstração é muito simples e pode ser vista no livro de Fraleigh [Fra89]. Teorema C.17 (Lagrange). Sejam (G, ∗) um grupo finito e (H, ∗) um subgrupo de (G, ∗). Então |H| é um divisor de |G|. Se (H, ∗) é subgrupo de (G, ∗) e H 6= G, então (H, ∗) é chamado de subgrupo próprio de G. O corolário a seguir é imediato do teorema C.17 de Lagrange. Corolário C.18. Se (H, ∗) é um subgrupo próprio de um grupo finito (G, ∗), então temos |H| ≤ |G|/2. Seja (G, ∗) um grupo finito e seja g ∈ G. Vamos mostrar uma maneira sistemática de se obter o “menor” subgrupo de (G, ∗) contendo g. Ou seja, vamos construir um subgrupo (H, ∗) de (G, ∗) tal que g ∈ H e, para todo subgrupo (H 0 , ∗) de (G, ∗) contendo g, temos H ⊆ H 0 . Para tanto, começamos encontrando todos os elementos de G que podem ser obtidos a partir da aplicação da operação ∗ em g. Seja e ∈ G o elemento 105 identidade do grupo (G, ∗). Para k ≥ 0, defina g k como e se k = 0, k g := k−1 g∗g se k > 0. (C.4) É óbvio que todo grupo contendo g também deve conter g k , para todo k ≥ 0. Mas o inverso de g também deve estar nesse grupo. Para k ≤ −1, defina g k como −1 g se k = −1, k g := (C.5) g −1 ∗ g k+1 se k < −1. É muito fácil provar o seguinte teorema: Teorema C.19. Seja (G, ∗) um grupo e seja g ∈ G. Então (H, ∗), onde H := {g k : k ∈ Z}, (C.6) é um subgrupo de (G, ∗). Denotamos o conjunto H do teorema C.19 por hgi, isto é, hgi := {g k : k ∈ Z}. É claro que hgi é o menor subgrupo de (G, ∗) contendo g, no sentido que foi discutido anteriormente. Definição C.20. Sejam G um grupo e g ∈ G. O subgrupo hgi é o subgrupo gerado por g. Dizemos também que g gera o subgrupo hgi ou que g é o gerador do subgrupo hgi. Se H é um subgrupo de G e H = hgi, então H é o subgrupo cı́clico gerado por g. Se G = hgi, então G é um grupo cı́clico. Se H é um subgrupo cı́clico gerado por g, a ordem de H, usualmente denotada por ord(H), poderá ser alternativamente denotada por ord(g). O valor ord(g) é chamado também de ordem de g em G. Teorema C.21. Seja (G, ∗) um grupo. Sejam e o elemento identidade de (G, ∗) e g ∈ G. Então ord(g) é o menor inteiro positivo t tal que g t = e. Demonstração. Seja t o menor inteiro positivo tal que g t = e. Seja k ∈ Z. Pelo teorema C.5 da divisão, existem inteiros q, r tais que k = qt + r e 0 ≤ r < t. q Então g k = g qt+r = (g t ) ∗ g r = eq ∗ g r = g r . Assim, |hgi| ≤ t. Agora vamos mostrar que |hgi| ≥ t. Suponha por um instante que existem inteiros 1 ≤ i < j ≤ t tais que g i = g j . Então g i+k = g j+k para todo k ≥ 0. Mas então g t = g j+(t−j) = e e, portanto, g i+(t−j) = e. Mas isso é um absurdo, pois 0 < i + (t − j) < t e t é o menor inteiro positivo satisfazendo g t = e. Segue que |hgi| ≥ t. Portanto, ord(g) = |hgi| = t, como querı́amos. 106 O seguinte corolário é imediato da prova do teorema C.21: Corolário C.22. Sejam G um grupo e g ∈ G. Então a seqüência hg 0 , g 1 , g 2 , . . .i é periódica com perı́odo t := ord(g). Em outras palavras, g i = g j se, e somente se, i ≡ j (mod t). Outro poderoso resultado da álgebra pode ser sintetizado a partir do corolário C.22 e do teorema C.17 de Lagrange: Corolário C.23. Seja (G, ∗) um grupo e seja e ∈ G o elemento identidade de (G, ∗). Então, para todo g ∈ G, g |G| = e. (C.7) Demonstração. Seja t := ord(g). Pelo teorema C.17 de Lagrange, t divide |G| e, portanto, |G| ≡ 0 (mod t). Mas então, pelo corolário C.22, g |G| = g 0 = e, como querı́amos. Vamos agora aplicar estes resultados ao grupo Z∗n . Reescrevendo o corolário C.23 na notação dos grupos multiplicativos, temos o seguinte teorema: Teorema C.24 (Euler). Seja n > 1. Então, para todo a ∈ Z∗n , aφ(n) ≡ 1 (mod n). (C.8) Como φ(p) = p − 1 para todo primo p, então obtemos imediatamente do teorema C.24 de Euler o resultado a seguir. Teorema C.25 (Fermat). Seja p um primo. Então, para todo a ∈ Z∗p , ap−1 ≡ 1 (mod p). (C.9) Definição C.26. Sejam n > 1 e r ∈ Z∗n . Se r é gerador do grupo Z∗n , então r é uma raiz primitiva de Z∗n . Seja r ∈ Z∗n . É óbvio que r é uma raiz primitiva de Z∗n se, e somente se, ordn (r) = φ(n), onde ordn (r) denota a ordem de r no grupo Z∗n . Se r é uma raiz primitiva de Z∗n , então o grupo Z∗n é cı́clico e todo elemento de Z∗n é uma potência de r. Ou seja, para todo a ∈ Z∗n , existe um 0 ≤ z < φ(n) inteiro tal que rz ≡ a (mod n). Definição C.27. Sejam n > 1 e r uma raiz primitiva de Z∗n . Seja a ∈ Z∗n . Sabemos que existe um inteiro 0 ≤ z < φ(n) tal que rz ≡ a (mod n). Tal z é o logaritmo discreto de a módulo n na base r, denotado por indn,r (a). Não é verdade que Z∗n é cı́clico para todo n: Teorema C.28. Os valores de n para os quais Z∗n é cı́clico são 2, 4, pk e 2pk para todos os primos ı́mpares p e inteiros positivos k. 107 C.3 Teorema do resto chinês Seja n um número composto e suponha que n pode ser escrito como um produto de inteiros mutuamente primos entre si, ou seja, n = n1 · · · nk , com mdc(ni , nj ) = 1 para todo i 6= j. O teorema do resto chinês mostra que o grupo Zn tem a “mesma estrutura” do produto cartesiano Zn1 × · · · × Znk . Teorema C.29 (Resto chinês). Seja n = n1 · · · nk , onde os ni são mutuamente primos entre si. Considere a correspondência a ↔ (a1 , . . . , ak ), (C.10) onde a ∈ Zn , ai ∈ Zni e ai = a mod ni para todo i. Então a correspondência (C.10) é uma bijeção entre Zn e o produto cartesiano Zn1 × · · · × Znk . Demonstração. Dado a ∈ Zn , é muito fácil encontrar inteiros a1 , . . . , ak com ai = a mod ni e ai ∈ Zni para todo i: bastam k divisões. Sejam a1 , . . . , ak inteiros com ai ∈ Zni para todo i. Vamos mostrar como obter a ∈ Zn tal que ai = a mod ni para todo i. Q Para cada i, defina mi := n/ni , isto é, mi = j6=i nj é o produto de todos os nj ’s exceto ni . É claro que mdc(mi , ni ) = 1. Pelo teorema C.7, existem inteiros x, y tais que xmi + yni = 1, ou seja, xmi ≡ 1 (mod ni ). Defina m−1 := x mod ni , pois x é o inverso multiplicativo de mi módulo ni . Fii nalmente, tome ci := mi m−1 i mod ni . Seja j 6= i. Então mj ≡ 0 (mod ni ), pois mi | mj . Concluı́mos assim que cj ≡ mj ≡ 0 (mod ni ). Também temos ci ≡ m−1 i mi ≡ 1 (mod ni ). Mas então ci ↔ (0, . . . , 0, 1, 0, . . . , 0), onde todos os componentes são nulos exceto o i-ésimo, que vale 1. Tome a := a1 c1 + · · · + ak ck mod n. Observe agora que, para todo i, temos a ≡ ai ci (mod ni ) e, portanto, a ≡ ai (mod ni ), já que ci ≡ 1 (mod ni ). Segue que a correspondência (C.10) é uma bijeção, como querı́amos. Os seguintes corolários seguem imediatamente do teorema C.29 do resto chinês. Corolário C.30. Sejam n1 , . . . , nk inteiros mutuamente primos entre si e n = n1 · · · nk . Então, para quaisquer inteiros a1 , . . . , ak , o sistema de equações x ≡ ai (mod ni ) para i = 1, . . . , k tem uma única solução módulo n. Corolário C.31. Sejam n1 , . . . , nk inteiros mutuamente primos entre si e n = n1 · · · nk . Então, para quaisquer inteiros x e a, temos x ≡ a (mod ni ) para i = 1, . . . , k se, e somente se, x ≡ a (mod n). 108 Podemos agora provar uma fórmula para a função totiente de Euler: Teorema C.32. Seja n > 1 um inteiro. Então Y 1 φ(n) = n 1− , p p∈P (C.11) onde P é o conjunto dos divisores primos de n. Demonstração. É óbvio que φ(p) = p − 1 para todo primo p, o que está de acordo com a equação (C.11). Suponha agora que n é uma potência de primo, isto é, que n = pk para algum k ≥ 1. Então é fácil calcular φ(n): os únicos inteiros entre 0 e n − 1, inclusive, que não são relativamente primos a n são os múltiplos de p, ou seja, 0, p, 2p, . . . , (pk−1 − 1)p. Portanto φ(n) = n − pk−1 = pk − pk−1 = pk (1 − 1/p). Observe novamente que estamos de acordo com a equação (C.11) e que esta fórmula fornece apropriadamente φ(p) = p − 1 quando o expoente k vale 1. Suponha então que n não é uma potência de primo. Então podemos escrever n como um produto n = n1 n2 de inteiros n1 , n2 relativamente primos. Então qualquer inteiro 0 ≤ m < n pode ser representado pelo par (m mod n1 , m mod n2 ) e, pelo corolário C.30, tal representação é única. Observe agora que mdc(m, n) = 1 se, e somente se, mdc(m, n1 ) = 1 e mdc(m, n2 ) = 1. Pelo teorema C.9, temos então que mdc(m, n) = 1 se, e somente se, mdc(m mod n1 , n1 ) = 1 e mdc(m mod n2 , n2 ) = 1. Portanto podemos calcular φ(n) recursivamente como φ(n) = φ(n1 )φ(n2 ), pois há φ(n1 ) possı́veis valores para a primeira coordenada e φ(n2 ) possı́veis valores para a segunda coordenada da representação mostrada acima tais que o inteiro representado seja relativamente primo a n. Uma função f sobre inteiros positivos é dita multiplicativa se f (1) = 1 e f (ab) = f (a)f (b) sempre que mdc(a, b) = 1. Acabamos de provar, então, que a função totiente φ(n) é multiplicativa. É claro que uma função multiplicativa é completamente definida pelo seu valor nas potências de primos. De fato, suponha que f é multiplicativa e que a fatoração de m seja Y m= pmp , p∈P onde P é o conjunto dos divisores primos de m. Então Y f (m) = f (pmp ). p∈P 109 Mas nós já sabemos o valor de φ(n) se n é uma potência de primo. Então temos " # Y Y Y 1 1 mp mp 1− φ(n) = φ(p ) = p =n 1− , p p p∈P p∈P p∈P como querı́amos. C.4 Equações modulares Estudaremos agora algumas equações sobre Zn e Z∗n . Primeiro consideramos as soluções da equação ax ≡ b (mod n), (C.12) onde a e n são inteiros positivos. Vamos denotar por hai o subgrupo de Zn gerado por a, isto é, hai := {ax mod n : x > 0}. É óbvio que a equação (C.12) admite soluções em Zn se, e somente se, b ∈ hai. O teorema a seguir caracteriza o subgrupo hai: Teorema C.33. Sejam a e n inteiros positivos e d = mdc(a, n). Então n o hai = hdi = 0, d, 2d, . . . , (n/d) − 1 d (C.13) e portanto |hai| = n/d. Demonstração. Primeiro vamos mostrar que hdi ⊆ hai. Pelo teorema C.7, existem inteiros x e y tais que ax+ny = d, ou seja, ax ≡ d (mod n). Então d ∈ hai. É claro também que todos os múltiplos de d estão em hai. Segue que hdi ⊆ hai. Agora mostraremos que hai ⊆ hdi. Seja m ∈ hai. Então m ≡ ax (mod n) para algum x > 0. Assim, existe um inteiro y tal que m = ax + ny. Como d | a e d | n, então d | m pela proposição C.2. Portanto m ∈ hdi, como querı́amos. Finalmente, observe que existem exatamente n/d múltiplos de d entre 0 e n − 1, de modo que |hai| = n/d. Corolário C.34. Sejam a, b inteiros, n um inteiro positivo e d = mdc(a, n). Se d | b, então a equação (C.12) admite exatamente d soluções em Zn . Caso contrário, ela não admite nenhuma solução. Demonstração. É óbvio que a equação ax ≡ b (mod n) admite soluções se, e somente se, b ∈ hai. Pelo teorema C.33, hai = hdi. Então a equação (C.12) admite solução se, e somente se, d | b. 110 Resta provarmos que, se d | b, então a equação (C.12) admite d soluções em Zn . Suponha, então, que d | b. Sabemos pelo corolário C.22 que a seqüência ai mod n, com i ≥ 0, é periódica com perı́odo ord(a) = |hai| e, pelo teorema C.12, |hai| = n/d. Então b mod n aparece d vezes na seqüência ai mod n, com 0 ≤ i ≤ n − 1: uma vez em cada bloco de comprimento n/d. Os ı́ndices x para os quais ax mod n = b mod n são as soluções da equação (C.12) em Zn . Então há d soluções para a equação (C.12), como querı́amos. Consideraremos agora alguns resultados interessantes acerca de equações sobre Z∗n . Teorema C.35 (Logaritmo discreto). Seja r uma raiz primitiva de Z∗n . Então a equação rx ≡ ry (mod n) vale se, e somente se, a equação x≡y (mod φ(n)) vale. Demonstração. Suponha que x ≡ y (mod φ(n)). Então x = y + kφ(n) para algum inteiro k. Assim, rx ≡ ≡ ≡ ≡ ry+kφ(n) k ry rφ(n) ry · 1k ry (mod n) (mod n) (mod n) (mod n), onde utilizamos o fato de que rφ(n) ≡ 1 (mod n), pelo teorema C.24 de Euler. Suponha agora que rx ≡ ry (mod n). Como r é uma raiz primitiva de Z∗n , então |hri| = φ(n). Pelo corolário C.22, a seqüência de potências de r módulo n é periódica com perı́odo φ(n). Mas então, rx ≡ ry (mod n) se, e somente se, x ≡ y (mod φ(n)). Teorema C.36. Seja p um primo ı́mpar e seja k ≥ 1 um inteiro. Então a equação x2 ≡ 1 (mod pk ) (C.14) tem exatamente duas soluções, a saber, x = ±1. Demonstração. Seja n := pk . Pelo teorema C.28, o grupo Z∗n tem um raiz primitiva. Seja r uma raiz primitiva de Z∗n . Utilizando logaritmos discretos, a equação (C.14) pode ser escrita como 2 rindn,r (x) ≡ rindn,r (1) (mod n). (C.15) 111 Pelo teorema C.35 do logaritmo discreto, a equação (C.15) é equivalente a 2 indn,r (x) ≡ 0 (mod φ(n)), (C.16) pois indn,r (1) = 0. Pelo teorema C.32, temos φ(n) = φ(pk ) = pk (1 − 1/p) = (p − 1)pk−1 . Então temos d = mdc 2, φ(n) = 2, pois p − 1 é par. Como d | 0, o corolário C.34 nos garante que a equação (C.16) tem exatamente d = 2 soluções. Portanto a equação (C.14) admite exatamente 2 soluções. É fácil ver então que x = ±1 são as únicas soluções da equação (C.14). Podemos considerar equações da forma x2 ≡ 1 (mod n) para qualquer n positivo. Soluções diferentes de ±1 são chamadas de raı́zes quadradas nãotriviais de 1 módulo n. O corolário a seguir é imediato da contrapositiva do teorema C.36. Corolário C.37. Seja n > 1 um inteiro. Se existe uma raiz quadrada nãotrivial de 1, módulo n, então n é composto. Vamos ver agora que, se tivermos à nossa disposição uma raiz quadrada não-trivial de um n > 0, então podemos facilmente obter um fator de n. Um algoritmo eficiente para o cálculo do máximo divisor comum será apresentado mais adiante. Teorema C.38. Sejam n > 1 um inteiro e x uma raiz quadrada não-trivial de 1, módulo n. Então ambos mdc(x − 1, n) e mdc(x + 1, n) são divisores não-triviais de n. Demonstração. Sabemos, pelo corolário C.37, que n é composto. Como x2 ≡ 1 (mod n), então n divide x2 − 1 = (x + 1)(x − 1). Por outro lado, x 6≡ 1 (mod n) implica que n 6 | (x − 1) e x 6≡ −1 (mod n) implica que n 6 | (x + 1). Então os fatores de n devem estar separados entre x−1 e x+1. Logo, ambos mdc(x−1, n) e mdc(x + 1, n) são fatores de n. C.5 Considerações computacionais Para os algoritmos que resolvem problemas de teoria dos números, adotamos a convenção de que um número n é codificado através de sua representação binária. Assim o tamanho da entrada de um algoritmo que recebe inteiros n1 , . . . , nk é β1 + · · · + βk , onde βi := blg ni c + 1 = O(lg ni ) é o comprimento da representação binária de ni e lg m denota o logaritmo de m na base 2. Tal 112 algoritmo é polinomial se seu tempo de execução for limitado por um polinômio em lg n1 , . . . , lg nk . Também precisamos ser cuidadosos com relação ao tempo de execução das operações aritméticas. Para muitos algoritmos, costuma-se considerar somas e multiplicações como operações elementares (ou primitivas) e que portanto executam em tempo constante. Porém, dado que estaremos trabalhando com números “grandes”, o tempo de execução destas operações será relevante. Como as operações aritméticas para inteiros de tamanho arbitrário são definidas em termos de operações sobre os bits de sua representação binária, é razoável medirmos o tempo de execução dos algoritmos de teoria dos números através do número de operações sobre bits que eles realizam. Por exemplo, a soma de dois números de β bits pode ser feita da maneira usual, como é feita com lápis e papel, de modo a envolver O(β) operações sobre bits. É claro que o tempo de execução deste algoritmo é linear no tamanho da entrada. A maneira usual de se multiplicar ou dividir, como se faz com lápis e papel, fornece algoritmos que executam em tempo O(β 2 ) quando recebem como entrada inteiros de β bits. Mas existem algoritmos mais rápidos para multiplicação. Uma simples aplicação do método de divisão e conquista fornece um algoritmo cujo tempo de execução é O(β lg 3 ), o que foi originalmente sugerido por Karatsuba e Ofman [KO62, KO63]. Atualmente, o algoritmo assintoticamente mais rápido é o de Schönhage e Strassen [SS71, Knu81, Sch82], com tempo de execução O(β lg β lg lg β). Mais detalhes sobre esses algoritmos podem ser vistos no livro de Knuth [Knu81]. O algoritmo ingênuo de fatoração, que procura por um divisor de n en√ √ 2 tre 2 e b nc, inclusive, consome tempo Θ(β n) = Θ(β 2 2 β/2 ) no pior caso, e portanto é exponencial em relação ao tamanho da entrada. C.5.1 O algoritmo de Euclides Em diversos algoritmos de teoria dos números é essencial saber como calcular eficientemente o máximo divisor comum entre dois inteiros positivos. O teorema C.9 da Recursão de Euclides nos fornece imediatamente o seguinte algoritmo, conhecido como algoritmo de Euclides: Algoritmo Euclides-MDC (a, b) 1 se b = 0 2 então devolva a 3 senão devolva Euclides-MDC (b, a mod b) Vamos analisar o número de chamadas recursivas feitas pelo algoritmo ao executarmos Euclides-MDC (a, b). Podemos supor que a > b ≥ 0. De fato, se 113 b > a ≥ 0, então a chamada recursiva seguinte será Euclides-MDC (b, a). É claro também que, se b = a > 0, então Euclides-MDC (a, b) faz apenas uma chamada recursiva. Defina os números de Fibonacci da seguinte maneira: se n = 0 0 1 se n = 1 Fn := (C.17) Fn−1 + Fn−2 se n > 1 Referimos o leitor ao livro de Graham et al. [GKP94] para um estudo mais detalhado desta seqüência de números. Lema C.39. Se a > b ≥ 1 e a execução de Euclides-MDC (a, b) faz k ≥ 1 chamadas recursivas, então a ≥ Fk+2 e b ≥ Fk+1 . Demonstração. Vamos provar o lema por indução em k. Para a base da indução, temos que b ≥ 1 = F2 e a ≥ 2 = F3 por hipótese. Para o passo da indução, suponha que a execução de Euclides-MDC (a, b) faz k > 1 chamadas recursivas. A primeira chamada recursiva é EuclidesMDC (b, a mod b) que, por sua vez, realiza k − 1 chamadas recursivas. Pela hipótese de indução, temos então b ≥ Fk+1 e (a mod b) ≥ Fk . Assim, resta provarmos que a ≥ Fk+2 . Como a > b > 0, então ba/bc ≥ 1, de forma que b + (a mod b) = b + (a − ba/bcb) ≤ a. Mas então a ≥ b + (a mod b) ≥ Fk+1 + Fk = Fk+2 , como querı́amos. Segue imediatamente a seguinte delimitação para o número de chamadas recursivas: Teorema C.40 (Lamé). Se a > b ≥ 1 e b < Fk+1 para algum inteiro k ≥ 1, então Euclides-MDC (a, b) faz menos de k chamadas recursivas. A delimitação apresentada pelo teorema C.40 é justa: basta verificar que, para qualquer k ≥ 1, a execução de Euclides-MDC (Fk+1 , Fk ) faz exatamente k − 1 chamadas recursivas. Não é difı́cil provar por indução que, para todo n ≥ 0, 1 n n √ Fn = φ − φ̂ , (C.18) 5 √ √ onde φ := (1 + √ 5)/2 é a razão áurea e φ̂ := (1 − 5)/2. Assim, Fn é aproximadamente φn / 5. Combinando esta aproximação com o teorema C.40 de 114 Lamé, concluı́mos que o número de chamadas recursivas numa execução de Euclides-MDC (a, b) é O(lg b). Supondo que a e b são inteiros de β bits e que a divisão entre inteiros de β bits consome O(β 2 ) operações sobre bits, o total de operações sobre bits realizado por Euclides-MDC (a, b) é de O(β 3 ). Com um pouco mais de cuidado, pode-se provar que Euclides-MDC (a, b) consome, na verdade, O(β 2 ) operações sobre bits. O gargalo do algoritmo de Euclides está no uso repetido de divisões entre inteiros de comprimento arbitrário. Se os inteiros a e b estiverem armazenados na base binária, como é usual, então podemos calcular mdc(a, b) utilizando apenas operações rápidas para a aritmética binária, como subtração, teste de paridade e divisão inteira por 2. O algoritmo resultante, conhecido como binary gcd algorithm, utiliza apenas O(lg a) operações binárias. Mais detalhes podem ser vistos no capı́tulo 31 do livro de Cormen et al. [CLRS01] e no livro de Knuth [Knu81]. O algoritmo de Euclides pode ser facilmente modificado para calcular inteiros x e y tais que mdc(a, b) = ax + by, cuja existência é garantida pelo teorema C.7. É trivial verificar que o algoritmo a seguir, conhecido como algoritmo estendido de Euclides, realiza tal tarefa: Algoritmo Euclides-Estendido-MDC (a, b) 1 se b = 0 2 então devolva (a, 1, 0) 0 3 (d , x0 , y 0 ) ← Euclides-Estendido-MDC (b, a mod b) 4 (d, x, y) ← (d0 , y 0 , x0 − ba/bcy 0 ) 5 devolva (d, x, y) Os inteiros x, y fornecidos pelo algoritmo estendido de Euclides certificam que a resposta devolvida pelo algoritmo está correta. De fato, é fácil verificar se d = ax + by, como o algoritmo garante. Se isso vale, então todo divisor de a e de b também divide d, de modo que mdc(a, b) | d. Também é fácil verificar se d é divisor comum de a e b. Se isso também vale, é óbvio que mdc(a, b) = d. C.5.2 Exponenciação modular Assim como o cálculo do máximo divisor comum, a exponenciação modular é uma operação fundamental para diversos algoritmos de teoria dos números. Dados inteiros a e b não-negativos e n positivo, queremos calcular eficientemente o valor ab mod n. O algoritmo ingênuo que realiza b multiplicações é obviamente exponencial em lg b. Uma idéia simples, mas poderosa, vem da utilização da representação binária do expoente b. Suponha que bk bk−1 . . . b0 é a representação de b em binário, 115 onde k := blg bc e, P obviamente, bi ∈ {0, 1} para todo i. Em outras palavras, suponha que b = ki=0 ci , onde ci := bi 2i . Seja B := {i : bi = 1}. Então b a =a Pk i=0 ci = k Y i=0 ac i = Y i a2 . (C.19) i∈B A equação (C.19) nos fornece imediatamente o seguinte algoritmo, usualmente chamado de exponenciação por repetição de quadrados (repeated squaring): Algoritmo Repetição-de-Quadrados (a, b, n) 1 seja bk bk−1 . . . b0 a representação binária de b 2 x←1 3 y←a 4 para i de 0 até k faça 5 se bi = 1 6 então x ← xy mod n 7 y ← y 2 mod n 8 devolva x É fácil provar que o algoritmo calcula corretamente o valor ab mod n, utilizando a equação (C.19) e o seguinte invariante: no inı́cio de cada iteração do i laço das linhas 4–7, temos que y = a2 mod n. Suponha que cada um dos inteiros a, b e n fornecidos como entrada têm β bits. A representação binária de b, se não estiver imediatamente disponı́vel, pode ser facilmente obtida através de β divisões inteiras de b por 2, o que consome tempo O(β 2 ). Como k = O(β), o laço das linhas 4–7 pode ser executado com O(β 3 ) operações sobre bits, supondo que cada multiplicação e divisão pode ser realizada em tempo O(β 2 ). Logo, o tempo de execução deste algoritmo é O(β 3 ). 116 Apêndice D Testes de primalidade e Criptografia RSA Aplicamos agora os resultados vistos no capı́tulo sobre teoria dos números para compreendermos o teste de primalidade de Miller-Rabin e o sistema de criptografia RSA, que serve como motivação para o estudo do algoritmo de Shor. D.1 Os problemas da primalidade e da fatoração O problema da primalidade consiste em, dado um inteiro n > 1, decidir se n é primo. O problema da fatoração consiste em, dado um inteiro n > 1, encontrar sua fatoração única, como descrita no teorema C.12. É evidente que o problema da primalidade está na classe coNP. De fato, se um inteiro n > 1 é composto, então n tem um divisor não-trivial, isto é, existe um inteiro 1 < d < n que divide n. O fator d é uma obstrução sucinta para a primalidade de n. De forma não tão imediata, pode-se provar também que o problema da primalidade está na classe NP, partindo-se da seguinte caracterização de primos: Teorema D.1 (Teste de Lucas). Um inteiro p > 1 é primo se, e somente se, existe um inteiro 1 < r < p tal que rp−1 ≡ 1 (mod p) e r(p−1)/q 6≡ 1 (mod p) para todos os divisores primos q de p − 1. A existência de certificados sucintos para primalidade é originalmente devida a Pratt [Pra75]: 117 Teorema D.2 (Pratt). O problema da primalidade está na classe NP. Seria interessante, então, que os testes de primalidade, ou seja, os algoritmos que resolvem o problema da primalidade, nos fornecessem respostas afirmativas acompanhadas de certificados sucintos e respostas negativas acompanhadas de obstruções sucintas. Tal certificado sucinto não precisa, necessariamente, ser o mesmo certificado cuja existência foi provada por Pratt. Da mesma forma, as obstruções devolvidas não precisam ser, necessariamente, fatores de um número composto n. Por exemplo, algumas das obstruções à primalidade devolvidas pelo Teste de Miller-Rabin, que vamos apresentar mais adiante, não oferecem nenhuma pista fácil sobre quais devem ser os fatores de n: não se sabe como se utilizar eficientemente a obstrução sucinta devolvida para se obter um fator de n. É claro que um teste polinomial de primalidade que devolve como obstrução um fator de n pode ser utilizado para fatorar n em tempo polinomial, ou seja, tal algoritmo estaria, na verdade, resolvendo o problema da fatoração. Acredita-se que, no modelo clássico, fatorar um número seja mais difı́cil do que decidir se ele é primo ou não. O sistema de criptografia de chave pública mais amplamente utilizado atualmente, o rsa, baseia-se exatamente nessa suposição e no conhecimento de testes polinomiais de primalidade. Os testes são empregados na busca de primos grandes, necessários para a geração de chaves. Sem testes eficientes de primalidade, seria muito complicado criar chaves seguras. Já a dificuldade de criptanálise do rsa baseia-se justamente na suposição de que é difı́cil fatorar números grandes. Atualmente, o algoritmo probabilı́stico de fatoração mais rápido é o general number field sieve, originalmente desenvolvido por Pollard [Pol93] e Lenstra et al. [LLMP93] e aperfeiçoado por Coppersmith [Cop93] e Buhler et al. [BLP93]. É difı́cil obter uma análise de tempo rigorosa para esse algoritmo, mas, partindo de suposições razoáveis, pode-se mostrar que o algoritmo consome tempo proporcional a 1/3 2/3 exp c (ln n) (ln ln n) , onde c := 1 3 √ 1/3 ∼ 92 + 26 13 = 1,902. Outro algoritmo probabilı́stico de fatoração é o método das curvas elı́pticas, desenvolvido por Lenstra [Len87]. De acordo com Pomerance [Pom96], esse algoritmo é mais lento que o general number field sieve apenas para uma pequena fração dos números compostos. Dado um inteiro n composto, esse método encontra um fator primo pequeno p de n em tempo estimado proporcional a exp d (ln p)1/2 (ln ln p)1/2 , 118 √ onde d ∼ = 2. Note que o tempo de execução de ambos algoritmos é superpolinomial em log n. A história é bastante diferente para testes de primalidade. O teste de Miller-Rabin [Mil75, Mil76, Rab80] é um algoritmo probabilı́stico polinomial com erro unilateral limitado. Seguindo a terminologia de Papadimitriou [Pap94], esse teste é um algoritmo polinomial de Monte Carlo para dizer se um inteiro é composto, o que significa que, se o teste afirma que um número n é composto, então n é composto com certeza. Já se o teste responde que n é primo, existe a possibilidade de ele estar errado, isto é, é possı́vel que n seja composto. Porém, a probabilidade de ocorrência deste erro é estritamente menor que 1/2. Isso estabelece que o problema da primalidade está na classe coRP. Além disso, o teste de Miller-Rabin, ao afirmar que um dado número é composto, nos devolve uma obstrução sucinta à sua primalidade. Existem algoritmos polinomiais de Monte Carlo para dizer se um inteiro é primo, isto é, o erro unilateral limitado destes testes é complementar ao erro do teste de Miller-Rabin. Ou seja, se o teste afirma que um número n é primo, então certamente isso é verdade. Já se o teste responde que n é composto, a probabilidade de ele estar errado é estritamente menor que 1/2. Entre esses testes está o algoritmo de Adleman e Huang [AH92], obtido a partir de modificações no algoritmo de Goldwasser e Kilian [GK86]. O algoritmo de Adleman e Huang, ao responder que um dado número é primo, nos devolve um certificado sucinto de primalidade. Estabelecemos assim que o problema da primalidade está na classe RP. Mas então o problema da primalidade está na classe ZPP = RP ∩ coRP, de modo que ele admite um algoritmo de Las Vegas, seguindo novamente a terminologia de Papadimitriou [Pap94]. Isto é, ao repetirmos k execuções alternadas dos algoritmos de Miller-Rabin e de Adleman e Huang, a probabilidade de nunca obtermos uma resposta definitiva é menor que 2−k . Estamos chamando de resposta definitiva as respostas dadas com certeza por cada algoritmo: no caso do teste de Miller-Rabin, a resposta definitiva é a afirmação de que o número é composto e, no caso do teste de Adleman e Huang, a afirmação de que o número é primo. Observe que, com este algoritmo de Las Vegas, não só a probabilidade de não obtermos respostas definitivas é arbitrariamente pequena, mas também obtemos certificados e obstruções sucintas de primalidade, o que é muito conveniente. Essa linha de pesquisa culminou com o aks, um algoritmo determinı́stico polinomial para o problema da primalidade, desenvolvido por Agrawal, Kayal e Saxena [AKS02a, AKS02b]. Provou-se assim que o problema da primalidade está na classe P, de modo que todos os resultados anteriores tornaram-se corolários deste. 119 Um histórico mais detalhado sobre o desenvolvimento de testes de primalidade pode ser visto na seção introdutória dos artigos de Agrawal, Kayal e Saxena [AKS02a, AKS02b]. D.2 O Teste de Miller-Rabin O teste de primalidade de Miller-Rabin [Mil75, Mil76, Rab80] é um algoritmo probabilı́stico extremamente simples e rápido. Porém, sua análise não é tão trivial. Utilizaremos quase todo o conteúdo das seções anteriores para sua exposição. Dado um inteiro n > 1 par, é óbvio que n é primo se e só se n = 2. Todos os outros pares positivos têm o divisor 2 como obstrução sucinta de primalidade. Nesta seção, vamos nos restringir ao problema da primalidade apenas para inteiros ı́mpares estritamente maiores que 1. Uma primeira idéia para um teste de primalidade é dada pela contrapositiva do teorema C.25 de Fermat: se an−1 6≡ 1 (mod n) para algum 0 < a < n, então n é composto. De fato, se n fosse primo, então an−1 ≡ 1 (mod n) para todo 0 < a < n, pois todo 0 < a < n é relativamente primo a n. Podemos dizer que a é uma testemunha do fato de n ser composto. Segundo Coutinho [Cou00], Leibniz utilizou esta idéia como critério de primalidade. Dado um inteiro n > 1 ı́mpar, se 2n−1 6≡ 1 (mod n), o teste de Leibniz responde que n é composto e que 2 é uma testemunha deste fato. Caso contrário, ele afirma que n é primo. Observe que esse teste responde que 341 = 11×31 é primo. Existem diversos outros inteiros compostos para os quais o teste de Leibniz dá a resposta errada. Isso nos sugere a seguinte definição: Definição D.3. Sejam n > 1 um número composto e 0 < a < n. Se an−1 ≡ 1 (mod n), (D.1) então n é pseudoprimo para a base a. O teste de Leibniz sempre dá a resposta errada para pseudoprimos para a base 2, pois afirma que eles são primos. Infelizmente, não basta estendermos o teste de Leibniz para que a equivalência (D.1) seja testada para alguma outra base, por exemplo, a = 3. A razão disso é que existem inteiros n que são pseudoprimos para todas as bases relativamente primas a n. Tais inteiros são chamados números de Carmichael [Car12]. O menor número de Carmichael é 561 = 3 × 11 × 17. Alford et al. [AGP94] provaram que existem infinitos números de Carmichael. 120 O teste de Miller-Rabin contorna essas falhas do teste de Leibniz, combinando o uso do teorema C.25 e do corolário C.37 com aleatorização para obter um teste probabilı́stico eficiente de primalidade, com erro limitado unilateral. Resumidamente, a base a da equivalência (C.9) é escolhida aleatoriamente e, durante o cálculo da exponenciação modular an−1 mod n, procuramos por raı́zes quadradas não-triviais de 1, módulo n. O teste responde que n é composto apenas se encontrar tais raı́zes ou se a e n não satisfizerem a equação (C.9) do teorema C.25 de Fermat. Detalhamos a seguir o pseudocódigo para o teste de Miller-Rabin: Algoritmo Miller-Rabin (n) 01 escolha um inteiro 0 < a < n aleatoriamente, com distribuição uniforme 02 sejam u um ı́mpar e t ≥ 1 inteiros tais que n − 1 = 2t u 03 x0 ← au mod n 04 para i de 1 a t faça 05 xi ← x2i−1 mod n 06 se xi = 1 e xi−1 6= 1 e xi−1 6= n − 1 07 então devolva “composto”, acompanhado de a 08 se xt 6= 1 09 então devolva “composto”, acompanhado de a 10 senão devolva “primo” Se a linha 3 for executada através do método de repetição de quadrados, então este algoritmo é apenas uma leve modificação do procedimento Repetiçãode-Quadrados, apresentado anteriormente, e seu tempo de execução é O(β 3 ), supondo que n é um inteiro de β bits. Caso o algoritmo devolva “composto” através da linha 7, então ele encontrou uma raiz quadrada não-trivial de 1, módulo n e, de acordo com o corolário C.37, o inteiro n é composto. Essa raiz é, no caso, ab mod n, onde b := 2i−1 u. Já se a resposta “composto” for proveniente da linha 9, então an−1 6≡ 1 (mod n) e, de acordo com a contrapositiva do teorema C.25 de Fermat, o número n é composto. Em ambos os casos, vamos chamar a base a de testemunha de que n é composto. Se o algoritmo não encontrou evidências de que n é composto, então ele responde que n é primo, apesar de não ter certeza. Precisamos agora limitar a probabilidade deste erro, proveniente de “azar” na escolha da base a. Faremos uso do seguinte lema: 121 Lema D.4. Seja n um número de Carmichael. Então n não é potência de primo. Demonstração. Seja n um número de Carmichael. Então, para todo x ∈ Z∗n , temos xn−1 ≡ 1 (mod n). (D.2) Suponha que n := pk , onde p é um primo e k > 1. Como n é ı́mpar, p também deve ser ı́mpar. Pelo teorema C.28, o grupo Z∗n é cı́clico, ou seja, Z∗n contém um gerador g tal que ordn (g) = |Z∗n | = φ(n). Pelo teorema C.32, φ(n) = pk (1−1/p) = (p−1) pk−1 . Pela equação (D.2), temos g n−1 ≡ 1 (mod n), ou seja, g n−1 ≡ g 0 (mod n). Então, pelo teorema C.35 do logaritmo discreto, temos n − 1 ≡ 0 (mod φ(n)), isto é, (p − 1) pk−1 (pk − 1). Como k > 1, então p divide (p − 1) pk−1 . Mas p não divide pk − 1. Isso é um absurdo. Segue que n não é potência de primo. A demonstração do teorema a seguir segue de perto a prova apresentada no livro de Cormen et al. [CLRS01]. Teorema D.5. Seja n um composto ı́mpar. Então o número de testemunhas de que n é composto é estritamente maior que (n − 1)/2. Demonstração. Sejam n um composto ı́mpar e 0 < a < n um inteiro. Se uma chamada a Miller-Rabin (n) responder que n é primo ao escolher a como base na linha 1, dizemos que a é uma não-testemunha de que n é composto. Vamos mostrar que o número de não-testemunhas de que n é composto é estritamente menor que (n − 1)/2, de onde o teorema segue imediatamente. É fácil ver que toda não-testemunha está em Z∗n . De fato, suponha que a é uma não-testemunha de que n é composto. Então xt = 1 na linha 8 do algoritmo, ou seja, an−1 ≡ 1 (mod n). Logo, a equação ax ≡ 1 (mod n) admite uma solução, a saber, x = an−2 . Pelo corolário C.34, temos que mdc(a, n) | 1 e, portanto, mdc(a, n) = 1. Segue que toda não-testemunha está em Z∗n . Vamos mostrar que toda não-testemunha está num subgrupo próprio B de Z∗n . Pelo corolário C.18, teremos então |B| ≤ |Z∗n |/2 = φ(n)/2. Como n é composto, então φ(n) < n − 1, de modo que teremos |B| < (n − 1)/2 e a demonstração estará concluı́da. Começamos tratando o caso em que n não é um número de Carmichael, ou seja, existe x ∈ Z∗n tal que xn−1 6≡ 1 (mod n). Seja B := {b ∈ Z∗n : bn−1 ≡ 1 (mod n)}. Como 1 ∈ B, o conjunto B não é vazio. Além 122 disso, é evidente que B é fechado sob multiplicação módulo n. Então B é um subgrupo de Z∗n . Observe que toda não-testemunha está em B, pois toda nãotestemunha a satisfaz an−1 ≡ 1 (mod n). Como x ∈ Z∗n \ B, então B é um subgrupo próprio de Z∗n , como querı́amos. Suponha, de agora em diante, que n é um número de Carmichael. Sejam u um ı́mpar e t ≥ 1 inteiros tais que n − 1 = 2t u. Dizemos que um par (v, j) de inteiros é aceitável se v ∈ Z∗n , 0 ≤ j ≤ t e v2 ju ≡ −1 (mod n). Pares aceitáveis certamente existem já que u é ı́mpar: tome, por exemplo, v = n − 1 e j = 0. Escolha o maior j possı́vel tal que existe um par (v, j) aceitável e fixe v de modo que (v, j) seja aceitável. Seja j B = x ∈ Z∗n : x2 u ≡ ±1 (mod n) . É fácil ver que B é fechado sob multiplicação módulo n, e portanto é um subgrupo de Z∗n . Toda não-testemunha está em B. De fato, considere a seqüência 2 t X := hx0 , x1 , x2 , . . . , xt i := au , a2u , a2 u , . . . , a2 u de inteiros módulo n calculada pelo algoritmo de Miller-Rabin. As possı́veis “formas” de X são: • X = h. . . , di, com d 6≡ 1 (mod n). Então an−1 6≡ 1 (mod n) e o algoritmo responde, na linha 9, que n é composto. • X = h1, . . . , 1i. Neste caso, a base a escolhida na linha 1 não é testemunha de que n é composto e o algoritmo responde que n é primo. • X = h. . . , −1, 1, . . . , 1i. Como a seqüência termina em 1 e a última entrada diferente de 1 é −1, a base a escolhida na linha 1 não é testemunha de que n é composto. O algoritmo responde que n é primo. • X = h. . . , d, 1, . . . , 1i, com d 6≡ ±1 (mod n). A seqüência termina em 1, mas o último valor diferente de 1 é d 6≡ ±1 (mod n), e portanto foi encontrada uma raiz quadrada não-trivial de 1, módulo n. O algoritmo responde, na linha 7, que n é composto. Note então que, se a é uma não-testemunha, então a seqüência X produzida para ela é da forma X = h1, . . . , 1i ou X = h. . . , −1, 1, . . . , 1i. Se a seqüência é toda de 1’s, então é óbvio que a ∈ B. Já se X = h. . . , −1, 1, . . . , 1i, então a 123 posição em que −1 ocorre não é maior que j, pela maximalidade de j. Assim, toda não-testemunha está em B. Vamos mostrar agora que B é um subgrupo próprio de Z∗n . Para tanto, vamos provar a existência de um w ∈ Z∗n \B através dos corolários do teorema C.29 do resto chinês. Pelo lema D.4, n não é potência de primo, já que n é um número de Carmichael. Então podemos escrever n como um produto n = n1 n2 , onde n1 e n2 são ı́mpares primos entre si, ambos maiores que 1. j Como v 2 u ≡ −1 (mod n), o corolário C.31 nos garante que v2 ju ≡ −1 (mod n1 ). (D.3) (mod n1 ) (mod n2 ), (D.4) Considere o sistema de equações y ≡ v y ≡ 1 com incógnita y. Seja w uma solução do sistema (D.4), cuja existência é garantida pelo corolário C.30. Como w ≡ v (mod n1 ), segue da equação (D.3) que w2 w ju 2j u ≡ −1 (mod n1 ) (D.5) ≡ +1 (mod n2 ). (D.6) j j j Pelo corolário C.31, w2 u 6≡ 1 (mod n1 ) implica que w2 u 6≡ 1 (mod n) e w2 u 6≡ j j −1 (mod n2 ) implica que w2 u 6≡ −1 (mod n). Então w2 u 6≡ ±1 (mod n), de modo que w 6∈ B. Resta apenas mostrarmos que w ∈ Z∗n . Como v ∈ Z∗n , então mdc(v, n) = 1 e, portanto, mdc(v, n1 ) = 1. Dado que w ≡ v (mod n1 ), então n1 | w − v. Seja d > 1 um divisor de n1 , de modo que d | w − v. Como d 6 | v, então não podemos ter d | w. Segue que mdc(w, n1 ) = 1. A equivalência w ≡ 1 (mod n2 ) implica que mdc(w, n2 ) = 1. Como w não tem divisores não-triviais em comum nem com n1 e nem com n2 , então mdc(w, n1 n2 ) = 1, ou seja, w ∈ Z∗n , como querı́amos. Segue imediatamente do teorema D.5 que a probabilidade de o teste de Miller-Rabin responder que n é primo quando, na verdade, n é composto, é estritamente menor que 1/2. Monier [Mon80] provou que, para todo n composto ı́mpar, existem no máximo (n−1)/4 bases 0 < a < n que não são testemunhas de que n é composto, e esta delimitação é justa. Isso diminui consideravelmente a probabilidade de erro do teste de Miller-Rabin, comparado à delimitação obtida pelo teorema D.5. 124 Seja n um composto e suponha que uma chamada a Miller-Rabin (n) respondeu que n é composto através da linha 7, acompanhado de uma base a, testemunha de que n é composto. É muito fácil obter uma raiz quadrada nãotrivial x de 1, módulo n, a partir de a: basta seguir as linhas 2–7 do mesmo algoritmo. Com esta raiz em mãos, é muito fácil obter um fator de n, utilizando o teorema C.38. Agora suponha que a testemunha a devolvida é proveniente da linha 9. Neste caso, não temos garantias de que é possı́vel obter um fator de n a partir de a. A idéia mais óbvia é verificar se mdc(a, n) > 1, mas claramente não temos como limitar inferiormente a probabilidade desse evento. Concluı́mos que não é uma tarefa óbvia a utilização do teste de Miller-Rabin e das obstruções sucintas por ele devolvidas para se resolver eficientemente o problema da fatoração. D.3 O sistema de criptografia RSA Suponha que Alice quer enviar para Beto uma mensagem privada através de um canal de comunicação inseguro. Isto é, suponha que existe uma intrusa malintencionada Eva capaz de interceptar mensagens enviadas através do canal. Considere a seguinte solução ingênua para este problema. Alice e Beto combinam previamente o uso de uma chave, que será mantida em segredo pelos dois. Quando Alice deseja enviar uma mensagem privada para Beto, ela utiliza a chave secreta para codificar a mensagem, de modo que o texto produzido seja ininteligı́vel por um interceptador que desconheça a chave, como Eva. Beto, ao receber a mensagem codificada, utiliza a chave para decodificar a mensagem, obtendo o texto original escrito por Alice. Um jeito simples de se codificar e decodificar uma mensagem utilizando uma chave é utilizar esta como um inteiro indicando um deslocamento no alfabeto. Assim, se a chave for 3, toda letra ‘a’ da mensagem vira ‘d’ na mensagem codificada, todo ‘b’ vira ‘e’, e assim por diante. Vale lembrar que este método de criptografia, utilizado com sucesso por muitos séculos, é muito inseguro, pois é facilmente quebrado. A principal falha desta abordagem é que ela exige que se combine previamente uma chave secreta. Isso impossibilita seu uso em diversas situações em que as entidades que desejam se comunicar não se conhecem, como por exemplo no comércio eletrônico. Para contornar essa falha, Diffie e Hellman [DH76] introduziram o conceito de criptografia de chave pública. Num sistema desse tipo, o envio da mensagem transcorreria da seguinte forma. Beto teria duas chaves: uma pública e outra 125 secreta. A chave pública, diferente da secreta, seria acessı́vel a todos. Alice, antes de enviar a mensagem, utilizaria a chave pública de Beto para codificá-la. Apenas Beto, através de sua chave secreta, é capaz de decodificar a mensagem codificada enviada por Alice. Vamos descrever o sistema mais formalmente. Seja M o conjunto de mensagens possı́veis. Por exemplo, M pode ser o conjunto de todas as cadeias de caracteres com comprimento finito. Seja PB a chave pública de Beto e SB sua chave secreta. Tanto PB quanto SB definem funções bijetoras em M. Por isso, vamos chamar essas funções também de PB e SB . Dada uma mensagem M ∈ M, a mensagem codificada é dada por PB (M ), isto é, utiliza-se a chave pública para a codificação. Para decodificar tal mensagem, queremos que SB (PB (M )) = M , isto é, a decodificação utiliza a chave secreta para obter a mensagem original. O detalhe essencial é que PB e SB devem ser escolhidos de forma que seja impraticável descobrir SB apenas a partir de PB (lembre-se que qualquer um tem acesso à chave pública PB ). Um sistema com essas caracterı́sticas pode ser utilizado também para criar assinaturas digitais. Por exemplo, suponha que Alice deseja assinar a mensagem a ser enviada para Beto, de forma que ninguém seja capaz de falsificar sua assinatura e que Beto seja capaz de se certificar de que Alice foi de fato o remetente. Seja PA a chave pública de Alice e SA sua chave secreta. Tais chaves definem funções bijetoras PA e SA em M. Como devemos ter SA (PA (M )) = M , então as funções PA e SA são uma a inversa da outra, de modo que temos também PA (SA (M )) = M . Como apenas Alice tem acesso à chave SA , ela pode utilizar σ := SA (M ) como assinatura da mensagem M . Ela pode enviar o par (M, σ) a Beto que, por sua vez, pode verificar se PA (σ) = M para se certificar de que Alice foi o remetente. Desta forma, apenas Alice é capaz de gerar sua assinatura. Além disso, se de alguma forma Eva conseguiu alterar a mensagem antes de Beto recebê-la, este será capaz de detectar a invalidade da mensagem. É claro que as operações de assinatura e de codificação de uma mensagem podem ser compostas para se obter uma mensagem assinada por Alice que apenas Beto possa ler. Rivest, Shamir e Adleman [RSA78] construı́ram um sistema de criptografia de chave pública, conhecido como rsa, que se baseia na relativa facilidade de se encontrar números primos grandes e na dificuldade de se fatorar inteiros. Vamos mostrar como Beto faria para criar suas chaves no rsa. Primeiro ele escolhe aleatoriamente dois primos grandes p e q. Para tanto, basta sortear um inteiro ı́mpar grande e executar algum teste de primalidade, como o aks, ou um número suficiente de execuções do teste de Miller-Rabin. Queremos delimitar inferiormente a probabilidade de o número sorteado ser primo. Podemos utilizar 126 o seguinte resultado, conhecido como teorema dos números primos. Teorema D.6. Seja π(n) : N −→ N a função definida por π(n) := {p : p < n e p primo}. (D.7) Então π(n) ∼ n/ ln n. Portanto a probabilidade de que o inteiro sorteado seja primo se aproxima de 1/ ln n para n grande. Assim, o número esperado de sorteios necessários para se obter um primo é ln n, o que é razoável. Com os primos p e q em mãos, Beto calcula o produto n := pq. Agora ele escolhe um ı́mpar e pequeno que seja relativamente primo a φ(n) = (p−1)(q−1), onde utilizamos o teorema C.32 para calcular φ(n). Como mdc e, φ(n) = 1, então e tem um inverso multiplicativo módulo φ(n), que pode ser calculado através do algoritmo estendido de Euclides, descrito na seção C.5.1. Seja d tal inverso. A chave pública de Beto será o par (e, n). A chave secreta é (d, n). Vamos considerar que o conjunto das possı́veis mensagens é M := Zn . A função associada com a chave pública (e, n) é PB (M ) := M e mod n. (D.8) A função associada à chave secreta é: SB (M ) := M d mod n. (D.9) Ambas as funções são facilmente calculadas utilizando o algoritmo de exponenciação modular, descrito na seção C.5.2. De fato, seja β := blg nc + 1 o número de bits de n. Então todas as operações descritas acima podem ser realizadas com O(β 3 ) operações sobre bits. Temos que mostrar que tais funções satisfazem as propriedades desejadas, de acordo com nossa especificação de um sistema de criptografia de chave pública. Começamos observando que as funções PB e SB , comutam, isto é, vale que PB (SB (M )) = SB (PB (M )) para todo M ∈ M = Zn . Seja M ∈ M = Zn . Temos SB (PB (M )) ≡ M ed (mod n). Como temos ed ≡ 1 (mod φ(n)), então ed = 1 + kφ(n) = 1 + k(p − 1)(q − 1) para algum inteiro k. Se M 6≡ 0 (mod p), então k(q−1) M ed ≡ M (M p−1 ) ≡ M (1)k(q−1) ≡ M 127 (mod p) (mod p) (mod p), onde utilizamos o teorema C.25 de Fermat para passar da primeira para a segunda linha. A relação M ed ≡ M (mod p) também vale se M ≡ 0 (mod p). Analogamente, temos M ed ≡ M (mod q) para todo M ∈ Zn . Então, pelo corolário C.31 ao teorema do resto chinês, temos M ed ≡ M (mod n) para todo M ∈ Zn , como querı́amos. Observe que, se conseguirmos fatorar n = pq, então será trivial calcular φ(n) = (p − 1)(q − 1), bem como d, o inverso multiplicativo de e, módulo φ(n). Lembre-se que e faz parte da chave pública de Beto, e que d é parte da chave secreta. Assim, um algoritmo eficiente de fatoração pode ser utilizado na quebra do rsa. 128 Apêndice E Circuitos clássicos No modelo clássico de computação, vimos três tipos distintos de máquina de Turing. Especialmente importante é a MTD, que formaliza o modelo teórico que fundamenta os computadores atuais, que têm comportamentos governados pelas leis da mecânica clássica. Como conseqüência, os dispositivos computacionais modernos têm uma série de restrições em suas primitivas básicas, afetando assim o poder computacional do modelo. Porém, como sabemos que o universo segue as leis da mecânica quântica, é natural que nos perguntemos se é possı́vel construir dispositivos computacionais baseados nas propriedades da mecânica quântica. Foi a partir dessa perspectiva que surgiu a Máquina de Turing Quântica. Sucintamente, podemos dizer que a MTQ é uma MTP com amplitudes de probabilidade complexas. Além disso, tais máquinas admitem superposições de configurações e interferência, o que sugere que o modelo quântico tem possivelmente maior poder computacional. Porém, a necessidade do uso de operações unitárias devido a “imposições” da mecânica quântica acaba levantando a seguinte questão: as evoluções unitárias, obrigatórias na mecânica quântica, restringem a classe de problemas eficientemente computáveis? Para tentar esclarecer algumas dessas questões, analisamos o funcionamento dos circuitos clássicos. Em especial, mostramos que as operações realizadas no modelo clássico podem ser feitas com portas reversı́veis, provando assim que o modelo quântico é pelo menos tão poderoso quanto o clássico. Nesse capı́tulo, nosso objetivo é explicar o funcionamento das portas lógicas nos computadores atuais. Inicialmente, apresentamos o conceito de porta universal na seção E.1. Em seguida, na seção E.2, vamos mostrar como podemos analisar a complexidade de um determinado algoritmo através do circuito usado 129 para implementá-lo. Por fim, veremos na seção E.3 que é possı́vel construir uma máquina clássica que realiza computações reversı́veis. E.1 Portas universais Podemos dizer que a computação clássica envolve o cálculo de funções. Cada uma dessas funções pode ser vista, sem perda de generalidade, como uma função que tem como domı́nio o conjunto das palavras formadas pelos sı́mbolos 0 e 1, e como imagem os números 0 e 1. Como os elementos da imagem podem representar rejeição e aceitação (de uma palavra em uma linguagem, por exemplo), essas funções serão denominadas funções de decisão. Denote por n o comprimento de uma palavra dada como entrada para uma função. Suponha que tal função tem como entrada apenas palavras de comprimento n. Como o número de entradas possı́veis é 2n e o número de respostas n para cada entrada é 2, o número de funções de decisão desse tipo é 22 . Todas as funções de decisão podem ser decompostas em seqüências de operações lógicas. Estamos interessados num conjunto de operações lógicas capaz de representar todas as essas funções. Além disso, para que a construção de um dispositivo capaz de computar qualquer função de decisão seja viável, é interessante utilizar um conjunto de operadores razoavelmente sucinto. A inserção de um operador lógico para cada função seria claramente inviável para valores muito grandes de n. Um resultado conhecido da álgebra booleana, que pode ser visto no livro de Feynman [Fey96], mostra que qualquer função de decisão pode ser construı́da com as portas and e not. Claramente, qualquer combinação de portas capaz de simular essas duas tem o mesmo poder. Dizemos que um conjunto de portas com essa propriedade é um conjunto completo de operadores. Vamos descrever uma porta universal, que nada mais é do que uma porta lógica que compõe sozinha um conjunto completo de operadores. Vale destacar, porém, que a obtenção de tal porta pode ser mero preciosismo em alguns casos, pois os custos envolvidos no uso de duas portas não é necessariamente maior que o do uso de uma única porta. Como as portas and e not são suficientes para representar qualquer função de decisão, se tivermos alguma porta capaz de simular essas duas então essa porta será universal. Uma porta que serve para tal propósito é a porta nand, que é a negação da porta and. É fácil construir a porta not a partir dela (basta colocar o sinal que deseja-se negar nas entradas da porta para que a negação seja obtida), e a partir da negação podemos obter a porta and. Logo, toda função de decisão pode ser representada por algum circuito formado exclusivamente 130 por portas nand. Por fim, vale destacar que a porta nand, apesar de universal, não é reversı́vel. Quando n > 1, se a saı́da devolvida for 1 não podemos determinar a entrada recebida pela porta. Na computação clássica esse fato é de menor relevância, mas na computação quântica isso é importante, pois todas as computações envolvidas devem ser reversı́veis. Por isso, vamos comentar adiante portas universais reversı́veis para o modelo clássico. E.2 Complexidade de circuitos Conforme já dissemos anteriormente, as funções de decisão podem ser vistas como codificações de problemas de decisão. Um problema de decisão é aquele que, para toda entrada, tem como resposta 1 ou 0. No estudo da complexidade, estamos interessados em saber qual é a dificuldade de um determinado problema. A dificuldade está diretamente relacionada aos recursos que uma solução vai consumir. Quando desenvolvemos uma solução para um problema utilizando circuitos, é razoável considerar o tamanho dos circuitos montados, que é o número de portas lógicas, por exemplo, e o tempo consumido para que uma determinada entrada seja computada. O tempo consumido por um circuito está relacionado ao que chamamos de profundidade do circuito, que é o maior número de passos que um circuito que admite paralelismo deve executar para computar o valor de uma entrada. Já a largura de um circuito é o maior número de operações lógicas executadas simultaneamente. Naturalmente, cada problema possui infinitas elaborações possı́veis de circuitos que o resolvem (ou decidem). No estudo da complexidade, porém, estamos interessados em circuitos de fácil adaptabilidade. Ou seja, dado um circuito que resolve o problema para entradas de tamanho n, deve ser fácil montar um circuito para entradas de tamanho n + 1. Em geral, a facilidade está relacionada à existência de um algoritmo que consome tempo polinomial para realizar a tarefa. Analisando o crescimento do tamanho dos circuitos em uma famı́lia de circuitos que resolvem um mesmo problema, podemos definir sua complexidade. Se o crescimento desses circuitos é limitado por algum polinômio, então dizemos que o problema que estamos tratando é fácil, pois ele admite uma solução polinomial. Como podemos simular em uma máquina de Turing qualquer circuito em tempo polinomial no tamanho do circuito, concluı́mos que essa noção de facilidade coincide com a oriunda das máquinas de Turing. Ou seja, a classe de 131 problemas que podem ser resolvidos por circuitos que crescem polinomialmente de acordo com o tamanho da entrada é a classe P, já discutida anteriormente. Infelizmente, nem todos os problemas podem ser resolvidos por meio de circuitos de tamanho polinomial. Porém, existem problemas desse tipo que são interessantes. Em especial, temos problemas para os quais não se conhece solução fácil, mas cujas soluções podem ser verificadas por um circuito (ou algoritmo) polinomial. Os problemas com essas caracterı́sticas pertencem à classe NP, também já discutida. Dessa forma, estabelecemos a relação entre as classes de complexidade do modelo clássico e os circuitos que são montados para resolver os problemas. E.3 Computação reversı́vel Conforme afirmamos anteriormente, estamos interessados em construir operações reversı́veis no modelo clássico. Para isso, precisaremos de mais duas portas para construir as funções desejadas. Denominaremos estas portas fanout e exchange. A primeira servirá para gerar dois “fios” com o mesmo pulso (ou bit) que o original. Já a segunda servirá para trocar os bits entre dois fios. Conforme dissemos anteriormente, a porta nand não é reversı́vel. Da mesma forma, outras portas, como and, or, xor e outras, também não são. Como queremos construir circuitos reversı́veis, não será possı́vel utilizar tais portas. Um exemplo de porta reversı́vel é a porta not. Ao analisar a saı́da gerada por ela, sabemos qual foi o sinal recebido na entrada. Para construir o conjunto de portas necessárias para representar todas as funções de decisão, vamos utilizar, junto com a porta not (N), as portas controlled not (CN) e controlled controlle not (CCN). Estamos nos baseando nos estudos de Bennett [Ben73] sobre computadores reversı́veis. A porta CN é um dispositivo com duas entradas A e B e duas saı́das A0 0 e B . Podemos resumir o funcionamento dessa porta da seguinte maneira: o valor de A0 é sempre igual ao valor de A. Já o valor de B 0 depende dos valores de A e de B. Se A = 1, então B 0 vai ser a negação de B. Caso contrário, B 0 = B. Analisando seu funcionamento, é fácil ver que esta porta é reversı́vel. Além disso, podemos ver B 0 como sendo a saı́da da função xor aplicada sobre as entradas A e B. A partir de uma porta CN , podemos construir também um circuito para a função fanout e um circuito para a função exchange. Como as quatro operações que temos com as portas N e CN (not, xor, fanout e exchange) não são suficientes para representar todas as funções, precisaremos de mais portas. Para que o conjunto fique completo, usaremos a 132 porta CCN . O funcionamento da porta CCN é muito parecido com o da CN . Essa porta tem três entradas, A, B e C, e três saı́das, A0 , B 0 e C 0 . Analogamente à porta CN , teremos A0 = A e B 0 = B. Já o valor de C 0 dependerá do valor de A e B. Se A = B = 1, então C 0 terá o valor inverso de C. Caso contrário, C 0 = C. Esta porta é bastante poderosa. Se colocarmos sinal 1 na porta A, temos que B, C, B 0 e C 0 formam uma porta CN . Além disso, ao colocar sinal 0 em C, obtemos uma porta and, tendo como entrada A e B e como saı́da C 0 . Neste ponto, já temos as portas and, not, fanout e exchange, que são suficientes para o que queremos. Logo, chegamos a um conjunto de portas que podem montar qualquer função de decisão desejada e que são todas reversı́veis. Isso sugere que o poder computacional desses componentes não é inferior ao poder dos componentes usados para operações não-reversı́veis. 133 Referências Bibliográficas [AGP94] W.R. Alford, A. Granville, and C. Pomerance. There are infinitely many Carmichael numbers. Ann. of Math. (2), 139(3):703–722, 1994. [AH92] L.M. Adleman and M.-D. Huang. Primality testing and two dimensional abelian varieties over finite fields. volume 1512 of Lecture Notes in Mathematics. Springer, Berlin, 1992. [AKS02a] M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Preprint. http://www.cse.iitk.ac.in/news/primality.pdf, 2002. [AKS02b] M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Revised. http://www.cse.iitk.ac.in/news/primality_v3.pdf, 2002. [BBBV97] C.H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [BBC+ 95] A. Barenco, C.H. Bennett, R. Cleve, D.P. DiVincenzo, N.H. Margolus, P.W. Shor, T. Sleator, J.A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457–3467, 1995. [Ben73] C.H. Bennett. Logical reversibility of computation. IBM J. Res. Develop., 17:525–532, 1973. [Ber98] D.J. Bernstein. Detecting perfect powers in essentially linear time. Math. Comp., 67(223):1253–1283, 1998. 134 [BH97] G. Brassard and P. Høyer. An exact quantum polynomial-time algorithm for Simon’s problem. In Israel Symposium on Theory of Computing Systems, pages 12– 23, 1997. [BLP93] J.P. Buhler, H.W. Lenstra, Jr., and C. Pomerance. Factoring integers with the number field sieve. In The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 50–94. Springer, Berlin, 1993. [Bre89] D.M. Bressoud. Factorization and Primality Testing. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1989. [BV93] E. Bernstein and U. Vazirani. Quantum complexity theory. In Proceedings of the 25th ACM Symposium on the Theory of Computation, pages 11–20, New York, 1993. ACM Press. [BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. [Car12] R.D. Carmichael. On composite numbers p which satisfy the Fermat congruence ap−1 ≡ 1 (mod p). Amer. Math. Monthly, 19:22–27, 1912. [CEMM98] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci., 454(1969):339– 354, 1998. [Chu33] A. Church. A set of postulates for the foundation of logic. Annals of Mathematics, 25:839–864, 1933. [Chu36] A. Church. An unsolvable problem of elementary number theory. Annals of Mathematics, 58:345–363, 1936. [CLRS01] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, second edition, 2001. [Cob65] A. Cobham. The intrinsic computational difficult of functions. 135 In Y. Bar-Hillel, editor, Logic, Methodology and Philosophy of Science, pages 24–30. North-Holland, 1965. [Coo71] S. Cook. The complexity of theorem proving procedures. In Proc. 3rd ACM Symposium on Theory of Computing, pages 151– 158, 1971. [Cop93] D. Coppersmith. Modifications to the number field sieve. J. Cryptology, 6(3):169–180, 1993. [Cou00] S.C. Coutinho. Números inteiros e criptografia RSA, volume 2 of Série de Computação e Matemática. Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, second edition, 2000. [Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. London Ser. A, 400(1818):97–117, 1985. [Deu89] D. Deutsch. Quantum computational networks. Proc. Roy. Soc. London Ser. A, 425(1868):73–90, 1989. [DH76] W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Trans. Information Theory, IT-22(6):644–654, 1976. [Edm65] J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965. [EJ96] A. Ekert and R. Jozsa. Quantum computation and Shor’s factoring algorithm. Rev. Mod. Phys., 68(3), 1996. [Fey82] R. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6 & 7):467–488, 1982. [Fey96] R. Feynman. Feynman Lectures in Computation. Addison-Wesley Publishing Company, 1996. 136 [Fra89] J.B. Fraleigh. A First Course in Abstract Algebra. Addison-Wesley Publishing Company, fourth edition, 1989. [GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NPCompleteness. Freeman, 1979. [GK86] S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 316–329. ACM Press, 1986. [GKP94] R.L. Graham, D.E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley Publishing Company, Reading, MA, second edition, 1994. A foundation for computer science. [Göd31] K. Gödel. On formally undecidable propositions of Principia Mathematica and related systems. Monatshefte fur Math. und Physik, 38:173–198, 1931. [Hal42] P.R. Halmos. Finite Dimensional Vector Spaces. Annals of Mathematics Studies, no. 7. Princeton University Press, Princeton, N.J., 1942. [HW54] G.H. Hardy and E.M. Wright. An Introduction to the Theory of Numbers. Oxford, at the Clarendon Press, 1954. 3rd ed. [Joy] D.E. Joyce. Mathematical problems by professor David Hilbert. http://aleph0.clarku.edu/~djoyce/hilbert/problems.html. [Kar72] R.M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103. Plenum, New York, 1972. [Kle36] S. Kleene. General recursive functions of natural numbers. 137 Mathematische Annalen, 112:727–742, 1936. [Kle52] S. Kleene. Introduction to Metamathematics. D. Van Nostrand, Princeton, NJ, 1952. [Knu81] D.E. Knuth. The Art of Computer Programming. Vol. 2. Addison-Wesley Publishing Co., Reading, Mass., second edition, 1981. Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing. [KO62] A. Karatsuba and Y. Ofman. Multiplication of multidigit numbers by automata (em russo). Dokl. Akad Nauk SSSR, 145:293–294, 1962. [KO63] A. Karatsuba and Y. Ofman. Multiplication of multidigit numbers by automata. Soviet Physics-Doklady, 7:595–596, 1963. [Len87] H.W. Lenstra, Jr. Factoring integers with elliptic curves. Ann. of Math. (2), 126(3):649–673, 1987. [Lev73] L.A. Levin. Universal sorting problems. Problems of Information Transmission, 9:265–266, 1973. [LLMP93] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, and J.M. Pollard. The number field sieve. In The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 11–42. Springer, Berlin, 1993. [Lom02] S.J. Lomonaco, Jr. A Rosetta Stone for quantum mechanics with an introduction to quantum computation. In Quantum computation: a grand mathematical challenge for the twenty-first century and the millennium (Washington, DC, 2000), volume 58 of Proc. Sympos. Appl. Math., pages 3–65. Amer. Math. Soc., Providence, RI, 2002. [Mil75] G.L. Miller. Riemann’s hypothesis and tests for primality. In Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N.M., 1975), pages 234–239. Assoc. Comput. Mach., New York, 1975. 138 [Mil76] G.L. Miller. Riemann’s hypothesis and tests for primality. J. Comput. System Sci., 13(3):300–317, 1976. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). [MK01] C.G. Moreira and Y. Kohayakawa. Tópicos em combinatória contemporânea. Publicações Matemáticas do IMPA. Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 2001. o 23 Colóquio Brasileiro de Matemática. [MM04] D.C. Marinescu and G.M. Marinescu. Lectures on quantum computing. http://www.cs.ucf.edu/~dcm/Fall2003Class-QC/ QCTextBookIndex.htm, 2004. [Mon80] L. Monier. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoret. Comput. Sci., 12(1):97–108, 1980. [MR95] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995. [Pap94] C.H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. [Pol93] J.M. Pollard. Factoring with cubic integers. In The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 4–10. Springer, Berlin, 1993. [Pom96] C. Pomerance. A tale of two sieves. Notices Amer. Math. Soc., 43(12):1473–1485, 1996. [Pos36] E. Post. Finite combinatory process. Journal of Symbolic Logic, 1:103–105, 1936. [Pra75] V.R. Pratt. Every prime has a succinct certificate. SIAM J. Comput., 4(3):214–220, 1975. [Pre04] J. Preskill. 139 Lecture notes for Physics 219/Computer Science 219. http://www.theory.caltech.edu/people/preskill/ph229, 2004. [Pru81] E. Prugovečki. Quantum Mechanics in Hilbert Space, volume 92 of Pure and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, second edition, 1981. [Rab80] M.O. Rabin. Probabilistic algorithm for testing primality. J. Number Theory, 12(1):128–138, 1980. [Ros00] K.H. Rosen. Elementary Number Theory and its Applications. Addison-Wesley Publishing Company, Reading, MA, fourth edition, 2000. [RP00] E. Rieffel and W. Polak. Introduction to quantum computing. ACM Computing Surveys, 32(3):300–335, 2000. [RSA78] R.L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21(2):120–126, 1978. [Sav70] W.J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970. [Sch82] A. Schönhage. Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients. In Computer algebra (Marseille, 1982), volume 144 of Lecture Notes in Comput. Sci., pages 3–15. Springer, Berlin, 1982. [Sho94] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), pages 124–134. IEEE Comput. Soc. Press, Los Alamitos, CA, 1994. [Sho97] P.W. Shor. 140 Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. [Sim97] D.R. Simon. On the power of quantum computation. SIAM J. Comput., 26(5):1474–1483, 1997. [SS71] A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing (Arch. Elektron. Rechnen), 7:281–292, 1971. [TI97] L.N. Trefethen and D. Bau III. Numerical Linear Algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. [Tur36] A. Turing. On computable numbers with an application to the entscheidungsproblem. Proc. London Math. Soc., 2:230–265, 1936. [Tur37] A. Turing. Rectifications to ‘on computable numbers. . .’. In Proc. London Mathematical Society, volume 4, pages 544–546, 1937. 141 Índice Remissivo eiθA , 13 eiθ , 13 secreta, 125 circuitos quânticos, 12 combinação linear inteira, 101 composto, 101 comutativo, 103 criptografia, 118 curvas elı́pticas, 118 abeliano, grupo, 103 adjunto, operador, 92 AKS, 119 algoritmo de Euclides, 113 de Monte Carlo, 119 de Adleman e Huang, 119 de Goldwasser e Kilian, 119 de Las Vegas, 119 estendido de Euclides, 115 amplitude, 11, 20, 97 assinatura, 126 associatividade, 103 auto-adjunto, operador, 92 autoespaço, 92 autovalor, 92 autovetor, 92 decomposição ortogonal, 91 desigualdade triangular, 87 Dirac, notação de, 87 distância, 87 distribuição geométrica, 42 divisı́vel, 100 divisão, 101 divisibilidade, 100 divisor, 100 comum, 101 não-trivial, 100 trivial, 100 base ortonormal, 90 bit quântico, 11 bra, 89 elemento gerador, 106 identidade, 103 emaranhamento quântico, 28 entangled state, 28 EPR, 29 escala, matriz de, 16 esfera de Bloch, 15 Poincaré, 15 espaço com produto interno complexo, 86 caixa preta, 34 Carmichael números de, 120 Cauchy, seqüência de, 88 Cauchy-Schwarz, desigualdade de, 87 certificado sucinto, 118 chave, 125 pública, 125 142 completo, 88 de Hilbert, 88 de Hilbert conjugado, 89 de Hilbert dual, 89 vetorial, 86 espectro, 92 estado emaranhado, 28 EPR, 29 quântico, 96 estados básicos, 11, 20, 97 Euclides algoritmo de, 113 algoritmo estendido de, 115 recursão de, 102 Euler, função totiente de, 105 evolução, 97 exponenciação modular, 115 cı́clico, 106 comutativo, 103 finito, 103 multiplicativo módulo n, 104 ordem de, 103 Hadamard, matriz de, 12 hermitiana, matriz, 92 idempotente, operador, 92 identidade, 103 inverso, 103 ket, 87 largura do circuito, 131 Las Vegas, 119 lei do paralelogramo, 87 Leibniz, teste de, 120 limitado, operador linear, 91 linear, 89 logaritmo discreto, 107, 111 Lucas, teste de, 117 fóton, polarização, 98 fator, 100 fator de fase global, 17, 97 relativa, 97 fatoração, 103, 113, 117 fechamento, 103 Fibonacci, números de, 114 função balanceada, 34, 37 constante, 34, 37 dois-para-um, 40 linear, 89 multiplicativa, 109 totiente, 105, 109 funções de decisão, 130 funcional, 89 máximo divisor comum, 101 módulo, 101 múltiplo, 100 matriz de Hadamard, 12 matrizes de Pauli, 16 medição, 11, 21, 98 Miller-Rabin, 119 Monte Carlo, 119 mudança de fase, matriz de, 16 multiplicação escalar, 86 multiplicativa, 109 número de Carmichael, 120 negação, matriz de, 17 norma de um operador linear, 91 de um vetor, 87 de uma matriz, 91 general number field sieve, 118 gerador, 106 grupo, 103 abeliano, 103 aditivo módulo n, 104 observável, 97 143 obstrução sucinta, 117 operação binária, 103 operações elementares, 113 primitivas, 113 sobre bits, 113 operador, 97 linear, 91 ordem, 103, 106 ortogonais, vetores, 89 ortonormais, vetores, 89 raio, 96 raiz primitiva, 107 raiz quadrada de 1, 112 ray, 96 recursão de Euclides, 102 registrador quântico, 19 relativamente primos, 101 repeated squaring, 116 repetição de quadrados, 116 representação de um vetor numa base, 90 resto, 101 reversı́vel, 23 rotação, 17 rotação, matriz de, 16 RSA, 118, 126 par EPR, 29 paralelismo quântico, 30 Parseval, identidade de, 90 Pauli, matrizes de, 16 perı́odo, 107 phase shift, 17 polaróide, 98 porta quântica, 12, 23 positivo, operador linear, 91 primo, 101, 103 relativamente, 101 primos entre si, 101 problema da fatoração, 117 da primalidade, 117 produto externo, 89 interno, 86 tensorial, 20, 94 profundidade do circuito, 131 projeção, 92 projetor, 92 pseudoprimo, 120 semi-definido, operador linear, 91 seqüência infinita, convergência de, 88 sistema quântico, 96 composição de, 96 soma direta, 91 subgrupo, 105 cı́clico, 106 gerado, 106 próprio, 105 superposição, 11, 20, 97 teste de Miller-Rabin, 120 teste de primalidade, 119, 120 testemunha, 120 totiente, 105, 109 traço de uma matriz, 93 vetor bra, 89 vetor ket, 87 quantum entanglement, 28 quantum parallelism, 30 qubit, 11, 15 quebra do RSA, 128 quociente, 101 144