How would I construct an Ising Hamiltonian for binary linear programming?

So I am preparing for an exam and stumbled upon this question which I am unable to answer:

The problem Binary Integer Linear Programming tries to find a binary vector $$\vec x=(x_1,x_2, ...,x_n)^T$$ with $$x \in \mathbb{F_2}$$ that maximizes the value of $$\vec s * \vec b$$ under the constraint that $$S\vec x = \vec b$$. The values $$\vec s \in \mathbb{F_2^n}, b\in \mathbb{F_2^n}$$ and $$S \in \mathbb{F_2^{n\times m}}$$ are given. Construct an Ising-Hamiltonian for the optimization problem.

Hint: Construct a Hamiltonian for the constraints, a hamiltonian for the maximization and construct a superposition with the fitting coefficients

While I do understand that the Ising Model can help us with optimization problems and I kinda figured out what my constraints and maximization function would look like, I do not know how I should construct a superposition and what it would be useful for.

• Are you sure that the use of "superposition" in the question statement is really meaning superposition in terms of a state? I wonder if it perhaps meant that you're supposed to add the different Hamiltonians together with some appropriate weights? Jul 25 '19 at 7:22
• @DaftWullie Tbh I am not sure, no. Adding them together with appropriate weights would make a ton of sense tough! Do you think that one could interprete the word "superposition" in that way? Jul 25 '19 at 9:27
• You shouldn't in normal circumstances! But I struggle to see what else it means. After all, the only state you'll be finding is a ground state, which is a basis state in the case of the Ising model (i.e. not a superposition). Still, someone else might understand things differently. Jul 25 '19 at 10:42
• You shouldn't be writing $\mathbb{F}_2$ for this problem. Otherwise $\vec{s} * \vec{b}$ would be an inner product in $\mathbb{F}_2^n$ which would produce an element of $\mathbb{F}_2$ as a result. It would be linear algebra over a finite field. Here, you only want to say the inputs are $0$ and $1$, but still integers, not elements of the finite field. Aug 25 '19 at 0:15

The word superposition had many meanings long before the phrase quantum superposition became popular.

A linear super-position of A and B is just "A + cB" where c is a constant.

So you have your binary optimization problem that has to be solved, for example:

H_problem = b1*b2 - b1*b3 + 2*b2*b4.

Then you have a constraint such as "b1*b2 = 1" which can be converted into a binary optimization problem because minimizing:

H_constraint = (b1*b2 - 1)^2

is the same as satisfying the constraint "b1*b2 = 1".

So the final Hamiltonian will be a linear superposition:

H = H_problem + c*H_constraint, where c > 0.

The goal is for the minimum of H to be the minimum of H_problem, and to also satisfy the constraint. Now notice that if the constraint is not satisfied, we don't have a minimum, because we will be adding a positive number, making the energy higher. If H_problem is not minimized, then clearly H is not minimized because one of the terms in H can be made lower by minimizing H_problem. So overall, H will only be minimized if both:

• H_problem is minimized, and
• H_constraint is minimized (i.e. the constraint is satisfied).

You can now convert this into Ising model by turning all binary variables from b={0,1} to sigma_z={-1,1}.

Hope this helps. It seems you've been thinking about quantum information for too long now, and now when you see "superposition" you immediately think (|0> + |1>)/sqrt(2). But superposition had another meaning long before quantum information became popular.

• how to include multiple constraints? Aug 26 '20 at 21:07