Computador quântico
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, 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, 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.
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.
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.
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.
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: Se existissem n qubits, então esta tabela teria 2n 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.
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.
