Computador quântico

Origem: Wikipédia, a enciclopédia livre.

Um computador quântico é um dispositivo que executa cálculos fazendo uso direto de propriedades da mecânica quântica, tais como sobreposição e emaranhamento. Teoricamente, computadores quânticos podem ser implementados e o mais desenvolvido atualmente trabalha com poucos qubits de informação. O principal ganho desses computadores é a possibilidade de resolver em tempo eficiente, alguns problemas que na computação clássica levariam tempo impraticável, como por exemplo: fatoração, busca de informação em bancos não ordenados, etc.

Computadores quânticos são diferentes de computadores clássicos tais como computadores de DNA e computadores baseados em transístores, ainda que estes utilizem alguns efeitos da mecânica quântica.

[editar] A estrutura dos computadores quânticos

Em mecânica quântica, é possível que uma partícula esteja em dois ou mais estados ao mesmo tempo. Uma famosa metáfora denominada o gato de Schrödinger expressa esta realidade: imagine que um gato está dentro de uma caixa, com 50% de chances de estar vivo e 50% de chances de estar morto, para a mecânica quântica, até abrirmos a caixa e verificarmos como está o gato, ele deve ser considerado vivo e morto ao mesmo tempo. A esta capacidade de estar simultaneamente em vários estados chama-se superposição.

Um computador clássico tem uma memória feita de bits. Cada bit guarda um "1" ou um "0" de informação. Um computador quântico mantém um conjunto de qubits. Um qubit pode conter um "1", um "0" ou uma sobreposição destes. Em outras palavras, pode conter tanto um "1" como um "0" ao mesmo tempo. O computador quântico funciona pela manipulação destes qubits.

Um computador quântico pode ser implementado com alguns sistemas com partículas pequenas, desde, é claro, que obedeçam a natureza descrita pela mecânica quântica. Podem-se construir computadores quânticos com átomos que podem estar excitados e não excitados ao mesmo tempo, ou com fótons que podem estar em dois lugares ao mesmo tempo, ou com prótons e neutrons que podem ter um spin ao mesmo tempo "para cima" e "para baixo". Com a utilização destes, ao invés de nano-cristais de silício, o computador quantico é menor que um computador tradicional.

Uma molécula microscópica pode conter muitos milhares de prótons e nêutrons, e pode ser usada como computador quântico com muitos milhares de qubits. A grande questão a ser resolvida hoje para a implementação destas máquinas, é a capacidade de controlar este sistema, já que as interferências são grandes e o tempo de coerência dos estados das partículas pequeno.

[editar] O poder dos computadores quânticos

Encontrar todos os factores primos de um número grande pode ser uma tarefa muito difícil. Um computador quântico poderia resolver este problema muito rapidamente. Se um número tiver n bits (ou seja, se tiver o comprimento de n dígitos quando escrito em binário), então um computador quântico com um pouco mais de 2n qubits poderá encontrar os seus factores. Também poderá solucionar um problema relacionado, chamado problema do logaritmo discreto. Esta capacidade poderia permitir a um computador quântico quebrar qualquer dos sistemas criptográficos actualmente em uso. A maior parte das cifras de chave pública mais populares poderiam ser quebradas com rapidez, incuindo formas da cifras RSA, ElGammal e Diffie-Helman. Estas cifras são utilizadas para proteger páginas web seguras, email encriptado e muitos outros tipos de dados. A quebra destes códigos poderia ter um impacto significativo. A única forma de tornar seguro um algoritmo com o RSA seria tornar o tamanho da chave maior do que o maior computador quântico que pudesse ser construído. Parece provável que possa sempre ser possível construir computadores clássicos com mais bits que o número de qubits no maior computador quântico, e se se verificar que isto é verdade, então algoritmos como o RSA poderão permanecer seguros.

Se um computador quântico fosse baseado nos prótons e nêutrons de uma molécula, seria talvez demasiado pequeno para ser visível, mas poderia factorizar números inteiros com milhares de bits. Um computador clássico a correr algoritmos conhecidos também poderia factorizar estes números. Mas para o conseguir fazer antes que o sol desaparecesse, teria de ser maior que universo conhecido. Seria algo inconveniente construí-lo.

