Computador quântico

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 interferência. Teoricamente, computadores quânticos podem ser implementados e o mais desenvolvido atualmente, o D-Wave Two, trabalha com 512 qubits de informação. O principal ganho desses computadores é a possibilidade de resolver algoritmos num tempo eficiente, alguns problemas que na computação clássica levariam tempo impraticável (exponencial no tamanho da entrada), como por exemplo, a fatoração em primos de números naturais. A redução do tempo de resolução deste problema possibilitaria a quebra da maioria dos sistemas de criptografia usados atualmente. Contudo, o computador quântico ofereceria um novo esquema de canal mais seguro. 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.

A esfera de Bloch é uma representação de um qubit, o bloco de construção fundamental de computadores quânticos.

IBM Q System One, computador quântico com 20 qubits supercondutores.

A estrutura dos computadores quânticos

Na mecânica quântica é possível que uma partícula esteja em dois ou mais estados ao mesmo tempo. Um famoso exemplo é o gato de Schrödinger. Imagine que um gato esteja 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. Esta capacidade de estar simultaneamente em vários estados se chama ‘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 que obedeçam à natureza descrita pela mecânica quântica. Pode-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 nêutrons, ou ainda com elétrons e pósitrons que podem ter estados de spin ao mesmo tempo "para cima" e "para baixo" e se movimentam em velocidades próximas à da luz. Com a utilização destes, ao invés de nano-cristais de silício, o computador quântico é 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.Um dos principais problemas enfrentados pelos cientistas é que essas máquinas não operam com bits "normais", mas com qubits — ou "bits quânticos". Cada um desses qubits pode representar 0 ou 1 (como um bit convencional), mas também os dois números ao mesmo tempo, a chamada "relação fásica". É essa capacidade que aumenta exponencialmente as velocidades computacionais.

E neste ponto residem os problemas. A maioria dos erros acontece quando um qubit está nos dois dígitos: eles podem voltar a ser apenas um 0 ou 1, desacelerando a computação (o "bit flip"). Outro entrave comum é a troca de sinais nessa relação "fásica" (o "phase flip").

Apesar de existirem técnicas que localizam esses erros, até agora foi impossível detectá-los ao mesmo tempo. E o computador quântico não pode ter erros para funcionar plenamente.

A IBM conseguiu resolver esse problema.  A equipe de pesquisa da empresa criou um sistema que detecta o qubit defeituoso, usando dois parâmetros diferentes para encontrar bit flips ou phase flips. Além disso, o método consegue corrigir automaticamente a informação defeituosa.

Aparentemente simples, a solução é a chave para que processadores quânticos sejam produzidos em massa. Segundo a IBM, assim que esses chips puderem ser fabricados em larga escala, com baixo índice de erros, o caminho estará livre para esse novo tipo de computador.

O poder dos computadores quânticos

Qubits são compostos de partículas controladas (por exemplo, dispositivos que aprisionam partículas e as trocam de um estado para outro)

Um computador quântico pode executar cálculos que um computador clássico não pode. Estima-se que esse computador precisaria de cerca de 50 qubits. Um computador quântico com cerca de 60 qubits e fidelidade razoável pode ser alcançado com as tecnologias de 2018. Essa capacidade de usar esses qubits torna os computadores quânticos muito mais poderosos que os computadores existentes na solução de certos tipos de problemas, como os relacionados à inteligência artificial, desenvolvimento de medicamentos, criptografia, modelagem financeira e previsão do tempo.

Localizar todos os fatores 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 fatores. 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 atualmente em uso. A maior parte das cifras de chave pública mais populares poderiam ser quebradas com rapidez, incluindo 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 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 maior, 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 aleatoriamente é 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.

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

O suspeito relacionalmente da BQP a outros espaços de problema.

1999(?) - No MIT foram construídos 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 prótons 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.

2007 - Empresa Canadense D-Wave afirmou ter desenvolvido um computador híbrido chamado Orion que inclui um processador quântico de 16 qubits mas que também processa bits convencionais. Se confirmado, será a primeira máquina desse tipo capaz de realizar tarefas práticas, o que é surpreendente. Alguns especialistas vinham prevendo que demoraria 20 anos para que os computadores quânticos pudessem ser usados na prática. O Orion seria capaz de resolver problemas de lógica, encontrar soluções para o jogo Sudoku e pesquisar alternativas para drogas usadas na indústria farmacêutica. Em seu estágio atual, o Orion não teria aplicação comercial. Mas a D-Wave diz que vai produzir um computador de 32 qubits ainda neste ano. No primeiro semestre de 2008, a empresa pretende chegar a 512 qubits para, em menos de dois anos, atingir 1 quiloqubit. A comunidade científica recebeu o anúncio da empresa com ceticismo, por ela não ter liberado maiores detalhes do processador.

2017 - A D-Wave Systems lançou comercialmente o 2000Q, um computador quântico de 2000 qubits a módicos US$ 15 milhões. O computador quântico anterior da companhia tinha 1.000 qubits. Os sistemas de 1.000 quibits da empresa canadense estão sendo testados pelo Google, NASA e pela Lockheed Martin. O físico brasileiro  Guilherme Tosi, juntamente com uma equipe de pesquisadores da Universidade de Nova Gales do Sul, na Austrália, inventou uma nova arquitetura radical para a computação quântica, baseada em ‘flip-flop qubits’ que pode ser usada em um novo tipo de computador quântico permitindo, assim, a fabricação de processadores quânticos em larga escala pode se tornar muito mais barata – e mais fácil – do que se pensava ser possível, sem a necessidade do processo complicado da colocação precisa dos átomos de silício no processador.

2019 - Um artigo científico, brevemente publicado em um site da NASA, afirma que o Google criou um computador quântico chamado Sycamore com 54 bits quânticos chamados qubits, 53 dos quais funcionais. Os pesquisadores usaram Sycamore para realizar uma série de operações em 200 segundos que levariam um supercomputador cerca de 10.000 anos para ser concluído.

Como trabalha

Um computador clássico com três bits de memória pode apenas armazenar dois estados lógicos (uns ou zeros). Num determinado momento, pode conter os bits "000" ou "001" ou "010" ou "011" ou "100" ou "101" ou "110" ou "111". 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:

Estado	Amplitude	Probabilidade
*	(a+ib)	(a²+b²)
000	0.37 + i 0.04	0.14
001	0.11 + i 0.18	0.04
010	0.09 + i 0.31	0.10
011	0.30 + i 0.30	0.18
100	0.35 + i 0.43	0.31
101	0.40 + i 0.01	0.16
110	0.09 + i 0.12	0.02
111	0.15 + i 0.16	0.05

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 diretamente 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 quântico 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 invertível, 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.

Teoria da Complexidade

Esta seção mostra o que é atualmente conhecido pela ciência matemática 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 de problemas solucionável como um algoritmo de tempo polinomial, 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 aprovadas por outros colegas.

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

Leitura adicional

• Computação Quântica é parte de processamento quântico da informação.
• Referência Geral:
  • Livro sobre computação quântica da Sociedade Brasileira de Matemática Aplicada e Computacional download
  • 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

Ligações externas

• Quantum Computing Group
• Gershenfeld, Neil, and Isaac L. Chuang. "Quantum computing with molecules." Scientific American 278.6 (1998): 66-71.