About the author:
Daniel is co-founder and CTO at Aqarios GmbH. He holds a M.Sc.
in Computer Science from LMU Munich, and has published papers
in reinforcement learning. He writes about technical topics in
quantum computing.
We have an extremely simple Number Partitioning problem consisting of the set
of numbers {1,2,3}. It has an optimal solution, which is splitting the
set into two subsets {1,2} and {3}.
The Ising formulation for Number Partitioning is given as
A(∑j=1mnjxj)2, where nj is the j-th number in the set.
Thus, with A=1, for the given set the result is
(x1+2x2+3x3)2=x1x1+4x1x2+6x1x3+4x2x2+12x2x3+9x3x3.
Now, the Hamiltonian for an Ising formulation is very simple: Replace xi
by a Pauli Z Gate. We can now write the Hamiltonian using QuBits (with an
exemplary QuBit state):
⟨010∣Z1Z2Z3∣010⟩
Thus, we can evaluate the cost of a possible set of subsets by using QuBits.
For instance, a state ∣010⟩ means that the numbers 1 and 3 are in
one subset and the number 2 is in another subset.
It should be noted that ⟨1∣Zi∣1⟩=−1 and
⟨0∣Zi∣0⟩=1.
More specifically (where xi=Zi), the Quantum formulation for our problem is: