@yuichirominato 2019.02.09更新 271views

[factoring] Variational Quantum Factoring using QAOA and VQE on blueqat


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.

Ising hamiltonian

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


Quantum factorization of 56153 with only 4 qubits

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. ∗



Variational Quantum Factoring

Eric R. Anschuetz, Jonathan P. Olson, Alán Aspuru-Guzik, Yudong Cao
(Submitted on 27 Aug 2018)

Prime Factorization Using Quantum Annealing and Algebraic Geometry



It’s simple, let’s check.

  1. Thinking factorization on binary number.
  2. Using some mathematical technique simplify the ising problem.
  3. 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.

1. Example. Factoring of 143

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.

2.Simplify the equations

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

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


$\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.

3. Solve the hamiltonian using QAOA algorithm.

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.


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() 
#=> (((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.

Bigger number

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.

Back To Top