QUANTUM INFORMATION AND COMPUTATION

EXERCISE SHEET 2
Nilanjana Datta n.datta@damtp.cam.ac.uk (Lent 2023-2024)

(1) (Generalised Pauli operations for dimension d)

For a d-dimensional quantum system (a so-called qudit) with orthonormal basis {|j→ : j ↑ Zd },
introduce the operations X and Z defined by their actions on basis states:
X |j→ = |j + 1 mod d→ Z |j→ = wj |j→
where w = e2ωi/d . Note that X and Z are unitary (why?) but not Hermitian (unless d = 2).

(a) Show ZX = wXZ, X d = Z d = I and express (X a )† and (Z b )† in terms of X and Z for

a, b ↑ Zd .

(b) Show that Tr (X a Z b ) = 0 for all (a, b) ↑ Zd ↓ Zd except (a, b) = (0, 0).
!
(c) Consider the 2-qudit state |!→ = →1d d↑1 i=0 |i→ |i→. Show that for any operator V on one
qudit, we have Tr V = d ↔!| V ↗ I |!→. (Here Tr V is the trace of the matrix of V with respect
to the orthonormal qudit basis of |i→’s, and this trace is in fact independent of choice of qudit
orthonormal basis).

(d) Using the above, invent a quantum dense coding scheme for d dimensional systems (gener-
alising the basic case of d = 2).
(Remark: the same formalism can be used to also give a quantum teleportation scheme for
qudits too.)

(e) If d = 2n (i.e. the qudit is isomorphic to a composite system n qubits) how does the scheme
in (d) compare to the use of the basic qubit dense coding scheme (as in lectures) applied
separately on each on n qubits?

(2) (Teleporting entanglement)

(a) Alice holds an entangled state |ω→A→ A of two qubits A↓ A and she teleports qubit A to Bob
i.e. she just applies the standard teleportation protocol to qubit A. Show that the teleportation
preserves entanglement i.e. that at the end, Bob’s qubit B will be entangled with A↓ just as A
was, so that Alice and Bob will jointly hold the state |ω→A→ B .

(b) (entanglement swapping, aka quantum repeater)

Alice (A) and Bob (B) are separated by distance 2d and wish to share a |ε+ → Bell state. However
because of environmental e”ects (maybe air pollution), flying qubits (maybe photonic polari-
sation qubits) retain their entanglement properties only up to a distance d so A cannot just
locally prepare |ε+ → and send one of its qubits over to B. Their friend Charlie (C) is positioned
midway between A and B (i.e. distance d away from each) and has shared a |ε+ → state with
each of them. Show how C can then grant A and B their wish by using only local operations
at C and classical communication to other parties.
Remark: thus if we can directly set up entanglement only over a (possibly small) bounded
distance, then by repeating the above process (hence “quantum repeater”) we establish entan-
glement over arbitrarily large distances, and entangle particles that have never been near to
each other (hence “entanglement swapping”).

(3) (Intercept-resend attack in BB84 QKD)

A general orthonormal qubit basis can be expressed as
B(a, b) = { |ϑ0 → = a |0→ + b |1→ , |ϑ1 → = ↘b↔ |0→ + a↔ |1→ }
where a, b ↑, |a|2 + |b|2 = 1 and ↔ denotes complex conjugation.
Alice and Bob are distantly separated in space. They can communicate classically and are also
connected by a noiseless quantum channel. They perform BB84 quantum key distribution.

1
Suppose Eve, hiding in between, attempts to eavesdrop by following the intercept-resend strat-
egy, measuring each passing qubit in the basis B(a, b) and sending on the post-measurement
state to Bob. Eve interprets her measurement outcome |ϑi → as bit value i.

(a) Calculate the average bit error rate, as a function of a and b, that Eve’s action will cause
in Alice and Bob’s strings. Calculate also the probability that Eve learns Alice’s encoded bit
correctly.

(b) Show that the minimum bit error rate can be achieved by using real values of a and b i.e.
if Eve is trying not to be detected then use of complex a and b does not help.

(c) Let a = cos ϖ and b = sin ϖ with 0 ≃ ϖ ≃ ϱ/2. For what value of ϖ does Eve cause the
least disturbance i.e. minimum bit error rate? For what value of ϖ does Eve gain the most
information i.e. maximum probability of learning Alice’s bit?

(4) (Positive operators, more on state distinguishability)

(a) An operator P is called positive if P is Hermitian and for all |ς→, ↔ς| P |ς→ is real with
↔ς| P |ς→ ⇐ 0. (Remark: actually ↔ς| P |ς→ being real for all |ς→ already implies that P is
Hermitian, as you might like to show.)
(i) Show that any projection operator is positive.
(ii) Show that if P is positive and # is a projection then #P # is positive.
(iii) Show that if P is positive then ↔ς| P |ς→ ≃ Tr P for any normalised |ς→. (It may help to
consider the eigenvalues and eigenbasis of P .)

