MULT20015 Elements of Quantum Computing
Elements of Quantum Computing
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MULT20015 Assignment
MULT20015 Elements of Quantum Computing
Assignment 2
Due: 5pm Thursday 12th October, 2023
Instructions: Work on your own, attempt all questions. Submit your completed written
work electronically as a pdf file (no other formats accepted) to LMS, with name and student
number on the front, on or before the due date. You may submit a scanned or photographed
copy of a hand-written assignment as long as your submission is clear and legible. Only
electronic submissions of PDF files are accepted.
Number of questions = 5 (4 pages)
Total marks = 30
Question 1 [2.0 + 2.0 + 2.0 = 6.0 marks]
The circuit below carries out two-bit addition S = A + B with an addition carry bit (c), where
A = a0 + 2a1, B = b0 + 2b1 (ordering is a0 = least significant bit, a1 = most significant bit
etc) and the sum S is represented using 3 bits, i.e. S = s0 + 2s1 + 4s2:
(a) Show, for the case A=3, B=2 (decimal notation), that the circuit works as expected by
considering the state of the system at each time-step
(b) Show how you would modify the circuit so that the bit ordering in each of A, B and S
are reversed (i.e. most significant bit last).
(c) With the circuit obtained in (b), set qubits a1, and a0 to each correspond to an equal
superposition across their bit values. Find the resulting state of the system, and explain what
happens when the qubits in S are measured.
a1
a0
b1
b0
c
s2
s1
s0
MULT20015 Assignment 2, 2023
2
Question 2 [2.0 + 3.0 = 5.0 marks]
Consider a set of functions !() defined over two-qubit inputs as follows:
The functions 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 and program a
quantum algorithm, which can determine whether the function is constant or balanced.
(a) For each function, !(), give a quantum circuit (oracle) that takes as input the state |〉|〉 and outputs the state |〉| ⊕ !()〉.
(b) Describe a quantum algorithm that, given an oracle, determines whether the corresponding
function is balanced or constant in just 1 query. Indicate the state of the system at each
timestep for an example balanced function and a constant function
Question 3 [1.0 + (3.0 + 1.0) + 1.0 = 6.0 marks]
For this question, the online Magma calculator (http://magma.maths.usyd.edu.au/calc/) may
be helpful, in particular the GCD, Modinv and Modexp functions.
(a) Alice chooses the two primes to construct her RSA keys:
p = 3444808566667045925904799621 and q = 74450012572222735635205799353.
Determine the smallest valid RSA public key and its corresponding private key for Alice. Show
your workings with an explanation justifying your answer.
(b) An experiment attempts to factor N = 899 using Shor’s algorithm on a quantum computer.
The experimenters choose a base of a = 4, and attempt to find the period, r, such that ar
= 1 mod N. After performing Shor’s algorithm, the upper control register, containing n = 20
qubits is measured and the value m = 110101111100011001002 (corresponding decimal m
= 883812) is obtained.
(i) Based on this measured value, use the continued fraction expansion to find candidate
periods, r. For each candidate period r test if ar = 1 mod N or not. Show your working.
(ii) Use the period, r, obtained in part (i) to find the factors of N = 899. Show your working.
(c) The experiment in (b) is modified to factor 413 using a = 11, n = 18. We measure the
value of 394 = a5 mod N in the bottom register. What can you say about the observed value
in the upper control register?
MULT20015 Assignment 2, 2023
3
Question 4 [1.0 + 2.0 + 2.0 + 2.0 + 1.0 = 8.0 marks]
(a) On the QUI, program a x-rotation gate with a rotation angle of 6, and a global phase
of 12, directly on a |ψ⟩ = |−⟩ = (|0⟩ − |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.
(b) Construct the Quantum Phase Estimation (QPE) circuit described in the lectures, which
could be used to estimate the eigenvalue of the eigenstate, |ψ⟩ = |−⟩ for a x-rotation gate,
with a rotation angle of 6, (with a global phase of 12, ). 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) Determine (using QUI) the probabilities of the resulting measurements (on the control/upper
register). Recall that if |ψ⟩ = exp(2πθ) |ψ⟩,
then QPE allows us to estimate θ using a quantum computer. Use these measurements for
the QPE circuit with U=Rx( 6, ) (with a global phase of 12, ) and |ψ⟩ = |−⟩ to estimate θ, and
briefly compare you estimates of θ with your answer in part (a). Why are they not identical?
(d) Modify your circuit and repeat steps above to determine the phase angle, θ, for U=Rx(4/5)
with a global phase of 2/5 applied to the state |ψ⟩ = |−⟩.
(e) Briefly explain what could you do to obtain a better estimate of θ?
MULT20015 Assignment 2, 2023
4
Question 5 (2.0 + 2.0 + 1.0 = 5.0 marks)
The triangular numbers are defined by " = ( + 1)/2, are 1, 3, 6, 10, 15, etc.
(a) Write out the circuit for an oracle of five qubits which marks (ie. applies a -1 phase to)
each of the states if it is a triangular number. You may use multiple controlled gates.
Implement the oracle on the QUI and verify its working for all triangular numbers over five
qubits (include screen shots).
(b) On the QUI (set to 5 qubits), program this oracle into Grover’s algorithm. Apply Grover
iterations (consisting of oracle and inversion about the mean) until the probability of measuring
a triangular number reaches a maximum. Include a screenshot of your circuit and its output.
Determine the angle of rotation in the geometrical picture and show that it is consistent with
the optimal number of iterations found in QUI.
(c) If you used Grover’s algorithm to find a random triangular number less than or equal to
127 (commensurate with 7 qubits), approximately how many iterations (consisting of oracle
and inversion about the mean) should you use to ensure a high probability of success? Show
your working.