Em mecânica quântica, é possível que uma partícula esteja em dois ou mais estados ao mesmo tempo. Um computador clássico tem uma memória feita de bits. Um computador quântico mantém um conjunto de qubits. 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. 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 computador quântico poderia resolver este problema muito rapidamente, 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 ú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. 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. 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. 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. 1994 - Peter Shor, no Bell Labs da AT&T em Nova Jersey, descobriu um excelente algoritmo. 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. Em 1999 no MIT foram construídos os primeiros computadores quânticos baseados em montagem térmica. Um computador quântico pode atualmente armazenar 16 valores analógicos em pares para formar oito números complexos. Um computador quântico pode colocar-se na super posição de assumir os oito estados simultaneamente. Neste sentido, um computador quântico de 3-qubit tem muito mais memória do que um computador clássico de 3-bit. 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). Para mais detalhes na seqüê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 oito números complexos. A escolha da interpretação não influi no cálculo, ou no comportamento do computador quântico.
