Quantum Architecture and Programming

Prof. Kunal Korgaonkar

BITS-Pilani, K K Birla, Goa Campus

September 15, 2025

1/44
Introduction

⇒ Deutsch’s Algorithm
⇒ Deutsch Jozsa’s Algorithm
⇒ Bernstein Vazirani Algorithm

2/44
Deutsch’s Algorithm

⇒ David Deutsch formulated the algorithm in 1985.

⇒ Current version is slight improvement.
⇒ Suppose we have 1-bit Boolean function f : {0, 1} → {0, 1}
without knowing details of implementation of f
⇒ Determine whether this function is balanced or constant.
⇒ Balanced Function → f (0) ̸= f (1)
⇒ Constant Function → f (0) = f (1)

3/44
Constant and Balanced Function
Tables for Constant Function:

Table: Constant 0 Table: Constant 1

X f(X) X f(X)
0 0 0 1
1 0 1 1

Tables for Balanced Function:

Table: Not Gate Table: Identity

X f(X) X f(X)
0 1 0 0
1 0 1 1

*No. of x’s where f(x) = 0 is equal to No. of x’s where f(x) = 1

4/44
Deutsch’s Algoritm

⇒ We need to check if

f (0) = f (1)?

⇒ If yes then f is constant else it is balanced.

⇒ Classical computer needs 2 queries of function.
⇒ Both f (0) and f (1) need to be calculated to check
whether f (0) = f (1)
⇒ Quantum Computer needs only 1 query to the function.

5/44
Reversible Gates
⇒ In quantum computation all gates and operation must be
reversible.
⇒ Reversible gates or reversible logic gates are the gates with a
property of equal number of inputs and outputs
⇒ Example of non-reversible classical gate: AND Gate and Its
conversion to reversible gate

Table: Reversible AND

Table: AND Gate A B C A B C⊗ f(A,B)
0 0 0 0 0 0
A B f(x)-AND Gate 0 0 1 0 0 1
0 0 0 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1
1 0 0 1 0 0 1 0 0
1 1 1 1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

*When C=0 output of this gate will be that of a AND gate 6/44
Quantum Oracle
⇒ We use technique above to build quantum oracles.
⇒ We have seen Grover’s Oracle before.
⇒ Here |x⟩ is input to function and |y ⟩ is target qubit where
output is to written. This ensures that oracle is reversible.
⇒ This would mean |x⟩|y ⟩ → |x⟩|y ⊕ f (x)⟩
⇒ It is important to note that x, y and f (x) are bits and |x⟩, |y ⟩
and |f (x)⟩ are quantum states
⇒ As we have seen in last table when y=0,

|x⟩|0⟩ → |x⟩|0 ⊕ f (x)⟩ = |x⟩|f (x)⟩

Since 0 ⊕ 0 = 0 and 0 ⊕ 1 = 1

x y x y ⊕ f (x)
x 0 x f (x)
x 1 x f (x)
Figure: A Basic Function Oracle Table: Function Oracle Table
7/44
Basis States

⇒ Z basis orthogonal States:

⇒ |0⟩
⇒ |1⟩
⇒ X basis orthogonal states:
⇒ |+⟩ = (|0⟩+|1⟩)
√
2
(|0⟩+|1⟩)
⇒ |−⟩ = √
2
⇒ Y basis orthogonal states:
⇒ |R⟩ = (|0⟩+i|1⟩)
√
2
(|0⟩−i|1⟩)
⇒ |L⟩ = √
2

8/44
Phase of Qubit

⇒ Phase of a qubit state is sin θ, where θ = angle between qubit

state and X-axis.
⇒ Phase for different basis states:

|0⟩ → θ = 0, sin θ = 0
|1⟩ → θ = π, sin θ = 0
π
|+⟩ → θ = , sin θ = 1
2
3π
|−⟩ → θ = , sin θ = −1
2

9/44
Phase Oracle
3π
⇒ Let’s set the target qubit to |−⟩. (θ = 2 , sin θ = −1)
⇒ Here we get something called as phase kickback.
⇒ Phase kickback is powerful quantum phenomenon that uses
entanglement properties to allow for transfer of phase
information from target register to control qubit
⇒ Here instead of f (x) being applied to target qubit, phase is
applied to input qubit.
⇒ This is important phenomenon and used in multiple
algorithms.

Figure: Phase Oracle

