4
$\begingroup$

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.

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – DaftWullie Jul 25 '19 at 7:22
  • $\begingroup$ @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? $\endgroup$ – beatbrot Jul 25 '19 at 9:27
  • 1
    $\begingroup$ 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. $\endgroup$ – DaftWullie Jul 25 '19 at 10:42
  • $\begingroup$ 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. $\endgroup$ – AHusain Aug 25 '19 at 0:15
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.