Computação Quântica/Capítulo 3
Introdução a Ciência da Computação
Circuitos (3.1.2)
- Máquina de Turing (MT) e o modelo de circuitos são modelos computacionais equivalentes. Uma MT é similar à um algoritmo e o modelo de circuitos é semelhante a implementação real dos computadores.
- Circuitos são acíclicos e são formados por fios e portas. Os fios carregam a informação e as portas realizam tarefas computacionais simples.
- Portas lógicas são funções f: {0,1}k ->{0,1} l, onde k representa os bits de entrada e l os bits de saída.
- Funções do tipo f: {0,1}n -> {0,1}, com n bits de entrada e um único bit de saída, são conhecidas como funções booleanas e seus circuitos correspondentes são circuitos booleanos.
- Máquina de Turing e o modelo de circuitos estão ligados através do conceito de família uniforme de circuitos. Uma família de circuitos é uma coleção de circuitos, representada por {Cn}, onde n é um inteiro positivo. Um circuito Cn possui n bits de entrada e um número finito de bits de trabalho e saída.
- Uma família de circuitos é dita uma família uniforme de circuitos, se existe um algoritmo em uma MT que gere a descrição de Cn. Caso não exista uma MT que gere a descrição de Cn, esta família é dita não uniforme.
- Circuitos desempenham diversas computações. A classe de funções computáveis por uma família uniforme de circuitos, é a mesma classe de funções computáveis por MT.
Complexidade Computacional (3.2.2)
- Complexidade computacional é o estudo do tempo e do espaço necessários para solucionar problemas computacionais.
- Geralmente os problemas são chamados de fáceis, tratáveis ou viáveis quando existe solução de ordem polinomial, ou são chamados de difíceis, intratáveis ou inviáveis quando a solução existente não é polinomial, mas, sim, exponencial.
- Há uma ênfase na preferência por soluções polinomiais, óbvio já que são bem mais eficientes que as soluções exponenciais, mas não é por isso que deve-se deixar de fazer uma análise comparativa entre as soluções possíveis.
- A forte tese de Church-Turing afirma que se um problema não tem solução polinomial em uma máquina de Turing probabilística então não tem solução eficiente em outro dispositivo de 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: (No livro de Papadimitriou sobre Complexidade Computacional, seção 7.3 encontra-se boas explicações sobre grande parte desta relação)
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.
- Também em Papadimitriou 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.
Outros modelos Computacionais (3.3)
- As máquina de Turing não é o único modelo computacional vigente. Outros modelos conseguem aumentar o desempenho de uma MT sem necessariamente alterar a classe de complexidade dos problemas a serem resolvidos.
- Um primeiro exemplo é a computação paralela. Uma MT é capaz de simular uma máquina de processamento paralelo em tempo polinomial, tanto em relação a tempo quanto a espaço.
- Computadores de DNA se apresentam como uma proposta atraente para computação em paralelo. Combinando aleatoriamente diversas bases nitrogenadas e posteriormente selecionando as seqüências que satisfazem determinadas condições, econtramos soluções para problemas pouco tratáveis, como encontrar caminhos hamiltonianos. Computadores de DNA não aumentam a quantidade de problemas , mas pelo fato deste permitir um número extremamente grande de moléculas processando paralelamente, o uso de DNA pode ser útil para diversas aplicações.
- Computadores analógicos têm a aparente vantagem de possuir uma quantidade ilimitada de estados, possibilitando uma memória teoricamente infinita, entretanto em sistemas reais, o ruído faz com que os computadores analógicos tenham uma quantidade finita de estados independentes, caso contrário estarão sujeitos a uma alta taxa de erro. Os computadores digitais possuem uma taxa de erro bem menor, tornando-se na prática mais atrativos que os analógicos.
- A computação distribuída é uma outra alternativa para a diminuição do tempo de processamento em relação à execução centralizada de uma MT. Entretanto, o maior dilema para esse modelo computacional é a comunicação entre as unidades de processamento. Não é trivial para muitos problemas separa-los em porções menores para que possam ser resolvidos separadamente.