<jupyter_start><jupyter_text>Number Partitioning DefinitionWe 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). ApplicationsThe 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 problemNumber 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](./introduction_combinatorial_optimization.ipynb) and a [reference](https://arxiv.org/abs/1302.5843)),$$ \displaystyle \largeH = \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. The QLM 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 heuristic Simulated Quantum Annealer (SQA) wrapped inside a Quantum Processing Unit (QPU). The SQA will minimize the Hamiltonian, hence find the best solution to our problem.For a more detailed explanation and a step-by-step guidance, please follow the sections below. Quantum resourcesTo represent the problem as Ising the QLM would need $N$ spins for each number in the list.   Example problemImagine 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 !<jupyter_code>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(10000) - 0.5) * 10000

# Show the set
print(numbers_set)<jupyter_output>[ 5 32 13 19 11 36 41 25 36 16 37 36 39 35 20 19 18 22  1 11 37 30 22 20
 10 47 41 12 26 10]<jupyter_text>We can then encode it with our `NumberPartitioning` class.<jupyter_code>from qat.opt import NumberPartitioning

number_partitioning_problem = NumberPartitioning(numbers_set)<jupyter_output><empty_output><jupyter_text>Solution Now we can proceed to compute the solution of the problem by following the steps:1. Extract the best SQA parameters found for Number Partitioning by calling the method `get_best_parameters()`.    The number of Monte Carlo updates is the total number of updates performed for each temperature (and gamma) on the spins of the equivalent 2D classical system. These updates are the product of the number of annealing steps $-$ `n_steps`, the number of "Trotter replicas" $-$ `n_trotters`, and the problem size, i.e. the number of qubits needed. Hence, we can use these parameters to get the best inferred value for `n_steps`. In general, the more these steps are, the finer and better the annealing will be. However this will cause the process to take longer to complete.        Similarly for the `n_trotters` field in `SQAQPU` $-$ the higher it is, the better the final solution could be, but the more time taken by the annealer to reach an answer.2. Create a temperature and a gamma schedule for the annealing.    We use the extracted max and min temperatures and gammas to create a (linear) temperature and a (linear) gamma schedule. These schedules evolve in time from higher to lower values since we simulate the reduction of temperatures and magnetic fields. If one wishes to vary them it may help if the min values are close to $0$, as this will cause the Hamiltonian to reach a lower energy state, potentially closer to its ground state (where the solution is encoded).    It should be noted that non-linear schedules may be investigated too, but for the same number of steps they could lead to a slower annealing. The best min and max values for gamma and the temperature were found for linear schedules.3. Generate the SQAQPU and create a job for the problem. The job is then sent to the QPU and the annealing is performed.4. 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.<jupyter_code>from qat.sqa import SQAQPU
from qat.core import Variable
from qat.sqa.sqa_qpu import integer_to_spins

# 1. Extract parameters for SQA
problem_parameters_dict = number_partitioning_problem.get_best_parameters()
n_monte_carlo_updates = problem_parameters_dict["n_monte_carlo_updates"]
n_trotters = problem_parameters_dict["n_trotters"]
n_steps = int(n_monte_carlo_updates /
              (n_trotters * len(numbers_set))) # the last one is the number of spins, i.e. the problem size
temp_max = problem_parameters_dict["temp_max"]
temp_min = problem_parameters_dict["temp_min"]
gamma_max = problem_parameters_dict["gamma_max"]
gamma_min = problem_parameters_dict["gamma_min"]

# 2. Create a temperature and a gamma schedule
tmax = 1.0
t = Variable("t", float)
temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)
gamma_t = gamma_min * (t / tmax) + gamma_max * (1 - t / tmax)

# 3. Create a job and send it to a QPU
problem_job = number_partitioning_problem.to_job(gamma_t=gamma_t, tmax=tmax, nbshots=1)
sqa_qpu = SQAQPU(temp_t=temp_t, n_steps=n_steps, n_trotters=n_trotters)
problem_result = sqa_qpu.submit(problem_job)

# 4. Present best configuration
state_int = problem_result.raw_data[0].state.int  # raw_data is a list of Samples - one per shot
solution_configuration = integer_to_spins(state_int, 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))<jupyter_output>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:
[16, 36, 39, 35, 20, 19, 18, 22, 11, 22, 20, 10, 47, 12, 26, 10]

The second subset has the numbers:
[5, 32, 13, 19, 11, 36, 41, 25, 36, 37, 1, 37, 30, 41]<jupyter_text>Solution analysisWe 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).<jupyter_code>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)))<jupyter_output>Sum of the numbers in the first subset:
363
Sum of the numbers in the second subset:
364
{'fraction_non_alphanumeric': 0.07198986058301647, 'fraction_numerical': 0.02788339670468948, 'mean_word_length': 4.6444921316165955, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '464759', 'license': 'Apache-2.0', 'n_tokens_mistral': 2480, 'n_tokens_neox': 2220, 'n_words': 1098, 'path': 'misc/notebooks/tutorials/combinatorial_optimization/number_partitioning.ipynb', 'repo_name': 'wmkirby1/CS-VQE', 'size': '7890'}