# Grover Search

```
using Yao
using Yao.EasyBuild: variational_circuit
using LinearAlgebra
```

## Grover Step

A single grover step is consist of applying oracle circuit and reflection circuit. The `reflection_circuit`

function takes the wave function generator `U`

as the input and returns `U|0><0|U'`

.

```
function grover_step!(reg::AbstractRegister, oracle, U::AbstractBlock)
apply!(reg |> oracle, reflect_circuit(U))
end
function reflect_circuit(gen::AbstractBlock)
N = nqubits(gen)
reflect0 = control(N, -collect(1:N-1), N=>-Z)
chain(gen', reflect0, gen)
end
```

`reflect_circuit (generic function with 1 method)`

Compute the propotion of target states to estimate the number of iterations, which requires computing the output state.

```
function solution_state(oracle, gen::AbstractBlock)
N = nqubits(gen)
reg= zero_state(N) |> gen
reg.state[real.(statevec(ArrayReg(ones(ComplexF64, 1<<N)) |> oracle)) .> 0] .= 0
normalize!(reg)
end
function num_grover_step(oracle, gen::AbstractBlock)
N = nqubits(gen)
reg = zero_state(N) |> gen
ratio = abs2(solution_state(oracle, gen)'*reg)
Int(round(pi/4/sqrt(ratio)))-1
end
```

`num_grover_step (generic function with 1 method)`

#### Run

First, we define the problem by an oracle, it finds bit string `bit"000001100100"`

.

```
num_bit = 12
oracle = matblock(Diagonal((v = ones(ComplexF64, 1<<num_bit); v[Int(bit"000001100100")+1]*=-1; v)))
```

`matblock(...)`

then solve the above problem

```
gen = repeat(num_bit, H, 1:num_bit)
reg = zero_state(num_bit) |> gen
target_state = solution_state(oracle, gen)
for i = 1:num_grover_step(oracle, gen)
grover_step!(reg, oracle, gen)
overlap = abs(reg'*target_state)
println("step $(i-1), overlap = $overlap")
end
```

```
step 0, overlap = 0.04685974121093736
step 1, overlap = 0.0780487209558483
step 2, overlap = 0.10916148124670066
step 3, overlap = 0.14016763852852288
step 4, overlap = 0.17103691335084453
step 5, overlap = 0.20173915993747182
step 6, overlap = 0.23224439562572258
step 7, overlap = 0.26252283014636996
step 8, overlap = 0.29254489471570244
step 9, overlap = 0.322281270911289
step 10, overlap = 0.35170291930325104
step 11, overlap = 0.3807811078130809
step 12, overlap = 0.40948743977231195
step 13, overlap = 0.4377938816536402
step 14, overlap = 0.46567279044741594
step 15, overlap = 0.49309694065677034
step 16, overlap = 0.5200395508850146
step 17, overlap = 0.5464743099893477
step 18, overlap = 0.5723754027753314
step 19, overlap = 0.5977175352070423
step 20, overlap = 0.6224759591082774
step 21, overlap = 0.6466264963306958
step 22, overlap = 0.6701455623652912
step 23, overlap = 0.6930101893741392
step 24, overlap = 0.7151980486199263
step 25, overlap = 0.7366874722713579
step 26, overlap = 0.7574574745631494
step 27, overlap = 0.7774877722899375
step 28, overlap = 0.7967588046140988
step 29, overlap = 0.8152517521681291
step 30, overlap = 0.8329485554329328
step 31, overlap = 0.8498319323740713
step 32, overlap = 0.8658853953187506
step 33, overlap = 0.8810932670570639
step 34, overlap = 0.8954406961517668
step 35, overlap = 0.9089136714416339
step 36, overlap = 0.9214990357242339
step 37, overlap = 0.9331844986047592
step 38, overlap = 0.9439586484983656
step 39, overlap = 0.953810963774298
step 40, overlap = 0.9627318230309194
step 41, overlap = 0.9707125144916121
step 42, overlap = 0.9777452445123718
step 43, overlap = 0.983823145192787
step 44, overlap = 0.9889402810829753
step 45, overlap = 0.9930916549799182
step 46, overlap = 0.9962732128075449
step 47, overlap = 0.9984818475757891
step 48, overlap = 0.9997154024147601
```

## Rejection Sampling

In practise, it is often not possible to determine the number of iterations before actual running. we can use rejection sampling technique to avoid estimating the number of grover steps.

In a single try, we `apply`

the grover algorithm for `nstep`