Não surpreendentemente, os computadores quânticos poderiam também ser úteis para correr simulações de mecânica quântica. O aumento de velocidade poderia ser tão grande como para factorizações. Isto poderia trazer grandes benefícios a muitos físicos.

Atualmente se sabe que essa vantagem dos computadores quânticos existe apenas para os três problemas seguintes: fatoração, logaritmo discreto e simulações de física quântica. Existe outro problema em que os computadores quânticos têm uma vantagem menor, porém menos significativa. É a busca quântica em base de dados, à qual é referida algumas vezes por square root speedup.

Suponha que existe um problema como encontrar a senha para desencriptar um arquivo. O problema possui as quatro propriedades:

• A única forma de resolvê-lo é chutar respostas repetidamente e verificá-las
• Existem n respostas possíveis para se verificar
• Toda resposta possível gasta o mesmo tempo de verificação
• Não existem pistas indicando quais respostas sejam melhores. Gerar as possibilidades randomicamente é tão eficiente quanto verificá-las em alguma ordem especial

Problemas com todas as quatro propriedades levarão uma média de n/2 tentativas para encontrar a resposta usando um computador clássico. O tempo gasto por um computador quântico seria proporcional à raiz quadrada de n. Isso pode representar um ganho enorme, encurtando o tempo para solução de alguns problemas de anos para segundos. Essa vantagem pode ser usada para atacar cifras simétricas tais como o 3DES e AES. Porém a defesa contra tal ataque é fácil, consistindo em dobrar o tamanho da chave para a cifra. Há também mais métodos complicados para tornar uma comunicação segura, tal como usar criptografia quântica.

Atualmente não há outro problema prático conhecido para o qual os computadores quânticos mostrem um ganho expressivo sobre os computadores clássicos. As pesquisas continuam, e mais problemas podem, então, ser identificados.

[editar] A história dos computadores quânticos

1981 - Richard Feynman elaborou a primeira proposta de utilizar um fenômeno quântico para executar rotinas computacionais. Foi numa palestra apresentada na Primeira Conferência de Computação Física no MIT. Ele mostrou que um computador tradicional levaria um tempo extremamente longo para simular um simples experimento de física quântica. Por outro lado, sistemas quânticos simples podem executar enormes quantidades de cálculos num curto espaço de tempo. Poderia ser possível utilizar essa capacidade para se calcular algo útil.

1985 - David Deutsch, na Universidade de Oxford, descreveu o primeiro computador quântico universal. Exatamente como uma Máquina de Turing pode simular outra máquina de Turing eficientemente, um computador quântico universal é capaz de simular o funcionamento de outro computador quântico com complexidade, no máximo, polinomial. Isso fez crescer a esperança de que um dispositivo simples seja capaz de executar muitos algoritmos quânticos diferentes.

1994 - Peter Shor, no Bell Labs da AT&T em Nova Jersey, descobriu um excelente algoritmo. Ele permite a um computador quântico fatorar grandes inteiros rapidamente. Ele resolve tanto o problema da fatoração quanto o problema do logaritmo discreto. O Algortimo de Shor poderia, em teoria, quebrar muitos dos sistemas criptográficos em uso atualmente. Essa descoberta criou um enorme interesse nos computadores quânticos, até fora da comunidade acadêmica.

1996 - Lov Grover, no Bell Labs, descobriu o algoritmo de pesquisa em bases de dados quânticas. O speedup de raiz quadrada não foi tão dramático quanto o speedup para fatoração, logs discretos, ou simulações físicas. Mas o algoritmo poderia ser aplicado a uma variedade muito maior de problemas. Qualquer problema que tinha que ser resolvido por uma pesquisa de força bruta, aleatória, podia agora ter um speedup de raiz quadrada.

1996(?) - ???? Proposto o primeiro esquema para correção de erro quântico. Isso é uma aproximação a computadores quânticos que podem processar grandes números de qubits por longos períodos de tempo. Erros sempre são introduzidos pelo meio, mas uma forma de correção de erros quânticos pode sobrescrevê-los e corrigí-los. Esta pode ser a chave tecnológica para a produção em larga escala de computadores quânticos que realmente funcionam. Estas propostas adiantadas tiveram um certo número de limitações. Poderiam corrigir alguns erros, mas não erros que ocorrem durante o próprio processo da correção. Algumas melhorias foram sugeridas, e a pesquisa sobre esta continua ativa.

