[SOLVED] Quantum computing (cs5100) : problem set 3

1. The total variation distance between two probability distributions P and Q on the same
set A, is defined as dT V (P, Q) = 1/2
P
i∈A |P(i)−Q(i)|. An equivalent alternative way
to define this: dT V (P, Q) is the maximum, over all events E ⊆ A, of |P(E) − Q(E)|.
Hence dT V (P, Q) is small iff all events have roughly the same probability under P and
under Q.
The Euclidean distance between two states |ϕ⟩ =
P
i αi
|i⟩ and |ψ⟩ =
P
i
βi
|i⟩ is defined
as ∥|ϕ⟩ − |ψ⟩∥ =
pP
i
|αi − βi
|
2
. Assume the two states are unit vectors. Suppose the
Euclidean distance is small: ∥|ϕ⟩ − |ψ⟩∥ = ε. If we measure |ϕ⟩ in the computational
basis then the probability distribution over the outcomes is given by the |αi
|
2
, and if
we measure |ψ⟩ then the probabilities are |βi
|
2
. Show that these distributions are close
in total variation distance, i.e., 1/2
P
i
||αi
|
2 − |βi
|
2
| is ≤ ε. (6 marks)
2. Suppose a ∈ R
N is a vector (indexed by ℓ = 0, . . . , N − 1) which is r-periodic in the
following sense: there exists an integer r such that aℓ = 1 whenever ℓ is an integer
multiple of r, and aℓ = 0 otherwise. Compute the Fourier transform FN a of this vector,
i.e., write down a formula for the entries of the vector FN a. Assuming r divides N,
write down a simple closed form for the formula for the entries. Which are the nonzero
entries in the vector FN a, and what is their magnitude? (5 marks)
1
3. (a) The squared Fourier transform, F
2
N , turns out to map computational basis states
to computational basis states. Describe this map, i.e., determine to which basis
state a basis state |k⟩ gets mapped for each k ∈ {0, 1, . . . , N − 1}. (5 marks)
(b) Show that F
4
N = I. What can you conclude about the eigenvalues of FN ?
(4 marks)
4. Consider the task of constructing a quantum circuit to compute |x⟩ 7→ |x + y mod N⟩,
where y is a fixed constant, and 0 ≤ x < N. Show that one efficient way to do this, for
values of y such as 1, is to first perform a quantum Fourier transform, then to apply
single qubit phase shifts, then an inverse Fourier transform. What values of y can be
added easily this way, and how many operations are required? (10 marks)
5. Construct a quantum circuit that computes the Hamming weight of a given string
x ∈ {0, 1}
n
. That is, it performs the following transformation: |x⟩|0⟩ 7→ |x⟩|hw(x)⟩,
where hw(x) is the Hamming weight of x. What is the size of your circuit?
(10 marks)
6. In the lectures we claimed without proof that Grover’s algorithm can be tweaked to
work with probability 1 if we know the number of solutions exactly. For N = 2n
, this
question asks you to provide such an exact algorithm for an x ∈ {0, 1}
n with a unique
solution (so we are promised that there is exactly one i ∈ {0, 1}
n with xi = 1, and our
goal is to find this i).
(a) Define a new 2N-bit string y ∈ {0, 1}
2N
, indexed by (n + 1)-bit strings j =
j1 . . . jnjn+1, by setting
yj =
(
1 if xj1···jn = 1 and jn+1 = 0,
0 otherwise.
Show how you can implement the following (n + 1)-qubit unitary
Sy : |j⟩ 7→ (−1)yj
|j⟩,
using one query to x (of the usual form Ox : |i, b⟩ 7→ |i, b⊕xi⟩) and a few elementary
gates. (5 marks)
(b) Let γ ∈ [0, 2π) and let Uγ =

cos γ − sin γ
sin γ cos γ

be the corresponding rotation
matrix. Let A = H⊗n ⊗ Uγ be an (n + 1)-qubit unitary. What is the probability
(as a function of γ) that measuring the state A|0
n+1⟩ in the computational basis
gives a solution j ∈ {0, 1}
n+1 for y (i.e., such that yj = 1)? (5 marks)
(c) Give a quantum algorithm that finds the unique solution in string x with probability 1 using O(
√
N) queries to x. (10 marks)
2
7. Let N = 2n and x = x0 . . . xN−1 be a sequence of distinct integers such that each
xi can be written exactly using b bits. We can query these in the usual way, i.e.,
we can apply (n + b)-qubit unitary Ox : |i, 0
b
⟩ 7→ |i, xi⟩, as well as its inverse. The
minimum of x is defined as min{xi
| 0 ≤ i ≤ N − 1}. Give a quantum algorithm
that finds (with probability ≥ 2/3) an index acheiving the minimum, using at most
O(
√
N log N) queries to the input. (10 marks)
8. Let x = x0 . . . xN−1, where N = 2n and xi ∈ {0, 1}
n
, be an input that we can query
in the usual way. We are promised that this input is 2-to-1: for each i there is exactly
one other j such that xi = xj
. Such an (i, j)-pair is called a collision. Give a quantum
algorithm that finds a collision (with probability ≥ 2/3) using O(N1/3
) queries.
(10 marks)
9. Consider an undirected graph G = (V, E), where V = {1, . . . , n}. Let M be the
adjacency matrix of G. Suppose we are given input graph G in the form of a unitary
that allows us to query whether an edge (i, j) is present in G or not:
OM : |i, j, b⟩ 7→ |i, j, b ⊕ Mij ⟩.
(a) Assume G is connected. Suppose we have a set A of edges which we already
know to be in the graph (so A ⊆ E; you can think of A as given classically, you
don’t have to query it). Let GA = (V, A) be the subgraph induced by only these
edges , and suppose GA is not connected, so it consists of c > 1 connected components. Call an edge (i, j) ∈ E “good” if it connects two of these components.
Give a quantum algorithm that finds a good edge with an expected number of
O(n/√
c − 1) queries to M. (10 marks)
(b) Give a quantum algorithm that uses at most O(n
3/2
) queries to M and decides
(with success probability ≥ 2/3) whether G is connected or not. (10 marks)
10. Consider a 2-bit input x = x0x1 with phase-oracle Ox,± : |i⟩ 7→ (−1)xi
|i⟩. Write out
the final state of the following 1-query quantum algorithm: HOx,±H|0⟩. Give a degree
2-polynomial p(x0, x1) that equals the probability that this algorithm outputs 1 on this
input x. (5 marks)
11. Let f : {0, 1}
N → {0, 1} be the N-bit Parity function, which is 1 iff its input x ∈ {0, 1}
N
has odd Hamming weight.
(a) Give a quantum algorithm that computes Parity with success probability 1 on
every input x, using N/2 queries (assume N is an even number). (5 marks)
(b) Show that this is optimal, even for quantum algorithms that have error probability
≤ 1/3 on every input. (10 marks)
12. Suppose we have a T-query quantum algorithm that computes the N-bit OR function
with success probability 1 on all inputs x ∈ {0, 1}
N
. Show that T ≥ N. (10 marks)
3
13. For a partial function f : {0, 1}
N → {0, 1, ∗}, let Y ⊆ f
−1
(1) and Z ⊆ f
−1
(0). Let
R ⊆ Y × Z be a set of pairs and for each coordinate j ∈ [N], define Rj = {(y, z) ∈ R |
yj ̸= zj}. Now suppose that
• for each y ∈ Y , there are at least m1 strings z ∈ Z with (y, z) ∈ R;
• for each z ∈ Z, there are at least m0 strings y ∈ Y with (y, z) ∈ R;
• for each y ∈ Y and j ∈ [N], there are at most ℓ1 strings z ∈ Z with (y, z) ∈ Rj
;
• for each z ∈ Z and j ∈ [N], there are at most ℓ0 strings y ∈ Y with (y, z) ∈ Rj
.
Then show that Q(f) ≥ Ω(p
m0m1/ℓ0ℓ1), where Q(f) denotes the quantum query
complexity of computing f with success probability at least 2/3. (10 marks)
14. Show a quantum query lower bound of Ω(p
N/k) for computing the following partial
function with error probability ≤ 1/3: output 1 if the input string x ∈ {0, 1}
N
has at
least k 1’s; output 0 if x = 0N . Be explicit about what relations R, Rj you are using,
and about the values of the parameters m0, m1, ℓ0, ℓ1. (4 marks)
15. Let k be an odd natural number and N = k
2
. Define f : {0, 1}
N → {0, 1} such that
f(x) = Majk
(ORk(x
(1)), . . . , ORk(x
(k)
)) where x = x
(1) . . . x(k) with each x
(i) ∈ {0, 1}
k
,
Majk
is the k-bit majority function and ORk is the k-bit OR function. Show that
Q(f) = Ω(N3/4
). Be explicit about what relations R, Rj you are using, and about the
values of the parameters m0, m1, ℓ0, ℓ1. (6 marks)