Treffer: Solving the 3-SAT problem using quantum algorithms

La computació quàntica és una àrea de les ciències de la computació que aplica els principis de la mecànica quàntica per crear un paradigma de computació diferent del que estem acostumats. Aquest projecte explora com solucionar 3-SAT utilitzant algorismes quàntics per trobar una assignació que ens satisfaci una fórmula donada. El primer enfocament del problema consisteix a utilitzar l'algorisme de Grover amb una fórmula per trobar les seves possibles solucions. L'algorisme de Grover, ens permet aconseguir un speedup quadràtic respecte a un algorisme de força bruta que busca en l'espai de totes les possibles assignacions d'una fórmula. A més, s'utilitza l'algorisme Quantum counting per determinar el nombre de solucions que té la nostra fórmula i així poder maximitzar la probabilitat d'èxit en l'algorisme de Grover mitjançant la repetició del seu operador. Els ordinadors clàssics poden solucionar el problema d'una forma més eficient que a força bruta, i per això es compara l'algorisme quàntic anterior amb un dels millors algoritmes clàssics per 3-SAT com és l'algorisme de Schöning. Finalment, l'algorisme de Grover és generalitzat i utilitzat juntament amb l'algorisme de Schöning par aconseguir un speedup quadràtic d'aquest últim. Els diferents algoritmes han estat implementats amb Qiskit, un programari desenvolupat per IBM que ens permet treballar amb ordinadors quàntics fent ús del llenguatge de programació Python.
Quantum computing is an area of computer science that applies quantum mechanics principles to create a different computational paradigm than the one we are used to. This project explores how to solve 3-SAT using quantum algorithms to find a satisfying assignment of a given formula. The first approach to the problem consists of using Grover's algorithm with a given formula to find its possible solutions. Grover's algorithm allows us to achieve a quadratic speedup over a brute-force search algorithm that searches in the space of all the possible assignments of the formula. In addition, the Quantum counting algorithm is used to determine how many solutions there are beforehand and thus maximize the probability of success in Grover's by repeating the Grover operator. Classical computers can solve the problem more efficiently than just using brute-force search. Therefore, the previous quantum algorithm is compared with Schöning's, one of the best classical algorithms for 3-SAT. Finally, Grover's algorithm is generalized and used with Schöning's to obtain a quadratic speedup of the latter. The different algorithms have been implemented using Qiskit, an open-source software development kit (SDK) developed by IBM to work with quantum computers using the Python Programming Language.