Quantum Architecture and Programming

Prof. Kunal Korgaonkar

BITS-Pilani, K K Birla, Goa Campus

September 13, 2024

1/21
Search Algorithms

⇒ Search problem we’ll pick a random number between 1 - 100

⇒ One Correct answer
⇒ Worst case we have 99 wrong guesses to classical Oracle.
⇒ Classical Oracle: theoretical computational device used in
classical computer science and complexity theory. It serves as
black box that can answer specific questions about functions.
⇒ This is example of unstructured search
⇒ In unstructured search wrong guess provides no information
about how to get closer to correct guess
⇒ If sorted list were added to implement binary search our
search time would reduce to O(log2 N) but sorting procedures
don’t come for free.

2/21
Grover’s Search Algorithm

⇒ Grover’s algorithm was developed in 1996

⇒ Applicable to any problem that can be solved classically by
random brute force search
⇒ Major algorithm for quantum computing, one of the most
popular
⇒ Grover’s algorithm takes advantage of qubit superposition and
phase interference√to improve unstructured database search
from O(N) to O( N)
⇒ In previous example worst case becomes square root of 100 or
10 circuit runs in quantum case.
⇒ We require 2N classical bits to represent N qubits.
⇒ Quadratic Speedup

3/21
Amplitude Amplification
⇒ Increase probability of observing correct answer by increasing
probability amplitude associated with answer ket → |answer ⟩
⇒ Decrease all other probabilities.
⇒ Example: Lets say we need to search |11⟩

1 1 1 1
|ψ⟩ = |00⟩ + |01⟩ + |10⟩ + |11⟩
2 2 2 2
Amplify |11⟩
√
1 1 1 3
|ψ⟩ = √ |00⟩ + √ |01⟩ + √ |10⟩ + |11⟩
12 12 12 2
⇒ Amplitude Amplification consists of two parts:
⇒ Oracle/Inversion : Assign −ve phase to chosen state
⇒ Diffuser/Reflection Operator : Amplify Amplitude of
selected(−ve) state and decrease amplitude of other
states.
4/21
Oracle/Inversion Operator
⇒ Initial State: |00⟩
⇒ Start with balanced superposition (using Hadamard Gate):
     
1 1 1 1 1 1 1 1
H|00⟩ = H|0⟩ ⊗ H|0⟩ = √ ⊗√
2 1 −1 0 2 1 −1 0
         
1 1 0 0 0
1 1  = 1 0 + 1 + 0 + 0
       
= 
2 1 2 0 0 1 0
1 0 0 0 1

1 1 1 1
|ψ⟩ = |00⟩ + |01⟩ + |10⟩ + |11⟩
2 2 2 2
⇒ Next assign -1 to selected |ket⟩ → |11⟩
⇒ This can be done using combination of X, Z and CZ gates.
 
    1 0 0 0
0 1 1 0 0 1 0 0 
X = ,Z = and CZ =  
1 0 0 −1 0 0 1 0 
0 0 0 −1

5/21
Oracle/ Inversion Operator
⇒ CZ gate flips phase of if control bit is 1.
⇒ For |11⟩ we can use CZ gate. We will get:
1 1 1 1
|ψ⟩ = |00⟩ + |01⟩ + |10⟩ + |11⟩
2 2 2 2
  
1 0 0 0 1
1 0 1 0 0 
 1
 
= 
2 0 0 1 0  1
0 0 0 −1 1
         
1 1 0 0 0
1 1  1 0 1 0  0 
=   =   +   +   +  
         
2 1 2 0 0 1 0 
−1 0 0 0 −1
1 1 1 1
= |00⟩ + |01⟩ + |10⟩ − |11⟩
2 2 2 2
⇒ Amplitude of states: (0.5, 0.5, 0.5, −0.5), Mean = 0.25

Figure: Oracle for Example

6/21
Tensor Product

⇒ Consider matrices A and B given below:

   
a11 a12 b11 b12
A= B=
a21 a22 b21 b22

