Grover Search¶

In [ ]:
using Yao
using YaoExtensions: 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'.

In [ ]:
function grover_step!(reg::AbstractRegister, oracle, U::AbstractBlock)
apply!(reg |> oracle, reflect_circuit(U))
end

function reflect_circuit(gen::AbstractBlock{N}) where N
reflect0 = control(N, -collect(1:N-1), N=>-Z)
chain(gen', reflect0, gen)
end


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

In [ ]:
function solution_state(oracle, gen::AbstractBlock{N}) where N
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}) where N
reg = zero_state(N) |> gen
ratio = abs2(solution_state(oracle, gen)'*reg)
Int(round(pi/4/sqrt(ratio)))-1
end


Run¶

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

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


then solve the above problem

In [ ]:
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


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.

In [ ]:
function single_try(oracle, gen::AbstractBlock{N}, nstep::Int; nbatch::Int) where N
reg = zero_state(N+1; nbatch=nshot)
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_remove!(reg, (N+1))
return res, reg
end


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

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


The register is batched, with batch dimension nshot. focus! views the first 1-N qubts as system. For a batched register, measure_remove! returns a vector of bitstring as output.

Run¶

In [ ]:
maxtry = 100
nshot = 3

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


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

In [ ]:
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)


We use a variational circuit generator defined in YaoExtensions

In [ ]:
gen = dispatch!(variational_circuit(num_bit), :random)
reg = zero_state(num_bit) |> gen


Run¶

In [ ]:
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


This notebook was generated using Literate.jl.