Last July, BSC member Sergi Ramos defended his TFG (Treball de Final de Grau, the equivalent of a Bachelor’s thesis) titled ‘Gap analysis for an adiabatic approach to the Exact Cover problem’. Sergi received an outstanding score!
Here is a summary of the project:
Adiabatic quantum computation is widely used for solving satisfiability problems. One of this problems is the Exact Cover problem, an extension to the 3-SAT problem with a unique solution. This fact makes the adiabatic approach to quantum computation extremely useful when solving this Exact Cover problem, as one can map the unique solution to a non-degenerate energy ground state.
The time needed to perform a computation scales with the inverse of the gap energy, squared. This gap energy is the energy difference between the ground state, solution of the problem, and the first excited state. A way in which the computation time can be improves is by finding an algorithm that increases the gap energy of the problem.
The algorithm proposed is based on the idea that not all clauses of the problem affect the outcome in the same way. Using a weighted system that classifies each clause in the problem using their number of appearances in each different instance, an improvement in the gap energy has been found. Additionally, the gap gain increases with the number of clauses (qubits) in the problem, since their underlying symmetries can be exploited more easily.