Combinatorial optimization deals with problems in which we seek an optimal solution
within a finite set of possible solutions, with the goal of minimizing or maximizing a
given objective function. Such problems are often NP-hard, since the number of possible
solution combinations grows exponentially with the number of variables. The QUBO
model (Quadratic Unconstrained Binary Optimization) provides a unified and practical
formulation for a wide range of such problems, making them solvable by both classical
and quantum approaches. In this thesis, we describe the complete process of solving
the knapsack problem. The problem is first presented in its classical formulation and
then gradually converted into the QUBO form. The end result of this process is a
matrix that encodes the entire optimization problem. The problem is then solved with
the Quantum Approximate Optimization Algorithm (QAOA), implemented in the Qrisp
framework. We describe in detail the conversion of the QUBO matrix into a Hamiltonian
operator, the construction of the corresponding quantum circuit, and the execution of
the algorithm on the Qiskit Aer simulator. In the concluding part, we also discuss the
obstacles to running QAOA on actual quantum computers, such as the effects of noise,
circuit-depth limitations, and measurement errors, all of which pose significant challenges
for the practical use of the algorithm.
|
