Quantum Fourier Transformation and Phase Estimation

Quantum Fourier Transformation and Phase Estimation

Let's use Yao first

using Yao

Quantum Fourier Transformation

The Quantum Fourier Transformation (QFT) circuit is to repeat two kinds of blocks repeatly:

ghz

The basic building block control phase shift gate is defined as

\[R(k)=\begin{bmatrix} 1 & 0\\ 0 & \exp\left(\frac{2\pi i}{2^k}\right) \end{bmatrix}\]

Let's define block A and block B, block A is actually a control block.

A(i, j) = control(i, j=>shift(2π/(1<<(i-j+1))))
A (generic function with 1 method)

Once you construct the blockl you can inspect its matrix using mat function. Let's construct the circuit in dash box A, and see the matrix of $R_4$ gate.

R4 = A(1, 4)
(n -> control(n, 1, 4 => shift(Inf)))

If you have read about preparing GHZ state, you probably know that in Yao, we could just leave the number of qubits, and it will be evaluated when possible.

R4(5)
nqubits: 5, datatype: Complex{Float64}
control(1)
└─ (4,) shift(Inf)

its matrix will be

mat(R4(5))
32×32 LinearAlgebra.Diagonal{Complex{Float64},Array{Complex{Float64},1}}:
 1.0+0.0im      ⋅          ⋅      …      ⋅           ⋅          ⋅     
     ⋅      1.0+0.0im      ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅      1.0+0.0im         ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅      …      ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
    ⋮                             ⋱                 ⋮                 
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅      …      ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅          ⋅     
     ⋅          ⋅          ⋅         NaN+NaN*im      ⋅          ⋅     
     ⋅          ⋅          ⋅      …      ⋅       1.0+0.0im      ⋅     
     ⋅          ⋅          ⋅             ⋅           ⋅      NaN+NaN*im

Then we repeat this control block over and over on different qubits, and put a Hadamard gate to ith qubit to construct i-th B block.

B(n, i) = chain(n, i==j ? put(i=>H) : A(j, i) for j in i:n)
B (generic function with 1 method)

We need to input the total number of qubits n here because we have to iterate through from i-th location to the last.

Now, let's construct the circuit by chaining all the B blocks together

qft(n) = chain(B(n, i) for i in 1:n)

qft(4)
nqubits: 4, datatype: Complex{Float64}
chain
├─ chain
│  ├─ put on (1)
│  │  └─ H gate
│  ├─ control(2)
│  │  └─ (1,) shift(1.5707963267948966)
│  ├─ control(3)
│  │  └─ (1,) shift(0.7853981633974483)
│  └─ control(4)
│     └─ (1,) shift(0.39269908169872414)
├─ chain
│  ├─ put on (2)
│  │  └─ H gate
│  ├─ control(3)
│  │  └─ (2,) shift(1.5707963267948966)
│  └─ control(4)
│     └─ (2,) shift(0.7853981633974483)
├─ chain
│  ├─ put on (3)
│  │  └─ H gate
│  └─ control(4)
│     └─ (3,) shift(1.5707963267948966)
└─ chain
   └─ put on (4)
      └─ H gate

Wrap QFT to an external block

In most cases, functions are enough to wrap quantum circuits, like A and B we defined above, but sometimes, we need to dispatch specialized methods on certain kinds of quantum circuit, or we want to define an external block to export, thus, it's useful to be able to wrap circuit to custom blocks.

First, we define a new type as subtype of PrimitiveBlock since we are not going to use the subblocks of QFT, if you need to use its subblocks, it'd be better to define it under CompositeBlock.

struct QFT{N} <: PrimitiveBlock{N} end
Error: invalid subtyping in definition of QFT
QFT(n::Int) = QFT{n}()
QFT (generic function with 1 method)

Now, let's define its circuit

circuit(::QFT{N}) where N = qft(N)
Error: TypeError: in Type{...} expression, expected UnionAll, got typeof(Ma
in.WeaveSandBox1.QFT)

And forward mat to its circuit's matrix

YaoBlocks.mat(::Type{T}, x::QFT) where T = mat(T, circuit(x))
Error: ArgumentError: invalid type for argument x in method definition for 
mat at none:1

You may notice, it is a little ugly to print QFT at the moment, this is because we print the type summary by default, you can define your own printing by overloading print_block

YaoBlocks.print_block(io::IO, x::QFT{N}) where N = print(io, "QFT($N)")
Error: TypeError: in Type{...} expression, expected UnionAll, got typeof(Ma
in.WeaveSandBox1.QFT)

Since it is possible to use FFT to simulate the results of QFT (like cheating), we could define our custom apply! method:

using FFTW, LinearAlgebra

function YaoBlocks.apply!(r::ArrayReg, x::QFT)
    α = sqrt(length(statevec(r)))
    invorder!(r)
    lmul!(α, ifft!(statevec(r)))
    return r
end
Error: ArgumentError: invalid type for argument x in method definition for 
apply! at none:3

Now let's check if our apply! method is correct:

r = rand_state(5)
r1 = r |> copy |> QFT(5)
Error: TypeError: in Type{...} expression, expected UnionAll, got typeof(Ma
in.WeaveSandBox1.QFT)
r2 = r |> copy |> circuit(QFT(5))
Error: TypeError: in Type{...} expression, expected UnionAll, got typeof(Ma
in.WeaveSandBox1.QFT)
r1 ≈ r2
Error: UndefVarError: r1 not defined

We can get iQFT (inverse QFT) directly by calling adjoint

QFT(5)'
Error: TypeError: in Type{...} expression, expected UnionAll, got typeof(Ma
in.WeaveSandBox1.QFT)