10/44
Phase Oracle proof:
⇒ We start with |x⟩|−⟩
1
|x⟩|−⟩ = |x⟩ √ (|0⟩ − |1⟩)
2
1
= √ (|x⟩|0⟩ − |x⟩|1⟩)
2
Apply Oracle Uf
1
= √ (Uf |x⟩|0⟩ − Uf |x⟩|1⟩)
2
Equivalent to
1
= √ (|x⟩|f (x)⟩ − |x⟩|f (x)⟩)
2

⇒ Now we get two cases,

( 1
√ (|x⟩|0⟩ − |x⟩|1⟩) : f (x) = 0
= 2
√1 (|x⟩|1⟩ − |x⟩|0⟩) : f (x) = 1
2

cont..
11/44
Phase Oracle proof:

⇒ Above cases can be rewritten as:

|x⟩ √1 (|0⟩ − |1⟩)
(
: f (x) = 0
= 2
|x⟩ √1 (|1⟩ − |0⟩) : f (x) = 1
2

⇒ Or, 
|x⟩|−⟩ : f (x) = 0
=
−|x⟩|−⟩ : f (x) = 1

⇒ This cases can be generalised as:

= (−1)f (x) |x⟩|−⟩

⇒ As can be seen Target qubit is left unchanged

⇒ Phase of (−1f (x) ) was applied to input qubit.

12/44
Deutsch’s Algorithm : Quantum Gates
⇒ Hadamard Gate(H):
⇒ Matrix Representation:
 
1 1 1
√
2 1 −1

⇒ Creates equal superposition state.

1
H|0⟩ = √ (|0⟩ + |1⟩) = |+⟩
2
1
H|1⟩ = √ (|0⟩ − |1⟩) = |−⟩
2

⇒ Matrix Representation for H|0⟩ and H|1⟩:

    
1 1 1 1 1 1 1
H|0⟩ = √ = √ = √ (|0⟩ + |1⟩) = |+⟩
2 1 −1 0 2 1 2
    
1 1 1 0 1 1 1
H|1⟩ = √ = √ = √ (|0⟩ − |1⟩) = |−⟩
2 1 −1 1 2 −1 2

13/44
Deutsch’s Algorithm : Quantum Gates
⇒ Pauli X Gate:
⇒ Single-qubit rotation through π radians around the x-axis.
⇒ This works like a not gate.
⇒ Matrix Representation:
 
0 1
1 0

⇒ Effect on |0⟩ and |1⟩

X |0⟩ = |1⟩
X |1⟩ = |0⟩

⇒ Matrix Representation for X |0⟩ and X |1⟩:

    
0 1 1 0
X |0⟩ = = = |1⟩
1 0 0 1
    
0 1 0 0
X |1⟩ = = = |0⟩
1 0 1 1

14/44
Deutsch’s Algorithm : Quantum Gates

⇒ CNOT Gate:
⇒ CNOT stands for Controlled NOT gate.
⇒ Unlike X Gate and Hadamard Gate, this gate is used with
two qubits.
⇒ Ex. [Link](q0 , q1 ) would mean q0 is control qubit and
q1 is bit that will be changed.
⇒ If q0 is 0 there are no changes to q1 .
⇒ If q0 is 1 then q1 is flipped.
⇒ Matrix Representation:
 
1 0 0 0
0 1 0 0
 
0 0 0 1
0 0 1 0

⇒ CNOT gate entangles qubit q0 and q1 .

15/44
Deutsch’s Algorithm : Quantum Gates

⇒ Ex. [Link](1, 0) as matrices:

    
1 0 0 0 0 0
0 1 0 0
 0 = 0 = |11⟩
   
CNOT (|10⟩) = 
0 0 0 1 1 0
0 0 1 0 0 1
    
1 0 0 0 0 0
0 1 0 0
 0 = 0 = |10⟩
   
CNOT (|11⟩) = 
0 0 0 1 0 1
0 0 1 0 1 0
    
1 0 0 0 1 1
0 1 0 0
 0 = 0 = |00⟩
   
CNOT (|00⟩) = 
0 0 0 1 0 0
0 0 1 0 0 0
    
1 0 0 0 0 0
0 1 0 0
 1 = 1 = |01⟩
   
CNOT (|01⟩) = 
0 0 0 1 0 0
0 0 1 0 0 0

16/44
Deutsch’s Algorithm

(b) Deutsch Algorithm Circuit on

(a) Deutsch Algorithm Circuit Qiskit(Oracle inside barriers)

Figure: Deutsch Algorithm Circuit

17/44
Working of Deutsch’s Algorithm
⇒ Initially qubits are in state |ψ0 ⟩ = |00⟩
⇒ Next we apply X gate on target qubit and get |ψ1 ⟩ = |01⟩
⇒ Applying Hadamard Gate on both qubit gives us:
1 1
|ψ2 ⟩ = | + −⟩ = √ (|0⟩ + |1⟩)|−⟩ = √ (|0⟩|−⟩ + |1⟩|−⟩)
2 2

Figure: Deutsch’s Algorithm Circuit

cont.. 18/44
Working of Deutsch’s Algorithm
⇒ Now we apply oracle Uf
1 1
|ψ3 ⟩ = Uf √ (|0⟩|−⟩ + |1⟩|−⟩) = √ (Uf |0⟩|−⟩ + Uf |1⟩|−⟩)
2 2
⇒ As can be seen above state (in red), are in Phase oracle form:
Uf |x⟩|−⟩ = (−1)f (x) |x⟩|−⟩
⇒ Now we can rewrite the equation as:
1
|ψ3 ⟩ = √ ((−1)f (0) |0⟩|−⟩ + (−1)f (1) |1⟩|−⟩)
2

cont.. 19/44
Working of Deutsch’s Algorithm
⇒ If we separate |−⟩ state we write the equation as:
1
|ψ3 ⟩ = √ ((−1)f (0) |0⟩ + (−1)f (1) |1⟩)|−⟩
2
⇒ Going forward we won’t consider |−⟩ state as it is not
measured. So,
1
|ψ3 ⟩ = √ ((−1)f (0) |0⟩ + (−1)f (1) |1⟩)
2

cont.. 20/44
Working of Deutsch’s Algorithm
⇒ Now if f (0) = f (1) = 0,
1
|ψ3 ⟩ = √ (|0⟩ + |1⟩)
2
⇒ If f (0) = f (1) = 1,
1
|ψ3 ⟩ = √ (−|0⟩ − |1⟩)
2
or
1
|ψ3 ⟩ = − √ (|0⟩ + |1⟩)
2
⇒ Here we can say that
1
|ψ3 ⟩ = ± √ (|0⟩ + |1⟩) = ±|+⟩ if f (0) = f (1)
2

21/44
Working of Deutsch’s Algorithm
⇒ Now if f (0) ̸= f (1),

1
|ψ3 ⟩ = ± √ (|0⟩ − |1⟩) = ±|−⟩ if f (0) ̸= f (1)
2
⇒ Now apply Hadamard Gate:
if f (0) = f (1) : |ψ4 ⟩ = ±|0⟩
if f (0) ̸= f (1) : |ψ4 ⟩ = ±|1⟩
⇒ Upon Measuremnt ± sign would not matter.
⇒ If we measure 0, f (x) is constant.
⇒ And if we measure 1, f (x) is balanced.

22/44
Deutsch - Jozsa Algorithm

⇒ A generalization of Deutsch’s algorithm.

⇒ It was proposed by David Deutsch and Richard Jozsa in 1992.
⇒ First examples of quantum algorithm that is exponentially
faster than any possible deterministic classical algorithm.
⇒ Suppose we have n-bit Boolean function f : {0, 1}n → {0, 1}
without knowing details of implementation of f
⇒ Determine whether this function is balanced or constant.
⇒ Balanced Function → 1 for exactly half of input domain and 0
for other half. i.e. exactly 50% of the times output is 0.
⇒ Constant Function → 0 on all inputs or 1 on all inputs.

23/44
Deutsch - Jozsa Algorithm

⇒ A classical computer will take at worst (2n−1 + 1) queries.

⇒ A quantum computer will take 1 query to solve the problem.
⇒ Worst Case for classical computers:
⇒ We input 2n−1 different inputs and all of them give same
output.
⇒ For (2n−1 + 1)th query:
⇒ if we get same output → f (x) is constant
⇒ if we get different output → f (x) is balanced.

24/44
Deutsch - Jozsa Algorithm Circuit

Figure: Deutsch’s Jozsa Algorithm Circuit

25/44
Deutsch - Jozsa Algorithm
⇒ Initial State:
|ψ0 ⟩ = |0⟩⊗n |−⟩

⇒ After application of Hadamard Gates to all input states:

|ψ1 ⟩ = H ⊗n |0⟩⊗n |−⟩

⇒ When we expand this we get:

1 1
|ψ1 ⟩ = √ (|0⟩ + |1⟩) ⊗ · · · ⊗ √ (|0⟩ + |1⟩)|−⟩
2 2

⇒ For n = 2:
1 1 1
H ⊗2 |0⟩⊗2 = √ (|0⟩ + |1⟩) ⊗ √ (|0⟩ + |1⟩) = √ (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2 2 22

26/44
Deutsch - Jozsa Algorithm
⇒ For N = 3:
1
H ⊗3 |0⟩⊗3 = √ (|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩)
23
⇒ We can write these equations as:
1 X 1 X
H ⊗2 |0⟩⊗2 = √ |x⟩ and H ⊗3 |0⟩⊗3 = √ |x⟩
22 x∈{0,1}2
23 x∈{0,1}3

⇒ We can generalize this equation as:

1 X
H ⊗n |0⟩⊗n = √ |x⟩
2n x∈{0,1}n

⇒ So we can write |ψ1 ⟩ as:

1 X
|ψ1 ⟩ = √ |x⟩|−⟩
2n x∈{0,1}n

27/44
Deutsch - Jozsa Algorithm
⇒ Apply Oracle to get |ψ2 ⟩:
1 X 1 X
|ψ2 ⟩ = Uf √ |x⟩|−⟩ = √ Uf |x⟩|−⟩
2n x∈{0,1}n
2n x∈{0,1}n

⇒ Each state in superposition is in Phase Oracle form. So we

will get phase kick back.
1 X
|ψ2 ⟩ = √ (−1)f (x) |x⟩|−⟩
2n x∈{0,1}n

⇒ We can omit |−⟩ qubit since we do not require it further.

1 X
|ψ2 ⟩ = √ (−1)f (x) |x⟩
2n x∈{0,1}n

28/44
Deutsch - Jozsa Algorithm

⇒ Next We apply Hadamard Gate to |ψ2 ⟩ to get |ψ3 ⟩ :

1 X
|ψ3 ⟩ = √ (−1)f (x) H ⊗n |x⟩
2n x∈{0,1}n

29/44
Hadamard Gate on |x⟩

H ⊗n |x⟩ = H|x0 ⟩H|x1 ⟩ · · · H|xn−1 ⟩

1 1
H|0⟩ = √ (|0⟩ + |1⟩) = √ (|0⟩ + (−1)0 |1⟩)
2 2
1 1
H|1⟩ = √ (|0⟩ − |1⟩) = √ (|0⟩ + (−1)1 |1⟩)
2 2
1 xi
H|xi ⟩ = √ (|0⟩ + (−1) |1⟩) ⇒ xi can be 0 or 1
2
Testing H ⊗2 |x⟩
1 1
H ⊗2 |x⟩ = H|x1 ⟩|x2 ⟩ = √ (|0⟩ + (−1)x1 |1⟩) √ (|0⟩ + (−1)x2 |1⟩)
2 2
1
= √ (|00⟩ + (−1) |01⟩ + (−1) |10⟩ + (−1)x1 (−1)x2 |11⟩)
x2 x1
22
Testing H ⊗3 |x⟩
H ⊗3 |x⟩ = H|x0 ⟩H|x1 ⟩H|x2 ⟩
1
= √ (|000⟩ + (−1)x2 |001⟩ + (−1)x1 |010⟩ + (−1)x1 (−1)x2 |011⟩
23
+ (−1)x0 |100⟩ + (−1)x0 (−1)x2 |101⟩ + (−1)x0 (−1)x1 |110⟩
+ (−1)x0 (−1)x1 (−1)x2 |111⟩)
30/44
Hadamard Gate on |x⟩
Above equation can be written as

1
H ⊗3 |x⟩ = √ (|000⟩ + (−1)x2 |001⟩ + (−1)x1 |010⟩ + (−1)x1 +x2 |011⟩ + (−1)x0 |100⟩
23
+ (−1)x0 +x2 |101⟩ + (−1)x0 +x1 |110⟩ + (−1)x0 +x1 +x2 |111⟩)

Wherever there is 1 in state there is (−1)xi in coefficient where xi is position of 1.

We can write these exponents as dot products of x with superposition’s of x.

1
H ⊗3 |x⟩ = √ (|000⟩ + (−1)x.001 |001⟩ + (−1)x.010 |010⟩ + (−1)x.011 |011⟩
23
+ (−1)x.100 |100⟩ + (−1)x.101 |101⟩ + (−1)x.110 |110⟩ + (−1)x.111 |111⟩)

We can write entire expression as sum of all possible combinations of 0 and 1 of

length n.

1 X
H ⊗3 |x⟩ = √ (−1)x.z |z⟩
23 z∈{0,1}3

Generalizing the Equation we get:

1 X
H ⊗n |x⟩ = √ (−1)x.z |z⟩
2n z∈{0,1}n
31/44
Deutsch - Jozsa Algorithm
1 X
|ψ3 ⟩ = √ (−1)f (x) H ⊗n |x⟩
2n x∈{0,1}n

⇒ Substituting Hadamard equation here we get:

⇒ Rewrite it as:

1 X 1 X
|ψ3 ⟩ = √ (−1)f (x) √ (−1)x.z |z⟩
2n x∈{0,1}n 2n z∈{0,1}n
1 X X
|ψ3 ⟩ = (−1)f (x) (−1)x.z |z⟩
2n
x∈{0,1}n z∈{0,1}n
1 X X
|ψ3 ⟩ = (−1)f (x)+x.z |z⟩
2n
x∈{0,1}n z∈{0,1}n

32/44
Deutsch - Jozsa Algorithm

1 X X
|ψ3 ⟩ = (−1)f (x)+x.z |z⟩
2n
x∈{0,1}n z∈{0,1}n

Rather than figuring out what we will get after measuring |ψ3 ⟩, let’s check: What is
probability that |ψ3 ⟩ will collapse to state |0⟩? We can answer this by setting z = 0
⇒ This happens if f (x) is constant
⇒ |ψ3 ⟩ with all 0 state |0⟩⊗n

1 X
|ψ3 ⟩ = (−1)f (x)+x.00···0 |0⟩
2n
x∈{0,1}n

⇒ This state can be written as

1 X
|ψ3 ⟩ = (−1)f (x) |0⟩
2n
x∈{0,1}n

Dot product of x with all 0 state is 0.

33/44
Deutsch - Jozsa Algorithm
⇒ If f(x) is constant:
(
1 P 0
2n n (−1) |0⟩ : f (x) = 0
|ψ3 ⟩ = 1 Px∈{0,1} 1
2n x∈{0,1}n (−1) |0⟩ : f (x) = 1
(
1 P 0
2n n (−1) |0⟩ : f (x) = 0
|ψ3 ⟩ = 1 Px∈{0,1} 1
2n x∈{0,1}n (−1) |0⟩ : f (x) = 1
1 n

|ψ3 ⟩ = 2n 2 |0⟩ : f (x) = 0
1 n
2n (−2 )|0⟩ : f (x) = 1

1|0⟩ : f (x) = 0
|ψ3 ⟩ =
−1|0⟩ : f (x) = 1
|ψ3 ⟩ = ±1|0⟩

⇒ This would mean when f (x) is constant probability of getting

all O state is 1 which also means that amplitude of all other
superposition’s of |z⟩ is 0 when f (x) is constant.
34/44
Deutsch - Jozsa Algorithm

⇒ If f is balanced, then half of f (x)’s will cancel other half

⇒ Examples, Let f (x) values be one of the following
(11110000), (11001100), (10101010), (11000101).
⇒ We have to remember that half of values should be 1’s and
other half should 0’s as per the problem statement.
⇒ The order of 0’s and 1’s do not matter.
⇒ In all above cases, number of (−1)0 will be equal to (−1)1 .
So there will be +1 for each -1.
|ψ3 ⟩ = 0|0⟩

⇒ When measuring |ψ3 ⟩, we will get |0⟩ iff function is constant.

If anything else is measured, function is balanced.

35/44
Bernstein Vazirani (BV) Algorithm
⇒ Invented by Ethan Bernstein and Umesh Vazirani in 1997.
⇒ Restricted version of Deutsch–Jozsa algorithm.
⇒ Instead of distinguishing between two different classes of
functions, it tries to learn string encoded in function.
⇒ Given oracle that implements function f : {0, 1}n → {0, 1}.
⇒ f (x) is promised to be dot product between x and secret
string s ∈ {0, 1}n modulo 2,
f (x) = x · s (mod 2) = x1 s1 ⊕ x2 s2 ⊕ · · · ⊕ xn sn , find s.
⇒ x.s = x1 s1 + x2 s2 + · · · + xn sn ⇒ ′ +′ stands for addition.
⇒ x1 s1 ⊕ x2 s2 ⊕ · · · ⊕ xn sn = 1 for odd no. of 1’s and 0 for
even no. of 1’s.
⇒ Ex.
(x.s) = (11.11) = (1)(1) + (1)(1) = 1 + 1 = 0
= (1)(1) ⊕ (1)(1) = 1 ⊕ 1 = 0
(x.s) = (100.111) = (1)(1) + (0)(1) + (0)(1) = 1 + 0 + 0 = 1
= (1)(1) ⊕ (0)(1) ⊕ (0)(1) = 1 ⊕ 0 ⊕ 0 = 1

⇒ Classical Algorithm needs n queries whereas Quantum

computer finds s in 1 query. 36/44
Classical Approach for BV Algorithm

37/44
Classical Approach for BV Algorithm

37/44
Classical Approach for BV Algorithm

37/44
Classical Approach for BV Algorithm

37/44
Classical Approach for BV Algorithm

37/44
Classical Approach for BV Algorithm

37/44
BV Algorithm

Figure: BV Algorithm Circuit

As can be seen this is same circuit as Deutsch Jozsa Algorithm.

38/44
BV Algorithm
⇒ As seen before |ψ3 ⟩ could be given as:
1 X X
|ψ3 ⟩ = (−1)f (x)+x.z |z⟩
2n
x∈{0,1}n z∈{0,1}n

⇒ Let’s take only magnitude of |z⟩ for time being:

1 X
(−1)f (x)+x.z
2n
x∈{0,1}n

⇒ From definition of BV algorithm we know, f (x) = x.s

1 X
(−1)x.s+x.z
2n
x∈{0,1}n

⇒ (−1)x.s+x.z will be same as (−1)x.(s+z)

⇒ As we are using (−1)(s+z) we can use (−1)(s+z) mod 2 instead.
Since (−1)0 = (−1)2 · · · = (−1)2n and (−1)1 = (−1)3 · · · = (−1)2n+1
39/44
BV Algorithm

⇒ Modulo 2 addition of x.(s + z) = x.(s ⊕ z)

⇒ Example for (−1)x.s+x.z = (−1)x.(s⊕z) :
Let x=1010, s=1110, z = 0110

(−1)x.s+x.z = (−1)3 = −1

(−1)x.(s⊕z) = (−1)1 = −1

⇒ The Equation for magnitude of |z⟩ will be:

1 X
(−1)x.(s⊕z)
2n
x∈{0,1}n

⇒ We need to maximise the possibility of getting state |z⟩.

Hence we need to maximise the above equation.
⇒ To get magnitude of |z⟩ as 1 we need s ⊕ z = 0 or when s = z.

40/44
BV Algorithm
⇒ Coming back to state |z⟩. |z⟩ is superposition of states:
|z⟩ = α0 |0 · · · 0⟩ + · · · + αs |s⟩ + · · · + αn |1 · · · 1⟩

⇒ Now as seen before |ψ3 ⟩ is given as:

 
1
X X
x.(s⊕z) 
|ψ3 ⟩ = (−1) |z⟩
n
2n
z∈{0,1} x∈{0,1}n

⇒ We now know that probability of |z⟩ to be in state |s⟩ is 1.

So, αs = 1
⇒ We also know that:
|α0 |2 + · · · + |αs |2 + · · · + |αn ⟩ = 1

⇒ |α0 |2 + · · · + 1 + · · · + |αn ⟩ = 1

⇒ This would imply that α0 , ...αn except αs are 0

⇒ This implies that when we measure after querying oracle we
will always get s.
41/44
BV Algorithm implementation on Qiskit.

Figure: BV Algorithm Circuit on Qiskit for checking ’101001’.Oracle

between the barriers

42/44
BV Algorithm Qiskit Circuit analysis.

⇒ Let’s analyse the circuit bit-wise.

⇒ If we see the Oracle. There are C-NOT gates where there
need to be 1 on output. This is done to flip bit qn from 0 to 1.
|q0 ⟩|q1 ⟩|q2 ⟩|q3 ⟩|q4 ⟩|q5 ⟩ = |000000⟩
On application of Hadamard Gates
= |+⟩|+⟩|+⟩|+⟩|+⟩|+⟩
On application of C-NOT Gates - Oracle
= |−⟩|+⟩|+⟩|−⟩|+⟩|−⟩
On application of Hadamard Gates
= |1⟩|0⟩|0⟩|1⟩|0⟩|1⟩

⇒ After measurement q0 will be in bit position 0, q1 in 1 and so

on. This will give us string ’101001’ 43/44
Thank You

44/44