(b) Alice sends Bob one of N equally likely states |ωk → for k = 1, . . . , N , each being a state
in d dimensions, representing the message k. On receiving the state Bob attempts to read
Alice’s message by first adjoining an ancilla |A→ to the received state and then performing a
measurement on the total state, with projectors #k , k = 1, . . . , N respectively for concluding
that the message was k.
(i) Write down an expression for the probability PS that Bob will correctly identify Alice’s
intended message k.
(ii) Show that for any measurement we have PS ≃ d/N .
(Hint: results from (a) may be useful here, including use of (a)(ii) with # there being projection
onto the span of the N states |ωk → |A→ in the enlarged space with the ancilla. Show that this
subspace has dimension at most d, so the projection has trace at most d.)

Thus we see that d-dimensional states can never be used to reliably send more than d mes-
sages, and if we attempt to use larger N ’s then the success probability will be correspondingly
necessarily worse. Is the bound d/N on PS here tight for a given set of N states |ωk → in d
dimensions? Give a reason for your answer.

(5) (Quantum money) (Optional question, do if time permits)

(S. Wiesner’s unforgeable quantum banknotes)
A quantum banknote has printed on it a serial number which is an N -bit string, visible to all.
It also has N qubits embedded in it (assumed to be perfectly stable, perhaps tastefully adorning
a holographic image of the reigning monarch). For each such banknote, the bank also sets up
a further N -bit string called the basis string and keeps this string secret. When the note is
manufactured, the serial number on it is encoded into the N qubits using the standard BB84
encoding scheme for the serial number bits 0 and 1 (viz. 0 encoded as |0→ or |+→, and 1 encoded
as |1→ or |↘→ for the corresponding basis bit string bit being 0 or 1 respectively).

Now when the note is returned to the bank after financial transaction, the bank tests the note
for authenticity as follows: the bank teller measures each of the N qubits in the basis given by
the corresponding basis string bit (known only to the bank) and accepts the banknote only if
all measurements give the correct result viz. the corresponding bit values of the serial number.

2
A counterfeiter wants to make fake notes that will pass this test. He/she clearly can read the
serial number’s bits but does not know the qubit encoding bases.

(a) Show that a genuine banknote will always pass the test and remain genuine after the test.

(b) Consider the k th qubit on the note. What is the maximum probability that the counterfeiter
can determine the k th basis string bit by a measurement on the qubit?

(c) The counterfeiter tries to identify the k th basis string bit as in (b) and then uses the result
to correspondingly set the state of the k th qubit on a fake banknote (printed with the same
serial number string). If subsequently inspected by the bank, what is the probability that the
k th qubit will pass the inspection?
Now suppose the note has N = 100 qubits on it. What is the probability that the fake note
(with each qubit set by the counterfeiter, as above) will be accepted as genuine by the bank?

(6) (Gate teleportation)

(a) Suppose we perform the standard teleportation protocol up to and including Alice’s mea-
surement, but instead of using |ε+ →AB we use the state |εU →AB = IA ↗ UB |ε+ →AB in its place.
Here U is any one-qubit unitary gate.
Show that each outcome ij of Alice’s measurement will again occur with probability 1/4 but
now the corresponding states of Bob’s qubit will be U Pij |ω→ where Pij |ω→ are the corresponding
states in standard teleportation.
Hence upon subsequently receiving the information of ij, if Bob applies the correction operators
Rij = U Pij† U † he will obtain U |ω→ in every case.

(b) In some cases the correction operators are simple. For U = H calculate the corresponding
operators Rij .

(c) Suppose we have a plentiful supply of |ε+ → states and can easily reliably perform Bell
measurements as well as Pauli gates on any qubits. We also have an H-gate machine but it
functions correctly only half the time and it also signals whether it has failed or succeeded.
We have one copy of a precious qubit state |ω→ and we want to make H |ω→. Show how this
may be achieved with any high success probability 1 ↘ φ (for any φ > 0).

(7) (B92 quantum key distribution)

We’ll describe a quantum key distribution scheme (devised by C. Bennett in 1992) that uses
only two non-orthogonal qubit states viz. |0→ and |+→, instead of the four states used in BB84.

Alice first generates a uniformly random N bit string x = x1 x2 . . . xN (a subset of which will
provide the shared secret key). She encodes these bits into qubit states using |0→ for bit value
0 and |+→ for bit value 1. Then she sends them over to Bob (in order). For each received
qubit, Bob randomly (with probability half) chooses to measure it in the Z eigenbasis or the
X eigenbasis.

(a) Show that for some of Bob’s possible measurement outcomes he can correctly learn Alice’s
corresponding bit and know for sure that he has learnt it. For what fraction µ on average, of
Alice’s bits, will this happen (assuming a perfectly noiseless quantum channel and no eaves-
dropping)?

