Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Quantum Computing
#8: Examples of Quantum Algorithms

송기원

2022
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Outline

1 Time Complexity

2 Deutsch-Jozsa Algorithm

3 Simon’s Problem

4 Bounded-error time complexity

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Even if we can solve the problem, is it practical?

Pn
▶ Think about calculating k=0 π(k!). We can, but we can’t.

Simple definition of P
A complexity class P is a class of problems that can be solved in
polynomial time step.

The term ‘polynomial time step’ is ambiguous, but this

intuitive definition is enough for discussion of complexity.
▶ The precise definition of P is defined with a Turing machine,
which is a theoretical machine with a bi-infinite strip of bits.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

NP

Definition(Certifier)
For some T/F problem P : X → { T , F } (its input is from X ),
a function V : X × C → { T , F } is a certifier if:

∃c ∈ C ; V (x, c) = T =⇒ P(x) = T

So it certifies x is a yes-instance helped by the certificate y .

Simple definition of NP
A complexity class NP is a class of T/F problems that has a
certifier working in polynomial time step.

Think about a question: “Is n composite?”.

▶ Choosing d and trying to divide n by d will verify it.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

P vs. NP

What is the difference? P and NP?

At least P is in NP, as we can choose V as the solution itself.
If P = NP: “A T/F problem can be solved in polynomial time
if there is a way to verify it is T within polynomial time”
Anyone who proves/disproves P = NP gets $100,000
▶ ([Link]
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Query complexity

From now on, the problems are testing functions.

n
▶ e.g. Given a function f : { 0, 1 } → { 0, 1 }, is f constant?
Instead of using time step as a unit, how about the number of
evaluating the function?

Definition(Query complexity)
Query complexity ignores all the time step took in calculation,
but only counts the number of inputs done to a given function.

It will be useful when calculating the function value of f takes

a significantly higher amount of time.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Outline

1 Time Complexity

2 Deutsch-Jozsa Algorithm

3 Simon’s Problem

4 Bounded-error time complexity

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Oracle

To use functions in quantum circuits, we need to make it as a

form of matrix.
As it has to be a reversible matrix, it has to be square.

Definition(Boolean oracle)
A boolean oracle Uf of f : { 0, 1 }m → { 0, 1 }n maps |x⟩ ⊗ |y ⟩
where x is m-qubits and y is n-qubits, to |x⟩ ⊗ |y ⊕ f (x)⟩

Definition(Phase oracle)
A phase oracle Pf of f : { 0, 1 }m → { 0, 1 } maps |x⟩ where x is
m-qubits , to (−1)f (x) |x⟩.

Note that both oracles’ inverses are themselves; thus orthogonal.

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch’s Problem

Definition(Balanced function)
A function f : { 0, 1 }n → { 0, 1 } is balanced when the number of
inputs that gives 0 and 1 are equal.

The problem of Deutsch

For given f : { 0, 1 } → { 0, 1 }, is it balanced or constant?

If it is solved classically, then twice of query is needed.

▶ f (0) = 0: f (1) = 0 then constant, otherwise balanced.
▶ f (0) = 1: f (1) = 0 then balanced, otherwise constant.
How about querying |0⟩ and |1⟩ at the same time?
▶ It does the work with only one query; first to have difference
from classical computing.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch Algorithm (1/3)

|0⟩ H H
Uf
|1⟩ H

The symbol at the right top corner means measurement.

▶ The second qubit is not measured.
After the Hadamard gates, the qubits |0⟩ ⊗ |1⟩ become:
1 1 1
√ (|0⟩ + |1⟩) ⊗ √ (|0⟩ − |1⟩) = (|00⟩ − |01⟩ + |10⟩ − |11⟩)
2 2 2
After Uf for any possible f , qubits become:
1
(|0⟩ ⊗ |f (0)⟩ − |0⟩ ⊗ |f (0) ⊕ 1⟩ + |1⟩ ⊗ |f (1)⟩ − |1⟩ ⊗ |f (1) ⊕ 1⟩)
2
1 1
= |0⟩ ⊗ (|f (0)⟩ − |f (0) ⊕ 1⟩) + |1⟩ ⊗ (|f (1)⟩ − |f (1) ⊕ 1⟩)
2 2
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch Algorithm (2/3)

|0⟩ H H
Uf
|1⟩ H

As |x⟩ − |x ⊕ 1⟩ = (−1)x (|0⟩ − |1⟩) for all x ∈ { 0, 1 }:

1 1
|0⟩ ⊗ (|f (0)⟩ − |f (0) ⊕ 1⟩) + |1⟩ ⊗ (|f (1)⟩ − |f (1) ⊕ 1⟩)
2 2
1   1  
= |0⟩ ⊗ (−1) (|0⟩ − |1⟩) + |1⟩ ⊗ (−1)f (1) (|0⟩ − |1⟩)
f (0)
2 2
1   1
= √ (−1)f (0) |0⟩ + (−1)f (1) |1⟩ ⊗ √ (|0⟩ − |1⟩)


2 2
Thus two qubits are not entangled.
▶ Let’s focus on the first qubit now.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch Algorithm (3/3)

|0⟩ H H
Uf
|1⟩ H

The first qubit after Uf :

1  
√ (−1)f (0) |0⟩ + (−1)f (1) |1⟩
2
We have two possibilities:
▶ If f (0) = f (1) then the qubits are ± √12 |0⟩ + |1⟩

▶ If f (0) ̸= f (1) then the qubits are ± √12 |0⟩ − |1⟩

√1 √1



The last H: 2
|0⟩ + |1⟩ to |0⟩ and 2
|0⟩ − |1⟩ to |1⟩
▶ f (0) = f (1) then ± |0⟩ and otherwise ± |1⟩
Thus if measurement gives 0 then constant, 1 then balanced
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Kronecker product

To deal with several qubits, we want to abbreviate matrices.

So we can define something like tensor product.
▶ For Hadamard gate: (H ⊗ H)(|x⟩ ⊗ |y ⟩) = H |x⟩ ⊗ H |y ⟩

Definition(Kronecker Product)
For matrices A and B, the kronecker product of A and B is
 
A B A12 B · · · A1n B
 11 
 A21 B A22 B · · · A2n B 
A⊗B = .
 
 .. .. .. .. 
 . . . 

Am1 B Am2 B · · · Amn B

So m × n matrix and p × q matrix yield pm × nq matrix.

Note that the Kronecker power is denoted A⊗n .
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Kronecker product of Hadamard gate

" # " #
⊗n−1 ⊗n−1
1 1 1 1 H H
H=√ so H ⊗n = √
2 1 −1 2 H ⊗n−1 −H ⊗n−1

Kronecker product of Hadamard gate

 
1 1 1 1
 
1 1 −1 1 −1
H ⊗2 = 


2
1 1 −1 −1 
1 −1 −1 1
 
1 1 ··· 1
 
1 −1 · · ·
1  −1
H ⊗3 = √  .

. .. .. .. 
2 2. . . . 

1 −1 · · · −1
√ n
Note that the first row of H ⊗n is always 1/ 2 .
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch-Jozsa Problem

Deutsch-Jozsa Problem
For given f : { 0, 1 }n → { 0, 1 }, is it balanced or constant?

Note that the inputs are either balanced or constant.

▶ There is no function like f (0, 0) = 0 and otherwise 1.
In classical way, it needs at most 2n−1 + 1 times of querying.
▶ But the quantum way, it needs only one query!
This proves that EQP ⊋ P, where EQP denotes the class
‘exact quantum polynomial time’ (sometimes just QP).
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch-Jozsa Algorithm (1/3)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
|1⟩ H
 
n X 1
1 Y 1
After H:  √ n |xi ⟩ ⊗ √ (|0⟩ − |1⟩)
2 i=1 xi =0 2
1 X
After Uf : √ n+1 |x⟩ ⊗ (|f (x)⟩ − |f (x) ⊕ 1⟩)
2 x∈{ 0,1 }n

▶ In the same way : (|f (x)⟩ − |f (x) ⊕ 1⟩) = (−1)f (x) (|0⟩ − |1⟩)

1 X 1
Thus after Uf : √ n (−1)f (x) |x⟩ ⊗ √ (|0⟩ − |1⟩)
2 x∈{ 0,1 }n
2
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch-Jozsa Algorithm (2/3)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
|1⟩ H

1 X
Focusing on the upper qubits √ n (−1)f (x) |x⟩
2 x∈{ 0,1 }n
√ n
Consider the first row of H ⊗n whose entries are all 1/ 2 .
⊗n
▶ The first row the gate yields is the amplitude of |0⟩ .
1 X
(−1)f (x)
2n n
x∈{ 0,1 }

Thus the probability amplitude of |0⟩⊗n is:

▶ 0 if f is balanced, 1 if f = 0 and −1 if f = 1.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Deutsch-Jozsa Algorithm (3/3)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
|1⟩ H

Thus the probability amplitude of |0⟩⊗n is:

▶ 0 if f is balanced, 1 if f = 0 and −1 if f = 1.
Thus if |0⟩⊗n appears, then f is constant.
And otherwise, f is definitely balanced.

It gives the same result: 0 then constant, otherwise balanced

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Outline

1 Time Complexity

2 Deutsch-Jozsa Algorithm

3 Simon’s Problem

4 Bounded-error time complexity

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Pointwise sum and dot product of bits

Before we look at the Simon’s algorithm...

Definition(Bitwise XOR)
For n-bits x = a0 a1 a2 · · · an and y = b0 b1 b2 · · · bn , the bitwise XOR
x ⊕ y = c0 c1 c2 · · · cn satisfies ai ⊕ bi = ci for all i ∈ { 0, 1, · · · , n }.

As XOR is a base 2 addition, we can think bitwise XOR as an

addition without a carry.

Definition(Dot product of bits)

For n-bits x = a0 a1 a2 · · · an and y = b0 b1 b2 · · · bn , the dot product
of x and y is defined as x · y = a0 × b0 ⊕ a1 × b1 ⊕ · · · ⊕ an × bn .

We can think x and y as n-dimensional vectors to dot product.

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Distributive law of · over ⊕

Distributive law of · over ⊕

For n-bits a, b and c, they hold a · (b ⊕ c) = a · b ⊕ a · c.

Proof
Prove x × (y ⊕ z) = (x × y ) ⊕ (x × z) for all x, y , z ∈ { 0, 1 }.
We can take all 8 cases and verify it.
Using the result, by the definition of the dot product:
a · (b ⊕ c) = a0 × (b ⊕ c)0 ⊕ a1 × (b ⊕ c)1 ⊕ · · · ⊕ an × (b ⊕ c)n
= a0 × (b0 ⊕ c0 ) ⊕ a1 × (b1 ⊕ c1 ) ⊕ · · · ⊕ an × (bn ⊕ cn )
= (a0 × b0 ) ⊕ (a0 × c0 ) ⊕ · · · ⊕ (an × bn ) ⊕ (an × cn )
= (a0 × b0 ) ⊕ · · · ⊕ (a0 × bn ) ⊕ (a0 × c0 ) ⊕ · · · ⊕ (an × cn )
=a·b⊕a·c
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Hadamard matrix and the dot product

" #
1 (−1)0·0 (−1)0·1
Rewrite the Hadamard matrix: H = √
2 (−1)1·0 (−1)1·1
We can think H as the powers of −1 based on coordinates:
0 1
" #
0 (−1)0·0 (−1)0·1
1 (−1)1·0 (−1)1·1

Then the Kronecker product can be treated as lengthening.

▶ (−1)0·0 (−1)a·b = (−1)0·0⊕a·b = (−1)0a·0b (left top: add 0, 0)
▶ (−1)0·1 (−1)a·b = (−1)0·1⊕a·b = (−1)0a·1b (right top: add 0, 1)
▶ (−1)1·0 (−1)a·b = (−1)1·0⊕a·b = (−1)1a·0b (left bot: add 1, 0)
▶ (−1)1·1 (−1)a·b = (−1)1·1⊕a·b = (−1)1a·1b (right bot: add 1, 1)
Thus the value of entry at 101-th row, 111-th column of H ⊗3
will be √1 3 (−1)101·111 = 2√
1
2
.
2
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Simon’s problem

Simon’s problem
For given f : { 0, 1 }n → { 0, 1 }n , it satisfies f (x) = f (y ) if and
only if x = y or x = y ⊕ s, for some nonzero constant s. Find s.

We can think s as a period of f .

In a classical way, at most (2n−1 + 1) times of query is needed
to get a pair of inputs that give the same output.
▶ If x and y is found, then x ⊕ y = x ⊕ (x ⊕ s) = s.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Simon’s algorithm: Quantum part (1/4)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
|0⟩⊗n
 
n X 1
1
|xi ⟩ ⊗ |0⟩⊗n
Y
After H:  √ n
2 i=1 xi =0
1 X
After Uf : √ n |x⟩ ⊗ |f (x)⟩
2 x∈{ 0,1 }n
1 X
After H: |ψ⟩ = √ n H ⊗n |x⟩ ⊗ |f (x)⟩
2 x∈{ 0,1 }n
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Simon’s algorithm: Quantum part (2/4)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
⊗n
|0⟩

Choose A ⊆ { 0, 1 }n such that x ∈ A ⇐⇒ x ⊕ s ̸∈ A

▶ This is possible as x 7→ x ⊕ s is a one-to-one function.
 
1 X X
|ψ⟩ = √ n  H ⊗n |x1 ⟩ ⊗ |f (x1 )⟩ + H ⊗n |x2 ⟩ ⊗ |f (x2 )⟩
2 x1 ∈A x2 ̸∈A
1 X  
=√ n H ⊗n |x⟩ ⊗ |f (x)⟩ + H ⊗n |x ⊕ s⟩ ⊗ |f (x ⊕ s)⟩
2 x∈A
1 X ⊗n
=√ n H (|x⟩ + |x ⊕ s⟩) ⊗ |f (x)⟩
2 x∈A
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Simon’s algorithm: Quantum part (3/4)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
⊗n
|0⟩
1 X
As H ⊗n |x⟩ = √ n (−1)x·y |y ⟩:
2 y ∈{ 0,1 }n
 
1 X 1 X  
|ψ⟩ = √ n √ n (−1)x·y + (−1)(x⊕s)·y |y ⟩ ⊗ |f (x)⟩

2 x∈A 2 y ∈{ 0,1 }n

As (−1)x·y + (−1)(x⊕s)·y = (−1)x·y (1 + (−1)s·y ):

1 X X  
(−1)x·y 1 + (−1)s·y |y ⟩ ⊗ |f (x)⟩


|ψ⟩ = n
2 n
x∈A y ∈{ 0,1 }
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Simon’s algorithm: Quantum part (4/4)

n n n n
|0⟩⊗n H⊗n H⊗n
Uf
⊗n
|0⟩

As 1 + (−1)s·y = 2 if s · y = 0 and otherwise 1 + (−1)s·y = 0:

1 X X
(−1)x·y |y ⟩ ⊗ |f (x)⟩


|ψ⟩ = n−1
2 n
x∈A y ∈{ 0,1 }
s·y =0

Thus measured |y ⟩ must be some vector y such that s · y = 0.

▶ The probability is uniform among the vectors with s · y = 0.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Simon’s algorithm: Classical part

Let’s say we got y1 , y2 , · · · , yn−1 by n − 1 repetitions.

▶ We have s · yi = 0 for 1 ≤ i ≤ n − 1.
To calculate unique s, they must be linearly independent.
▶ Only n − 1 vectors are sufficient, as s ̸= 0n .
Over 1/2 chance to have all vectors linearly independent.
▶ The probability of a vector to be independent to other k
2k 1
independent vectors is 1 − n = 1 − n−k
2 2
n−2
Y  n−1
Y  n−1
Y 
1 1 1
P= 1− = 1− k >2 1− k > 57%
2n−k 2 2
k=1 k=2 k=1

Not always solvable, but likely to solve.

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

Outline

1 Time Complexity

2 Deutsch-Jozsa Algorithm

3 Simon’s Problem

4 Bounded-error time complexity

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

BPP(Bounded-error Probabilistic Polynomial time)

Deutsch-Jozsa Algorithm takes O(2n ) queries so it is

techincally EXPTIME, but isn’t it too harsh?
▶ The case taking 2n−1 + 1 steps does not occur frequently.
If N random inputs to f gave all 0, f is a balanced function
1
with probability less than N .
2
▶ Plus, if there is at least one 1, it ensures that f is balanced.
f is a constant function with high enough probability.
▶ Just two trials of input reduces error under 1/4.

Definition(BPP)
BPP is a complexity class for problems that can be solved in a
polynomial time, allowing at most 1/3 giving the wrong answer.

Note that 1/3-chance means repeating it makes practically small.

Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

BQP(Bounded-error Quantum Polynomial time)

Simon’s algorithm does not have any upper bounds of query

to get the definite answer.
▶ Maybe y = 0 can come out every time.
But we know that n − 1 repetition gives exact s with
probability greater than 1/2.
If we do that twice, the error will be:
Error = (1 − P)2 < (1 − 1/2)2 = 1/4
Definition(BQP)
BQP is a complexity class for problems that can be solved in a
polynomial time with a quantum computer, allowing at most 1/3
giving the wrong answer.
Time Complexity Deutsch-Jozsa Algorithm Simon’s Problem Bounded-error time complexity

BPP ⊊ BQP

As all classical algorithms can be implemented with quantum

computers, BPP ⊆ BQP.
Simon’s problem is in BQP, as it takes O(n) queries to get
the right answer with probability greater than 2/3.
But we have to check at least Ω(2n/2 ) queries to find the
period in 3/4 chance.
▶ Check for proof here.
Thus Simon’s problem distinguishes BPP and BQP.
Conclusion

Conclusion: Practicality?

The quantum algorithms are not simply using the superposed

0 and 1s, but also having many procedures to use them.
▶ It is not simply faster like writing log at the front.
These algorithms show there are clear differences between
classical computing and quantum computing, but...
Is Deustch-Jozsa Problem practical? No.
▶ Functions that are neither balanced nor constant?
Is Simon’s problem practical? Maybe.
▶ But is making oracles easy enough? Practical?

Shor’s algorithm and Grover’s algorithm is practical.

▶ Not like problems that are made for using properties
▶ Covered in lecture 09 (an extra lecture)