@yuichirominato 2019.02.18更新 82views

[Factoring] Factoring on D-Wave using optimization


Introduction

This time we try implement the factoring algorithm on D-wave machine.

引用元:https://www.dwavesys.com/resources/media-resources

引用元:https://www.dwavesys.com/resources/media-resources

This is the D-Wave’s website

https://www.dwavesys.com/

An example

Let’s solve this simple problem.

$15 = 5*3$

Prepare the qubits

Now we have $p$ and $q$ for multiply.

$15 = p*q$

We prepare p using 2qubits and q using 1qubit

$p = 1+2q_0+4q_1\\
q = 1+2q_2$

Optimization problem

By subtracting p*q from 15 and have the square of it.

$
H = (15-p*q)^2
$

If we have H=0 this is the optimization problem to solve.

Expanding

Just try to expand the equation.

$
H = \{15-(1+2q_0+4q_1)(1+2q_2)\}^2
$

Finally we have,

$
H = 16q_0^2q_2^2 + 16q_0^2q_2 + 4q_0^2 + 64q_0q_1q_2^2 + 64q_0q_1q_2 + 16q_0q_1 + 16q_0q_2^2 – 104q_0q_2 – 56q_0 + 64q_1^2q_2^2 + 64q_1^2q_2 + 16q_1^2 + 32q_1q_2^2 – 208q_1q_2 – 112q_1 + 4q_2^2 – 56q_2 + 196
$

And we have binary number as $q_i^2=q_i$

$
16q_0q_2 + 16q_0q_2 + 4q_0 + 64q_0q_1q_2 + 64q_0q_1q_2 + 16q_0q_1 + 16q_0q_2 – 104q_0q_2 – 56q_0 + 64q_1q_2 + 64q_1q_2 + 16q_1 + 32q_1q_2 – 208q_1q_2 – 112q_1 + 4q_2 – 56q_2 + 196
$

Finally we have simple equation as

$
H = 128q_0q_1q_2 + 16q_0q_1 – 56q_0q_2 – 52q_0 – 48q_1q_2 – 96q_1 – 52q_2 + 196
$

Boolean reduction on 3-body interaction

Now we have $q_0q_1q_2$ that cannot solve diretly on D-Wave machine. By using $q_3$ we have new equation.

$
q_1q_2 = q_3
$

$q_1,q_2,q_3$ and using the new penalty rules we have new equation only written in 2-body interaction using boolean reduction.

$
H = 128q_0q_3 + 16q_0q_1 – 56q_0q_2 – 52q_0 – 48q_1q_2 – 96q_1 – 52q_2 + 196 + \delta(3q_3+q_1q_2-2q_1q_3-2q_2q_3)
$

To QUBO matrix

We have coefficient and make the QUBO matrix.

$
\begin{array}
-&q_0&q_1&q_2&q_3\\
q_0 & -52 & 16 & -56 & 128\\
q_1 & & -96 & \delta-48 & -2\delta \\
q_2 & & & -52 & -2\delta\\
q_3 & & & & 3\delta
\end{array}
$

Let’s convert it to ising model

The software usually convert automatically.

$
\begin{array}
-&q_0&q_1&q_2&q_3\\
q_0 & -4 & 4 & -14 & 32\\
q_1 & & -0.25\delta-56 & 0.25\delta-12 & -0.5\delta \\
q_2 & & & -0.25\delta-52 & -0.5\delta\\
q_3 & & & & 0.5\delta+32
\end{array}
$

On D-Wave

Just input to D-Wave. But now we are using full connect of 6qubits and have to convert the connection to chimera graph.

Thinking about delta value in the equation we have matrix, and just input to D-Wave machine.

Now we have the answer,

$q_0=-1,q_1=1,q_2=1$ and $q_3=1$. Boolean reduction successfully done.

Recommend


Back To Top