Next in the B92 protocol, Bob (publicly) announces to Alice the positions (i.e. subscripts
1 ≃ i ≃ N ) for which he has learnt her bit (but does not disclose the bit values themselves!),
and they both retain only these bits, discarding all the others. In the ideal situation of a
noiseless channel and no eavesdropping, the resulting string (of average length µN ) gives the
desired shared secret key.

3
(b) To get an idea of the e”ects of attempted eavesdropping in the B92 protocol, we’ll look only
at a simple example of an intercept-resend attack by Eve, while assuming the qubit channel is
noiseless. Suppose that Eve measures each passing qubit in the Breidbart basis and sends the
post-measurement state on to Bob.
Consider only those qubits for which Alice sent |0→. (A similar analysis will apply for |+→).
Show that the fraction µ of these for which Bob will think that he has learnt Alice’s bit, is the
same as the value of µ in (a). Show that for these bits, the bit error rate will be 1/2 i.e. Bob
will conclude the wrong value of Alice’s bit for half of these on average.

(8) (Approximate cloning) (Optional question, do if time permits)

Let |ω0 → = cos 2ε |0→ + sin 2ε |1→ and |ω0 → = cos 2ε |0→ ↘ sin 2ε |1→ be two qubit states (for a fixed
chosen value of 0 < ϖ < ϱ/2).
We know that these states cannot be perfectly cloned so consider an approximate cloning
machine Mε of the following kind:
on input |ω0 → |0→ the output is a 2-qubit state |c00 →; and
on input |ω1 → |0→ the output is a 2-qubit state |c11 →.
Here |cjj → (generally possibly entangled) is our approximate cloning result for |ωj → i.e. our
approximation for |ωj → |ωj →. The cloning fidelity for |ωj → is defined to be Fcl (j) = | ↔ωj | ↔ωj | cjj →|2
(so cloning fidelity 1 would mean perfect cloning). The cloning machine Mε is required to have
the following properties:
(P1): it is a unitary operation on the two qubits;
(P2): it has equal cloning fidelity for both |ω0 → and |ω1 →;
(P3): the states |c00 → and |c11 → lie in the two dimensional span of |ω0 → |ω0 → and |ω1 → |ω1 → and
furthermore, in the standard qubit basis, they both have real amplitudes.

(a) Subject to the above constraints, find the optimal achievable value of Fcl (j), and show that
if ϖ = ϱ/4 then the optimal cloning fidelity is cos2 (ϱ/24).

(b) A more general kind of approximate cloning machine allows intermediate" # measurements
" (m)
and probabilistic choices too, resulting in a variety of possible outputs "cjj (for each input
|ωj →), occurring with known probabilities pm,j determined by the specification of the process.
! (m)
The cloning fidelity is then defined to be the pm,j -average Fcl (j) = m pm,j | ↔ωj | ↔ωj | cjj →|2 .
Use the theorem on optimal discrimination of two non-orthogonal states as given in lectures,
to design an approximate cloning machine Nε of this more general sort.

For the case of ϖ = ϱ/4, identify explicitly the optimal qubit measurement for distinguishing
these states. Then compare the cloning fidelity of Nω/4 with that of Mω/4 in (a), to see that
cloning by first trying to classically identify the state (and then producing two copies of the
result) is generally not as good as a process that bypasses attempted identification, and stays
“intrinsically quantum” all the way.

[Remark: in (a) I’d expect(?) the value of Fcl (j) there to remain optimal for any unitary cloner
having equal cloning fidelities for the two states (i.e. if the last condition (P3) is lifted) but I
guess the argument would be more complicated.]

4
 QUANTUM INFORMATION AND COMPUTATION
EXERCISE SHEET 3
Nilanjana Datta n.datta@damtp.cam.ac.uk (Lent 2023-2024)

(1) (Bernstein-Vazirani problem)

For n-bit strings x = x1 . . . xn and a = a1 . . . an in Bn we have the sum x → a which is an n-bit
string, and now introduce the 1-bit “dot product” x · a = x1 a1 → x2 a2 → . . . → xn an .
For any fixed n-bit string a = a1 . . . an consider the function fa : Bn ↑ B1 given by

fa (x1 , . . . , xn ) = x · a (1)

(a) Show that for any a ↓= 00 . . . 0, fa is a balanced function i.e. fa has value 0 (respectively 1)
on exactly half of its inputs x.
(b) Given a classical black box that computes fa describe a classical deterministic algorithm
that will identify the string a = a1 . . . an on which fa is based. Show that any such black box
classical algorithm must have query complexity at least n.

Now for any n let Hn = H ↔ . . . ↔ H be the application of H to each qubit of a row of n qubits.
Show that (for x ↗ B1 and a ↗ Bn )
1
1 ! 1 !
H |x↘ = ≃ (⇐1)xy |y↘ Hn |a↘ = ≃ (⇐1)a·y |y↘
2 y=0 2n y→B
n

