Extended Examples

Formulating an Integer CSP as a QUBO Problem

As an example application of reformulating a given problem as a QUBO with the techniques of Reformulating a Problem, this example shows how any integer program may be converted to QUBO form. An example of an integer CSP is the map coloring problem described in Simple Map Coloring Problem.

Consider the integer program:

\[\min_{\vc{y}} \, \ip{\vc{c}}{\vc{y}} \qquad \text{subject to:} \;\;\; \vc{A}\vc{y} = \vc{a}, \;\; \vc{B}\vc{y} \le \vc{b}, \;\; y_i\in \{0,D_i-1\}\]

where \(D_i\) is the number of allowed values for variable \(y_i\). As a first step in translating this into a QUBO, the non-binary valued \(y_i\) must be made binary valued. This can be accomplished either by introducing indicator variables or by writing \(y_i\) in binary. We write \(y_i\) in binary to limit the number of new Boolean valued variables required. Let \(d_i = \lceil \log_2 D_i \rceil\) and \(y_i = \ip{\vc{2}}{\vc{x}_i}\) where \(\vc{2}=[2^{d_i},\cdots, 2,1]\) is the vector of powers of two and \(\vc{x}_i = [x_{i,d_i}, \cdots, x_{i,1}, x_{i,0}]\) represents the bits of \(y_i\). The binary representation may allow for \(y_i\) values larger than \(D_i\) so we further impose the inequality constraints that \(\ip{\vc{2}}{\vc{x}_i}\le D_i-1\). Thus, the original integer program may easily be converted to:

\[\min_{\vc{x}} \, \ip{\vc{c}}{\vc{x}} \qquad \text{subject to:} \;\;\; \vc{A}\vc{x} = \vc{a}, \;\; \vc{B}\vc{x} \le \vc{b}, \;\; x_i\in \{0,1\} \label{ipEq}\]

where the new \(\vc{B}\) and \(\vc{b}\) have the additional inequality constraints appended, and where \(\vc{c}\) has been suitably modified. In this form, it remains only to represent the equality and inequality constraints within the unconstrained QUBO. These are easily translated to quadratic penalties.

Thus, the binary program can be written as the QUBO objective:

\[\argmin_{\vc{x},\vc{\xi}} \left\{ \ip{\vc{c}}{\vc{x}} + \sum_k m^=_k \bigl(\ip{\vc{A}_k}{\vc{x}}-a_k \bigr)^2 + \sum_i m_i^\le \bigl(\ip{\vc{B}_i}{\vc{x}}-b_i + \ip{\vc{2}}{\vc{\xi}_i}\bigr)^2 \right\}\]

where \(k\) runs over the equality constraints and \(i\) runs over the inequality constraints.

The only remaining question is how to set the sizes of the penalty weights \(\vc{m}^=\) and \(\vc{m}^\le\). Without problem specific knowledge, we approach this issue the same way it is done in Lagrangian methods by incrementally increasing the weights until the constraints are satisfied. If \(\vc{m}=[\vc{m}^=,\vc{m}^\le]\) is some setting of the penalty weights and \(\vc{x}(\vc{m}),\vc{\xi}(\vc{m})\) are the optimal variable settings for that choice of \(\vc{m}\), then we update the penalty weights in proportion to the constraint violations:

\[m^=_k :=m^=_k + \alpha \bigl| \ip{\vc{A}_k}{\vc{x}(\vc{m})} - a_k \bigr| m^\le_k := m^\le_k + \alpha\bigl| \ip{\vc{B}_k}{\vc{x}(\vc{m})} - b_k + \ip{\vc{2}}{\vc{\xi}(\vc{m})} \bigr|,\]

where \(\alpha>0\) determines the rate at which penalty weights are accumulated.

Further information

  • [Bac2002] compares performance of two transformations from non-binary to binary constraints used in CSPs: the dual transformation and the hidden (variable) transformation.

Factoring

