using Yao, BitBasis, LinearAlgebra, SparseArrays
deutsch(Uf) = chain(2, put(2=>X), repeat(2, H), Uf, put(1=>H))
deutsch (generic function with 1 method)
Ufs = [
igate, # f(x) = 0 (constant)
put(2=>X), # f(x) = 1 (constant)
control(1, 2=>X), # f(x) = x (balanced)
chain( # f(x) = !x (balanced)
control(1, 2=>X),
put(2=>X))
]
[zero_state(2) |> deutsch(Uf) |> focus!(1) |> measure! |> bint for Uf in Ufs]
4-element Array{Int64,1}: 0 0 1 1
As we can see this is giving us 0 when the function is constant and 1 when it's balanced.
Define a circuit with $m$ bits and an ancillary bit.
deutsch_jozsa(m, Uf) = chain(m+1, put(m+1=>X), repeat(m+1, H), Uf, repeat(H, 1:m))
deutsch_jozsa (generic function with 1 method)
In this case the functions $U_f$ are a little more complicated to create. We'll do it by bit fiddling permutations rather than using a circuit. See here for alternatives.
function Uf(m::Int, f)
N = 2^(m+1)
perm = [(y ⊻ f(x))<<m + x for y in 0:1 for x in 0:2^m-1]
permute(sparse(I, N, N), perm.+1, collect(1:N)) |> Matrix{Complex{Float64}} |> matblock
end
Uf (generic function with 1 method)
$U_f$ is a reversible function from $\mathbb{Z}^{m+1} \rightarrow \mathbb{Z}^{m+1}$ which can be seen as a permutation. The final line converts the permutation to a matrix block used by Yao.jl.
Now we can evaluate it multiple times (using the nshots
parameter) to ensure that the result is always non-zero (balanced).
m=3
f(x) = x%2 # balanced (any function that returns 0 or 1 half the time)
zero_state(m+1) |> deutsch_jozsa(m, Uf(m, f)) |> focus!(1:m) |> r -> measure(r,nshots=10)
10-element Array{BitStr{3,Int64},1}: 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎ 001 ₍₂₎
We can do the same with a constant function and check that the result is always $0$.
f(x) = 1 # constant
zero_state(m+1) |> deutsch_jozsa(m, Uf(m, f)) |> focus!(1:m) |> r -> measure(r,nshots=10)
10-element Array{BitStr{3,Int64},1}: 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎ 000 ₍₂₎