Tanto um computador clássico quanto um computador quântico fazem uso de algoritmos para realização de suas operações. Este trabalho se propõe a apresentar de forma simplificada uma breve introdução à computação quântica, compará-la com a computação clássica e mostrar o desempenho do algoritmo de Shor em um software desenvolvido para este trabalho, para o cálculo dos fatores coprimos de um número, em relação ao algoritmo de Fermat utilizado na computação clássica, demonstrando os resultados encontrados.
Tanto um computador clássico quanto um computador quântico fazem uso de algoritmos para realização de suas operações. Este trabalho se propõe a apresentar de forma simplificada uma breve introdução à computação quântica, compará-la com a computação clássica e mostrar o desempenho do algoritmo de Shor em um software desenvolvido para este trabalho, para o cálculo dos fatores coprimos de um número, em relação ao algoritmo de Fermat utilizado na computação clássica, demonstrando os resultados encontrados.
Computação quântica é uma área de grande desenvolvimento hoje em dia e isso traz uma necessidade para desenvolver hardware e software. Uma vez que o hardware disponível é muito pouco e o software precisa de ser testado, existe uma necessidade de uma boa plataforma para testar as soluções de software. Simular um computador quântico num computador clássico não é ideal, contudo é uma resposta viável a esta necessidade, para um pequeno número de qubits. Além disso, os computadores quânticos necessitam dos computadores clássicos de forma a criar um sistema real prático, isto apresenta-se como uma excelente oportunidade para testar técnicas de programação clássica para melhorar a programação quântica. Esta tese propõe o uso de programação clássica para melhorar a implementação de um algoritmo de adição modular usando transformadas de Fourier quânticas. Os principais objectivos deste trabalho são: simular um circuito quântico; testar um algoritmo quântico e compará-lo com o seu equivalente clássico; implementar o algoritmo de adição modular, usando as capacidades de aceleração de computação das transformadas de Fourier quânticas e optimizá-lo; Testar e implementar códigos quânticos de correcção de erros; fazer um teste num computador quântico real.De forma a testar a linguagem e comparar um algoritmo quântico com um clássico, fez-se um teste ao algoritmo de Shor que está disponível de raiz na plataforma liquid. Apesar do algoritmo de Shor ter, teoricamente, uma dependência de tipo polinomial com a dimensão do problema, os testes realizados mostraram que o tempo de computação tem um comportamento exponencial. Simular um algoritmo quântico num computador clássico requer tempo de computação que cresce de forma exponencial, pois é necessário armazenar e processar todos os estados do sistema, que é um espaço de Hilbert de dimensão 2^n.O algoritmo de adição modular usando transformadas de Fourier quânticas foi implementado na plataforma liquid. Seguidamente fizeram-se melhorias e optimizações. O número de operações teórico é O(n^2). Contudo, depois de fazer melhorias ao circuito, removendo gates desnecessárias para casos específicos, o número de operações passa a ter um valor mínimo de Omega(n). Com este tipo de alterações o sistema pode apresentar melhorias no que respeito ao tempo de simulação até um factor de ordem 10. Isto mostra que programar um algoritmo quântico tendo em conta casos específicos pode melhorar imenso o desempenho da simulação.Os códigos de correção de erros quânticos foram implementados num circuito simples, com as ferramentas disponíveis na plataforma liquid, e obteve-se um sistema que consegue lidar com erros com probabilidade inferior ou igual a 2%, com uma taxa de sucesso na sua correção de 95%. Contudo são necessários circuitos muito grandes, pouco exequíveis.A plataforma disponibilizada pela IBM para fazer testes num computador quântico real, foi utilizada para testar o algoritmo de adição modular e adição normal (com carry bit). Uma vez que esta plataforma tem um número limitado de gates, reforça a ideia de que se deve otimizar os algoritmos tendo em conta casos particulares. Os resultados destes testes mostram também que é importante utilizar correcção de erros quânticos, mas para que isso seja viável é necessário que haja mais qubits disponíveis ou outro tipo de códigos.
Este trabalho aborda a utilização de computação quântica para a quebra da criptografia RSA.Para isso é realizada a análise de como as chaves pública e privada são geradas a partir do produto obtido pela multiplicação entre dois números primos.Este algoritmo é baseado na dificuldade de se realizar a fatoração de um número grande para encontrar seus coeficientes, que são dois números primos.A computação quântica pode ser utilizada na etapa de fatoração dos primos de um produto para otimizar esse processo.Para realizar essa tarefa é utilizado o algoritmo de Shor.Para verificar a capacidade de efetuar a quebra de uma chave RSA, foi desenvolvido um programa utilizando o SDK do Qistik para realizar a quebra da criptografia RSA, executado em um simulador de computador quântico.As chaves utilizadas para os testes foram de valores pequenos devido a limitação de qubits do simulador.
Um estudo passo a passo dos algoritmos de Grover e Shor A step-by-step study of Grover and Shor algorithmsResumo Os algoritmos de Grover e de Shor são duas das principais descobertas da computação quântica no início das pesquisas nessa área.O primeiro é um algoritmo de busca com um ganho de velocidade significativo em relação aos algoritmos clássicos e com grande aplicação na resolução de diversos outros problemas.O segundo é capaz de resolver o problema da fatoração de um número C em tempo polinomial, o que foi responsável por um grande impulso na pesquisa em computação e criptografia quântica.Neste trabalho de Iniciação Científica apresentamos os algoritmos quânticos de Grover e Shor, amplamente utilizados na computação quântica, com uma proposta original focada nos estados quânticos obtidos após cada passo na evolução do circuito.Dessa forma, exercita-se a aplicação das portas quânticas e a percepção das propriedades quânticas, bem como o funcionamento desses dois algoritmos.No circuito de Grover destacamos a fundamental propriedade de emaranhamento quântico que permite executar tarefas de processamento de informação.
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
A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação.Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável.Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências.Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação.Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema.Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica.Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo.Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial.Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas.Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos.Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas.
Este manual apresenta uma introdução técnica e aplicada à computação quântica, articulando os seus fundamentos físicos, matemáticos e computacionais com exemplos práticos de programação, simulação e análise de algoritmos. A obra explica a constituição de sistemas quânticos contemporâneos, incluindo processadores baseados em qubits supercondutores, infraestrutura criogénica, portas quânticas, superposição, interferência, medição e entrelaçamento. São desenvolvidos cálculos passo a passo para demonstrar a representação de estados quânticos, a aplicação de operadores matriciais e o comportamento probabilístico dos circuitos. O manual aborda ainda algoritmos como Grover e Shor, a utilização da biblioteca Qiskit e a diferença entre simulação clássica e execução em hardware quântico real. Em complemento, discute aplicações emergentes em química computacional, ciência dos materiais, investigação biomolecular, otimização e criptografia pós-quântica, destacando tanto o potencial transformador dessas tecnologias quanto as suas atuais limitações técnicas. A abordagem adotada procura diferenciar resultados já demonstrados experimentalmente de hipóteses, projeções e aplicações ainda em desenvolvimento, oferecendo uma visão crítica, pedagógica e cientificamente fundamentada sobre o papel da computação quântica na evolução da ciência e da engenharia.