19?? - ???? no MIT foram construído os primeiros computadores quânticos baseados em montagem térmica. O computador é , na verdade, uma única molécula pequena, que armazena qubits na rotação (spin) de seus protons e nêutrons. Trilhões e trilhões destas moléculas podem flutuar em um copo da água. O copo está colocado em um equipamento de ressonância magnética nuclear, similar à imagem por ressonância magnética das máquinas usadas nos hospitais. Este conjunto do room-temperature (' ' thermal ' ') das moléculas (' ' ensemble ' ') tem quantidades maciças de redundância, que permite que mantenha coerência muito melhor do que muitos outros sistemas propostos.

O maior computador quântico construído até 2001 tem 7 (????) qubits.

[editar] Como trabalha

Um computador clássico com três bits de memória pode apenas armazenar três caracteres (uns ou zeros). Num determinado momento, pode conter os bits "101". Um computador quântico pode atualmente armazenar 16 valores analógicos em pares para formar 8 números complexos. Em um dado instante, ele poderia conter isto:

Se existissem n qubits, então esta tabela teria 2 linhasⁿ. Para um n nas centenas, isso seriam mais linhas do que os átomos conhecidos no universo.

A primeira coluna mostra todos os estados possíveis para os três bits. Um computador clássico apenas suporta um destes padrões de cada vez. Um computador quântico pode colocar-se na super posição de assumir os 8 estados simultaneamente. A segunda coluna mostra a "amplitude" para cada um dos 8 estados. Estes 8 números complexos são uma imagem dos conteúdos de um computador quântico num determinado momento. Durante a computação, estes 8 números irão modificar e interagir uns com os outros. Neste sentido, um computador quântico de 3-qubit tem muito mais memória do que um computador clássico de 3-bit.

No entanto, não existe nenhuma forma de ver directamente estes 8 números. Quando o algoritmo é terminado, é feita uma única medida. A medida fornece uma simples linha de 3-bit, e elimina todos os 8 números complexos. A linha fornecida é gerada aleatoriamente. A terceira coluna da tabela calcula a probabilidade de cada linha possível. Neste exemplo, há uma probabilidade de 14% de que a linha fornecida seja "000", uma de 4% de que seja "001", e assim por diante. Cada probabilidade é encontrada com a execução do quadrado do módulo do número complexo (ou a multiplicação do complexo pelo seu conjugado - dá no mesmo). O quadrado do módulo de (a+ib) é (a²+b²). As 8 probabilidades somam até 1.

Geralmente, um algoritmo num computador quantico irá dar início a todos os números complexos de modo a se equivalerem a valores, por isso todos os estados terão probabilidades equivalentes. A lista de números complexos pode ser vista como um vector de 8 elementos. Em cada passo do algoritmo, esse vector é modificado ao multiplicá-lo por uma matriz. A matriz advém da física da própria máquina, e será sempre invertivél, e irá garantir que as probabilidades continuem a somar até 1 (ou seja, a matriz será sempre ortogonal).

Para uma máquina térmica completa, a operação é realizada disparando um curto pulso de radiação no recipiente de moléculas. Diferentes tipos de pulsos resultam em diferentes matrizes. O algoritmo para o computador quântico consiste em que pulsos usar e em que ordem. A sequência é usualmente escolhida de modo que todas as probabilidades tendam a 0 exceto uma. Essa probabilidade é a que corresponde à linha que é a resposta correta. Então, quando as medidas são feitas, essa resposta é a mais provável de ser retornada. Para um dado algoritmo, as operações serão sempre feitas na mesma ordem. Não existe regras "SE ENTÃO" para variar a ordem, já que não há modo de ler a memória antes da medição no final.

Para mais detalhes na sequência de operações usada para vários algoritmos, veja computador quântico universal, Algoritmo de Shor, busca quântica em base de dados, e correção de erro quântico.

O computador quântico do exemplo acima pode ser imaginado como uma caixa preta contendo 8 números complexos. Ou, pode ser imaginado como 8 caixas pretas, cada uma contendo 1 número complexo, cada um se situando num universo alternativo diferente, e todas se comunicando uma com as outras. Essas duas interpretações correspondem a Interpretação Copenhaque e Interpretação Everett de diferentes-mundos, respectivamente, da mecânica quântica. A escolha da interpretação não influi no cálculo, ou no comportamento do computador quântico. Nos dois casos, é um vetor de 8 elementos que é modificado pela multiplicação da matriz.

