Este artigo apresenta um estudo inicial sobre o uso de computação quântica para o Problema do Caixeiro Viajante (TSP), explorando sua modelagem por grafos e sua relação com formulações QUBO, QAOA e Quantum Annealing. A partir de uma implementação preliminar em Qiskit, o trabalho organiza abordagens relacionadas e define critérios para comparar algoritmos clássicos, híbridos e quânticos em instâncias controladas, considerando desempenho, qualidade das rotas e limitações de dispositivos NISQ.
Este artigo apresenta um estudo inicial sobre o uso de computação quântica para o Problema do Caixeiro Viajante (TSP), explorando sua modelagem por grafos e sua relação com formulações QUBO, QAOA e Quantum Annealing. A partir de uma implementação preliminar em Qiskit, o trabalho organiza abordagens relacionadas e define critérios para comparar algoritmos clássicos, híbridos e quânticos em instâncias controladas, considerando desempenho, qualidade das rotas e limitações de dispositivos NISQ.
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 Computacao Quântica surgiu como uma promissora tecnologia alternativa capaz de contornar os problemas previstos para acontecerem em breve com a saturacao da tecnologia atual (Computacao Classica). Estes problemas acontecem quando se trabalha com componentes muito pequenos, da ordem de poucos nanometros, quando os efeitos da Mecânica Quântica comecam a tornar-se mais fortes, gerando resultados aleatorios. A Computacao Quântica toma proveito desses efeitos, resultando numa Computacao nao somente mais rapida, como um novo tipo de Computacao, capaz de realizar tipos novos de computacao impossiveis, em principio, de serem realizadas classicamente. Embora a teoria da Computacao Quântica venha se desenvolvendo com rapidez, a parte experimental ainda enfrenta grandes dificuldades. Embora implementacoes de algoritmos simples e com poucos qubits ja tenham sido realizadas, ainda ha problemas serios de escalabilidade, descoerencia 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 simulacao, porem, apresenta um problema, no que um sistema quântico so pode ser simulado eficientemente por outro sistema quântico. Um sistema quântico de n qubits levara um tempo O(2n ) para ser simulado por um computador classico. A simulacao, entretanto, mostra-se a alternativa mais viavel em vista da falta de um hardware quântico. Este trabalho apresenta o processo de concepcao e implementacao de um simulador universal de circuitos quânticos, denominado Zeno. O modelo de circuitos quânticos foi escolhido por ser amplamente difundido e de facil assimilacao. O trabalho apresenta uma introducao aos conceitos de Computacao Quântica usados na implementacao do simulador, os requisitos gerais desejaveis para um novo simulador de circuitos quânticos, tanto do ponto de vista funcional quanto do nao-funcional, o processo de desenvolvimento utilizado e uma analise dos resultados obtidos com a implementacao do simulador.
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.
Neste artigo descrevemos os fundamentos da computação quântica adiabática, que consiste na interpolação de diferentes Hamiltonianos, desde um Hamiltoniano inicial, com autoestados e autoenergias conhecidos, até um Hamiltoniano final, onde é codificada a solução de um dado problema. Em particular, discutimos o método do annealing quântico, que é utilizado pela empresa canadense D-Wave, pioneira nessa área. Primeiramente apresentamos uma das demonstrações do teorema adiabático quântico e de uma condição de adiabaticidade para evolução de sistemas quânticos. Para exemplificar, descrevemos a implementação do algoritmo de Grover via computação quântica adiabática, discutindo os impactos da escolha da forma de interpolação dos Hamiltonianos inicial e final na complexidade do algoritmo. Em seguida, mostramos um algoritmo para o problema do caixeiro viajante executável na plataforma da D-Wave. Por fim, apresentamos aspectos físicos importantes da tecnologia dos computadores quânticos da D-Wave, expondo suas vantagens e desvantagens, além de descrever qualitativamente a engenharia de seu processador quântico.
Realizar computacao quântica real esta no roteiro de trabalho de empresas gigantes da computacao como Microsoft, Google e IBM. Algumas delas disponibilizam acesso a seus prototipos gratuitamente por meio de suas APIs para pesquisadores de todo o mundo a fim de popularizar o assunto entre a academia e entusiastas. Este e o caso do Qiskit, uma API Open Source escrita em Python para dar suporte a modelagem, simulacao e execucao de algoritmos quânticos em dispositivos NISQ (Noise Intermediate Scale Quantum) da IBM. Porem, a dificuldade de construir um computador quântico torna ainda necessario investir na simulacao de sistemas quânticos em computadores classicos, com o objetivo de fornecer um ambiente mais acessivel para criacao e aprimoramento de algoritmos quânticos maiores do que os prototipos existentes podem suportar. Acontece que a natureza paralela e exponencial da computacao quântica torna impossivel realizar simulacoes com eficiencia de tempo em maquinas sequenciais classicas. Para enfrentar este problema, a literatura tem mostrado alternativas explorando o paralelismo de outras arquiteturas como FPGAs e GPUs, com o objetivo de transferir a complexidade da simulacao do dominio do tempo para o dominio do espaco. Curiosamente, apesar de suportar simulacao em GPU, a API Qiskit ainda nao possui suporte para executar em FPGA. Pretendemos investigar diferentes modelos de arquitetura customizada para simulacao de algoritmos quânticos em FPGA, visando futura implementacao em um ASIC. Os modelos serao implementados em Verilog HDL, validados usando os prototipos de computadores quânticos da IBM como modelos de referencia, e serao comparados tendo como metricas de avaliacao parâmetros como escalabilidade e tempo de execucao. A ideia final e contornar o mecanismo de simulacao nativo da Qiskit para executar remotamente em um modelo FPGA disponivel remotamente por meio de nosso servico web capaz de processar essas solicitacoes, executar o algoritmo quântico e enviar os resultados finais de volta. O projeto encontra-se em desenvolvimento, ja tendo sido realizado os primeiros estudos sobre os fundamentos da computacao quântica, estudo da API Qiskit, e implementacao dos primeiros circuitos quânticos em C e em Python visando entendimento e desafios da complexidade de simulacao inerentes a esse novo modelo computacional.