Quantum Alternating Operator Ansatz assisted by Quantum Annealing

Quantum computing holds great promise for solving problems that are intractable for classical computers, yet achieving practical quantum advantage remains a challenge for current Noisy Intermediate-Scale Quantum (NISQ) devices. This thesis explores a hybrid approach combining two of the main paradigms of quantum computation, i.e. gate-based quantum computing and Quantum Annealing, to solve the NP-hard Minimum Exact Cover Problem (MECP). A MECP instance consists of a set and a collection of its subsets. The goal is to cover all elements exactly once by selecting the minimum number of subsets. The MECP can be reframed as finding the ground state of an Ising Hamiltonian and it can be solved via simulation on Qiskit of the Quantum Alternating Operator Ansatz (QAOA+), a Variational Quantum Algorithm that aims to enhance the efficiency of the Quantum Approximate Optimization Algorithm (QAOA) by limiting the search space to states that satisfy the problem's constraints. However, QAOA+ requires to be initialized in a feasible state, which can itself be an NP-complete problem. This thesis examines an existing trivial initialization state and introduces a more efficient alternative. It also compares different QAOA+’s parameters initialization techniques, discovering that, under resource-limited conditions, the Random Initialization technique performs better than Parameter Fixing. Moreover, the Hamiltonian’s hyperparameters are tuned with Quantum Annealing on a D-Wave annealer to enhance QAOA+ performance by increasing the energy gap between the optimal solution and the first excited state. These results indicate that hybrid strategies could be a promising approach for tackling combinatorial optimization problems on NISQ devices.