@yuichirominato 2019.02.13更新 88views

[QUBO] Select K qubits from N qubits


Introduction

To understand basic method to solve ising model which is usually use when you use D-Wave or QAOA on universal model, we now check the cost function and constraint term on QUBO and solve basic example here.

Select K qubtis from N qubits

select K qubits from N qubits means that just two qubits from 5qubits take value “1” from the array of qubits. We can solve this problem by making QUBO matrix on the cost function.

Cost function

Cost function is an equation to solve the problem programmed the penalty on the problem.

$E = (\sum_{i=0}^{N}q_i – K)^2$

QUBOmatrix

By using QUBO matrix we can solve the problem. Let’s try an example to select 2 qubits from 5 qubits.

$
E = (\sum_{i=0}^4 q_i -2)^2 = (\sum_{i=0}^4 q_i)^2 -2*2*(\sum_{i=0}^4 q_i) + 2^2
\\ = (q_0+q_1+q_2+q_3+q_4)^2 -4*(q_0+q_1+q_2+q_3+q_4) + 4
\\ = -3q_0-3q_1-3q_2-3q_3-3q_4+2q_0q_1+2q_0q_2+ \cdots + 2q_3q_4 + 4
$

We expand it and using the binary rule.$q_i^2 = q_i$. Now we have QUBO matrix and ,

$
\begin{array}
-&q_0&q_1&q_2&q_3&q_4\\
q_0& -3&2&2&2&2\\
q_1& & -3&2&2&2\\
q_2& & & -3&2&2\\
q_3& & & &-3&2\\
q_4& &&& &-3
\end{array}
$

Now we use blueqat for this operation.

pip3 install blueqat
from blueqat import opt
a = opt.opt()
a.qubo = [[-3,2,2,2,2],[0,-3,2,2,2],[0,0,-3,2,2],[0,0,0,-3,2],[0,0,0,0,-3]]
a.sa()

Output is…

[0, 0, 1, 1, 0]

Just 2 qubtis are value 1 and rest are 0.

Generalize

Clealy there is a rule for the generalize this algorithm. To select 1 qubit from 3qubits are,

$
E = (\sum_{i=0}^2 q_i -1)^2 = (\sum_{i=0}^2 q_i)^2 -2*1*(\sum_{i=0}^2 q_i) + 1^2
\\ = (q_0+q_1+q_2)^2-2*(q_0+q_1+q_2)+1
\\ = -q_0-q_1-q_2+2q_0q_1+2q_0q_2+2q_1q_2+1
$

QUBOmatrix is

$
\begin{array}
-&q_0&q_1&q_2\\
q_0& -1&2&2\\
q_1& & -1&2\\
q_2& & & -1
\end{array}
$

Diagonal is 1-2K and off-diagonal is 2.

from blueqat import opt
a = opt.opt()
a.qubo = [[-1,2,2],[0,-1,2],[0,0,-1]]
a.sa()
[0, 1, 0]

and try

import numpy as np 

N = 5
K = 2
a.qubo = np.diag([1-2*K]*N)+np.triu([[2] * N for i in range(N)],k=1)
a.sa()
[1, 1, 0, 0, 0]

check the matrix…

print(a.qubo)

[[-3  2  2  2  2]
 [ 0 -3  2  2  2]
 [ 0  0 -3  2  2]
 [ 0  0  0 -3  2]
 [ 0  0  0  0 -3]]

Let’s try on bigger number.

N=100
K=5

略

[0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0]

As function

We usually use it, so prepare as a function.

from blueqat import opt
a = opt.opt()
a.qubo = opt.sel(20,10) #select 10 qubits from 20
a.sa()

[1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0]

It is ok.

This algorithm on universal gate model.

By using QAOA on gate model we can solve the same problem.

from blueqat import opt,vqe

qubo = opt.pauli(opt.sel(4,1)) 
step = 4 
result = vqe.Vqe(vqe.QaoaAnsatz(qubo,step)).run() 
print(result.most_common(5))                                                                                                                  

(((0, 1, 0, 0), 0.1895196081954192), ((1, 0, 0, 0), 0.18951960819541913), ((0, 0, 1, 0), 0.1895196081954191), ((0, 0, 0, 1), 0.1895196081954191), ((0, 0, 0, 0), 0.14702076574218317))

These are answer and probability. And it is solved.

Recommend


Back To Top