Computação Quântica/Capítulo 3
Introdução a Ciência da Computação
Mais sobre Classes de Complexidade (3.2.4)
- O estudo de classes de complexidade na computação é essencial para o entendimento do poder de resolver problemas;
- Para compreender quão poderoso venha a ser um computador quântico devemos entender os problemas por este solúveis e verificar a relação das classes de complexidade nestes termos;
Classes de Complexidade
- São definidas por três variáveis: os recursos (tempo de computação, espaço na fita, quantidade de movimentação do cabeçote da máquina, etc), o tipo de problemas, e o modelo computacional em questão (Máquina de Turing determinística, MT não determinística, computador quântico, etc).
- Até agora o interesse maior foi em examinar as classes com recursos no tempo. Agora vamos examinar a classe PSPACE que se refere a problemas computáveis em uma máquina de turing, sem limite no tempo mas com uma quantidade polinomial de espaço.
- Não é provado que
- Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: . Percebamos que se: existem problemas eficientemente solúveis por um computador quântico, mas não por um computador clássico, pode-se concluir que: .
- A relação entre classes é conhecida: (Em \cite{complexidade-papa}, seção 7.3 encontra-se boas explicações sobre grande parte desta relação)
\end{itemize}
Tratando problemas não computáveis
- Existem duas formas de lidar com problemas NP-Completos ou de outra classe não computável? Duas abordagens possíveis são: reduzir o problema a casos especiais mais plausíveis de computação, ou mudar a natureza do problema considerado.
- A segunda abordagem remete a um importante conceito: A redução de problemas em outros.
- Em \cite{complexidade-papa} capítulo 8, toda uma teoria sobre Redução é descrita. Segue uma idéia inicial;
- Redução sejam A e B problemas, B é redutível a A se existe uma transformação R (de computação fácil - no espaço) em que, para todo input x de B é possível a produção de um R(x) que resolva A.
- Desta forma, a computação de B se reduz a geração de R(x) e a computação de A.
- A é ao menos da ordem de B.
- Um exemplo: Seja uma MT probabilística, que decide a próxima ação jogando uma moeda. Tal máquina M decide linguagens . Se então M aceita x com uma probabilidade de no mínimo e se então M rejeita x com probabilidade de no mínimo .
- Uma importante observação sobre o exemplo acima é que se o algoritmo for repetido algumas vezes a probabilidade de sucesso pode ser essencialmente 1.
- BPP pode ser considerada a classe realmente computável por máquinas clássicas com uma equivalente BQP no estudo de máquinas quânticas.