Bachelor and Master Theses

The Hamiltonian Cycle Problem (HCP is a well-known NP-hard problem in graph theory with exponential computational complexity. It seeks a cycle in an undirected graph that visits each vertex exactly once. This master’s thesis proposes an investigation into solving HCP for small graph instances using hybrid quantum-classical algorithms, specifically the Quantum Approximate Optimization Algorithm (QAOA), implemented via Qiskit. By leveraging near-term quantum devices or simulations, the study aims to encode HCP, optimize quantum circuits, and benchmark performance against classical methods like backtracking and simulated annealing. The work will address hardware limitations, offering practical strategies for quantum optimization in the noisy intermediate-scale quantum (NISQ) era.

More specifically, the thesis work includes the following:

1.     Encode HCP into quantum circuits for QAOA, exploring efficient mappings (e.g., permutation or adjacency-based).

2.     Implement QAOA in Qiskit, optimizing circuits for minimal depth and noise resilience.

3.     Tune classical parameters to enhance solution quality.

4.     Benchmark QAOA against classical solvers on small graphs (5-10 vertices), comparing solution quality, runtime, and resource usage.

5.     Identify strategies to mitigate NISQ hardware constraints, providing insights for scaling to larger instances.

HCP will be reformulated as a quantum optimization problem, mapping graph structures to qubit interactions using permutation-based or adjacency-based encodings to minimize qubit requirements. QAOA circuits will be built in Qiskit and tested on Qiskit Aer simulators with noise models (and potentially running on IBM Quantum devices). Optimizations include transpilation for hardware topologies and error mitigation. Classical optimizers (e.g., COBYLA, SPSA) will tune QAOA parameters. Post-processing will decode quantum outputs into valid cycles, possibly with greedy heuristics. Experiments will use small graphs (random, complete, or TSP-like). Classical baselines (backtracking, simulated annealing) will be implemented in Python. Metrics include approximation ratio, runtime, and resources (qubits, gates, or iterations). Qiskit is the preferred language. However, other alternatives include PennyLane, Cirq, or Q#.

Prerequisites

Suitable for students with Python, graph theory, and basic quantum mechanics knowledge. No quantum hardware experience is required.