Apresentamos o problema de Bernstein-Vazirani, que consiste em descobrir uma string de n bits conhecida apenas por um oráculo, e o algoritmo quântico que resolve este problema com um única consulta ao oráculo, enquanto a melhor solução clássica exige n consultas ao oráculo.
A computação quântica é uma área de pesquisa recente que engloba três áreas conhecidas: matemática, física e computação. Com as pesquisas na área de algoritmos\nquânticos veio a necessidade de entender e expressar tais algoritmos do ponto de vista de programação. Diversas linguagens e modelos para programação quântica de alto nível têm sido propostas nos últimos anos. A Mecânica Quântica (MQ) é um conjunto de regras matemáticas que servem para a construção de teorias físicas, desde a sua criação até os dias de hoje ela tem sido aplicada em diversos ramos. Neste contexto se desenvolveu a Computação Quântica, talvez a mais espetacular proposta de aplicação prática da MQ. A dificuldade de se desenvolver algoritmos quânticos propicia o uso de técnicas alternativas à solução de problemas puramente algorítmica, como por exemplo o aprendizado de máquinas e algoritmos genéticos. Carlo Trugenberger propõe um modelo de memória\nquântica associativa onde os padrões binários de n bits são armazenados em superposição com um subconjunto apropriado da base computacional de n qubits. Este modelo resolve o problema de escassez de capacidade bem conhecida da memória clássica associativa,provendo uma melhoria grande em capacidade. A distribuição proposta por Trugenberger usa a distância de Hamming, em que as amplitudes tem um pico nos padrões armazenados, que tem menor distância em relação à entrada. A precisão do reconhecimento de padrões pode ser ajustado por um parâmetro b, isto é, aumentando b aumenta a probabilidade\nde reconhecimento. Este trabalho analisa a diversidade genética das abelhas sem ferrão Melipona quinquefasciata, obtidas de várias colônias silvestres, em localidades distintas\nda Chapada do Araripe-CE, Chapada da Ibiapaba-CE, cidade do Canto do Buriti-PI e Luziânia-GO. As sequências de DNA foram transformados substituindo A por 00, G por 01, C por 10 e T por 11. Os resultados mostram que essa probabilidade é muito eficiente para reconhecer os padrões de sequências de DNA das abelhas sem ferrão Melipona quinquefasciata\ndas regiões 18S e ITS1 parcial. O algoritmo não é computacionalmente eficiente em um computador clássico, mas será extremamente eficiente em um computador quântico. Concluiu-se que este método de reconhecimento quântico de padrões é melhor que o método clássico utilizado por Pereira.
Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas
resumo A computação quântica possibilita a resolução eficiente de problemas complexos, superando métodos clássicos em diversas aplicações. Em 2009, Harrow, Hassidim e Lloyd propuseram um algoritmo para solução de sistemas lineares, demonstrando aceleração exponencial (em condições ideais) com complexidade p o l y ( log N ), em contraste com abordagens clássicas que, no caso geral, apresentam complexidade da ordem de O ( N 3 ), ainda que possam atingir O ( N ) em casos específicos com matrizes esparsas. Esse algoritmo tem potencial para avanços em aprendizado de máquina, equações diferenciais, regressão linear e ataques a criptossistemas. No entanto, sua estrutura é complexa e há poucos materiais detalhados disponíveis na literatura. Neste contexto, este artigo pretende apresentar um tutorial abordando os fundamentos físicos e matemáticos do algoritmo HHL, direcionado para estudantes de graduação, explicando sua construção teórica e implementação para a resolução de sistemas de equações lineares. Após a discussão dos conceitos matemáticos e físicos subjacentes, apresentamos exemplos numéricos ilustrando a evolução do circuito quântico. Por fim, analisamos sua complexidade, limitações e perspectivas futuras. Os exemplos abordados são comparados com suas simulações clássicas, permitindo uma avaliação operacional da performance do algoritmo.
Resumo: A classe de problemas para os quais existem algoritmos quânticos eficientes é denotada por BQP (Bounded-error Quantum Polynomial). Uma abordagem comum em teoria da computação para a compreensão dos limites de uma classe de complexidade é esclarecer relações desta com outras subclasses e superclasses próximas. Uma superclasse de BQP que tem sido foco de pesquisa recentemente é a classe naCQP (non-adaptive Collapse-free Quantum Polynomial Time), também conhecida como PDQP (Product Dynamical Quantum Polynomial time), introduzida por Aaronson et al. (2016), a qual corresponde a problemas que podem ser resolvidos eficientemente por um algoritmo quântico em um modelo hipotético de computação em que é possível realizar medições sem provocar o colapso do estado quântico. Provas interativas de conhecimento zero têm recebido muita atenção nas últimas décadas, em virtude de suas aplicações importantes em segurança de informação. A classe dos problemas que admitem provas interativas de conhecimento zero estatístico na computação clássica é a classe SZK (Statistical Zero Knowledge). Embora a relação entre BQP e SZK ainda seja desconhecida, Aaronson et al. (2016) mostraram que SZK está contida em naCQP. Uma das abordagens para investigação de separações entre classes é o estudo de suas relações relativas a um oráculo. Aaronson et al. (2016) mostraram que existe um oráculo A para o qual NPA ^ naCQPA. Nós provamos que existe um oráculo A para o qual PA = BQPa = SZKA = naCQPA ã (UP n coUP)A = EXPA, onde UP (Unambiguous Polynomial time) é uma subclasse importante de NP. Ainda, mostramos que, relativo a um oráculo A escolhido uniformemente de modo aleatório, temos (UP n coUP)A ^ naCQPA com probabilidade 1. Nossos resultados ampliam resultados de Bennett et al. (1997), Fortnow e Rogers (1999), Tamon e Yamakami (2001) e Aaronson et al. (2016). A classe SZK possui muitas subclasses notáveis, como NISZK e NIPZKi. A classe NISZK é associada a sistemas de prova com somente um envio de mensagem do provador para o verificador. Para NIPZK1, subclasse de NISZK, ainda é requirido conhecimento zero perfeito e que as instâncias positivas do problema sejam aceitas pelo verificador com probabilidade igual a 1. Mostramos um problema completo para NIPZK1 e também que uma restrição não trivial do problema de subgrupo oculto está em NIPZK1. Além disso, mostramos uma restrição não trivial de um problema completo para NISZK que está em BQP.