(c) (the Bernstein–Vazirani problem/algorithm)

For each a consider the function fa which is a balanced function if a ↓= 00 . . . 0 (as shown
above). Show that the Deutsch-Jozsa algorithm will perfectly distinguish and identify the
2n ⇐ 1 balanced functions fa (for a ↓= 00 . . . 0) with only one query to the function (quantum
oracle for f ). Indeed, show that the n bit output of the final measurements of the algorithm
gives the string a with certainty for these special balanced functions.

(2) (Classical complexity – integer exponentiation mod N )

Exponentiation of integers mod N is a basic arithmetic task (it’ll be used for example in Shor’s
algorithm) and it is important to know that it can be done in poly(n) time where n = log N is
the number of digits for integers in ZN .
To compute say 3k mod N (for k ↗ ZN and N > 3) we could multiply 3 together k times. Show
that this is not a poly(n) time computation.
Devise an algorithm that does run in poly(n) time. (Hint: consider repeated squaring).
You may assume that multiplication of integers in ZN may be done in O(n2 ) time.
Generalise to a poly time computation of k1k2 mod N for k1 , k2 ↗ ZN showing that it may be
computed in O(n3 ) time.

(3) (Simon’s algorithm)

Simon’s decision problem is the following:
Input: an oracle for a function f : Bn ↑ Bn ,
Promise: f is either (a) a one-to-one function or (b) a two-to-one function of the following
special form – there is an ω ↗ Bn such that f (x) = f (y) i! y = x → ω (i.e. ω is the period of f
when its domain is viewed as being the group (Z2 )n ).
Problem: determine which of (a) or (b) applies (with any prescribed success probability 1 ⇐ ε
for any ε > 0).

It can be argued (e.g. as indicated in lecture notes) that for classical computation, this requires
at least O(2n/4 ) queries to the oracle. In this question we will develop a quantum algorithm that
that solves the problem with quantum query complexity only O(n). Even more, the algorithm
will determine the period ω if (b) holds. Thus (unlike the balanced vs. constant problem) we’ll

1
have a provable exponential separation between classical and quantum query complexities, even
in the presence of bounded error.

To begin, consider 2n qubits with the first (resp. last) n comprising the input (resp. output)
register for a quantum oracle Uf computing f i.e. Uf |x↘ |y↘ = |x↘ |y → f (x)↘ for n-bit strings x
and y.
(a) With all qubits starting in state |0↘ apply H to each qubit of the input register, query
Uf and then measure the output register (all measurements being in the computational basis).
Write down the generic form of the n-qubit state |ϑ↘ of the input register, obtained after the
measurement. Suppose we then measure |ϑ↘. Would the result provide any information about
the period ω?

(b) Having obtained |ϑ↘ as in (a), apply H to each qubit to obtain a state denoted |ϖ↘. Show
that if we measure |ϖ↘ then the n-bit outcome is a uniformly random n-bit string y satisfying
ω · y = 0 (so any such y is obtained with probability 1/2n↑1 ).

Now we can run this algorithm repeatedly, each time independently obtaining another string y
satisfying ω · y = 0. Recall that Bn = (Z2 )n is a vector space over the field Z2 . If y1 , . . . , ys are s
linearly independent vectors (bit strings) then their linear span contains 2s of the 2n vectors in
Bn . Furthermore to solve systems of linear equations over Bn we can use the standard Gaussian
elimination method (calculating with the algebra of the field Z2 ), which runs in poly(n) time.

(c) Show that if (n⇐1) bit strings y are chosen uniformly randomly and independently satisfying
y · ω = 0 then they will be linearly independent (and not include the all-zero string 00 . . . 0)
with probability
"#
n↑1
2k↑1
$
1"
n↑2 #
2k↑1
$
1 ⇐ n↑1 = 1 ⇐ n↑1 .
2 2 2
k=1 k=1

Show that this is at least 1/4. (It may be helpful here to recall that for a and b in [0, 1] we have
(1 ⇐ a)(1 ⇐ b) ⇒ 1 ⇐ (a + b)).

(d) Show how the above may be used to solve Simon’s problem with O(n) quantum query
complexity (for any desired success probability 0 < 1 ⇐ ε < 1).

(4) (Another query complexity problem with quantum advantage)

Let Bn denote the set of all n-bit strings. The Hamming distance between two n-bit strings
a = a1 . . . an and x = x1 . . . xn is the number of places j where aj and xj di!er. Let Ha : Bn ↑
B2 be the function

Ha (x) = (Hamming distance between a and x) mod 4.

Here we are identifying B2 with Z4 via the usual binary representations of 0,1,2,3. (For example
if a = 101110000 and x = 001001110 then Ha (x) = 6 mod 4 = 2.)

Now consider the promise problem HAM-mod4:

