masterThesis
Otimização em computadores quânticos: formulação QUBO para o problema CMO
Autor
OLIVEIRA, Nicolas Melo de
Institución
Resumen
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. FACEPE Quantum computing is a computational paradigm that has motivated the appearance of several researches aimed at presenting solutions to problems, currently, considered difficult. The emergence of quantum algorithms that operate faster than their classic analogues has made corporations such as Google, NASA, and IBM invest in this paradigm. Therefore, the search for alternative formulations for problems was intensified, aiming at solving them in a quantum computational environment. Among these formulations are the problem solving in quantum computing from QUBO (Quadratic Unconstrained inary Optimization) formulations, a NP-hard problem whose principle is to minimize a quadratic function. QUBO format is commonly used in the literature when looking for quantum solution of optimization problems and several authors have resorted to this characterization due to its applicability in a considerable range of problems. Thus, representing a given problem as a QUBO problem directly implies that we can run it in a quantum computational environment (generic or specific purpose). The CMO (Contact Map Overlap) problem is defined as an NP-hard combinatorial optimization problem consisting of the measure of similarity between pairs of proteins based on their respective contact maps. In bioinformatics, the study of problems that seek similar functions between biological structures, especially proteins, is a field of great interest. Therefore, this research work addresses the CMO problem in the conjecture of solving optimization problems in quantum computers through their QUBO formulation. In addition to providing a QUBO formulation for the CMO protein problem, experimental results were obtained with the help of the qbsolv tool and validated this approach as an alternative to existing classical methods.