Implementação de problemas SAT no algoritmo de Grover

Abstract

Este trabalho explorou a relação entre problemas SAT e o algoritmo quântico de Grover. Para isso foi feita uma exploração de como funciona o algoritmo de Grover, analisando como funciona a criação de suas partes utilizando portas lógicas quânticas, podendo assim modelar outros tipos de problemas dentro do algoritmo de Grover. O problema escolhido para ser modelado nesse trabalho foi o problema de satisfação booleana, conhecido como SAT, onde o SAT é transformado em um oráculo para o algoritmo de Grover e assim, sendo utilizado para resolver o problema SAT. Essa utilização tem um ganho quadrático em relação ao método de resolução de SAT clássico, assim podendo resolver problemas de maior complexidade em menos tempo. O problema que é o foco deste trabalho foi o crossover-point, um ponto dos problemas SAT que se caracteriza pela dificuldade de se provar se existe ou não existe resposta para o problema SAT. Sabendo sobre esse ponto, este trabalho tem como objetivo final analisar como irá funcionar o algoritmo de Grover ao se executar problemas dentro desse ponto e se terá algum ganho relevante em relação à execução clássica do problema.