Input: a black box for a function f : Bn ↑ B2 .
Promise: f is Ha for some n-bit string a.
Problem: determine a with certainty.

In the quantum context the black box is a unitary operation on (n + 2) qubits given by

Uf |x↘ |y↘ = |x↘ |y + f (x)↘ .

Here the x register is n qubits and in the y register we’ll write the basis as {|0↘ , |1↘ , |2↘ , |3↘}
with addition in the expression y + f (x) being addition in Z4 .

(a) Show that classically the query complexity of HAM-mod4 is at least n/2.

2
We will now show that the problem can be solved quantumly with just one query. Let M be
the matrix # $
1 1 i
M= ≃ .
2 i 1
Note that M is unitary. Also introduce the 1-bit functions h0 , h1 : B1 ↑ B1 where

h0 (0) = 0 h0 (1) = 1 and h1 (0) = 1 h1 (1) = 0

i.e. ha is just Ha for 1-bit string a.

(b) For a1 = 0, 1 show that

1
1 ! ha (x1 )
M |a1 ↘ = ≃ i 1 |x1 ↘ .
2 x1 =0

(c) Returning to the case of n-bit strings a = a1 . . . an and x = x1 . . . xn show that

Ha (x) = ha1 (x1 ) + . . . + han (xn ) mod 4.

Hence describe how the state

1 ! Ha (x)
|Ha ↘ = ≃ i |x↘
2n x→B
n

may be manufactured from |a↘.

(d) Let S denote the 2-qubit “shift” operation

S |y↘ = |y + 1 mod 4↘ y ↗ Z4 .

Let QF T denote the quantum Fourier transform mod 4. Calculate the state |ϱ3 ↘ = QF T |3↘
and show that S |ϱ3 ↘ = i |ϱ3 ↘.

(e) Use the above results to show how HAM-mod4 may be solved with certainty using just
one query to the oracle Uf and poly(n) total time complexity. (It may be helpful to note that
UHa |x↘ |y↘ = |x↘ S Ha (x) |y↘.)
Draw a circuit diagram for your quantum algorithm.

[ Optional afterthought: note that this algorithm is structurally “the same as” the Bernstein-
Vazirani (BV) algorithm and it is interesting to compare the corresponding ingredients and
their functionality. What are the BV ingredients corresponding to the use of QF T , |ϱ3 ↘, M ,
ha and Ha here? ]

(5) (Approximately universal quantum gate sets)

(a) For unitary gates U1 , V1 , U2 , V2 show that:
if ||U1 ⇐ V1 || ⇑ ε1 and ||U2 ⇐ V2 || ⇑ ε2 (i.e. the V ’s are “approximate versions” of the U ’s)
then ||U2 U1 ⇐ V2 V1 || ⇑ ε1 + ε2 i.e. “errors” in using approximate versions at most add when
gates are composed.
(Recall that here ||U ⇐ V || is defined as the maximum length of the vector (U ⇐ V ) |ϱ↘ over all
choices of normalised |ϱ↘’s.)

Deduce that if ||Ui ⇐ Vi || ⇑ ε for i = 1, . . . , n then ||Un . . . U1 ⇐ Vn . . . V1 || ⇑ nε.

(b) For the purposes of this question you may assume the following: if a gate set is approx-
imately universal then any one- or two-qubit gate U may be approximated to within ε by a
circuit of gates from of size poly(1/ε). (Actually by the Solovay-Kitaev theorem, mentioned in
lectures, a stronger result is true viz. that a circuit of much smaller size poly(log(1/ε)) su”ces,
but we will not need that improvement here.)

3
Let G and H be two approximately universal sets of gates comprising one- and two-qubit gates
only. Suppose that the decision problem D is in the complexity class BQP with all quantum
gates in the circuits being from the set G. Show that D is then also in the class BQP defined
using quantum gates from the set H i.e. the definition of BQP is independent of the choice of
approximately universal set of gates used.

(6) (Period finding algorithm)

Consider the function f (x) = 5x mod 39 on the domain x ↗ Z2m with say m = 11 (as in fact
would occur in Shor’s algorithm for factoring 39).

(a) Show that f is periodic and determine its period r (hmm.. reach for a calculator.)

(b) Suppose we construct the equal superposition state |f ↘ of (x, f (x)) values over the domain
Z2m , measure the second register, perform the quantum Fourier transform mod 2m on the post-
measurement state of the first register, and finally measure it. What is the probability for each
possible outcome 0 ⇑ c < 2m in the latter measurement? (Note: this should require very little
calculation!) What is the probability that we successfully determine r from this measurement
result, using the standard process of the quantum period finding algorithm?

(7) (Entanglement is necessary for advantage in quantum computation)