The factoring problem is to decompose a number into a product of other numbers (factors) that give the original when multiplied together. [Bur2002] shows that factoring can be used as a generator of difficult optimization problems.

This section shows a complete example of solving a problem with QUBOs, using techniques that make best use of the D-Wave system. As here, it is generally true that in any given problem, precision, connectivity, and number of qubits may all be traded off against each other.

This example factors \(p\), an integer of \(\ell\) bits, as a product of a pair of integers \(a\) and \(b\), all represented in binary[1]. Factors \(a\) and \(b\) are assumed to be \(\ell_a\) and \(\ell_b\) bits respectively so that \(\ell=\ell_a+\ell_b\) or \(\ell=\ell_a+\ell_b-1\).

[1]
That is, \(p=\ip{\vc{2}}{\vc{p}}\), \(a=\ip{\vc{2}}{\vc{a}}\), and
\(b=\ip{\vc{2}}{\vc{b}}\) where \(\vc{2}\) is a vector of the powers of two of appropriate length.

One approach is to cast this task as an optimization problem for which a reasonable objective is to minimize the difference:

\[\argmin_{\vc{a},\vc{b}} \bigl(p-\ip{\vc{a}}{\vc{2}} \ip{\vc{2}}{\vc{b}} \bigr)^2.\]

This reformulation involves quartic interactions in the optimization variables so ancillary variables will need to be introduced to reduce the objective to quadratic as described in Non-Quadratic (Higher-Degree) Polynomials to Ising/QUBO. More problematically, there are a large number of interactions between pairs of variables and the magnitudes of these interactions varies from \(1\) to \(2^{2\ell_a+2\ell_b-4}\). Thus, both connectivity and precision requirements are severe in this formulation of the problem as described in Overcoming Imprecisions of Qubit Biases and Coupling Strengths.

To ameliorate these difficulties, we adapt the ``inverse verification” idea to this factoring context. Representing factoring as a constraint satisfaction problem, as discussed in CSP Reformulation with Inverse Verification, greatly reduces precision requirements, and Boolean circuits (see Elementary Boolean Operations to QUBO) enable us to tuneably define the connectivity between optimization variables.

Multiplication Circuits as QUBOs

For factorization, the verification circuit is formed from the circuit which multiplies the inputs \(\vc{a}\) and \(\vc{b}\). We then fix the output of the circuit to the known bit string \(\vc{p}\), and minimize the energy of the penalty formulation of the circuit to find \(\vc{a}\) and \(\vc{b}\). The multiplication circuit is built from AND gates, half adders and full adders. The AND gate which realizes \(t=x_1 \wedge x_2\) is given by the penalty \(P_\wedge(x_1,x_2;t)= x_1 x_2-2(x_1+x_2)r + 3t\). The half adder takes two input bits \(x_1\) and \(x_2\) and gives two output bits \(s\) and \(c\) representing the sum and carry of the two bits. These are defined through \(s+2c=x_1+x_2\). Clearly, then the penalty function for this equality constraint is \(P_{2A}(x_1,x_2;s,c) = (s+2c-x_1-x_2)^2\). Similarly, the full adder adds three inputs bits and returns the sum and carry as \(s+2c=x_1+x_2+x_3\). The full adder penalty function is \(P_{3A}(x_1,x_2,x_3;s,c) = (s+2c=x_1+x_2+x_3)^2\). The penalty functions result in fully connected groups of 3, 4, and 5 variables respectively. Moreover, the range of coupling coefficients is small. The full multiplication circuit will be built from repeated use of these simple elements, and total precision requirements will remain small.

The multiplication circuit parallels standard multiplication circuits with logical gates replaced by the corresponding penalty functions. A simple circuit architecture is inspired by the explicit multiplication table. Consider the multiplication of two 4 bit integers. Schematically, the product is formed from the multiplication shown in Figure 43.

image

Fig. 43 Multiplication of two 4-bit integers.