[editar] Teoria da Complexidade

Esta secção mostra o que é actualmente conhecido matematicamente acerca do poder dos computadores quânticos. Descreve os resultados conhecidos da teoria da complexidade e da teoria da computação que dizem respeito aos computadores quânticos.

Uma classe de problemas que pode ser resolvida eficientemente por computadores quânticos é chamada BQP, para "bounded error, quantum, polynomial time". Computadores quânticos somente executam algoritmos aleatórios, então BQP em computadores quânticos é a parte contrária do BPP em computadores clássicos. É definido como um conjunto da problemas solucionável como um algoritmo de tempo polimonial, cuja probabilidade de errar é reduzida para metade. Um computador quântico "resolve" um problema se, para toda situação, sua resposta estará certa com alta probabilidade. Se esta solução for encontrada em tempo polinomial, então este problema é BQP.

BQP é supostamente disjunto de NP-Completo e super-conjunto de P, mas nada é conhecido. Tanto a factorização de inteiros como o logaritmo discreto pertencem a BQP. Ambos são problemas NP mas suspeita-se que não estejam em P nem em NP-Completo. Existe um comum mal-entendido que os computadores quânticos poderão resolver problemas completos em NP em tempo polinomial. Existem muitas dúvidas, mas é considerada uma afirmação falsa.

Já foi mostrado que se um computador quântico pudesse ser desenhado com operadores não-lineares, então poderia resolver problemas completos em NP em tempo polinomial e até para #P-Completos. No entanto estes formulações ainda não foram aprovados por outros colegas.

Embora computadres quânticos sejam algumas vezes mais rápidos que os computadores clássicos, eles não podem solucionar problemas que computadores clássicos não podem resolver, tendo tempo e memória suficientes. Uma Máquina de Turing pode simular um computador quântico, então um computador quântico nunca poderá solucionar um problema sem a capacidade de decisão parecido com o Problema da parada. A existência de computadores quânticos não pode refutar a tese de Church-Turing.

[editar] Outras Informações

• Computação Quântica é parte de processamento quântico da informação.

• Referência Geral:
  • Centro de Computação Quântica, Universidade de Oxford http://www.qubit.org

• Usando computadores quânticos para a simulação em sistemas quânticos:
  • Feynman, R. P. "Simulating Physics with Computers" International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. download

• Criptografia Quântica:
  • A primeira publicação no assunto: Wiesner, S. "Conjugate Coding" SIGACT News, Vol. 15, 1983, pp. 78-88; Brassard, G. and Bennett, C.H., Proceedings of the IEEE International Conference on Computer Systems and Signal Processing, 1984, p. 175 Ekert, A. "Quantum Cryptography Based on Bell's Theorem" Physical Review Letters, Vol. 67 1991 pp. 661-663.
  • The first paper ever published on this: Bennett, C. H., Brassard, G., Breidbart, S. and Wiesner, S., "Quantum cryptography, or unforgeable subway tokens", Advances in Cryptology: Proceedings of Crypto 82, August 1982, Plenum Press, pp. 267 - 275.
  • A listing of a huge number of quantum cryptography papers, with some discussion of them, is at http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html

• Universal quantum computer and the Church-Turing thesis:
  • Deutsch, D. "Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer" Proc. Roy. Soc. Lond. A400 (1985) pp. 97-117.

• Shor's factoring algorithm:
  • Shor, P. "Algorithms for quantum computation: discrete logarithms and factoring" Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20-22 Nov. 1994, IEEE Comput. Soc. Press (1994) pp. 124-134.
  • John-Pierre Seifert, "Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation," download

• Quantum database search:
  • Grover, L. K. "A Fast Quantum Mechanical Algorithm for Database Search" Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, (1996) pp. 212-219.

• Solving NP-Complete and #P-Complete problems:
  • Daniel S. Abrams (1), Seth Lloyd (2) ( (1) Dept. of Physics, MIT, (2) Dept. of Mechanical Engineering, MIT), 1988, "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems"download
  • Phil Gossett, 1988, "NP in BQP with Nonlinearity", download
  • Not peer reviewed: Yu Shi, 1999, "Entanglement Between Bose-Einstein Condensates" download