Quantum Computing Foundations to Frontier
Quantum Computing: Foundations to Frontier Fall 2018
Lecturer: Henry Yuen Scribes: Deeksha Adil, Xing Hu, Jinhui Li, Fengwei Sun
1 Overview
In the last lecture we were looking at Simon’s algorithm. In this lecture we complete the analysis
of Simon’s algorithm and move on to Quantum Fourier Transform and its applications.
2 Simon’s Algorithm (continued)
Recall that Simon’s algorithm solves the following problem. The input is a function f : {0, 1}n →
{0, 1}n with the property, ∃s 6= 0 such that ∀x, y,
f(x) = f(y)⇐⇒
x = y ⊕ s.
The problem is to find s. Simon’s algorithm outputs s in polynomial time. To solve the problem
classically, any algorithm has to at least find a collision if it has to recover s and for that we need
at least Ω(2n/2) queries. Therefore, any classical algorithm requires exponentially many queries to
f to find s. In the last lecture we were analyzing the main subroutine of the algorithm.
2.1 Basic Subroutine
Let us briefly recall the subroutine.
1. Apply the Hadamard operator to each of the first n qubits.
2. Next apply Uf to all 2n qubits.
3. Again apply the Hadamard operator to each of the first n qubits.
4. Finally measure the first n qubits.
In the previous lecture we had seen that after step 3 the state looks like,
(−1)x·y|f(x)〉
Now, it remains to analyse the outcome of measurement. When we measure we get a string
y ∈ {0, 1}n with probability,
∥∥∥∥∥ 12n∑
(−1)x·y|f(x)〉
Let A denote the image space of the function f i.e., A = {z : ∃x, f(x) = z}. For every x ∈ {0, 1}n,
there exists x′ = x ⊕ s ∈ {0, 1}n such that f(x) = f(x′). Therefore, we have 2n−1 values in the
range of A, i.e., 1/2 × |{0, 1}n|. For every value a ∈ A, let x1(a), x2(a) denote the two strings for
which f(x) = a. As a result of the property of the function f , we must have x2(a) = x1(a)⊕ s.
∥∥∥∥∥ 12n ∑
(−1)x1(a)·y + (−1)x2(a)·y
∥∥∥∥∥ 12n ∑
(−1)x1(a)·y + (−1)(x1(a)⊕s)·y
∥∥∥∥∥ 12n ∑
(−1)x1(a)·y + (−1)x1(a)(−1)s·y
∥∥∥∥∥ 12n ∑
(−1)x1(a)·y (1 + (−1)s·y) |a〉
Note that, 1 + (−1)s·y = 0 when s · y = 1 mod 2 and 1 + (−1)s·y = 2 otherwise. Using this, we
0 if s · y = 1 mod 2
x1(a)·y|a〉
∥∥2 otherwise
0 if s · y = 1 mod 2
|A| otherwise
0 if s · y = 1 mod 2
otherwise.
There are 2n−1 strings y such that its inner product with s is non zero. When we measure at step
4 of the subroutine we get one such string y uniformly at random.
2.2 The Algorithm
We now look at the main algorithm.
1. Run the basic subroutine m = 100n2 times. This gives us y1, y2, …, ym that satisfy yi · s = 0
2. Solve the system of linear equations for s using any standard technique such as Gaussian
Elimination (with arithmetic done modulo 2).
Running the subroutine O(n2) times, with high probability we get n − 1 linearly independent
equations and we can easily solve for s.
3 Quantum Fourier Transform (QFT)
Simply speaking, Fourier transform is a way to break up functions into simpler pieces (called
frequencies). In quantum computing, the quantum Fourier transform is an algorithm to apply linear
transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform.
3.1 Discrete Fourier Transform
Given n numbers: ψ0, ψ1, . . . , ψN−1 ∈ CN . We can interpret ψx as a discrete signal, then
x = 0, . . . , N − 1
The coefficients {ψ̂k} are called the Fourier coefficients of {ψx} and represents the contributions of
each frequency function e
N . Let φk(x) =
N (the frequency functions), then φk(x) can
be interpreted as vectors in CN and {φk(x)} form an orthonormal basis.
Now ψx can be written as ψx =
k=0 ψ̂kφk(x).
3.2 Quantum Fourier Transform
In quantum set up, if we are working in n-qubit space, then the Hilbert space is (C2)⊗n ∼= C2
Let N = 2n, |ψ〉 =
x=0 ψx|x〉. Then |ψ〉 =
k=0 ψ̂k|φk〉, where |φk〉 =
The Fourier transform is simply the change of basis: F : |φk〉 −→ |k〉, which is an unitary operator
ψ̂kF |φk〉 =
ψ̂k|k〉 = |ψ̂〉
The quantum Fourier transform (QFT) is an algorithm that implements this unitary F .
Question: Why is this useful?
If we measure |ψ̂〉, we get outcome |k〉 with probability |ψ̂k|2. However, we cannot really figure
out ψk because quantum states are fragile: when you measure |ψ̂〉, the quantum state collapses and
the information about ψ̂k’s disappears. So why is it useful? QFT is useful because it can perform
Fourier transform on exponentially long vectors (N = 2n- dimensional vector) by implementing
F with only poly(n)(= polylog(N)) number of gates and ancillas. In other words, it trades off
between the ability to directly access the Fourier coefficients of ψ and the ability to compute (in a
sense) the Fourier transform of an exponentially large vector.
Let FN denote the N ×N Fourier transform unitary that does the transformation:
where x, k are n-bit numbers.
= Hadamard gate
→ (reordering columns)→ 1√4
where we define
For F4, in the first matrix we wrote, the columns are associated with the basis states |00〉, |01〉, |10〉, |11〉
(in that order). If we reorder the columns so that the ones corresponding to basis states |00〉 and
|10〉 are on the left, and the columns corresponding to basis states |01〉 and |11〉 are on the right,
then we get the matrices on the right. We’re not changing the linear operator, but just reordering
the columns just so it’s evident that F4 has a nice recursive structure.
This recursive structure holds for FN when N = 2
where for all M , we define
with ω2M = e
Again, this recursive structure appears if we order the columns so that the “even” columns (columns
corresponding to basis states that end in 0) are on the left, and the “odd” columns are on the right.
3.3 QFT Circuit
Assuming that there’s a circuit for unitaries, FN
, the circuit below implements a circuit
3.4 Circuit Analysis
Now we will show that the circuit above actually implements the unitary FN . We prove this by
calculating the action of the circuit on all basis states |x1, . . . , xn〉.
Case 1: xn = 0. Let y = (x1, . . . , xn−1) be the (n − 1)-bit prefix of x. Then the states of the
circuit are as follows:
• Beginning: |x〉 = |x1, . . . , xn〉 = |y, 0〉
• After applying FN/2: (FN/2|y〉)⊗ |0〉
• After the controlled AN/2 (which )doesn’t do anything): (FN/2|y〉)⊗ |0〉.
• After applying H on the last qubit: 1√
FN/2|y〉 ⊗ (|0〉+ |1〉).
• After the shift: 1√
(|0〉+ |1〉)⊗ FN/2|y〉
Why is this correct?
|j1 . . . jn−1〉
|j1 . . . jn−1〉
|j1 . . . jn−1〉
The last equality holds because
n−i−1 = 2y.
Since j is a (n− 1)-bit number, it is interpreted as j = j12n−2 + j22n−3 + . . .+ jn−1. Plugging this
back in, the final state of the circuit is
(|0〉+ |1〉)⊗
|j1 . . . jn−1〉
|0, j1, . . . , jn−1〉+
|1, j1, . . . , jn−1〉
Claim: Fix j = (j1, . . . , jn−1). For i = 0, 1 let ki = (i, j1, . . . , jn−1). Then
obvious because as integers k0 = j
n−2 + . . .+ jn−1
but notice that
2πi(2n−1 + j)x
Then we can rewrite our state as
which is exactly FN |x1 . . . xn〉, as desired.
Case 2: xn = 1. Let y = (x1, . . . , xn−1), and note that x = 2y + 1. Then we have the output of
the circuit being
(|0〉 − |1〉)⊗AN/2FN/2|y〉
Let’s calculate this:
(|0〉 − |1〉)⊗
AN/2|j1 . . . jn−1〉
(|0〉 − |1〉)⊗
2πij(2y + 1)
|j1 . . . jn−1〉
AN/2|j〉 = ω
N = exp(2πij/N)
4 Implementation of AN
Recall the definition of AN :
1 0 0 . . . 0
0 ω2N 0 . . . 0
0 0 0 . . . ωN−12N
, where ω2N = e 2πi2N
For any integer 0 ≤ x < 2n, we can write AN |x〉 = ωx2N |x〉. Since x can also be expressed as the sum of its binary digits, i.e. n−2 + · · ·+ xn, We have the following: n−2+···+xn 2N |x1x2 . . . xn〉 = (ω 2N |x1〉)⊗ (ω 2N |x2〉)⊗ . . . (ω We can also rewrite 2·2n−t = ω2(2n−t) . This matrix adds a phase eiπθ if the state is |1〉, or nothing if the state is |0〉. By substituting a series of Rθ into the previous equation, we get |x1〉)⊗ (R 1 |x2〉)⊗ . . . (R2−(n+1) |xn〉) This leads to the design of our controlled AN/2 unitary (as used in the QFT circuit) as the following: According to the Solovay-Kitaev Theorem, we can implement each conditional-rotation gate up to � accuracy very efficiently in terms of our universal gate set. Question: Unrolling the recursion, how many elementary gates does FN require? Answer: We need O(n) gates for the implementation of AN/2 (which acts on n− 1 qubits), and then we invoke the circuit for FN/2 (which acts on n− 1 qubits as well). There is also O(n) gates needed to implement the cyclic shift of qubits at the end. Thus, if we let T (n) denote the number of gates needed to implement FN , the total number of elementary gates required would be T (n) = O(n) + T (n− 1) = O(n2). 5 Applications of Quantum Fourier Transform 5.1 Phase Estimation Setup: Consider a unitary operation U on n-qubits. Fact: the eigenvalues of U are all on the unit circle: e2πiθ. Without loss of generality, we assume that 0 ≤ θ < 1. Suppose we are given an eigenvector |ψ〉 of U as a quantum state. It has the eigenvalue e2πiθ, but θ is not known to us, and it is what we would like to find out. Suppose we are also given the ability to apply controlled U2 for a range of j’s. In other words, we are able to run the following quantum circuits: U U2 . . . U2 Using this ability, along with the eigenvector |ψ〉, we can obtain a good estimate of θ with high probability. Assumption: Suppose that θ = 0.θ1θ2 . . . θt can be represented using exactly t bits. Equivalently, + · · ·+ θt . Then the circuit below would be able to solve the Phase Estimation problem: |ψ〉 U U2 . . . U2 Illustration of why it works: |φ0〉 : |0〉⊗t ⊗ |ψ〉 |φ1〉 : (H|0〉)⊗t ⊗ |ψ〉 = (|0〉+ |1〉)⊗ (|0〉+ |1〉)⊗ · · · ⊗ (|0〉+ |1〉)︸ ︷︷ ︸ (|0〉+ |1〉)⊗ (|0〉+ |1〉)⊗ · · · ⊗ (|0〉+ ei2πθ|1〉)⊗ |ψ〉 (|0〉+ei2πθ2 |1〉)⊗(|0〉+ei2πθ2 |1〉)⊗· · ·⊗(|0〉+ei2πθ|1〉)⊗|ψ〉 = ei2πθx|x〉|ψ〉 As was mentioned above, θ = θ1 + · · ·+ θt Let θ̃ = 2tθ = 2t( θ1 + · · ·+ θt ) = 2t−1θ1 + 2 t−2θ2 + · · ·+ θt. Then we have Notice that the binary expansion of θ̃ is θ1θ2 . . . θt. Therefore, applying the inverse Quantum Fourier Transform gate QFT−1 to |φt+1〉 will give us |θ̃〉|ψ〉. After this step, we have recovered θ in the output qubits. Question: What happens when θ is not expressable as t bits? Answer: We can show that we have got a good approximation to θ, which requires some more detailed calculations. 5.2 Order Finding In this lecture, we won’t talk about Shor’s algorithm in full, as there’s a fair amount of details. Instead, we will illustrate the core quantum part of Shor’s algorithm, which solves the problem of Order Finding. Factoring problem: Given N > 0, find a nontrivial factor 1 < p < N such that p divides N. Using a few tricks from basic number theory, the Factoring problem can be reduced to the problem Order finding: Given x,N > 0 such that x < N and gcd(x,N) = 1, find the order of x in Z∗N , i.e. the smallest integer r such that xr = 1 mod N . There is no known efficient classical algorithm for this problem. However, there exists an efficient quantum algorithm using Phase Estimation. Important Note: When we say the algorithm is ”efficient”, it means that the algorithm has to run in polynomial time of the input size, i.e. poly(log(N)) = poly(n). Given the input to the Order Finding problem: x,N , we will set up an instance of the Phase Estimation problem. Let r be the order of x, which is what we want to solve. Let 2n−1 < N < xn, which means that N can be represented with n bits. Let U be the n− qubit unitary operator such that for y ∈ 0, 1n, |xy mod N〉 0 ≤ y < N |y〉 otherwise Claim: U is a unitary operator, because y 7→ xy mod N is a one-to-one mapping (since x is invertible). Let the eigenvector be ]|xk mod N〉 where 0 ≤ s < r. ]U |xk mod N〉 ]|xk+1 mod N〉 ]|xk mod N〉 = exp[ Thus, the eigenvalue of |us〉 is exp[2πisr ]. This indicates that we can use Phase Estimation to get s and compute r if: 1. we can implement the controlled gates U2 efficiently; 2. we can get our hands on |us〉. First, we only need O(n) bits to represent s , so we can do Phase Estimation on this for t ≈ n. This means that we will need to have the ability to implement controlled U2 |y〉 = |xy2 This is a very high power of y, but we can do this efficiently using modular exponentiation: the idea is to compute smaller powers of y and then combine them while doing mod N . For example, y8 mod N = (y4 mod N)2 mod N = ((y2 mod N)2 mod N)2 mod N Therefore, we can do this in poly(n) time. Regarding the access to |us〉, we don’t know how to prepare a specific |us〉, but we can easily prepare a superposition of them: |us〉 = |1〉 If we run the Phase Estimation algorithm and get |us〉|s̃/r〉 Here s̃/r is an approximation of s/r. If we measure the second register, we will get θ ≈ s uniformly random s. Question: How do we recover r since we just have the binary expansion of s Answer: We use something called the Continued Fractions algorithm. The point is, we are looking for a fraction with the smallest numerator and denominator that is close to θ. This will with high probability. In the end, this allows us to get r with high probability.