Na teoria da complexidade computacional, o problema do caixeiro viajante (PCV) é um problema da classe NP-complexo em otimização combinatória, importante na ciência da computação teórica e na pesquisa operacional. Devido à natureza do problema, apresenta um grande número de variáveis, o que aumenta de forma significante o custo computacional, desta forma, optou-se pela computação quântica, como base para estruturação de um algoritmo para resolução viável deste problema. Não obstante, a partir utilizando uma nova técnica que alude à denominada codificação em múltiplas bases, o que dá permissividade para resolver o problema com um número menor de qubits e desta forma reduzindo-se o custo computacional para a resolução deste problema com quatro e cinco instâncias. O presente trabalho contou com a técnica seminal da codificação em múltiplas bases, ideia egressa das redes neurais e que se mostra profícua na resolução de problemas de optimização combinatória.
Na teoria da complexidade computacional, o problema do caixeiro viajante (PCV) é um problema da classe NP-complexo em otimização combinatória, importante na ciência da computação teórica e na pesquisa operacional. Devido à natureza do problema, apresenta um grande número de variáveis, o que aumenta de forma significante o custo computacional, desta forma, optou-se pela computação quântica, como base para estruturação de um algoritmo para resolução viável deste problema. Não obstante, a partir utilizando uma nova técnica que alude à denominada codificação em múltiplas bases, o que dá permissividade para resolver o problema com um número menor de qubits e desta forma reduzindo-se o custo computacional para a resolução deste problema com quatro e cinco instâncias. O presente trabalho contou com a técnica seminal da codificação em múltiplas bases, ideia egressa das redes neurais e que se mostra profícua na resolução de problemas de optimização combinatória.
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 paradigma computacional que tem motivado o aparecimento de diversas pesquisas que visam apresentar soluções para problemas, atualmente, considerados difíceis. O surgimento de algoritmos quânticos que operam mais rápido que seus análogos clássicos tem feito com que corporações como Google, NASA e IBM invistam nesse paradigma. Por isso, intensificou-se a busca por formulações alternativas para problemas, visando resolvê-los em um ambiente computacional quântico. Entre essas formulações, estão os trabalhos que abordam a resolução de problemas na computação quântica a partir de formulações QUBO (Quadratic Unconstrained Binary Optimization), um problema NP-difícil cujo princípio consiste em minimizar uma função quadrática. O formato QUBO é comumente utilizado na literatura quando da solução quântica de problemas de otimização e diversos autores têm recorrido à esta caracterização devido à sua aplicabilidade em uma considerável gama de problemas. Dessa forma, representar um dado problema como um problema QUBO implica diretamente que podemos executá-lo em um ambiente computacional quântico (genérico ou de propósito específico). O problema CMO (Contact Map Overlap) é definido como um problema de otimização combinatória NPdifícil que consiste na medida de semelhança entre pares de proteínas com base em seus respectivos mapas de contato. Em bioinformática, o estudo de problemas que buscam por funções similares entre estruturas biológicas, especialmente de proteínas, é um campo de grande interesse. Com isso, este trabalho de pesquisa aborda o problema CMO na conjectura da resolução dos problemas de otimização em computadores quânticos através da formulação QUBO dos mesmos. Além de fornecermos uma formulação QUBO para o problema de proteína CMO, resultados experimentais foram obtidos com o auxílio da ferramenta qbsolv e validaram esta abordagem como uma alternativa aos métodos clássicos existentes.
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.
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.
Esta dissertação explora o problema da Transferência Perfeita de Estado (PST) em grafos, que tem implicações significativas na computação quântica. O objetivo é determinar quais grafos permitem transferir perfeitamente o estado de um qubit (ou vértice) para outro qubit em um determinado tempo. O texto apresenta uma introdução ao tema utilizando técnicas de álgebra linear, discutindo condições necessárias e suficientes para alcançar o PST e enfatizando a transferência de longa distância entre qubits. O objetivo da otimização ´e minimizar o número de componentes quânticos necessários para alcançar a transferência perfeita de estado. Uma classe importante de grafos que admite PST são os caminhos com pesos. Para o PST entre vértices nos extremos, o problema foi completamente resolvido explorando a conexão desses grafos com polinômios ortogonais. No entanto, o problema se torna consideravelmente mais complexo para vértices em outras posições, levando a novos resultados e conexões explorados neste documento. Entre esses resultados, podemos citar uma fórmula que relaciona, de maneira inédita, o polinômio extremo com outro polinômio arbitrário em uma sequência de polinômios ortogonais; como criar uma sequência de polinômios ortogonais que contenha outros dois dados; e como o PST em caminhos com pesos se relaciona com o problema de Prouhet-Tarry-Escott, um problema em aberto na área de teoria dos números. Por fim, o documento apresenta uma abordagem para a construção de grafos com PST, explorando caminhos ponderados e partições equitativas. Também são apresentados novos teoremas nessa ´área, que têm relevância geral para a teoria dos grafos. Entre esses teoremas, destaca-se um critério para dois grafos possuírem um quociente simetrizado em comum; como as matrizes de partições equitativas se relacionam com matrizes projetivas; e como o conjunto de partições equitativas se transforma quando o grafo original é quocientado.
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.