@yuichirominato 2019.02.13更新 227views

## [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.