Multiplication of two 4-bit integers \((a_3,a_2,a_1,a_0)\) and \((b_3,b_2,b_1,b_0)\) form the 8-bit product \((p_7,p_6,p_5,p_4,p_3,p_2,p_1,p_0)\).

Each of the products \(a_i b_j\) is the logical AND of the two bits. We introduce the ancillary variables \(t_{i,j} \equiv a_i \wedge b_j\), \(s_b^l\) representing partial sums contributing to the \(b\) th output bit at level \(l\), and \(c_b^l\) representing carries from adding contributions to the \(b\) th output bit at level \(l\).

One circuit representation for the multiplication is formed from adding up the contributions to each output bit \(p_b\) as in Figure 43. As an example, the following QUBO objective realizes the multiplication of two 4-bit integers \(a\) and \(b\) into their product \(p\).

\[\begin{split}\text{bit }p_0\text{:} &\quad P_\wedge(a_0,b_0;p_0) \\ \text{bit $p_1$:} &\quad P_\wedge(a_1,b_0;t_{1,0}) + P_\wedge(a_0,b_1;t_{0,1}) + P_{2A}(t_{1,0},t_{0,1}; p_1, c^1_1) \\ \text{bit $p_2$:} &\quad P_\wedge(a_0,b_2;t_{0,2}) + P_\wedge(a_1,b_1;t_{1,1}) + P_\wedge(a_2,b_0;t_{2,0}) + P_{2A}(t_{2,0}, t_{1,1}; s^1_2, c^1_2) + P_{3A}(t_{0,2},s^1_2,c^1_1; p_2, c^2_2) \\ \text{bit $p_3$:} &\quad P_\wedge(a_0,b_3;t_{0,3}) + P_\wedge(a_1,b_2;t_{1,2}) + P_\wedge(a_2,b_1;t_{2,1}) + P_\wedge(a_3,b_0;t_{3,0}) + P_{2A}(t_{2,1},t_{3,0}; s^1_3,c_3^1) + \\ &\quad P_{3A}(t_{1,2}, s_3^1, c_2^1; s_3^2, c_3^2) + P_{3A}f(t_{0,3}, s_3^2, c_2^2; p_3, c_3^3) \\ \text{bit $p_4$:} &\quad P_\wedge(a_1,b_3;t_{1,3}) + P_\wedge(a_2,b_2;t_{2,2}) + P_\wedge(a_3,b_1;t_{3,1}) + P_{2A}(t_{2,2},t_{3,1}; s_4^1,c_4^1) + \\ &\quad P_{3A}(t_{1,3},s_4^1, c_3^1; s_4^2, c_4^2) + P_{3A}(s_4^2,c_3^2,c_3^3; p_4, c_4^3) \\ \text{bit $p_5$:} &\quad P_\wedge(a_2,b_3;t_{2,3}) + P_\wedge(a_3,b_2;t_{3,2}) + P_{3A}(t_{2,3},t_{3,2},c_4^1; s_5^2; c_5^2) + P_{3A}(s_5^2, c_4^2, c_4^3; p_5, c_5^3) \\ \text{bit $p_6$:} &\quad P_\wedge(a_3,b_3;t_{3,3}) + P_{3A}(t_{3,3}, c_5^2,c_5^3; p_6, p_7) \\ \text{bit $p_7$:} &\quad \text{the carry from the $p_6$ sum}\end{split}\]

This QUBO objective has energy 0 if and only if the binary encodings of \(a\) and \(b\) satisfy \(p=ab\).

The graphical representation of these QUBO contributions is perhaps simpler, and is shown in Figure 44.

image

Fig. 44 Graphical representation of the multiplication circuit for two 4-bit integers. The structure reflects Figure 43. See text for the explicit QUBO form of the circuit.

Yellow ellipses represent \(\wedge\) penalties, green rounded boxes represent half-adder penalties, and red boxes represent full-adder penalties. Variables are represented by edges and connect appropriate penalty terms. The contributions to each bit are separated by a blue dashed line. The thick dashed blue line separating output bits \(p_3\) and \(p_4\) separates parts of the circuit having different connectivity rules.

