Embedding strategies for adiabatic quantum computation

Abstract

Quantum Annealing (QA) is an alternative to gate based Quantum Computation (QC) to solve problems not efficiently tractable on classical devices. Right now, QA is advantageous over QC in the noisy intermediate-scale quantum (NISQ) era for its lesser need of error correction codes and the resource overhead they suppose. However, hardware limitations in terms of connectivity and feasible interactions create incompatibilities between the chip and the structure of the problem, which leads to what is called the graph embedding problem. To circumvent this obstacle, we first analyse the current solutions based on heuristic algorithms and their limitations. We then explore the potential of a digital assisted annealing (DaA) approach. The novelty of this technique relies on the fact that the state generated by the quantum annealer is used as the initial state of the variational circuit, the role of which is to approach a target solution the annealer could not reach by itself due to its hardware limitations. We complete this thesis with a detailed study on the performance of our approach for different scenarios and branches we would like to explore.