# Study of Approximate Solutions for The Number Partitioning Problem

## Palavras-chave:

Number Partitioning, Quantum Approximate Optimization Algorithm, Evolutionary Methods## 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.