@yuichirominato 2019.02.09更新 109views

Tweet

It’s quite difficult to implement shor’s algorithm on NISQ machine which is available at the moment. So let’s try another way to solve factoring.

By using universal gate model quantum computer to simulate quantum adiabatic calculation we can solve simple factoring using optimization problem.

Nikesh S. Dattani,1,2,∗ Nathaniel Bryans3,†

1Quantum Chemistry Laboratory, Kyoto University, 606-8502, Kyoto, Japan, 2Physical & Theoretical Chemistry Laboratory,

Oxford University, OX1 3QZ, Oxford, UK, 3University of Calgary, T2N 4N1, Calgary, Canada. ∗

dattani.nike@gmail.com,

†

nbryans1@gmail.com

https://arxiv.org/pdf/1411.6758.pdf

Eric R. Anschuetz, Jonathan P. Olson, Alán Aspuru-Guzik, Yudong Cao

(Submitted on 27 Aug 2018)

https://arxiv.org/abs/1808.08927

It’s simple, let’s check.

- Thinking factorization on binary number.
- Using some mathematical technique simplify the ising problem.
- Use QAOA to solve the ising model without decomposing to 2-body interaction (directly simulating over 3-body interactions)

QAOA is an algorithm on quantum computer to solve optimization problem.

Let’s see factoring of 143. The multiply of binary number is like below.

We simply think m=p*q. It’s clear that p&q has 1 on the first and last bit.

Just multiply these binary number using the simple rule of multiplication of 2 binary numbers.

After adding each place we have some equations.

$$\begin{eqnarray}p_1+q_1 &=& 1+2z_{12}\\

p_2+p_1q_1+q_2+z_{12} &=& 1+2z_{23}+4z_{24}\\

1+p_2q_1+p_1q_2+1+z_{23} &=& 1+2z_{34}+4z_{35}\\

…

q_2+p_2+z_{45}+z_{35} &=& 0+2z_{56}+4z_{57}\\

1+z_{56}+z_{46} &=& 0+2z_{67}\\

z_{67}+z_{57} &=& 1\end{eqnarray}$$

We can simplify the equations by checking each number on detail.

on $p_1+q_1=1+2z_{12}$ we already have 1, so $p_1$ or $q_1$ is 1. So 2 never appear and $z_{12}=0$

…

By applying these techniques to all equations we have,

$$\begin{eqnarray}p_1+q_1-1 &=&0\\

p_2+q_2-1 &=& 0\\

p_2q_1+p_1q_2-1 &=&0

\end{eqnarray}$$

From these equations we have final hamiltonian just by squaring these equations and get the sum of these.

$$H=(p_1+q_1-1)^2 + (p_2+q_2-1)^2+(p_2q_1+p_1q_2-1)^2\\=5-3p_1-p_2-q_1+2p_1q_1-3p_2q_1+2p_1p_2q_1-3q_2+p_1q_2+2p_2q_2+2p_2q_1q_2$$

When we check the energy value one by one, we get

$5,2,4,1,4,3,0,1,2,0,3,1,1,1,1,3$

$\mid 6 \rangle$ and $\mid 9 \rangle$ has $H=0$

So, $\mid 0110 \rangle$ and $\mid 1001 \rangle$ are the answer.

$p=13,q=11$ and $p=11,q=13$ are the answer.

We have function to convert 01 binary QUBO to Ising model value +1 and -1. and then have QAOA with powell’s algorithm for optimization of parameters.

https://github.com/mdrft/Blueqat

```
from blueqat import vqe
from blueqat.pauli import qubo_bit as q
hamiltonian = -3*q(0)-q(1)-q(2)+2*q(0)*q(2)-3*q(1)*q(2)+2*q(0)*q(1)*q(2)-3*q(3)+q(0)*q(3)+2*q(1)*q(3)+2*q(1)*q(2)*q(3)
step = 4
result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run()
print(result.most_common(5))
#=> (((0, 1, 1, 0), 0.38282701807018904), ((1, 0, 0, 1), 0.17092057836615537), ((1, 1, 1, 0), 0.08073422675654193), ((0, 1, 1, 1), 0.08073422675654193), ((1, 0, 1, 1), 0.045786141364148956))
```

Now we have 0110 and 1001 with enough big probability amplitude. And this is the global minimum finally.

56153 can be solve with 4 qubits. 291311 can be solve with 6 qubits.

By using universal quantum machine, we can easily solve many body interaction. If we want to solve this problem on quantum annealing, we need boolean reduction with a lot of step of tuning of parameters.

TweetBack To Top