Number Partitioning

Given a set of real and potentially repeating numbers, the problem consists in partitioning them in two subsets, such that the sum of the numbers in both of them is equal (or as close as possible). To obtain an answer, we would need to use our NumberPartitioning class and anneal \(N\) spins, where \(N\) is the size of the set of numbers.

Solving this problem using the simulated annealing method requires the SimulatedAnnealing QPU.

import numpy as np
from qat.opt import NumberPartitioning
from qat.qpus import SimulatedAnnealing
from qat.simulated_annealing import integer_to_spins
from qat.core import Variable

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

# Show the set
print(numbers_set)
number_partitioning_problem = NumberPartitioning(numbers_set)

# 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"]

# 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)

# 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)

# 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")

# 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))

[16 20 40 30 20  9 36 32 11 18  9 18 48 12  1 44 14 33  1 34 47 39 27  7
 26 44 12 35 19 28]
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:
[40, 20, 11, 18, 44, 14, 47, 7, 26, 44, 12, 35, 19, 28]

The second subset has the numbers:
[16, 20, 30, 9, 36, 32, 9, 18, 48, 12, 1, 33, 1, 34, 39, 27]
<stdin>:27: UserWarning: If SQAQPU is used, gamma_t will be needed.

This example is also detailed in this notebook on solving Number Partitioning problems with SA.