Investigação do crossover point do problema da satisfação booleana utilizando o algoritmo quântico de Grover

Abstract

O crossover point representa um ponto onde as instâncias do problema de satisfação booleana (SAT) são muito mais difíceis de serem resolvidas. O objetivo desse trabalho é fazer uma investigação do comportamento das instâncias ao serem executadas no algoritmo de Grover. O algoritmo de Grover é um algoritmo quântico utilizado para encontrar um elemento em uma lista desordenada que apresenta comportamento assintótico da ordem de √N, onde N é a quantidade de elementos na lista. Para sua implementação, fez-se uso da linguagem Ket e do simulador de computação quântica QuBox. A investigação faz uso de instâncias SAT geradas aleatoriamente, porém limitadas no número de qubits. Foram implementados, além do algoritmo de Grover e o de geração de instâncias SAT, um algoritmo para converter tais instâncias em oráculos de Grover e um algoritmo para iterar o algoritmo de Grover, quando o número de respostas para o oráculo é desconhecido. Devido às diversas limitações e ao tempo necessário para a execução das instâncias, não foi possível ter uma visão clara sobre a real complexidade da execução de instâncias SAT no ponto de crossover, quando executadas no algoritmo de Grover.