miniatura|direita|A esfera de Bloch é uma representação de um qubit, o bloco de construção fundamental de computadores quânticos.
Na ciência da informação quantica, o computador quântico é um dispositivo computacional que executa cálculos fazendo uso direto de propriedades da mecânica quântica, tais como interferência e sobreposição (o bit pode ser 0 e 1 simultaneamente), baseada na proposta do físico Richard Feynman em 1981. 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 em 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 possibilita a quebra da maioria dos sistemas de criptografia usados atualmente. Contudo, o computador quântico também oferece 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.
Estrutura 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.
Poder computacional thumb|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. blueprint for demonstrating quantum supremacy with superconducting qubits por C. Neil et al Science Vol. 360, edição 6385, pp. 195-199 DOI: 10.1126/science.aao4309 (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.
História 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. esquerda|250px| O suspeito relacionalmente da BQP a outros espaços de problema.|thumb