Small Problems with Two Variables

General Process

The following steps can be used to create a two-variable BQM.

  1. Make a constraint satisfaction table.
  2. Create a system of equations.
  3. Solve the system of equations.

The constraint satisfaction table is similar to a truth table - it covers all possible values for our two variables and considers whether or not the constraint that we are modeling is true or false for each choice of values.

Example

We start with a simple problem. We have two variables, say \(v_1\) and \(v_2\), and we want a BQM that represents the constraint \(v_1=v_2\). For QUBO and Ising we follow the same process.

Step 1: Constraint Satisfaction Table

Set up a table for the two variables that covers all possible values they might take. Add a column in the table to indicate whether or not the constraint is satisfied (true) for each combination of variable values.

QUBO Ising Equal?
\(x_1\) \(x_2\) \(s_1\) \(s_2\)
0 0 -1 -1 Yes
0 1 -1 +1 No
1 0 +1 -1 No
1 1 +1 +1 Yes

Next, replace the final column of yes/no values with small/large values, respectively.

QUBO Ising Value
\(x_1\) \(x_2\) \(s_1\) \(s_2\)
0 0 -1 -1 0
0 1 -1 +1 1
1 0 +1 -1 1
1 1 +1 +1 0

In this step, we choose a small value when the constraint is satisfied because the QPU is designed to minimize a BQM. By choosing a small value, we line up the ground state (lowest energy the QPU can find) with the constraint being satisfied. Note that any choice of small and large value can be used.

Step 2: Make a System of Equations

Recall from the last section the general form for QUBO and Ising.

QUBO:

\[a_1x_1+a_2x_2+b_{1,2}x_1x_2+c\]

Ising:

\[h_1s_1+h_2s_2+J_{1,2}s_1s_2+c\]

Using each row in the constraint satisfaction table, we can write an equation. Each pair of variable values, the general BQM model, and the final column value together determine an equation in which the BQM coefficients are the only unknowns. This results in four different equations (one for each row in the table).

QUBO Ising
\(a_1\cdot 0+a_2 \cdot 0 +b_{1,2} \cdot 0 \cdot 0 +c=0\) \(h_1\cdot (-1)+h_2\cdot (-1)+J_{1,2}\cdot (-1)\cdot (-1)+c=0\)
\(a_1\cdot 0+a_2 \cdot 1 +b_{1,2} \cdot 0 \cdot 1 +c=1\) \(h_1\cdot (-1)+h_2\cdot (+1)+J_{1,2}\cdot (-1)\cdot (+1)+c=1\)
\(a_1\cdot 1+a_2 \cdot 0 +b_{1,2} \cdot 1 \cdot 0 +c=1\) \(h_1\cdot (+1)+h_2\cdot (-1)+J_{1,2}\cdot (+1)\cdot (-1)+c=1\)
\(a_1\cdot 1+a_2 \cdot 1 +b_{1,2} \cdot 1 \cdot 1 +c=0\) \(h_1\cdot (+1)+h_2\cdot (+1)+J_{1,2}\cdot (+1)\cdot (+1)+c=0\)

Step 3: Solve the System of Equations

Solve the system of equations for your coefficients.

QUBO Ising
\(a_1=1\) \(h_1=0\)
\(a_2 =1\) \(h_2 =0\)
\(b_{1,2}=-2\) \(J_{1,2}=-0.5\)
\(c=0\) \(c=0.5\)

To help with solving these systems of equations there are many resources online that are available. Some of these are WolframAlpha (wolframalpha.com) or Matrix Calculator (matrixcalc.org).

Our final models are:

QUBO:

\[x_1+x_2-2x_1x_2\]

Ising:

\[-0.5s_1s_2+0.5\]

Exercise

What do the QUBO and Ising models look like for the constraint \(v_1\geq v_2\)?