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.
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.
O artigo explora o impacto da computação quântica na teoria da complexidade computacional, com destaque para as classes P e BQP, abordando como os paradigmas quânticos desafiam as categorizações clássicas de problemas. Ao examinar os algoritmos de Shor e Grover, o estudo discute a maneira como esses algoritmos ampliam o escopo de problemas considerados resolvíveis, o que anteriormente era inviável em termos de tempo polinomial em sistemas clássicos. A análise apresenta uma revisão histórica das classes de complexidade, abordando o surgimento e a importância das classes P e NP e a relevância de algoritmos quânticos em problemas intratáveis. Além disso, o artigo aborda a introdução de teorias híbridas que integram métodos clássicos e quânticos, como o Variational Quantum Eigensolver (VQE) e o Quantum Annealing, destacando a eficiência dessas abordagens para resolver problemas de otimização complexos. As discussões sobre as classes probabilísticas BPP e PP também são centrais para compreender o papel da probabilidade em algoritmos quânticos, uma característica intrínseca ao modelo de computação quântica. O estudo justifica-se pela necessidade de uma reavaliação contínua das bases da teoria da complexidade frente aos avanços quânticos, que redefinem limites teóricos e práticos. Embora a computação quântica ainda enfrente desafios, como a estabilidade dos qubits, as propostas de paradigmas híbridos oferecem caminhos promissores para resolver problemas de alta complexidade, sinalizando uma transição para uma era computacional mista, com potencial para revolucionar a resolução de problemas no século XXI.
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.
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 aprendizagem de máquina quântica é um campo em rápido crescimento e tem surgido como uma alternativa à aprendizagem de máquina clássica para impulsionar a busca por soluções eficientes para certos problemas. Além disso, o avanço da tecnologia em Computação Quân- tica trouxe possibilidades para a execução de algoritmos em dispositivos quânticos reais. Aqui, centramos nossa pesquisa no estudo de uma das tarefas mais comuns dentro da aprendizagem de máquina, a classificação supervisionada. Nos nossos estudos, limitamos a temática para os classificadores quânticos baseados em distância, visando a execução dos mesmos em disposi- tivos quânticos ruidosos de escala intermediária (Noisy Intermediate-Scale Quantum (NISQ)). Embora algoritmos quânticos anteriores para classificação baseada em distância tenham se mostrado promissores, muitos deles não são adequados com os dispositivos NISQ e não con- seguem lidar com problemas envolvendo múltiplas classes. O Hadamard Classifier (HC) é um modelo quântico de aprendizagem de máquina baseado em distância para reconhecimento de padrões. A partir dele, desenvolvemos dois classificadores quânticos baseados em distância para execução em dispositivos NISQ: o primeiro deles, Quantum One-Class Classifier (QOCC), é um modelo de classificação elementar. Nosso objetivo com o QOCC é oferecer um classi- ficador que consuma menos recursos computacionais quânticos, estando menos propenso aos erros provenientes de ruídos, ao mesmo tempo em que possui desempenho competitivo quando comparado a análogos clássicos. Os resultados obtidos nos experimentos com o QOCC foram promissores e confirmaram um desempenho equiparável tanto contra classificadores clássicos quanto contra o HC, mesmo usando menos qubits (bits quânticos) e menos operações quânti- cas. Em seguida, focamos nossos esforços em utilizar o QOCC como base para um classificador multiclasse. Nossa motivação para isso consistiu na carência desse tipo de classificador na li- teratura da aprendizagem de máquina quântica e na impossibilidade atual de executar, em dispositivos NISQ, algumas rotinas presentes nos classificadores multiclasse existentes. Propo- mos o quantum Variational Distance-based Centroid Classifier (qVDCC), que faz uso da teoria dos circuitos quânticos variacionais para, em um esquema híbrido de computação quântica- clássica, realizar a classificação de bases de dados multiclasse. Essa abordagem nos permitiu utilizar o maquinário bem-estabelecido da aprendizagem de máquina clássica para encontrar e otimizar centroides artificiais para as bases de dados que minimizassem suas distâncias para os demais dados da respectiva classe. Simulamos o funcionamento do qVDCC em dois ambientes distintos: primeiramente em uma simulação ideal (livre de erros); em seguida, em um uma simulação ruidosa que mimetiza um dispositivo NISQ. Mais uma vez, nossos resultados se mostraram promissores e competitivos em relação aos classificadores clássicos.
A Computação Quântica surgiu como uma promissora tecnologia alternativa capaz de contornar os problemas previstos para acontecerem em breve com a saturação da tecnologia atual (Computação Clássica). Estes problemas acontecem quando se trabalha com componentes muito pequenos, da ordem de poucos nanômetros, quando os efeitos da Mecânica Quântica começam a tornar-se mais fortes, gerando resultados aleatórios. A Computação Quântica toma proveito desses efeitos, resultando numa Computação não somente mais rápida, como um novo tipo de Computação, capaz de realizar tipos novos de computação impossíveis, em princípio, de serem realizadas classicamente. Embora a teoria da Computação Quântica venha se desenvolvendo com rapidez, a parte experimental ainda enfrenta grandes dificuldades. Embora implementações de algoritmos simples e com poucos qubits já tenham sido realizadas, ainda há problemas sérios de escalabilidade, descoerência e controlabilidade a serem resolvidos. Devido a esses problemas, torna-se imperativo o uso de simuladores tanto para o desenvolvimento de novos algoritmos quanto para o estudo dos algoritmos existentes. A simulação, porém, apresenta um problema, no que um sistema quântico só pode ser simulado eficientemente por outro sistema quântico. Um sistema quântico de n qubits levará um tempo O(2n ) para ser simulado por um computador clássico. A simulação, entretanto, mostra-se a alternativa mais viável em vista da falta de um hardware quântico. Este trabalho apresenta o processo de concepção e implementação de um simulador universal de circuitos quânticos, denominado Zeno. O modelo de circuitos quânticos foi escolhido por ser amplamente difundido e de fácil assimilação. O trabalho apresenta uma introdução aos conceitos de Computação Quântica usados na implementação do simulador, os requisitos gerais desejáveis para um novo simulador de circuitos quânticos, tanto do ponto de vista funcional quanto do não-funcional, o processo de desenvolvimento utilizado e uma análise dos resultados obtidos com a implementação do simulador.
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.