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.

Entrada " Set Theory " na Stanford Encyclopedia of Philosophy

A entrada, assinada por Thomas Jech, traz uma excelente descrição do estado da arte dos conjuntos, as principais questões técnicas e as questões filosóficas relacionadas.
Leia aqui.

Meu curso de Teoria dos Conjuntos (Doutorado em Filosofia/Logica, IFCH. UNICAMP)

HF005 Teoria de Conjuntos I, turma A
Prof. Walter Carnielli

Segundas-feiras, 14h às 18h
CLE, sala 211

Ementa:

Disciplina introdutória sobre a teoria axiomática dos conjuntos,
partindo de uma visão geral da teoria intuitiva (ingênua) da noção de
conjuntos até um estudo detalhado da axiomática de Zermelo-Fraenkel
(ZF) e seu papel na fundamentação e na filosofia da matemática. Inclui
ordinais, cardinais, indução e recursão transfinita, o Axioma da Escolha
e a Hipótese do Contínuo e seu estatuto filosófico

Programa:
1. Histórico. Teoria ingênua dos conjuntos e seus problemas.
2. Os axiomas básicos de ZF. Produtos cartesianos. Funções e relações.
3. Relações de ordem. Relações de equivalência.
4. Funções em ZF. Equipolência.
5. Conjuntos finitos e infinitos.
6. Outros axiomas de ZF.
7. Introdução aos ordinais.
8. Indução e recursão transfinita. Aplicações.
9. Aritmética ordinal.
10. Cardinais.
11. Aritmética cardinal.
12. A Hipótese do Contínuo e o Axioma da Escolha
13. O Axioma da Fundacionalidade e o Axioma da Construtibilidade
14. AS questões da consistência e independência:
15. Teoria dos conjuntos e os fundamentos da matemática

Bibliografia:
Primária

Hrbacek, Karel Jech, Thomas
Introduction to set theory.
Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc., New York, terceira edição (1999)
ISBN: 0-8247-7915-0

Auxiliar
- Coniglio, M.E., Teoria Axiomática de Conjuntos: uma Introdução. Notas
de aula. Disponível aqui.


- Di Prisco, C.A., Una Introducción a la Teoría de Conjuntos, Coleção
CLE,vol. 20, UNICAMP (1997).

- Enderton, H.B., Elements of Set Theory. Academic Press (1977).

- Devlin, K., The Joy of Sets: Fundamentals of Contemporary Set Theory
Springer; 2 edição (1993) ISBN-13: 978-0387940946

- Suppes, P., Axiomatic Set Theory. Dover (1972).


Calendário

Março
05 – Conjuntos, Axiomas e Operações sobre Conjuntos: Cap. 1 (pp. 1-15)
12 – Pares Ordenados, Relações e Funções: Cap. 2, seções 1,2,3 (pp. 17-29)
19 – Partições e Ordem: Cap.2, seções 4, 5 (pp. 29-38)
+ Números Naturais: Cap.3, seção 1 (pp. 39-42)
26 – Propriedades dos Naturais, Recursão e Aritmética: Cap 3, seções 2, 3, 4
(pp. 42-54)

Abril
02 – Estruturas: Cap 3, seção 5 (pp. 55-61) + Cardinalidade, Conjuntos Finitos e
Enumeráveis: Cap 4, seções 1, 2, 3 (pp. 65-79)
09 – Ordens Lineares, Ordens Completas e Conjuntos Não-Enumeráveis:
Cap. 4, seções 4, 5, 6 (pp. 79-92)

16 – Aritmética Cardinal: Cap. 5, seções 1, 2 (pp. 93-101)
23 – Primeira prova

Maio
07 – Ordinais e o Axioma da Substituição: Cap. 6, seções 1, 2,3 (pp. 103-114)
14 – Indução Transfinita e Aritmética Ordinal: Cap. 6, seções 4, 5 (pp. 114-123)
21 – Os Alephs: Cap. 7, seções 1, 2 (pp. 129-136)
28 – O Axioma da Escolha: Cap. 8, seção 1 (pp. 137-144)

Junho
04 – Aprofundando a Aritmética dos Cardinais: Cap. 9, seções 1, 2, 3 (pp. 155-169)

Tópicos adicionais:

11 - O Axioma da Fundacionalidade: Cap. 14, seções 1, 2, 3(pp. 251-262)
18- Consistência e Independência: A Hipótese do Contínuo, o Axioma da Escolha
e o Axioma da Construtibilidade: Cap. 14, seção 2 (pp. 270-277)
25 - Reserva

Julho
02 -Segunda prova