This repository contains the material I used in order to face the Quantum Computing area. I started to study this field thanks to a university project where I had to choose an algorithm to make a comparison between a classical and a quantum solver. In particular I decided to study the SAT problem for its importance in the field of Artificial Intelligence but also to show the impact of the enhancements provided by quantum algorithms on one of the most important problems for Computational Theory.
Two directories make a distinction between the implementations I realized and the corresponding documentation, respectively in the Code and Report folders we will find a folder for each of the studies. Up to now we can only find my first approach related to the SAT problem with the sources and documentations that I realized at the end of my work. The result of my first research project is a paper that tries to give a description of the state of the art by providing coding examples to clarify the difficult quantum principles behind the real algorithms.
This folder contains the quantum implementations that I realized in order to deepen my knowledge in this very mathematical and complex area called Quantum Computing. Each directory focuses on a particular problem, in this first version we can see in the SAT the different algorithms that I decided to implement for the aim of my research project, thus the comparison with the classical counterpart solver.
The following table shows the libraries used to realize quantum algorithms and the respective implementations based on them:
| Library | Implementations |
|---|---|
| Qiskit | SAT |
In order to study the Satisfiability Problem I developed three different implementations that are based on different approaches that can all be used in order to solve particular instances of the SAT. The following list provides a description of each algorithm and the respective commands to use the solvers:
- Decision Version: this implementation is able to encode in a quantum circuit the Conjunctive Normal Form of a given SAT specified in the respective folder. The solver that is based on this initialization considers the Quantum Fourier Transform to find the solution. This solver only draws the representation of the conjunctive normal form for the SAT instance considered. It helped me to draw conclusions on the impossibility to implement a solver that encoded the problem in this way. To run the algorithm it suffices to use python and specify the name of the file containing the SAT problem to be represented:
python quantumSat.py satProblemDefinition
-
Exactly-1 k-SAT: this implementation consists of a real solver able to find a solution for the general version of a k-SAT problem with "unlimited" number of variables and clauses. This solver is based on Grover's search algorithm that uses Amplitude Amplification in order to find the correct solution. To execute the solver we need to pass four parameters:
- Problem Definition: the file containing the formalization of the problem
- System Flag: either 0 or 1, respectively 0 executes on the simulator while 1 on the real system
- Cycles: integer specifying the number of times you want to iterate Grover's Algorithm
- System Name: the name of the real system where you want to execute the algorithm. Check the enumeration Systems for the specific name.
In the end you will have to run using python with a code like the following:
python quantumSat.py satProblemDefinition 0|1 #cycles MELBOURNE -
Notebook: this jupyter notebook shows how the solver provided by Qiskit library is able to find the solution of very complex specifications of the problem. It has been used to start the approach with Qiskit and to understand the tradeof between the optimization regarding the number of qubits and the decoherence.
This folder contains the documentations related to the implementations I realized during my study. The result of my first research project is a paper that contains a brief introduction to the state of the art of quantum computing and then compares the quantum solvers with the classical counterparts. This paper is titled An Introdution to Quantum Computing for Computer Scientist, with SAT and it contains the precise descriptions of all the three implementations that can be find in the SAT folder in the Code section.