⇒ Tensor Product A ⊗ B is given as:

    
b11 b12 b11 b12
    a 11 a12
a11 a12 b
⊗ 11
b12 b21 b22  b21 b22 

= 
a21 a22 b21 b22 b b12 b b12 
a21 11 a22 11

b21 b22 b21 b22
 
a11 b11 a11 b12 a12 b11 a12 b12
a11 b21 a11 b22 a12 b21 a12 b22 
=
a21 b11

a21 b12 a22 b11 a22 b12 
a21 b21 a21 b22 a22 b21 a22 b22

7/21
Oracle/Inversion Operator

(a) Oracle for |00⟩ (b) Oracle for |01⟩ (c) Oracle for |10⟩

Figure: Oracles for other |kets⟩

Oracle for State |01⟩

Since the states are in superposition Two qubits are considered as together not individuals

1
Z |ψ⟩ = Z (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
1
= Z (|00⟩ − |01⟩ + |10⟩ − |11⟩) → Please refer next slide for explanation
2
1
CZ |ψ⟩ = CZ (|00⟩ − |01⟩ + |10⟩ − |11⟩)
2
1
= (|00⟩ − |01⟩ + |10⟩ + |11⟩)
2
8/21
Z gate
Z gate on a single qubit

    
1 0 1 1
Z |0⟩ = = = |0⟩
0 −1 0 0
    
1 0 0 0
Z |1⟩ = = = −|1⟩
0 −1 1 −1

Z gate on Two qubit

    
    1 0 0 0 1 1
1 0 1 0 0 −1 0 0 
 0
  0
Z |00⟩ = (Z ⊗ I )|00⟩ = ⊗ |00⟩ =  0 = |00⟩
= 
0 −1 0 1 0 0 1 0  0
0 0 0 −1 0 0
    
    1 0 0 0 0 0
1 0 1 0 0 −1 0 0 
 1
  −1
Z |01⟩ = (Z ⊗ I )|01⟩ = ⊗ |01⟩ =   0  = −|01⟩
= 
0 −1 0 1 0 0 1 0  0
0 0 0 −1 0 0
    
    1 0 0 0 0 0
1 0 1 0 0 −1 0 0 
 0
  0
Z |10⟩ = (Z ⊗ I )|10⟩ = ⊗ |10⟩ =  1 = |10⟩
= 
0 −1 0 1 0 0 1 0  1
0 0 0 −1 0 0
    
    1 0 0 0 0 0
1 0 1 0 0 −1 0 0 
 0
   0 
Z |11⟩ = (Z ⊗ I )|11⟩ = ⊗ |11⟩ =   0  = −|11⟩
= 
0 −1 0 1  0 0 1 0   0
0 0 0 −1 1 −1

9/21
Diffuser/Reflection Operator

⇒ Inverts amplitude about the mean.

⇒ Amplitudes of +ve |ket⟩ are to be decreased whereas
amplitudes of −ve |ket⟩ are to increased.
⇒ This is done using combination of Hadamard, X and CZ gates
⇒ First we apply H gates followed by X to all |ket⟩
⇒ H gates will bring amplitude of −ve |ket⟩ towards 1, and
+ve |ket⟩ towards 0.
⇒ X gate will be used to invert probabilities of 0 and 1.
   
1 1 0 1 1 1 1 1
H= ,X = and |ψ⟩ = |00⟩ + |01⟩ + |10⟩ − |11⟩
1 −1 1 0 2 2 2 2

⇒ Next we apply CZ gate, X and H gate so that we get +ve

amplitude of probabilistic nature.

|ψ⟩ = 0|00⟩ + 0|01⟩ + 0|10⟩ + 1|11⟩

10/21
Diffuser/Reflection Operator And Circuit for example.

Figure: Diffusion Operator

Figure: Circuit for Example

11/21
Diffuser/Reflection Operator
Hadamard Gate:

1
H|ψ⟩ = H(|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
1
= ((H ⊗ H)|00⟩ + (H ⊗ H)|01⟩ + (H ⊗ H)|10⟩ − (H ⊗ H)|11⟩)
2
    
1 1 1 1 1 1
(H ⊗ H)|00⟩ = √ ⊗√ ] [|0⟩ ⊗ |0⟩]
2 1 −1 2 1 −1
    
1 1 1 1 1 1
1 1 −1 1 −1 0 1 1
=     =  

2 1 1 −1 −1 0 2 1
1 −1 −1 1 0 1
1
= (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
1
H|01⟩ = (|00⟩ − |01⟩ + |10⟩ − |11⟩)
2
1
H|10⟩ = (|00⟩ + |01⟩ − |10⟩ − |11⟩)
2
1
H|11⟩ = (|00⟩ − |01⟩ − |10⟩ + |11⟩)
2
1
H|ψ⟩ = (|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
12/21
Diffuser/Reflection Operator
X Gate:
1
X |ψ⟩ = X (|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
   
0 1 0 1
X |00⟩ = ⊗ [|0⟩ ⊗ |0⟩]
1 0 1 0
    
0 0 0 1 1 0
0 0 1 0 0 0
X |00⟩ = 
    =   = |11⟩
0 1 0 0 0 0
1 0 0 0 0 1
X |01⟩ = X |10⟩, X |10⟩ = X |01⟩, X |11⟩ = X |00⟩
1
X |ψ⟩ = (−|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
CZ Gate:
 
1
CZ |ψ⟩ = CZ (−|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
    
1 0 0 0 −1 −1
1 0 1 0  1  = 1  1 
0     
= 
2 0 0 1 0  1  2 1 
0 0 0 −1 1 −1
1
CZ |ψ⟩ = (−|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
13/21
Diffuser/Reflection Operator
X Gate:

1
X |ψ⟩ = X (−|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
1
X |ψ⟩ = (−|00⟩ + |01⟩ + |10⟩ − |11⟩)
2

Hadamard Gate:

1
H|ψ⟩ = H(−|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
1
H(−|00⟩) = (−|00⟩ − |01⟩ − |10⟩ − |11⟩)
2
1
H|01⟩ = (|00⟩ − |01⟩ + |10⟩ − |11⟩)
2
1
H|10⟩ = (|00⟩ + |01⟩ − |10⟩ − |11⟩)
2
1
H(−|11⟩) = (−|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
H|ψ⟩ = |11⟩

14/21
Grover’s Algorithm for 3 Qubits

(a) Oracle for 3 Qubits (b) Diffuser for 3 Qubits

Figure: Circuit for 3 Qubit Grover Algorithm

15/21
Grover’s Algorithm for 3 Qubits
⇒ Let’s assume we need to build oracle for |111⟩
⇒ H gate for 3 qubits will be given as

H|ψ⟩ = (H ⊗ H ⊗ H)
1 1 1 1 1 1 1 1
 
1 −1 1 −1 1 1 −1 1 
1 1 −1 1 1 1 −1 −1
 
 
HH HH 1 −1 −1 1 1 −1 −1 1 
 
H= = (0.354) 
HH −HH 1 1 1 1 −1 −1 −1 −1

1 −1 1 −1 −1 1 −1 1 
 
1 1 −1 −1 −1 −1 1 1 
1 −1 −1 1 −1 1 1 −1
1 1 1 1 1 1 1 1 1 1
    
1 −1 1 −1 1 1 −1 1  0 1
1 1 −1 1 1 1 −1 −1 0 1
    
1 −1 −1 1 1 −1 −1 1  0 1
    
H|0001⟩ = (0.354)     = (0.354)  
1 1 1 1 −1 −1 −1 −1 0 1
1 −1 1 −1 −1 1 −1 1  0 1
    
1 1 −1 −1 −1 −1 1 1  0 1
1 −1 −1 1 −1 1 1 −1 0 1
= (0.354)(|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩)
16/21
Grover’s Algorithm for 3 Qubits
Oracle/Inversion Operator:

CZ Gate for 3 Qubits

CCZ = I ⊗ I ⊗ |0⟩⟨0| + CZ ⊗ |1⟩⟨1|

1 0 0 0 0 0 0 0
 
0 1 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
 
0 0 0 1 0 0 0 0 
 
=
0 0 0 0 1 0 0 0 

0 0 0 0 0 1 0 0 
 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 −1

CCZ |ψ⟩ = (0.354)CCZ (|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩)
= (0.354)(|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ − |111⟩)

17/21
Grover’s Algorithm for 3 Qubits - Diffuser
H Gate:

H|ψ⟩ = (0.354)H(|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ − |111⟩)

= (0.75)|000⟩ + (0.25)|001⟩ + (0.25)|010⟩ − (0.25)|011⟩
+ (0.25)|100⟩ − (0.25)|101⟩ − (0.25)|110⟩ + (0.25)|111⟩

X Gate:

X |ψ⟩ = X ((0.75)|000⟩ + (0.25)|001⟩ + (0.25)|010⟩ − (0.25)|011⟩

+ (0.25)|100⟩ − (0.25)|101⟩ − (0.25)|110⟩ + (0.25)|111⟩)
= (0.25)|000⟩ − (0.25)|001⟩ − (0.25)|010⟩ + (0.25)|011⟩
− (0.25)|100⟩ + (.25)|101⟩ + (0.25)|110⟩ + (0.75)|111⟩

CCZ Gate:

CCZ |ψ⟩ = CCZ ((0.25)|000⟩ − (0.25)|001⟩ − (0.25)|010⟩ + (0.25)|011⟩

− (0.25)|100⟩ + (0.25)|101⟩ + (0.25)|110⟩ + (0.75)|111⟩)
= (0.25)|000⟩ − (0.25)|001⟩ − (0.25)|010⟩ + (0.25)|011⟩
− (0.25)|100⟩ + (0.25)|101⟩ + (0.25)|110⟩ − (0.75)|111⟩

18/21
Grover’s Algorithm for 3 Qubits - Diffuser
X Gate:

X |ψ⟩ = X ((0.25)|000⟩ − (0.25)|001⟩ − (0.25)|010⟩ + (0.25)|011⟩

− (0.25)|100⟩ + (0.25)|101⟩ + (0.25)|110⟩ − (0.75)|111⟩)
= −(0.75)|000⟩ + (0.25)|001⟩ + (0.25)|010⟩ − (0.25)|011⟩
+ (0.25)|100⟩ − (0.25)|101⟩ − (0.25)|110⟩ + (0.25)|111⟩

H Gate:

H|ψ⟩ = H(−(0.75)|000⟩ + (0.25)|001⟩ + (0.25)|010⟩ − (0.25)|011⟩

+ (0.25)|100⟩ − (0.25)|101⟩ − (0.25)|110⟩ + (0.25)|111⟩)
= −(0.18)|000⟩ − (0.18)|001⟩ − (0.18)|010⟩ − (0.18)|011⟩
− (0.18)|100⟩ − (0.18)|101⟩ − (0.18)|110⟩ − (0.88)|111⟩

After 1 run of oracle and diffuser:

|psi⟩ = −(0.18)|000⟩ − (0.18)|001⟩ − (0.18)|010⟩ − (0.18)|011⟩

− (0.18)|100⟩ − (0.18)|101⟩ − (0.18)|110⟩ − (0.88)|111⟩

After 2 runs of oracle and diffuser:

|psi⟩ = −(0.09)|000⟩ − (0.09)|001⟩ − (0.09)|010⟩ − (0.09)|011⟩

− (0.09)|100⟩ − (0.09)|101⟩ − (0.09)|110⟩ − (0.97)|111⟩
19/21
Grover’s Algorithm
⇒ Amplitude Amplification will increase the probability of state
being measured to correct value.
√
⇒ We need to repeatedly apply Oracle and Diffuser N times.
⇒ Variation of Grover’s Algorithm for
q multiple
 targets also
N
possible. Will have complexity O t for t possible
matches.

Figure: Generalized Circuit

20/21
Thank You

21/21