Consider a quantum computation, given as a poly-sized circuit family {C1 , C2 , . . . , Cn , . . .}
where each Cn comprises gates from a universal set G comprising one- and two-qubit gates, and
suppose that this computation solves a decision problem A in BQP.
Suppose further that for any input x ↗ Bn to the circuit Cn (for any n), at every stage of the
process, the quantum state is unentangled i.e. it is a product state of all the qubits involved.
Show that then the problem A is also in BPP i.e. if no entanglement is ever present in a quan-
tum computation, then it cannot provide any computational benefit over classical computation
(up to at most a polynomial overhead in time). (Hint: consider calculating the progress of the
quantum process itself on a classical computer).

4
 QUANTUM INFORMATION AND COMPUTATION
EXERCISE SHEET 4
Nilanjana Datta n.datta@damtp.cam.ac.uk (Lent 2023-2024)

Note: questions 6(b), 7(c) and 8 are optional and can be left till last or omitted.

(1) (Rotation in Grover’s algorithm) !

For the plane P(x0 ) spanned by |x0 → and |ω0 → = →1N x↑Bn |x→ set up an orthonormal basis in
the plane. Then using the basis, show algebraically (rather than geometrically as in lectures)
that the Grover iteration operator Q is a rotation in the plane and derive the angle of rotation.

(2) (Grover’s algorithm with an arbitrary starting state)

Consider Grover’s algorithm for a unique good item x0 in a search space of size N = 2n .
Suppose that instead of the usual uniform superposition state |ω0 →, we ↑ start with any state
|ε0 → of n qubits and conduct the algorithm just as before i.e. apply ω4 N iterations of Q and
measure.
With |ε0 → = |ω0 → the final measurement gives x0 with probability 1 up to terms of order
1/N . If we instead begin with some other starting state |ε0 →, describe geometrically how |ε0 →
evolves in the course of the computation. Give an expression (up to terms of order 1/N ) for
the probability of obtaining x0 in the final measurement. Show that this may generally be
improved by changing the number of Grover iterations.

(3) (An algebraic interpretation of Grover’s algorithm) !

(a) Consider the operator ↓I|ε0 ↓ = 2 |ω0 → ↔ω0 | ↓ I with |ω0 → = →1 |x→ and N = 2n .
N x↑Bn
Show that
2 "
↓I|ε0 ↓ = |x→ ↔y| ↓ I.
N
all x,y

!
(b) Let! |ϑ→ = x ax |x→ be any n-qubit state. The average amplitude a is defined to be
a = (
! ↔ x x a )/N . The operation R of “inversion in the average” is defined as follows: R |ϑ→ =
↔
x ax |x→ where ax = ax ↓ 2(ax ↓ a) i.e. the value of each amplitude is inverted about the
average. Pictorially:

a ↓a a ↓a
! ! !
"x ! "x !
!
a↔x a ax

Using the formula in (a) show that ↓I|ε0 ↓ |ϑ→ = R |ϑ→ .

(c) Hence Grover’s algorithm may be described as follows: start with state |ω0 →; then flip the
sign of the x0 amplitude; then do R, an inversion of all amplitudes in the average; then iterate
the last two steps alternately. We can represent states (with real amplitudes) pictorially as
a graph of the amplitudes: the x axis has the labels x and each amplitude is a (positive or
negative) vertical bar. In terms of this pictorial representation, starting with |ω0 →, carry out
one or two iterations of the “flip x0 and then do R” operation to see how the initial amplitude
distribution, uniform over all x, begins to become concentrated at x0 .

(d) Consider the definite case of N = 4 (so x ↗ {0, 1, 2, 3}) and take x0 = 3 say. (In lectures
we saw that for this case of “1 in 4”, one Grover iteration serves to find x0 with certainty i.e.
rotating |ω0 → exactly onto |x0 →). Draw the pictorial graph representation of |ω0 → and carry out
one Grover iteration as a flip followed by inversion in the average. Show that as a result, the
amplitude becomes exactly zero at x ↘= x0 and 1 at x = x0 .

1
(4) (Shor’s quantum algorithm for discrete logarithms)
For any prime p consider the set Z↗p = {1, 2, . . . , p ↓ 1} ≃ Zp of nonzero integers modulo p,
with the operation of multiplication mod p. A generator for Z↗p is an element g whose powers
generate all of Z↗p i.e. for all x ↗ Z↗p there is y ↗ Zp↘1 with x = g y mod p. y is called the
discrete logarithm of x (to base g). You may assume that Z↗p always has a generator g and that
it satisfies g p↘1 = 1 mod p.

Suppose we are given a generator g and element x ↗ Zp , and we wish to compute its discrete
logarithm y.

(a) Consider the function f : Zp↘1 ⇐ Zp↘1 ⇒ Z↗p given by

f (a, b) = g a x↘b mod p.

For each fixed c ↗ Z↗p , show that there is a corresponding fixed k ↗ Zp↘1 such that

f (a, b) = c i! a = by + k mod (p ↓ 1).

(b) Suppose we have constructed the state

