Estará a computação quântica "passando por cima" do problema P = NP?

Recentemente a empresa canadense D-Wave Systems Inc.
(dwavesys.com) realizou um teste com o "primeiro" computador
quântico de verdade, chamado "Orion", com 16 qubits (um "qubit"
é um "bit quântico") e que poderia ser produzido em escala.
Veja detalhes aqui.

O anúncio da própria empresa, porém, provoca um erro grave
(certamente querendo elevar o preço das ações) ao inventar:

"Quantum-computer technology can solve what is known as
“NP-complete” problems. "

Isso é falso. Na verdade, nem o que o "Orion" pode fazer, nem o
que o famoso "Algoritmo de Shor" para fatorar números inteiros
faz, sequer chega perto da questão "P =?NP".

Primeiro é essencial definir o que seria a "complexidade de um
computador quântico". A classe de problemas que um computador
quântico pode resolver eficientemente é chamada "classe BQP",
acrônimo para "bounded error quantum in polynomial time".

Conforme Michael Nielsen e Isaac Chuang, "Quantum Computation
and Quantum Information". Cambridge: Cambridge University Press,
(2000), ISBN 0-521-63503-9, a classe BQP é definida como a
classe de problemas solúveis em tempo polinomial (relativo aos
dados da entrada do problema) cuja probabilidade de erro é
limitada por um certo fator.

O problema da fatoração resolvido pelo algoritmo de Shor e as
façanhas do "Orion" estão certamente fora da classe P (isto é,
da classe dos problemas solúveis em tempo polinomial por uma
máquina de Turing determinística).

Contudo, é importante notar que o problema da fatoração de inteiros
não é (ou pelo menos nunca foi demonstrado ser) NP-completo: veja
"Integer factorization" da Wikepedia

Suspeita-se, mas parece que não se sabe, que estes problemas
estariam fora da classe BPP (isto é, da classe dos problemas
solúveis por uma máquina de Turing probabilística (não-determinística)
com erro limitado.

Pois bem: a classe BQP, onde estão os problemas os quais um
computador quântico pode resolver eficientemente, não é a mesma
coisa que a classe dos problemas NP-completos (nem se sabe se
são classes disjuntas ou não).

Dessa forma, é um erro imaginar que computadores quânticos podem
resolver problemas NP-completos, ou mesmo "passar por cima" da
questão "P =? NP".

Os computadores quânticos não podem fazer nada a mais do que os
clássicos podem fazer: uma máquina de Turing pode simular
perfeitamente um computador quântico (pelo menos os tratados na
literatura atualmente).

Temos então as seguintes conclusões:

1) Um computador quântico não pode resolver nenhum problema que
uma máquina de Turing não possa resolver (por exemplo, não
poderão passar a barreira do "Problema da Parada" de Turing,
(ver o capítulo 14 de Walter Carnielli e Richard L. Epstein, "Computabilidade,
funções computáveis, lógica e os fundamentos da Matemática"
Editora da UNESP, 2006, ISBN: 85-7139-650-7).

2) Consequentemente, um computador quântico não pode levar a
nenhuma objeção filosófica contra a Tese de Church (ver discussão
sobre a Tese de Church no Capítulo 24 de "Computabilidade...”).

O que pode acontecer então com a computação quântica? Na verdade,
mesmo sem tocar nas questões de fundamentos da computabilidade, o
algoritmo Shor, se implementado num computador mais potente
como o "Orion", pode levar a quebrar os códigos de criptografia
de chave pública como o famoso RSA (porque o RSA se baseia no
produto de dois primos muito grandes, e portanto quem souber
fatorar rapidamente quebra os códigos!)

Recentemente postamos (meu estudante de Doutorado Juan Carlos
Agudelo e eu) um artigo ousado, "Quantum Computation via
Paraconsistent Computation" (Juan C. Agudelo e Walter Carnielli)
que acabamos de postar em "arXiv".

Tratamos das "Máquinas de Turing Paraconsistentes" e mostramos
como estas podem simular algoritmos quânticos, resolvendo alguns
problemas lógicos do paralelismo quântico. É interessante notar
que as "Máquinas de Turing Paraconsistentes" resolvem alguns
problemas em tempo exponencialmente mais rápido que as máquinas
de Turing determinísticas usuais. Mas nunca tocamos diretamente
na questão "P =? NP".

O que sugerimos é que esta tenebrosa questão possa ser vista como "lógico
dependente", no sentido em que a solução da questão possa
passar pela lógica, e não só pela análise de algoritmos. Se assim
for, pode-se esclarecer o fato de tal questão ser independente
do "status" atual da computação, como alguns cientistas pensam.