MULT20015 Elements of Quantum Computing
Assignment 2
Due: 10th October 2024 5pm (AEST)
Worth: Total points: 30. Weight for subject mark: 30%.
Number of problems: 5.
Submit your completed written work electronically as a PDF (no other formats accepted) to Canvas/LMS. You
are welcome to use an app like CamScanner to convert your handwritten notes to pdf, and keep submissions under
10MB. Please put your name and student number on the front of your submission. Show all working.
While we encourage you to discuss this assignment with your classmates (e.g., you can organize informal
discussion session or meetups), every student must write their own solution based on their personal understanding.
Copying full or partial solutions from other students may invalidate your submission, please remind yourself of
UniMelb’s Academic Integrity Policy and Penalties.
1 Algorithmic Primitives [0.5+0.5+0.5+1.0+1.0+1.0 = 4.5 points]
Recall that a SWAP gate is a two qubit gate that swaps the state of a two bit register: SWAP |ψ⟩⊗ |ϕ⟩ = |ϕ⟩⊗ |ψ⟩.
The controlled SWAP is an important three qubit gate. If the first qubit is zero then it does nothing (or identity)
on the bottom two qubits. If the first qubit is one then it SWAPs the bottom two qubits. Of course the interesting
thing happens when we send a superposition of one and zero through the top wire.
(a) Construct the following circuits using the QUI.
Using the QUI compute the probability of measuring “0” on the top wire (the “check qubit”) for circuits (i),
(ii), (iii), and (iv).
(b) The states on the bottom two wires at the blue dashed line (before the controlled SWAP) are: (i) |0⟩ , |0⟩;
(ii) |0⟩ , |1⟩; (iii) |1⟩ , |1⟩; (iv) |+⟩ , |0⟩. For each of these states compute |⟨state of qubit 1|state of qubit 2⟩|2,
e.g. for (i) |⟨0|0⟩|2.
(c) Use your results from part (b) and compute Pr(0) = 12 (1 + |⟨state of qubit 1|state of qubit 2⟩|2) for each
circuit. This probability should be equal to the probability for measuring “0” on the “check qubit” from the
QUI in part (a).
(d) Let’s consider two general states on the bottom wires |ψ⟩ = a0 |0⟩ + a1 |1⟩ and |ϕ⟩ = b0 |0⟩ + b1 |1⟩. So the
state of the register before the controlled SWAP is
|+⟩ ⊗ |ψ⟩ ⊗ |ϕ⟩ .
Expand the plus state to |+⟩ = (|0⟩+ |1⟩)/√2 and then apply the controlled SWAP
cSWAP = |0⟩⟨0| ⊗ I ⊗ I + |1⟩⟨1| ⊗ SWAP
to the inital state, that is compute |Ψ⟩ = cSWAP |+⟩⊗ |ψ⟩⊗ |ϕ⟩. [Hint: don’t use a matrix representation!]
1
Elements of Quantum Computing Assignment 2 MULT20015
(e) Now multiply the resulting state by the H gate on the top wire, i.e. H ⊗ I ⊗ I |Ψ⟩. Let’s call the resulting
state |Ψ′⟩. Write |Ψ′⟩ resulting state as |Ψ′⟩ = |0⟩⊗ (something)+ |1⟩⊗ (something else). Where “something”
and “something else” are linear combinations of quantum states.
(f) The part of the state that represents measuring zero on the first qubit is |0⟩⊗(something). By only considering
that part show that Pr(0) = 12 (1 + |⟨ψ|ϕ⟩|2). [Hints: (1) Revise the lecture on multiqubit measurement.
(2) Recall (number 1) ⊗ (number 2) = (number 1) × (number 2). (3) Recall that ⟨ψ|ϕ⟩ × ⟨ϕ|ψ⟩ = |⟨ψ|ϕ⟩|2
and ⟨ϕ|ψ⟩ × ⟨ψ|ϕ⟩ = |⟨ψ|ϕ⟩|2. ]
2 Deutsch-Josza & Simon’s [2.0+2.0+3.0 = 7.0 points]
Consider the Deutsch-Josza algorithm for the case where the function f(x) is defined over n-bit numbers, x. In
Lectures, the general circuit for function evaluation was given by:
Consider a set of functions fi defined over four qubit (n = 4) inputs as follows:
f1(x) = 0
f2(x) = 1
f3(x) = x mod 2
f4(x) = (x+ 1) mod 2 .
The functions above are either constant or balanced. If you are given an unknown function fi where i is one of the
4 values from the set {1, 2, 3, 4}, your job is to develop a classical and a quantum algorithm, which can determine
whether the function is constant or balanced.
(a) Describe a classical algorithm to solve the above problem. What is the elementary step? What is the cost
function (under worst-case scenario) as a function of input size n? Find the Big-O class from the cost
function.
(b) Use the Deutsch-Josza quantum algorithm to solve the above problem for n = 4. Determine the quantum
circuit for each fi and explain carefully how they work, that is step through the logic of this circuit. Provide
a screen shot of each circuit from the QUI.
(c) Consider a related problem where we have a set of n functions defined over n-bit numbers x as:
fi(x) = xi,
where xi is the i’th bit of x (i = 0..3, counting from the least significant bit (i = 0)). Assume you are given the
oracle corresponding to the function fi but do not know its details. Devise a classical and quantum algorithm
to determine the value of i. (Hint. For the quantum case, examine the upper register of the Deutsch-Josza
algorithm) What is the elementary step in your classical and quantum implementations? Determine the
worst-case number of elementary steps required for n = 4 for both the classical and quantum algorithms.
3 Quantum Phase Estimation [1.0+3.0+2.0+3.0 = 9.0 points]
(a) On the QUI, program a Y-rotation gate with a rotation angle of 2π3 and a global phase of
π
3 directly on a
|ψ⟩ = (|0⟩ − i |1⟩)/√2 state. What is the resulting state (including phase) when this rotation is applied to
the |ψ⟩ state? Show that |ψ⟩ is an eigenstate of this rotation. Include your circuit in your answer.
University of Melbourne Page 2/4 Due: 10th October 2024 5pm (AEST)
Elements of Quantum Computing Assignment 2 MULT20015
(b) Construct the Quantum Phase Estimation (QPE) circuit described in the lectures to estimate the eigenvalue
of the eigenstate, |ψ⟩ for the Y-rotation gate specified in part (a). Use four qubits in the control (upper)
register. You may make use of the following (inverse) quantum Fourier Transform for four qubits:
The angles of the controlled-Z rotations shown (in order, from left to right) are:
i −π2 (with a global phase of −π4 )
ii −π4 (with a global phase of −π8 )
iii −π2 (with a global phase of −π4 )
iv −π8 (with a global phase of − π16 )
v −π4 (with a global phase of −π8 )
vi −π2 (with a global phase of −π4 )
Include a screenshot of your circuit in your answer.
(c) Recall that if
U |ψ⟩ = exp(2 iπθ) |ψ⟩ ,
then QPE allows us to estimate θ using a quantum computer. Determine (using QUI) the measurement
probabilities on the control/upper register of the QPE circuit in part (b). Use these measurements to estimate
θ, and briefly compare you estimates of θ with your answer in part (a). Why are they not identical?
(d) Now consider the rotation U = RY (2π/5) (with a global phase of π/5). Repeat (b)-(c) for this new rotation
operation.
4 RSA & Shor’s algorithm [1.0+(1.0+1.0) = 3.0 points]
(a) Alice chooses the two primes to construct her RSA keys:
p = 2881309652927113715947711, and
q = 14323296331779246294235011689 .
Determine the smallest valid RSA public key and its corresponding private key for Alice. Show your working
with an explanation justifying your answer. You may use http://magma.maths.usyd.edu.au/calc/ .
(b) An experiment attempts to factor 511 using Shor’s algorithm on a quantum computer. The experimenters
choose a base of a = 3, and attempt to find the period, r, such that ar = 1 mod 511. After performing
Shor’s algorithm, the upper control register, containing n = 18 qubits is measured and the value m =
1001010101010101012 is obtained.
i Based on this measured value, use the continued fraction expansion to find candidate periods, r. For
each candidate period, r, test to determine if ar = 1 mod 511 or not. Show your working.
ii Use the period, r, obtained in part (i) to find the factors of 511. Show your working.
5 Grover [1.0 + 1.0 + 1.0 + 1.0 + 1.0 + (1.0 + 0.5) = 6.5 points]
In lectures and tutorials you have seen how to implement Grover’s algorithm to find a particular number that you
already know when constructing the oracle. In this problem we will construct an oracle that uses the properties of
a solution to solve a problem where we don’t know the exact solution in advance.
A quantum-sudoku is a 2 × 2 grid, filled with the numbers 0 and 1. The entries within each row and column
must be unique, i.e. a row cannot contain the sequence 00 or 11. In this problem we label each entry as in Fig. a
below;
University of Melbourne Page 3/4 Due: 10th October 2024 5pm (AEST)
Elements of Quantum Computing Assignment 2 MULT20015
v0 v1
v2 v3
(Fig. a)
1 0
0 1
(Fig. b)
(a) Write down four relations between the vis that are equivalent to the uniqueness conditions on each row and
column.
(b) Write down a quantum circuit that takes two input qubits corresponding to vi and vj , and sets an output
ancilla qubit to 0 if they are the same and 1 if they are different.
(c) Write an oracle for Grover’s algorithm that uses 4 qubits to represent the state of the sudoku board, 4 ancillas
to hold the results of the uniqueness checks, and one output qubit initially prepared in the |−⟩ state. The
oracle should mark valid states with a phase of −1. Program this into QUI and include a screenshot.
Note: you should do some uncomputation to return the ancilla qubits to the |0⟩ state at the end of the oracle.
(d) Program the mean inversion step into QUI and run Grover’s algorithm. How many iterations do you need to
have the maximum probability of finding a valid solution to the sudoku? Include a link to the QUI circuit.
Note: You can select multiple gates in QUI with the pointer, and copy and paste to repeat an iteration of
Grover’s algorithm.
(e) In a “real” sudoku, some squares on the grid are already filled. How can we program this additional constraint
into our oracle for Grover’s algorithm? Consider the specific case where v0 = 1. How many Grover iterations
are optimal in this case? Show your circuit and the corresponding QUI output.?
(f) i. How does the computational complexity of this problem scale with n, the length of a row/column?
Assume that the ratio between the number of possible grids and the number of possible solutions to the
sudoku is f(n)1. Give your answer in big-O notation.
ii. A full 3 × 3 sudoku also has the condition of each subsquare containing every number exactly once. If
you created an oracle including this condition, what is the computational complexity of the algorithm
in big-O notation?
1It turns out the mathematics of sudoku is quite complicated
University of Melbourne Page 4/4 Due: 10th October 2024 5pm (AEST)