@yuichirominato 2019.02.10更新 15views

Grover’s algorithm


Overview

Grover’s algorithm is a simple search algorithm to find the data from random data.

The step of the algorithm is

  1. Superposition
  2. Marking
  3. Amplitude amplification
-|Superposition|-|Marking|-|Amplitude amplification|-|Marking|-|Amplitude amplification|-

By iterating proper times you can get better answer.

About marking

Marking is simple. Just marking with -1 on the right state vector. If you want to find the first data you will make a matrix that the first diagonal as -1.

#00
[[-1  0  0  0]
 [ 0  1  0  0]
 [ 0  0  1  0]
 [ 0  0  0  1]]

#01
[[ 1  0  0  0]
 [ 0 -1  0  0]
 [ 0  0  1  0]
 [ 0  0  0  1]]

#10
[[ 1  0  0  0]
 [ 0  1  0  0]
 [ 0  0 -1  0]
 [ 0  0  0  1]]

#11
[[ 1  0  0  0]
 [ 0  1  0  0]
 [ 0  0  1  0]
 [ 0  0  0 -1]]

Marking as gate set

The making matrix is made from combination of gate set. * is controlled gate and Z is target gate.

#00
--H--S--*--S--
--H--S--Z--S--

Circuit(2).h[:].s[:].cz[0,1].s[:]

#01
--H-----*-----
--H--S--Z--S--

Circuit(2).h[:].s[1].cz[0,1].s[1]

#10
--H--S--*--S--
--H-----Z-----

Circuit(2).h[:].s[0].cz[0,1].s[0]

#11
--H-----*-----
--H-----Z-----

Circuit(2).h[:].cz[0,1]

About amplitude amplification

It is also simple just prepare minus diagonal and plus off-diagonal matrix.

[[ -1   1   1   1]
 [  1  -1   1   1]
 [  1   1  -1   1]
 [  1   1   1  -1]]
Circuit(2).h[:].x[:].cz[0,1].x[:].h[:].m[:]

--H-X-*-X-H--
--H-X-Z-X-H--

Grover’s algorithm

Combining these gate set we can easily use grover’s algorithm

#Amplitude amplification
a = Circuit(2).h[:].x[:].cz[0,1].x[:].h[:].m[:]

#00
--H--S--*--S----H-X-*-X-H--
--H--S--Z--S----H-X-Z-X-H--

(Circuit(2).h[:].s[:].cz[0,1].s[:] + a).run(shots=100)
Counter({'00': 100})

#01
--H-----*-------H-X-*-X-H--
--H--S--Z--S----H-X-Z-X-H--

(Circuit(2).h[:].s[1].cz[0,1].s[1] + a).run(shots=100)
Counter({'01': 100})

#10
(Circuit(2).h[:].s[0].cz[0,1].s[0] + a).run(shots=100)
Counter({'10': 100})
--H--S--*--S----H-X-*-X-H--
--H-----Z-------H-X-Z-X-H--

#11
(Circuit(2).h[:].cz[0,1] + a).run(shots=100)
Counter({'11': 100})
--H-----*-------H-X-*-X-H--
--H-----Z-------H-X-Z-X-H--

For 3 qubits

Fro 3qubits of grover’s algorithm we use toffoli or ccx gate

#Amplitude amplification
b = Circuit(3).h[:].x[:].h[2].ccx[0,1,2].h[2].x[:].h[:].m[:]

#with marking of 111
(Circuit(3).h[:].h[2].ccx[0,1,2].h[2] + b).run(shots=100)

Counter({'111': 76,
         '010': 3,
         '001': 4,
         '101': 8,
         '100': 4,
         '110': 1,
         '011': 2,
         '000': 2})

You need iteration for correct answer.

#marking of 111
b = Circuit(3).h[2].ccx[0,1,2].h[2]
#amplitude amplification
c = Circuit(3).h[:].x[:].h[2].ccx[0,1,2].h[2].x[:].h[:]

d = b+c

#iterating twice
(Circuit(3).h[:] +d+d).m[:].run(shots=100)

Counter({'111': 91,
         '000': 2,
         '101': 1,
         '110': 2,
         '011': 2,
         '100': 1,
         '010': 1})

If you have N qubits you have to iterate √Ntimes.

This time we looked at very basic grover’s algorithm.

Recommend


CONTACT

info@mdrft.com

Back To Top

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方