Computação Quântica/Capítulo 3

Introdução a Ciência da Computação

Volte para a página principal do livro clicando aqui: Computação_Quântica

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}ⁿ ->{0,1} ^m, onde n representa os bits de entrada e m os bits de saída.
• Funções do tipo f: {0,1}ⁿ -> {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.

Como Quantificar Recursos Computacionais (3.2.1)

• Muitas vezes pequenas mudanças em um algoritmo alteram a quantidade ou intensidade de recursos que ele necessita para sua execução;
• Exemplo de pergunta de interesse: quantos passos de tempo/espaço/energia são necessários para a computação de um algorítmo?
• Notação Assintótica:
  • É utilizada a fim de representar o comportamento essencial de uma função;
  • Serve de medida de comparação entre os diversos tipos de algoritmos. Leva em consideração o número de passos precisos para sua computação;
  • Durante intervalos de tempo longos, somente o termo de maior grandeza realmente importa numa análise de recursos gastos por um algorítimo;
  • Em 24n + 2log₂n + 16, o termo que vai interessar para n grande será apenas "24n". Mais ainda: tendo constants como de importância secundária, temos que a expressão cresce linearmente, ou seja, como n;
  • O ('Big O')
    • Limita superiormente uma função;
    • f(n) é O(g(n)) se existirem um n₀ e um c tais que f(n) <= c.g(n), para n >= n₀;
  • Ω('Big Omega')
    • Limita inferiromente uma função;
    • f(n) é (g(n)) se existirem um n₀ e um c tais que c.g(n) <= f(n), para n >= n₀;
  • Θ('Big Teta')
    • Limita superior e inferiormente uma função;
    • f(n) é Θ(g(n)) se for O(g(n)) e Ω(g(n)) ao mesmo tempo, ou seja, se existirem n0, c_{1 e c2 tais que c1.g(n) <= f(n) <= c2.g(n), para n >= n0;}

Complexidade Computacional (3.2.2)

• Complexidade computacional é o estudo dos recursos (eg tempo e 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 para o mesmo. 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 e isso se dá por serem, em geral, 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 tese forte 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.

Problemas de Decisão e Complexidade P e NP (3.2.3)

Problemas de Decisão

• Muitos problemas computacionais são mais facilmente formulados com problemas de decisão que tem como resposta “Sim” ou “Não”. Por exemplo: O número dado m é um número primo ou não? Este é um problema de decisão primária.

• Uma linguagem L sobre o alfabeto S é um subconjunto do conjunto S* de todos os símbolos de S. Por exemplo: se S = {0,1}, então L = {0,10,100,110,...} pertence a S*.

• Os problemas de decisão podem ser codificados de uma maneira simples usando problemas com linguagens. Por exemplo, o problema de decisão do primo pode ser codificado usando o alfabeto binário S = {0,1}. O conjunto S* pode ser interpretado como números inteiros não negativos. Por exemplo, 0010 pode ser interpretado como o número 2 em inteiro.

• A linguagem L é definida de forma a conter todas as combinações binárias tais que o número gerado por ela seja primo. Para resolver o problema de decisão de números primos, é preciso ter uma maquina de turing que, dado um número n em sua fita de entrada, tivesse como saídas respostas do tipo “sim” se n for primo e “não” quando n não for um número primo.

Complexidade P e NP

• As classes de complexidades são definidas para ser uma coleção de linguagens. Há problemas que não podem ser resolvidos em tempo polinomial. Infelizmente, provar que algum problema dado não pode ser resolvido em tempo polinomial parece ser muito difícil. Um exemplo de problema de decisão que se acredita que não estar na classe de complexidade P é o problema fatoração.

• Supondo que P seja diferente de NP é possível provar que há uma classe não vazia para problemas intermediários NPI (NP intermediário), os quais não são solucionados com recursos polinomiais, nem com NP-completo. Obviamente, não há nenhum problema conhecido que esteja em NPI, mas há diversos problemas que são considerados como sendo prováveis candidatos a NPI. Dois dos candidatos os mais fortes são os problemas de fatoração e os de grafos isomórficos.

• Na teoria de complexidade computacional o co-NP é uma classe de complexidade que é o complemento da classe NP, ou seja é a classe dos problemas em que a verificação das provas são não instanciáveis.

• O problema SAT é um outro problema de decisão da teoria da complexidade. Nele defini-se uma expressão booleana escrita usando somente AND, OR e NOT, variáveis e parêntesis. Na matemática, uma fórmula da lógica proposicional é dita satisfatível, se os valores verdades puderem ser atribuídos as suas variáveis. A classe das fórmulas satisfatíveis pertence à classe NP-completo.

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.

• • $P\subset PSPACE$
  • $NP\subset PSPACE$
  • Não é provado que $P!\subset PSPACE$
  • Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: $CQ\subset PSPACE$. 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: $P\neq PSPACE$.

• A relação entre classes é conhecida: $L\subseteq P\subseteq NP\subseteq PSPACE\subseteq EXP$ (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 - $O(\log {}{n})$ 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 $L\in BPP$. Se $x\in L$ então M aceita x com uma probabilidade de no mínimo ${\frac {3}{4}}$ e se $x\notin L$ então M rejeita x com probabilidade de no mínimo ${\frac {3}{4}}$.

• 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 $P$, 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.

Volte para a página principal do livro clicando aqui: Computação_Quântica