Number Partitioning¶

Definition¶

We are given a set of $N$ real and potentially repeating numbers and our aim is to partition them in two subsets, such that the sum of the numbers in each subset is equal (or as close as possible).

Applications¶

The Number Partitioning problem comes up in a variety of fields:

  • Fair division of assets between two parties.

  • In Statistical Mechanics to count the available states to many-particle systems and for calculation of the Partition function.

  • Partitioning irreducible representations of important groups like the permutation group $S(n)$ and the Unitary Group $U(n)$, which themselves have applications in Molecular Chemistry, Crystalography and Quantum Mechanics.

  • Computing many-variable integrals, representing wave functions of many-body systems and in Statistical Theory of Random Matrices that is used to model complex networks, disordered media and chaotic quantum systems.

  • Public key encryption and task scheduling.

Path to solving the problem¶

Number Partitioning can be formulated as a minimization problem and its cost function can be cast to an Ising problem through its respective Hamiltonian (see the Introduction and a reference),

$$ \displaystyle \large H = \displaystyle \left(\textstyle\sum\limits_{i=1}^{N} n_i s_i \right) ^2 $$

where $n_i$ is the $i$-th number from the list of numbers and $s_i$ is a spin variable, indicating which subset $n_i$ belongs to. If $s_i = 1$, it is in one subset and if $s_i = -1$, it is in the other.

Qaptiva HPC allows us to encode a problem in this Hamiltonian form with the help of the NumberPartitioning class and by providing a list of numbers. We can then create a job from the problem and send it to a Simulated Annealer (SA) wrapped with a Quantum Processing Unit (QPU) interface. The SA will minimize the Hamiltonian, hence we find the solution to our problem.

In fact, the QLM contains an even more powerful solver $-$ Simulated Quantum Annealing (SQA). This quantum annealer has been tested on numerous benchmarks for the NP problems supported and produces results with a quality usually exceeding $98\%$. More details can be found in the documentation.

Quantum resources¶

To represent the problem as Ising, myQLM would need $N$ spins, one for each number in the list.

Example problem¶

Imagine we are given a list of $30$ integers, drawn at random in the range $1$ to $50$. Let us describe the procedure for partitioning such a list using tools from the QLM. In fact, it will be applicable for finding the partitioning of any list of real numbers !

In [1]:
import numpy as np

# Specify the set of numbers
# First example
numbers_set = np.random.randint(low=1, high=50, size=30)

# # Second example
# numbers_set = (np.random.rand(1000) - 0.5) * 1000

# Show the set
print(numbers_set)

[24 48 28 48  3 22  7 21 39 34 13 33 18 29 21 12 42 30 22 36 39 43 32 20
 31 18  7 31  7 23]

We can then encode it with our NumberPartitioning class.

In [2]:
from qat.opt import NumberPartitioning

number_partitioning_problem = NumberPartitioning(numbers_set)

Solution¶

We can now proceed to compute the solution of the problem by the following procedure:

  1. Extract some fine-tuned parameters for NumberPartitioning (found for SQA) which are needed for the temperature schedule.

  2. Create the temperature schedule using the t time variable (instance of the class Variable) and thus the SimulatedAnnealing QPU.

  3. Create a job from the problem by calling the to_job() method and send it to the QPU.

  4. Extract the Result and present the solution spin configuration.

  5. Show the respective numbers in each set.

The solution configuration is a sequence of spins. The position of each spin in the array corresponds to the position of each number from the list. If a spin has the value $1$ or $-1$, this means that the respective number is either in the one or the other subset.

In [3]:
from qat.qpus import SimulatedAnnealing
from qat.simulated_annealing import integer_to_spins
from qat.core import Variable

# 1. Extract parameters for SA
problem_parameters_dict = number_partitioning_problem.get_best_parameters()
n_steps = problem_parameters_dict["n_steps"]
temp_max = problem_parameters_dict["temp_max"]
temp_min = problem_parameters_dict["temp_min"]

# 2. Create a temperature schedule and a QPU
tmax = 1.0
t = Variable("t", float)
temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)
sa_qpu = SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)

# 3. Create a job and send it to the QPU
problem_job = number_partitioning_problem.to_job('sqa', tmax=tmax)
problem_result = sa_qpu.submit(problem_job)

# 4. Extract and print the solution configuration
state = problem_result.raw_data[0].state.int  # raw_data is a list of Samples - one per computation
solution_configuration = integer_to_spins(state, len(numbers_set))
print("Solution configuration: \n" + str(solution_configuration) + "\n")

# 5. Show subsets
indices_spin_1 = np.where(solution_configuration == 1)[0]
spin_1_subset = [numbers_set[i] for i in indices_spin_1]
print("The first subset has the numbers:\n" + str(spin_1_subset) + "\n")

indices_spin_minus_1 = np.where(solution_configuration == -1)[0]
spin_minus_1_subset = [numbers_set[i] for i in indices_spin_minus_1]
print("The second subset has the numbers:\n" + str(spin_minus_1_subset))

Solution configuration: 
[ 1. -1. -1.  1.  1.  1. -1. -1. -1. -1. -1.  1. -1.  1.  1. -1. -1.  1.
 -1. -1. -1.  1.  1. -1.  1.  1. -1.  1. -1.  1.]

The first subset has the numbers:
[24, 48, 3, 22, 33, 29, 21, 30, 43, 32, 31, 18, 31, 23]

The second subset has the numbers:
[48, 28, 7, 21, 39, 34, 13, 18, 12, 42, 22, 36, 39, 20, 7, 7]

/tmp/ipykernel_3796/2267825075.py:18: UserWarning: If SQAQPU is used, gamma_t will be needed.
  problem_job = number_partitioning_problem.to_job('sqa', tmax=tmax)

Solution analysis¶

We can perform a simple check to decide how good the partitioning was. As stated in the beginning, the sums of the numbers in each subset should be equal (or very close).

In [4]:
print("Sum of the numbers in the first subset:\n" + str(sum(spin_1_subset)))
print("Sum of the numbers in the second subset:\n" + str(sum(spin_minus_1_subset)))

Sum of the numbers in the first subset:
388
Sum of the numbers in the second subset:
393