Memetic algorithms for mapping p-body interacting systems in effective quantum 2-body Hamiltonians

Quantum computing is an emerging research area which promises to offer a revolution in the computing performance. The world's first commercially available quantum computer has been the D-Wave machine which aims at solving complex problems by representing them in terms of Ising Hamiltonians. This formulation allows addressing several combinatorial optimization problems since generally it is possible to map any problem to the Hamiltonian of the Ising model. However, D-Wave's architecture restricts the Ising Hamiltonian to the case with only 2-body interactions. Therefore, in order to face problems mapped on systems with p-body interactions (p≥2), it is necessary to implement a procedure to compute 2-body effective Hamiltonians of p-body interacting systems. Due to the complexity of this task, recently, meta-heuristic methods have been applied with promising results. The aim of this paper is to implement a procedure to convert from p-body to 2-body Hamiltonians by means of memetic algorithms. As shown in the experimental session involving the ferromagnetic p-spin model as a case study, the proposed approach improves by 60% on average over the state-of-the-art meta-heuristic approaches.