Relatore: Davide Pastorello (Università di Trento)
Abstract
In Adiabatic Quantum Computing (AQC) and Quantum Annealing (QA) the solution of a given problem is encoded in the ground state of a quantum system. The computation is realized by the evolution of the system from a known initial state towards the ground state. The typical hardware architecture of a quantum annealer is given by a network of qubits arranged on the vertices of a graph whose edges represent the interactions between neighbors. The embedding of a given optimization problem into the hardware architecture of a quantum annealer may be computationally hard with deleterious effects on performances. In this talk I introduce a hybrid algorithm where repeated calls of a quantum annealer are carried out within a classical iterative structure. In the considered approach the representation of the problem into the quantum architecture is not a priori fixed but evolves guided by a variation of the tabu search paradigm. This scheme provides a procedure to avoid the direct reduction of a general quadratic unconstrained binary optimization (QUBO) problem into the sparse quantum annealer graph [1]. Moreover I introduce another hybrid algorithm to solve optimization problems with an adiabatic quantum computer, where the solution must be encoded into the ground state of a “problem Hamiltonian”. Here the algorithm implements a search in the space of available Hamiltonians in order to find the best encoding of the given problem [2]. This hybrid algorithm returns a solution of the considered optimization problem, a Hamiltonian operator whose ground state corresponds to the solution and the evolution time to reach the ground state. Therefore the present scheme can be used to learn adiabatic quantum algorithms by examples to solve a considered class of optimization problems.