Computação Quântica/Capítulo 3: mudanças entre as edições
imported>NiginiOliveira ("Resumo" do capítulo 3 do livro: Quantum Computation and Quantum Information de Nielsen & Chuang) |
imported>NiginiOliveira Sem resumo de edição |
||
Linha 1: | Linha 1: | ||
== Introdução a Ciência da Computação == | == Introdução a Ciência da Computação == | ||
Linha 5: | Linha 4: | ||
* O estudo de classes de complexidade na computação é excencial para o entendimento do poder de resolver problemas; | * O estudo de classes de complexidade na computação é excencial para o entendimento do poder de resolver problemas; | ||
* Para compreender quão poderoso venha a ser um | * 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 ==== | ==== Classes de Complexidade ==== | ||
Linha 11: | Linha 10: | ||
* 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). | * 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 | * 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. | ||
** | ** <math>P \subset PSPACE</math> | ||
** | ** <math>NP \subset PSPACE</math> | ||
** Não é provado que | ** Não é provado que <math>P! \subset PSPACE</math> | ||
** Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: | ** Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: <math>CQ \subset PSPACE</math>. 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: <math>P \neq PSPACE</math>. | ||
* A relação entre classes é conhecida: | * A relação entre classes é conhecida: <math>L \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP</math> (Em \cite{complexidade-papa}, seção 7.3 encontra-se boas explicações sobre grande parte desta relação) | ||
\end{itemize} | \end{itemize} | ||
==== Tratando problemas não computáveis ==== | ==== Tratando problemas não computáveis ==== | ||
* Existem duas formas de lidar com problemas | * 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. | * 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 | ** 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 - <math>O(\log{}{n})</math> 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. | ** 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. | ** A é ao menos da ordem de B. | ||
* Um exemplo: Seja uma MT probabilística, que decide a próxima ação | * Um exemplo: Seja uma MT probabilística, que decide a próxima ação ''jogando uma moeda''. Tal máquina M decide linguagens <math>L \in BPP</math>. Se <math>x \in L</math> então M aceita x com uma probabilidade de no mínimo <math>\frac{3}{4}</math> e se <math>x \notin L</math> então M rejeita x com probabilidade de no mínimo <math>\frac{3}{4}</math>. | ||
* Uma importante observação sobre o exemplo acima é que se o algoritmo for repetido algumas vezes a probabilidade de sucesso pode ser excencialmente 1. | * Uma importante observação sobre o exemplo acima é que se o algoritmo for repetido algumas vezes a probabilidade de sucesso pode ser excencialmente 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. | * 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. |
Edição das 19h49min de 11 de julho de 2005
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 é excencial 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 excencialmente 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.