This thesis addresses the Maximum Independent Set problem and its solution using the Pulser quantum emulator. Pulser enables the emulation of Pasqal's quantum processor, which is based on neutral atom technology. The problem is first formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem and then mapped to the task of finding the ground state of an appropriate Hamiltonian.
To solve the problem, we employ an adiabatic quantum algorithm, in which the quantum system is slowly evolved from an easily prepared initial state to a final state that encodes the solution. We also examine the physical model of Rydberg atoms, which naturally enables the encoding of unit disk graphs.
The algorithm is implemented and analyzed using the Pulser framework. Simulation results show that performance improves with longer evolution times and depends on the choice of parameters such as the Rabi frequency and detuning. The results indicate that quantum approaches represent a promising direction for solving combinatorial optimization problems.
|
