Uma introdução à computação quântica para não-físicos

A observação de Richard Feynman de que certos efeitos quânticos não podem ser simulados de forma eficiente em um computador levou à especulação de que a computação, em geral, poderia ser realizada de maneira mais eficiente se utilizasse esses efeitos quânticos. Essa especulação se provou justificada quando Peter Shor descreveu um algoritmo quântico de tempo polinomial para fatoração de inteiros. Em sistemas quânticos, o espaço computacional aumenta exponencialmente com o tamanho do sistema, o que possibilita um paralelismo exponencial. Esse paralelismo poderia levar a algoritmos quânticos muito mais rápidos do que os possíveis de forma clássica. O problema é que acessar os resultados, o que requer medição, se mostra complicado e exige novas técnicas de programação não tradicionais. O objetivo deste artigo é guiar os cientistas da computação através das barreiras que separam a computação quântica da computação convencional. Introduzimos princípios básicos da mecânica quântica para explicar de onde vem o poder dos computadores quânticos e por que é difícil aproveitá-lo. Descrevemos criptografia quântica, teletransporte e codificação densa. Vários métodos para explorar o poder do paralelismo quântico são explicados. Concluímos com uma discussão sobre correção de erros quânticos.