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.
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
Este artigo explora a intersecção fascinante entre a mecânica quântica e a computação, dois campos aparentemente distintos que se entrelaçam em uma simbiose surpreendente. Ao destacar os princípios fundamentais da mecânica quântica, como superposição e emaranhamento, este estudo lança luz sobre sua aplicação inovadora na computação quântica. Em particular, focamos no algoritmo Shor, uma conquista marcante neste campo emergente. O algoritmo Shor demonstra a capacidade única da computação quântica de resolver rapidamente problemas que seriam intratáveis para computadores clássicos. Exploramos como o algoritmo utiliza os princípios quânticos de superposição e emaranhamento para fatorar números inteiros em seus primos constituintes com eficiência exponencialmente superior aos métodos clássicos. Além disso, discutimos as implicações profundas desse avanço, desde a criptografia até a modelagem de sistemas complexos. Ao destacar o potencial revolucionário da computação quântica, este artigo lança luz sobre o futuro promissor de uma nova era de computação, onde os limites tradicionais são desafiados e novas fronteiras são abertas.
Os algoritmos quânticos variacionais têm se destacado como uma maneira de obter vantagem quântica no atual estado da arte da computação quântica, a chamada era NISQ (escala quântica intermediária com ruídos). A estrutura destes algoritmos consiste em estrategicamente combinar processamento quântico (circuito parametrizado) com otimização clássica, conectados por meio de uma função custo que norteia a otimização dos parâmetros. Neste trabalho damos principal enfoque nos circuitos parametrizados inicialmente na tarefa de detecção de emaranhamento em cadeias de spin-1/2 descritas pelo Hamiltoniano de Heisenberg com interações de primeiros vizinhos e ausência de campo externo, via testemunha de emaranhamento, em que dois circuitos são utilizados em conjunto nesta tarefa, sendo um totalmente separável, enquanto outros com capacidade de gerar emaranhamento. Utilizando estes mesmos circuitos, buscamos obter o conjunto de parâmetros ideais para preparar o estado fundamental destes mesmos Hamiltonianos, os quais consideramos de 2 a 15 q-bits. Outro resultado consiste em uma proposta de extração de trabalho em baterias quânticas descritas como uma cadeia de spin-1/2 com interações de primeiros vizinhos, considerando várias configurações dos termos de anisotropia. Utilizamos circuitos parametrizados com diferentes topologias (conexão entre os q-bits definida por portas de 2 q-bits) para obter a ergotropia nestes sistemas. Neste resultado da ergotropia, consideramos sistemas com 2 a 8 q-bits.
Algoritmos Quânticos: Da lógica clássica à computação quântica apresenta uma introdução progressiva, técnica e computacional aos fundamentos e aos principais algoritmos da computação quântica. A obra parte dos conceitos clássicos de algoritmo, complexidade computacional, teoria dos números e álgebra linear para construir, passo a passo, a compreensão de qubits, superposição, medição, interferência, portas quânticas, circuitos e emaranhamento. Ao longo do livro são desenvolvidos algoritmos fundamentais como Deutsch, Deutsch–Jozsa, Simon e Grover, avançando para a Transformada Quântica de Fourier (QFT), estimação quântica de fase e o algoritmo de Shor. A obra também discute amplificação de amplitude, criptografia pós-quântica, computação híbrida quântico-clássica, VQE, QAOA, barren plateaus, ruído, correção e mitigação de erros, além dos diferentes significados de vantagem quântica e dos limites atuais da tecnologia. Uma parte substancial do livro é dedicada à implementação prática com Python e Qiskit, incluindo preparação e medição de estados, estados de Bell, circuitos de Grover, QFT, estimação de fase, demonstrações de Shor, simulação local, transpilação e execução em processadores quânticos (QPUs). O texto procura distinguir rigorosamente vantagem algorítmica teórica, vantagem experimental e utilidade prática, evitando interpretações excessivamente simplificadas da computação quântica. O objetivo é oferecer uma ponte entre Ciência da Computação clássica e computação quântica para estudantes, desenvolvedores, pesquisadores e leitores interessados em compreender não apenas como os algoritmos quânticos funcionam, mas também quando, por que e sob quais condições eles podem oferecer vantagens computacionais. Palavras-chave Computação quântica; Algoritmos quânticos; Quantum computing; Quantum algorithms; Qubits; Circuitos quânticos; Quantum circuits; Qiskit; Algoritmo de Grover; Grover's algorithm; Algoritmo de Shor; Shor's algorithm; Transformada Quântica de Fourier; Quantum Fourier Transform; Estimação quântica de fase; Quantum Phase Estimation; VQE; QAOA; Computação híbrida quântico-clássica; Criptografia pós-quântica; Complexidade computacional; Emaranhamento quântico; Amplificação de amplitude; Programação quântica.
Desde a primeira vez que computação quântica foi concetualizada por Feynman, simulação quântica tem estado na vanguarda das possiveis aplicações de interesse. Os custos proibitivos de simular sistemas quânticos com computadores classicos são uma forte motivação para a investigação em computação quântica. Ao longo da última década, tem-se observado um progresso notável no desenvolvimento de hardware quantico. No entanto, os obstáculos entre nos e a era de vantagem quantica util mantem-se essencialmente os mesmos: A informação quântica e fragil, e protegê-la é um desafio. Visto que os dispositivos quânticos atuais são ruidosos e tem um número limitado de qubits, desenvolver algoritmos que possam ser executados neles e uma area de investigação importante. Por resultarem em circuitos de preparação de estado (ansatze) pouco profundos e treinaveis, algoritmos quânticos variacionais (VQAs) adaptativos são uma opção promissora. O primeiro algoritmo nesta classe, o ADAPT-VQE, pode ser utilizado para problemas de estrutura eletronica, otimização combinatoria, materia condensada, sistemas periódicos no tempo, entre outros. Nesta tese, são propostas varias melhorias para VQAs adaptativos, com o objetivo de diminuir os custos e aumentar a viabilidade a curto prazo. Propõe-se um otimizador quasi-Newton para VQAs adaptativos que reduz os custos de medição necessários para implementar estes algoritmos em hardware quântico, bem como o tempo necessario para os simular classicamente. Propõe-se ainda um novo conjunto de operadores — “operatores de intercambio acoplado” (CEOs) — que resulta no menor numero de portas quanticas e na menor profundidade de circuito entre todas as propostas na literatura. Combina-se varios desenvolvimentos-chave e mostra-se uma redução dramatica dos recursos computacionais quânticos necessários em comparação com as primeiras versões do algoritmo ou com ansätze estáticos para VQE. Adicionalmente, propõe-se uma versão codesenhada do ADAPT-VQE (Co-ADAPT-VQE) onde o hardware quântico e tido em consideração na construção do ansatz. Este paradigma pode ser utilizado para otimizar circuitos de preparação de estado em qualquer dispositivo, colmatando limitações como conetividade limitada, tempos de coerencia curtos, e erros nas portas quanticas. Finalmente, propomos estrategia para mitigar “vales de gradientes”, um problema de convergência especifico ao ADAPT-VQE.
A descoberta do algoritmo de Shor, para a fatoração de inteiros em tempo polinomial, motivou esforços rumo a implementação de um computador quântico. Ele é capaz de quebrar os principais criptossistemas de chave pública usados hoje (RSA e baseados em curvas elípticas). Estes fornecem diversos serviços de segurança, tais como confidencialidade e integridade dos dados e autenticação da fonte, além de possibilitar a distribuição de uma chave simétrica de sessão. Para quebrar estes criptossistemas, um computador quântico grande (2000 qubits) é necessário. Todavia, alternativas começaram a ser investigadas. As primeiras respostas vieram da própria mecânica quântica. Apesar das propriedades interessantes encontradas na criptografia quântica, um criptossistema completo parece inatingível, principalmente devido as assinaturas digitais, essenciais para a autenticação. Foram então propostos criptossitemas baseadas em problemas puramente clássicos que (acredita-se) não são tratáveis por computadores quânticos, que são chamadas de pós-quânticas. Estes sistemas ainda sofrem da falta de praticidade, seja devido ao tamanho das chaves ou ao tempo de processamento. Dentre os criptossistemas pós-quânticos, destacam-se o McEliece e o Niederreiter. Por si só, nenhum deles prevê assinaturas digitais, no entanto, as assinaturas CFS foram propostas, complementandos. Ainda que computadores quânticos de propósito geral estejam longe de nossa realidade, é possível imaginar um circuito quântico pequeno e dedicado. A melhoria trazida por ele seria a diferença necessária para tornar essas assinaturas práticas em um cenário legitimamente pós-quântico. Neste trabalho, uma arquitetura híbrida quântica/clássica é proposta para acelerar algoritmos criptográficos pós-quânticos. Dois coprocessadores quânticos, implementando a busca de Grover, são propostos: um para auxiliar o processo de decodificação de códigos de Goppa, no contexto do criptossistema McEliece; outro para auxiliar na busca por síndromes decodificáveis, no contexto das assinaturas CFS. Os resultados mostram que em alguns casos, o uso de um coprocessador quântico permite ganhos de até 99; 7% no tamanho da chave e até 76; 2% em tempo de processamento. Por se tratar de um circuito específico, realizando uma função bem específica, é possível manter um tamanho compacto (300 qubits, dependendo do que é acelerado), mostrando adicionalmente que, caso computadores quânticos venham a existir, eles viabilizarão os criptossistemas pós-quânticos antes de quebrar os criptossistemas pré-quânticos. Adicionalmente, algumas tecnologias de implementação de computadores quânticos são estudadas, com especial enfoque na óptica linear e nas tecnologias baseadas em silício. Este estudo busca avaliar a viabilidade destas tecnologias como potenciais candidatas à construção de um computador quântico completo e de caráter pessoal.