1 "
|ϖ→ = |a→ |b→ |f (a, b)→
(p ↓ 1)
a,b↑Zp→1

(in Hp↘1 ⇑ Hp↘1 ⇑ Hp , where Hn denotes a state space of dimension n, with orthonormal
basis {|k→ : k ↗ Zn }) and we measure the third register obtaining a result c0 . Find the post-
measurement state of the first two registers.

(c) If we then apply the quantum Fourier transform mod (p ↓ 1) to each of these two registers
and measure both registers, which output pairs (c1 , c2 ) ↗ Zp↘1 ⇐ Zp↘1 can be obtained with
non-zero probability?
Can y be determined from any such pair?
Hence outline a quantum algorithm for computing discrete logarithms, that runs in time
O(poly(log p)) for large p, and succeeds with probability 1 ↓ ϱ for any chosen constant ϱ > 0.
You may assume that f and QF Tp↘1 may be implemented in O(poly(log p)) time.

(5) (Shor’s factoring algorithm, continued fractions)

This question relates closely to §11.1 - §11.3 of online lecture notes.
Suppose we wish to factor N = 21 using Shor’s algorithm and we have chosen a = 2 so we aim
to determine the period of f (x) = 2x mod 21. We proceed through the quantum algorithm and
finally measure the x register. Suppose we obtain measurement result c = 427.

(a) What is the number m of qubits that is used for the x register?

(b) Use the continued fraction method to find a fraction j/r with denominator less than 21,
that is within 1/2m+1 of the ratio c/2m .

(c) We hope that the denominator of j/r (when the fraction is cancelled down to lowest terms)
is the period of f (x). Check to see that it is indeed the period in this example.
Use your value of r to find factors of 21 (following the method used in Shor’s algorithm).

2
(6) (Grover search with multiple good items; application to collision finding)
(a) Write N = 2n and let f : Bn ⇒ B1 be a function taking value 1 exactly K times, with
f (x) = 1 i! x ↗ G = {x1 , . . . , xK }. The Grover operator is defined by Q = ↓Hn I0 Hn IG where
Hn = H ⇑ . . . ⇑ H is the Hadamard operation on each of n qubits, and for all x ↗ Bn , I0 and
IG are defined by
# #
↓ |x→ if x = 0 . . . 0 ↓ |x→ if x ↗ G
I0 |x→ = IG |x→ =
|x→ if x ↘= 0 . . . 0 |x→ if x ↗/ G.
! !
Write |ω0 → = →1N x↑Bn |x→ and introduce |ωG → = →1K x↑G |x→. Derive a geometrical inter-
pretation of the action of Q in the two-dimensional subspace of n qubits spanned by |ω0 → and
|ωG →. Using this interpretation, show that if IG is given as a black $box then an x in G may
be obtained with high probability (better than a half say) with O( N/K) uses of IG , if N is
large, and K is small compared to N .

(b) (optional) Let g : Bn ⇒ Bn be a 2-to-1 function i.e. for every y in the range of g there are
precisely two strings x ↗ Bn with g(x) = y. A collision is a pair of strings x1 , x2 ↗ Bn with
g(x1 ) = g(x2 ). The standard quantum oracle Ug for g is the unitary operation on 2n qubits
defined by
Ug |x→ |y→ = |x→ |y ⇓ g(x)→ x, y ↗ Bn
where ⇓ denotes bitwise addition of n-bit strings.

Suppose that we are given Ug as a black box operation. Using the result of (a), or otherwise,
show that a collision may be found with high probability (better than a half say) with O(N 1/3 )
uses of Ug .
Hint: start by partitioning the domain of g into sets A and B of sizes N 1/3 and (N ↓ N 1/3 )
and listing all the values of g(x) for x ↗ A. We might find a collision there, but if we’re not so
lucky, what should we do next with B?
↑
Remark: the classical query complexity for collision finding is O( N ). The O(N 1/3 ) upper
bound on its quantum query complexity established in this question can also be shown to be
optimal.

(7) (QFT, shift invariant states)

(a) For the state space HN with orthonormal basis {|k→ : k ↗ ZN } consider the (unitary)
shift operator S defined by S |k→ = |k + 1 mod N → for all k ↗ ZN . Also introduce the states
|ςk → = QF TN |k→, called shift invariant states.

Show that the |ςk →’s are eigenstates of S and determine the corresponding eigenvalues.

Let |ω→ be any state in HN . Show (using the foregoing) that if S m |ω→ (for any m) is measured
relative to the shift invariant basis then the output probabilities are independent of the amount
of shift m. (This provides an alternative derivation of the e”cacy of QF T in the quantum
period finding algorithm, as presented in lectures).

(b) For any two positive integers x and N with x < N , and let Ux be the operator on HN
defined by Ux |y→ = |xy mod N → for all y ↗ ZN i.e. Ux is the shift operator for the multiplicative
(rather than additive) action of x on ZN .

