This Qiskit Aqua Optimization notebook demonstrates how to use the VQE algorithm to compute a balanced partition of a set of numbers. This problem is known as "number partitioning" or simply "partition" in computer science.
The problem is defined as follows. We are given a set of numbers $S$, and we want to determine a partition of $S$ into disjoint sets $S_1, S_2$ such that $|\sum_{a \in S_1} - \sum_{a \in S_2}|$ is minimized.
The list of numbers provided as an input is used first to generate an Ising Hamiltonian, which is then passed as an input to VQE. As a reference, this notebook also computes the maximum stable set using the NumPyMinimumEigensolver classical algorithm and the solver embedded in the commercial IBM CPLEX product (if it is available in the system and the user has followed the necessary configuration steps in order for Qiskit Aqua to find it). Please refer to the Qiskit Aqua Optimization documentation for installation and configuration details for CPLEX.
import numpy as np
from qiskit import BasicAer
from qiskit.aqua import QuantumInstance
from qiskit.optimization.applications.ising import partition
from qiskit.aqua.algorithms import NumPyMinimumEigensolver, VQE
from qiskit.aqua.components.optimizers import L_BFGS_B
from qiskit.circuit.library import TwoLocal
from qiskit.optimization.applications.ising.common import (read_numbers_from_file,
random_number_list, sample_most_likely)
Here an Operator instance is created for our Hamiltonian. In this case the Paulis are from an Ising Hamiltonian of the number partitioning problem (expressed in minimization form). Rather than minimizing the absolute value of the difference of the sum of numbers into two sets, we minimize the difference square.
We load a small instance of the problem.
number_list = read_numbers_from_file('sample.partition')
qubitOp, offset = partition.get_operator(number_list)
print(number_list)
[ 1 3 4 7 10 13 15 16]
We also offer a function to generate a set of numbers as a input.
if True:
np.random.seed(8123179)
number_list = random_number_list(5, weight_range=25)
qubitOp, offset = partition.get_operator(number_list)
print(number_list)
[ 9 8 23 4 2]
Here we test for the presence of algorithms we want to use in this notebook. If Aqua is installed correctly NumPyMinimumEigensolver and VQE will always be found. ClassicalCPLEX is dependent on CPLEX being installed (see introduction above). CPLEX is not required but if installed then this notebook will demonstrate the ClassicalCPLEX algorithm , that uses CPLEX, to compute partition as well.
to_be_tested_algos = ['NumPyMinimumEigensolver', 'ClassicalCPLEX', 'VQE']
print(to_be_tested_algos)
['NumPyMinimumEigensolver', 'ClassicalCPLEX', 'VQE']
We can now use the Operator without regard to how it was created. Here we will use the NumPyMinimumEigensolver first to return the smallest eigenvalue. Backend is not required since this is computed classically not using quantum computation. The result is a dictionary.
result = NumPyMinimumEigensolver(qubitOp).run()
x = sample_most_likely(result.eigenstate)
print('energy:', result.eigenvalue.real)
print('partition objective:', result.eigenvalue.real + offset)
print('solution:', x)
print('solution objective:', partition.partition_value(x, number_list))
energy: -694.0 partition objective: 0.0 solution: [1 1 0 1 1] solution objective: 0
Note: If CPLEX is installed then the Aqua ClassicalCPLEX algorithm will be able to be used. If not, then solving this problem using this particular algorithm will simply be skipped.
We change the configuration parameters to solve it with the CPLEX backend. The CPLEX backend can deal with a particular type of Hamiltonian called Ising Hamiltonian, which consists of only Pauli Z at most second order and often for combinatorial optimization problems that can be formulated as quadratic unconstrained binary optimization problems, such as the Number Partitioning problem.
Note that for a Number Partitioning problem, since we are computing a bipartition of the set $S$, every binary vector $x$ and its complement (i.e., the vector $y$ such that $y_j = 1 - x_j$ for all $j$) represent exactly the same solution, and will have the same objective function value. Different solution methods may return solutions that look different, but in fact have the same objective function value.
try:
from qiskit.aqua.algorithms import ClassicalCPLEX
result = ClassicalCPLEX(qubitOp, display=0).run()
x_dict = result['x_sol']
print('energy:', result['energy'])
print('time:', result['eval_time'])
print('partition objective:', result['energy'] + offset)
x = np.array([x_dict[i] for i in sorted(x_dict.keys())])
print('solution:', x)
print('solution objective:', partition.partition_value(x, number_list))
except Exception as ex:
print(str(ex))
Version identifier: 12.10.0.0 | 2019-11-27 | 843d4de CPXPARAM_Read_DataCheck 1 CPXPARAM_Threads 1 CPXPARAM_MIP_Display 0 CPXPARAM_TimeLimit 600 CPXPARAM_MIP_Tolerances_MIPGap 0 CPXPARAM_MIP_Tolerances_Integrality 0 energy: -694.0 time: 0.050331075999999975 partition objective: 0.0 solution: [1 1 0 1 1] solution objective: 0
Now we want VQE and so change it and add its other configuration parameters. VQE also needs and optimizer and variational form. While we can omit them from the dictionary, such that defaults are used, here we specify them explicitly so we can set their parameters as we desire.
vqe = VQE(qubitOp,
TwoLocal(qubitOp.num_qubits, ['ry', 'rz'], 'cz', reps=3, entanglement='linear'),
L_BFGS_B(maxfun=6000))
result = vqe.run(QuantumInstance(BasicAer.get_backend('statevector_simulator')))
x = sample_most_likely(result.eigenstate)
print('energy:', result.eigenvalue.real)
print('time:', result.optimizer_time)
print('partition objective:', result.eigenvalue.real + offset)
print('solution:', x)
print('solution objective:', partition.partition_value(x, number_list))
energy: -693.9999999999553 time: 38.03071618080139 partition objective: 4.46789272245951e-11 solution: [0. 0. 1. 0. 0.] solution objective: 0