times.

```
function single_try(oracle, gen::AbstractBlock, nstep::Int; nbatch::Int)
N = nqubits(gen)
reg = zero_state(N+1; nbatch)
focus(reg, (1:N...,)) do r
r |> gen
for i = 1:nstep
grover_step!(r, oracle, gen)
end
return r
end
reg |> checker
res = measure!(RemoveMeasured(), reg, (N+1))
return res, reg
end
```

`single_try (generic function with 1 method)`

After running the grover search, we have a checker program that flips the ancilla qubit if the output is the desired value, we assume the checker program can be implemented in polynomial time. to gaurante the output is correct. We contruct a checker "program", if the result is correct, flip the ancilla qubit

```
ctrl = -collect(1:num_bit); ctrl[[3,6,7]] *= -1
checker = control(num_bit+1,ctrl, num_bit+1=>X)
```

```
nqubits: 13
control(¬1, ¬2, 3, ¬4, ¬5, 6, 7, ¬8, ¬9, ¬10, ¬11, ¬12)
└─ (13,) X
```

The register is batched, with batch dimension `nshot`

. `focus!`

views the first 1-N qubts as system. For a batched register, `measure!`

returns a vector of bitstring as output.

#### Run

```
maxtry = 100
nshot = 3
for nstep = 0:maxtry
println("number of iter = $nstep")
res, regi = single_try(oracle, gen, nstep; nbatch=3)
# success!
if any(==(1), res)
overlap_final = viewbatch(regi, findfirst(==(1), res))'*target_state
println("success, overlap = $(overlap_final)")
break
end
end
```

```
number of iter = 0
number of iter = 1
number of iter = 2
number of iter = 3
number of iter = 4
number of iter = 5
number of iter = 6
number of iter = 7
success, overlap = -1.0 + 0.0im
```

The final state has an overlap of `1`

with the target state.

## Amplitude Amplification

Given a circuit to generate a state, now we want to project out the subspace with [1,3,5,8,9,11,12] fixed to 1 and [4,6] fixed to 0. We can construct an oracle

```
evidense = [1, 3, -4, 5, -6, 8, 9, 11, 12]
function inference_oracle(nbit::Int, locs::Vector{Int})
control(nbit, locs[1:end-1], abs(locs[end]) => (locs[end]>0 ? Z : -Z))
end
oracle = inference_oracle(nqubits(reg), evidense)
```

```
nqubits: 12
control(1, 3, ¬4, 5, ¬6, 8, 9, 11)
└─ (12,) Z
```

We use a variational circuit generator defined in `Yao.EasyBuild`

```
gen = dispatch!(variational_circuit(num_bit), :random)
reg = zero_state(num_bit) |> gen
```

```
ArrayReg{2, ComplexF64, Array...}
active qubits: 12/12
nlevel: 2
```

#### Run

```
solution = solution_state(oracle, gen)
for i = 1:num_grover_step(oracle, gen)
grover_step!(reg, oracle, gen)
println("step $(i-1), overlap = $(abs(reg'*solution))")
end
```

```
step 0, overlap = 0.07332145670592895
step 1, overlap = 0.1220074451492908
step 2, overlap = 0.1704014495257762
step 3, overlap = 0.21838765495053947
step 4, overlap = 0.26585122246931236
step 5, overlap = 0.31267856388708226
step 6, overlap = 0.3587576136034965
step 7, overlap = 0.40397809680444396
step 8, overlap = 0.4482317933679888
step 9, overlap = 0.49141279685308464
step 10, overlap = 0.5334177679512655
step 11, overlap = 0.5741461817947644
step 12, overlap = 0.6135005685292055
step 13, overlap = 0.651386746575144
step 14, overlap = 0.6877140480202186
step 15, overlap = 0.722395535602514
step 16, overlap = 0.755348210765858
step 17, overlap = 0.7864932122891436
step 18, overlap = 0.8157560050143191
step 19, overlap = 0.8430665582213942
step 20, overlap = 0.8683595132235745
step 21, overlap = 0.8915743397814486
step 22, overlap = 0.9126554809618972
step 23, overlap = 0.9315524860950557
step 24, overlap = 0.9482201315111407
step 25, overlap = 0.9626185287681979
step 26, overlap = 0.9747132201117643
step 27, overlap = 0.9844752609379932
step 28, overlap = 0.9918812890628973
step 29, overlap = 0.9969135806319311
step 30, overlap = 0.999560092536117
```

*This page was generated using Literate.jl.*