This circuit can be run in ``reverse” by fixing the output bits \((p_7,\cdots,p_0)\) to the values defined by the number to be factored, and then optimizing over the remaining \(\vc{a}\) and \(\vc{b}\) variables as well as the intermediate sum and carry variables. As is visible from Figure 44 the connectivity between variables is much sparser than the naive \((p-\ip{\vc{a}}{\vc{2}} \ip{\vc{2}}{\vc{b}})^2\) objective. Connectivity is defined by the sparse connections between small completely connected subgraphs of size 3, 4, and 5.

A Regularly Structured Factoring Lattice

To scale to large integers we need a regular circuit structure. One way to do this is to embed the ANDing of variables directly within the adder gates. Consequently, we define the new adder penalties \(\tilde{P}_{2A}(x_1^1,x_1^2,x_2; s,c)\) which realizes the constraint \(s+2c = x_1^1 x_1^2 + x_2\) and \(\tilde{P}_{3A}(x_1^1,x_1^2,x_2,x_3)\) which realizes \(s+2c = x_1^1 x_1^2 + x_2 + x_3\). By running the method described in CSP Reformulation with Penalty Functions, we rapidly find that the following penalties realize these constraints:

\[\begin{split}\tilde{P}_{2A}(x_1^1, x_1^2,x_2;s,c) = \begin{bmatrix} x_1^1 & x_1^2 & x_3 & s & c \end{bmatrix} \begin{bmatrix} 0 & 1 & 2 & -2 & -4 \\ 0 & 0 & 2 & -2 & -4 \\ 0 & 0 & 1 & -4 & -6 \\ 0 & 0 & 0 & 3 & 6 \\ 0 & 0 & 0 & 0 & 8 \end{bmatrix} \begin{bmatrix} x_1^1 \\ x_1^2 \\ x_2 \\ s \\ c \end{bmatrix} \\ \tilde{P}_{3A}(x_1^1, x_1^2,x_2,x_3;s,c) = \begin{bmatrix} x_1^1 & x_1^2 & x_2 & x_3 & s & c \end{bmatrix} \begin{bmatrix} 0 & 1 & 2 & 2 & -2 & -4 \\ 0 & 0 & 2 & 2 & -2 & -4 \\ 0 & 0 & 1 & 4 & -4 & -8 \\ 0 & 0 & 0 & 1 & -4 & -8 \\ 0 & 0 & 0 & 0 & 3 & 8 \\ 0 & 0 & 0 & 0 & 0 & 10 \end{bmatrix} \begin{bmatrix} x_1^1 \\ x_1^2 \\ x_2 \\ x_3 \\ s \\ c \end{bmatrix}.\end{split}\]

Note that no additional ancillary variables are needed to represent these non-linear constraints. Thus, we can eliminate all the \(t_{i,j}\) variables representing the \(\wedge\) s of \(a_i b_j\). The price paid for this variable reduction is additional connectivity. The \(\tilde{P}_{2A}\) and \(\tilde{P}_{3A}\) gates are now connected graphs of size 5 and 6.

A regularly structured constraint/optimization network representing the multiplication of two 8-bit numbers using the new gates is shown in Figure 45.

image

Fig. 45 The constraint network representing the multiplication of two 8-bit numbers.

The dark black lines represent the desired \(\vc{a}\) and \(\vc{b}\) variables which thread through the lattice. From the product of two \(\ell\) bit integers into an integer of at most \(2\ell\) bits, the circuit has \(\mathcal{O}(\ell^2)\) variables and the maximal connectivity of any variable is \(\mathcal{O}(\ell)\) (this maximal connectivity occurs for the \(\vc{a}\) and \(\vc{b}\) variables). Again the \(\vc{p}\) variables will be fixed to the bits of the number to be factored.

Further, circuit improvements are possible. The resulting QUBO can be a difficult optimization problem to solve, with a great many local minima.