QFT and iQFT are different from FFT and IFFT in three ways,

  1. they are different by a factor of $\sqrt{2^n}$ with $n$ the number of qubits.
  2. the bit numbering will exchange after applying QFT or iQFT.
  3. due to the convention, QFT is more related to IFFT rather than FFT.

Phase Estimation

Since we have QFT and iQFT blocks we can then use them to realize phase estimation circuit, what we want to realize is the following circuit:

phase estimation

using Yao

First we call Hadamard gates repeatly on first n qubits.

Hadamards(n) = repeat(H, 1:n)
Hadamards (generic function with 1 method)

Then in dashed box B, we have controlled unitaries:

ControlU(n, m, U) = chain(n+m, control(k, n+1:n+m=>matblock(U^(2^(k-1)))) for k in 1:n)
ControlU (generic function with 1 method)

each of them is a U of power $2^(k-1)$.

Since we will only apply the qft and Hadamard on first n qubits, we could use Concentrator, which creates a context of a sub-scope of the qubits.

PE(n, m, U) =
    chain(n+m, # total number of the qubits
        concentrate(Hadamards(n), 1:n), # apply H in local scope
        ControlU(n, m, U),
        concentrate(QFT(n)', 1:n))
PE (generic function with 1 method)

we use the first n qubits as the output space to store phase $ϕ$, and the other m qubits as the input state which corresponds to an eigenvector of oracle matrix U.

The concentrator here uses focus! and relax! to manage a local scope of quantum circuit, and only active the first n qubits while applying the block inside the concentrator context, and the scope will be relax!ed back, after the context. This is equivalent to manually focus! then relax!

fullly activated

r = rand_state(5)
ArrayReg{1, Complex{Float64}, Array...}
    active qubits: 5/5

first 3 qubits activated

focus!(r, 1:3)
ArrayReg{1, Complex{Float64}, Array...}
    active qubits: 3/5

relax back to the original

relax!(r, 1:3)
ArrayReg{1, Complex{Float64}, Array...}
    active qubits: 5/5

In this way, we will be able to apply small operator directly on the subset of the qubits.

Details about the algorithm can be found here: Quantum Phase Estimation Algorithm

Now let's check the results of our phase estimation.

First we need to set up a unitary with known phase, we set the phase to be 0.75, which is 0.75 * 2^3 == 6 == 0b110 .

using LinearAlgebra

N, M = 3, 5
P = eigen(rand_unitary(1<<M)).vectors
θ = Int(0b110) / 1<<N
phases = rand(1<<M)
phases[bit"010"] = θ
U = P * Diagonal(exp.(2π * im * phases)) * P'
32×32 Array{Complex{Float64},2}:
  -0.246555-0.0697194im  …    0.0164516+0.20199im    
   0.140836-0.184911im         0.117138-0.186668im   
  -0.033541-0.188321im       0.00708774+0.0561032im  
   0.158775-0.02915im         -0.049991-0.0830655im  
 -0.0912761-0.101848im        0.0417233-0.0936014im  
 -0.0218269-0.0323136im  …     0.164063-0.0473988im  
   0.139351-0.115742im        -0.247879+0.198315im   
  0.0294649-0.122678im         0.113348-0.0185818im  
  0.0192854+0.138258im        0.0829611-0.120783im   
 -0.0120772-0.104449im       -0.0438298-0.256125im   
           ⋮             ⋱                           
   0.108772-0.246992im         0.154458-0.0636287im  
  0.0174485+0.0986131im        0.184565-0.101437im   
   0.160682+0.0855615im  …  -0.00943402+0.0514696im  
  0.0835713+0.305537im       0.00759161+0.000830744im
  0.0230268-0.0625085im      -0.0820562+0.116394im   
  -0.124717-0.0261351im        0.098833-0.097164im   
  0.0649558-0.0483459im       0.0652906+0.0379194im  
   0.213449-0.027227im   …    0.0412434+0.0499675im  
  -0.157055+0.085528im        -0.149556-0.0410193im

and then generate the state $ψ$

psi = P[:, 3]
32-element Array{Complex{Float64},1}:
  0.016093383840594763 + 0.051791561491353375im 
   -0.1589443681268857 - 0.0004645460909437904im
  -0.10455679818692931 - 0.20255470666605485im  
  -0.25316252176706094 + 0.039471131427543785im 
   0.05757137410012075 + 0.021389457770649066im 
 -0.046184024602617016 - 0.03939070535948873im  
   0.14412021325025468 + 0.026689035869855916im 
  -0.09363913820310225 - 0.1959912171101399im   
    0.3547069407124919 + 0.0im                  
 0.0018901480514435989 - 0.025711415733685718im 
                       ⋮                        
  -0.06237447807050837 + 0.09859039484225503im  
   0.06703422499543366 - 0.05514305049177408im  
  -0.09242192711213695 + 0.06183844372965327im  
    -0.160886067591948 - 0.006706060320658305im 
  0.026171000101573496 - 0.13420741892335278im  
   0.01482742948147029 - 0.11661138122933573im  
  0.028687047293363924 + 0.05479855429165585im  
  -0.10483209279960026 + 0.2646687182520858im   
 -0.028905399900154297 + 0.015875621380681815im

In the phase estimation process, we will feed the state to circuit and measure the first n qubits processed by iQFT.

r = join(ArrayReg(psi), zero_state(N))
r |> PE(N, M, U)
Error: TypeError: in Type{...} expression, expected UnionAll, got typeof(Ma
in.WeaveSandBox1.QFT)

Since our phase can be represented by 3 qubits precisely, we only need to measure once

results = measure(r, 1:N; nshots=1)
1-element Array{Int64,1}:
 0

Recall that our QFT's bit numbering is reversed, let's reverse it back

using BitBasis
estimated_phase = bfloat(results[]; nbits=N)
0.0

the phase is exactly 0.75!