Study of Approximate Solutions for The Number Partitioning Problem

Resumo

The number partitioning problem (npp) is important because it is a combinatorial optimization NP-hard
problem and one of the canonical cases of NP-complete decision problem described in the literature. An exact
formulation for the decision problem is presented through dynamic programming approach. However, since the
npp is NP-complete, the dynamic programming algorithm has pseudo-polynomial complexity time which works
well for small instances. Also, several heuristic methods are used to approximate the exact solution for the problem.
In this paper, following the Ising formulation described in the literature, the npp optimization problem is formulated
as a cost Hamiltonian in terms of spin variables. Additionally, we discuss solutions for this formulation by two
quantum heuristics for a limited number of qubits. In the first one, we use a Quantum Approximate Optimization
Algorithm procedure based on some given ansatz to make a search for approximate solutions. In the second one,
we use an evolutionary technique ansatz-free with evolutionary quantum gate circuits. Both procedures show the
good features of the Ising model formulation for easy instances of such a problem.