(i) Show that Ux is unitary i! x and N are coprime.

Assume now that x and N are coprime. Let r be the order of x mod N (i.e. the minimal t > 0
such that xt = 1 mod N ). For 0 ⇔ s ⇔ r ↓ 1, define the states

1 " ↘2ωisk/r %% k &

r↘1
|ωs → := ↑ e %x mod N .
r
k=0

3
(ii) Show that each state |ωs → is an eigenvector of Ux with eigenvalue e2ωis/r (i.e. these are shift
invariant states for the multiplicative action).
!
(iii) Show that →1r r↘1
s=0 |ωs → = |1→ .

(c) (Optional) Suppose now that we have a quantum process A that achieves the following: for
any unitary V , if |φϑ → is any eigenstate of V with eigenvalue e2ωiϑ then A is a unitary process
which on input |φϑ → |0→ produces the final state |φϑ → |↼→ (from which the value of ↼ may be
read out by a measurement on the second register). Here the second register (initially |0→) is
of suitable size to be able to represent the possible values of ↼ (and we are ignoring issues of
precision here). Such a process A does in fact exist and is usually called the phase estimation
algorithm. For the purposes of this question we will assume that A is given for the case of
V = Ux , and also that in this case, it runs in poly(log N )-time (which is true). (For an account
of the phase estimation algorithm see e.g. Nielsen and Chuang §5.2).

Show how the results of (b) together with the phase estimation algorithm for V = Ux can
be used to provide a poly(log N )-time quantum algorithm for factoring N (called Kitaev’s
factoring algorithm). Hint: start with the reduction of factoring to order finding, as done in
Shor’s algorithm.

(8) (A query complexity problem with no promise) (optional)

Let x = x0 x1 . . . xN ↘1 be an N -bit string. We may think of x as the list of values of a function
from ZN to {0, 1}. A quantum oracle Ox for x is a unitary operation on a state space of
dimension 2N whose action is defined by Ox |i→ |y→ = |i→ |y ⇓ xi →, where i ↗ ZN , y ↗ {0, 1} and
⇓ denotes addition modulo 2.
Note: this simply generalises the notion of an oracle for f : Bn ⇒ B1 (corresponding to domain
size N = 2n ) to arbitrary sized domains that are not powers of 2.

Consider the following oracle problem BAL:

Input: an oracle Ox for some N -bit string x with N = 2K being even.
Problem: decide with certainty whether x is (i) balanced or (ii) not balanced. (Here ‘balanced’
means that exactly half of the bit values are 0 and half are 1).

We know that if we impose a promise on x that it is either balanced or constant, then the
problem can be solved with just one query to the oracle (by the Deutsch-Jozsa algorithm). But
if there is no promise on the form of x (as in BAL) then it can be shown that any quantum
1
algorithm solving it requires at least O(N 6 ) queries to the oracle (so is exponential in n for
N = 2n ). The actual (optimal) quantum query complexity is not known.

(a) Show that any classical deterministic algorithm that solves Problem BAL on any input must
make at least N = 2K queries to the oracle in the worst case.

We now develop a quantum algorithm that solves BAL with at most K = N/2 queries thus
improving (albeit modestly) on any classical algorithm.

(b) Begin by writing x̂i = (↓1)xi and we will work on a state space of dimension N 2 with
orthonormal basis states |i→ |j→ for i, j ↗ ZN . Consider the following three computational steps:
! ↘1
Step 1: Make the state |ω0 → = →1N N i=0 |i→ |0→ and then (together with a qubit in state |↓→)
use one query to the oracle to make
N ↘1
1 "
|ω1 → = ↑ x̂i |i→ |0→ .
N i=0

4
Step 2: Consider a transformation U whose action on states |i→ |0→ is given by
' (
1 " "
U : |i→ |0→ ⇒ ↑ |i→ |k→ ↓ |k→ |i→ + |0→ |0→ .
N k>i k<i

Then by linearity the action of U on |ω1 → will be

' N ↘1 (
1 " " (x̂i ↓ x̂j )
|ω2 → = U |ω1 → = x̂i |0→ |0→ + |i→ |j→
N N
i=0 i<j

as you can directly check.

Step 3: Measure |ω2 → to obtain an outcome (k, l) with k, l ↗ ZN .

(i) Show that there exists a unitary transformation Ũ on the whole state space whose action
on the states |i→ |0→ coincides with the action of U as given in step 2.

(ii) Suppose for a moment that we impose the promise on x that it is either balanced or constant.
If we see (0, 0), respectively (i, j) ↘= (0, 0), as the measurement outcome in step 3, what can we
deduce about the string x?

(iii) Now returning to general input strings x and considering the possible measurement out-
comes (k, l), show that Problem BAL may be solved with certainty with at most K = N/2
queries to the oracle in every case (by suitable uses of the steps above).