COMS 4281 Problem Set 3 Quantum Algorithms
COMS 4281 – Intro to Quantum Computing
Problem Set 3, Quantum Algorithms
Due: November 2, 11�59pm.
Collaboration is allowed and encouraged (teams of at most 3). Please read the syllabus
carefully for the guidlines regarding collaboration. In particular, everyone must write their
own solutions in their own words.
Write your collaborators here:
Problem 1: Basic Fourier Math
Problem 1.1
For two strings , let denote
Prove that for all ,
Problem 1.2
Let denote the -th root of unity. Prove that for all integers ,
In [ ]: %run utils.py
x, y ∈ {0, 1}n x ⋅ y
x1y1 + x2y2 + ⋯ + xnyn mod 2.
x ∈ {0, 1}n
(−1)x⋅y = {
0 if x ≠ 0n
2n if x = 0n
ωn = exp( )
0 if j is not a multiple of n
n if j is a multiple of n
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 2/10
Problem 1.3
Let denote a positive integer between and , and let denote an
integer such that (meaning that is coprime to ). Let be the order of
modulo ; meaning that (i.e., dividing by yields a remainder of ).
Recall the unitary map acting on qubits such that for all ,
and recall the eigenvectors
Problem 1.4
Recall the Fourier Transform unitary that acts as follows: for all ,
Compute the vector .
Note: The definition of differs from the one presented in class, because the exponent
of is rather than .
Problem 2: Modified Simon’s Algorithm
In this problem you will analyze a variant of Simon’s Problem. Suppose you are given black-
N 2n−1 2n 1 ≤ x ≤ N − 1
gcd(x, N) = 1 x N r x
N xr ≡ 1 mod N xr N 1
n 0 ≤ y < 2n Ux |y⟩ = { |xy mod N⟩ if y < N |y⟩ otherwise k mod N⟩ . |us⟩ = |1⟩ . FN 0 ≤ j < N FN ∣∣fj⟩ = |j⟩ 10/20/22, 11:23 AM pset3 localhost:8888/nbconvert/html/pset3.ipynb?download=false 3/10 box query access to a function that encodes two secrets . This means that We will assume that are both nonzero and are not equal to each other. Note: the sum of two bit strings is another string where we've XOR'd the coordinates Problem 2.1 Given such a function , what is the size of its range? Meaning, how many possible strings can be output by ? Problem 2.2 Write a classical + quantum hybrid algorithm that makes queries to and outputs, with high probability, the secrets . You should use Simon's Algorithm for inspiration. Problem 2.3 Prove that your algorithm works. Problem 2.4 What if we now considered the situation where the function is hiding not two but secrets (which are all nonzero and distinct strings). How would your answers to 7.2 and 7.3 change? Problem 3: Quantum Minimum Finding Problem 3.1 f : {0, 1}n → {0, 1}n s, t ∈ {0, 1}n f(x) = f(y) if and only if x + y ∈ {0n, s, t, s + t} s(1), … , s(k) 10/20/22, 11:23 AM pset3 localhost:8888/nbconvert/html/pset3.ipynb?download=false 4/10 Let be an integer. Devise a quantum algorithm that, in expectation, makes queries to a function , and computes . You can assume that is injective. Hint: Use that Grover's algorithm, when run on a function with solutions, outputs a uniformly random such that using queries in expectation for some constant . Hint: Your algorithm can have unbounded running time; you just need to show that the expected number of queries before the algorithm finds the minimum is . Problem 3.2 Show that, assuming that Grover's algorithm is optimal for unstructured search (meaning that any quantum algorithm finding a preimage of requires queries to ), any quantum algorithm that finds the minimum of a function with high probability must also make queries. Problem 3.3 Now let's implement our minimum finding algorithm for arbitrary 5 qubit functions. Below are helpers for converting functions into quantum oracles, and an implementation of the Grover's Diffusion gate, use those to help you implement minimum search, and test is on the examples given below. For fun, track the number of oracle calls you use (num_oracle_calls), but you won't lose points for using too many oracle calls if your solution is correct asymptotically. M ≥ 2 O(√N) f : {0, 1}n → {0, 1, … , M − 1} minx f(x) g : {0, 1}n → {0, 1} T x g(x) = 1 c√N/T f : {0, 1}n → {0, 1} Ω(√N) In [ ]: num_oracle_calls = 0 def inc_num_oracle_calls(): global num_oracle_calls num_oracle_calls += 1 def reset_num_oracle_calls(): global num_oracle_calls num_oracle_calls = 0 def append_oracle(input_circuit: QuantumCircuit, f: Callable[[int], bool], quantum_registers: List[int]) -> QuantumCircuit:
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 5/10
append_oracle takes a boolean function (with inputs from 0 to 31) and appen
inc_num_oracle_calls()
oracle_gate = UnitaryGate(np.diag([(-1)**f(i) for i in range(32)]))
input_circuit.append(oracle_gate, quantum_registers)
return input_circuit
def append_diffusion_gate(input_circuit: QuantumCircuit,
quantum_registers: List[int]) -> QuantumCircuit:
Takes an input circuit and appends a diffusion gate to the registers.
The quantum registers must be length 5.
if len(quantum_registers) != 5:
return None
for i in quantum_registers:
input_circuit.h(i)
diffuse = -1*np.eye(32)
diffuse[0,0] = 1
input_circuit.append(UnitaryGate(diffuse), quantum_registers)
for i in quantum_registers:
input_circuit.h(i)
return input_circuit
def get_most_likely_outcome(quantum_circuit: QuantumCircuit) -> int:
backend = Aer.get_backend(‘qasm_simulator’)
job_sim = backend.run(transpile(quantum_circuit, backend), shots=5024)
result_sim = job_sim.result()
counts = result_sim.get_counts(quantum_circuit)
return int(max(counts, key = counts.get), 2)
In [ ]: ### ======== BEGIN CODE =============
Below are some suggested templates for functions that would be useful to implem
You don’t have to use them if you don’t want
def grovers_search_known_sols(f: Callable[[int], bool], num_sols: int) -> int:
Runs Grovers search, assuming there are num_sols number of solutions (we’ll
Assumes that the input space is dimension 32.
def grovers_search(f: Callable[[int], bool]) -> int:
Runs Grovers search with an unknown number of solutions by halving the gues
Returns -1 if no answer is found.
### ======== END CODE =============
def find_min(f: Callable[[int], int]) -> int:
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 6/10
Test your code on the following examples.
Problem 4: Exploring Order Finding
In this problem, we’ll explore the quantum algorithm for Order Finding (which is different
from the one covered in class; in fact this one is closer to the way Peter Shor implemented
it). Consider the following function
where ranges from to , so that can be represented using bits.
Problem 4.1
What is the period of this function? Meaning, what value of is such that
Problem 4.2
Let’s see how we could’ve figured this out using quantum computation! First, we create a
quantum circuit with 8 qubits and 4 classical bits to store measurement outcomes.
Add gates to the order finding circuit to get to the following state:
reset_num_oracle_calls()
y = random.randrange(0, 32)
### ======== BEGIN CODE =============
### ======== END CODE =============
In [ ]: f1 = lambda x: x – 16
print(“Minimum of f2 is: “, find_min(f1))
print(“Oracle calls used: “, num_oracle_calls)
In [ ]: f2 = lambda x: x**2 – 13*x + 3
print(“Minimum of f2 is: “, find_min(f2))
print(“Oracle calls used: “, num_oracle_calls)
In [ ]: f3 = lambda x: 1.0 – np.sin(x / 16)
print(“Minimum of f3 is: “, find_min(f3))
print(“Oracle calls used: “, num_oracle_calls)
f(x) = 3x mod 16
x 0 15 x 4
f(x + r) = f(x) x
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 7/10
Note that here and refer to integers, but in your circuit they will need to be
represented in binary using 4 bits.
Problem 4.2
We provide code that implements the unitary, which acts on 8 qubits (4 for input, 4 for
ancilla) as follows:
Append the oracle unitary to your circuit to get the following state
Problem 4.3
|i⟩) ⊗ |0⟩
In [ ]: order_finding_circuit = QuantumCircuit(8,4)
### ======== BEGIN CODE =============
### ======== END CODE =============
order_finding_circuit.draw(output=”mpl”)
Uf |i⟩ |j⟩ = |i⟩ |j ⊕ f(i)⟩
i mod 16⟩)
In [ ]: def reverse_bits(i: int) -> int:
Reverses the bits of a number up to 5 bits (0 through 31)
return int(‘{:08b}’.format(i)[::-1], 2)
#This function returns the UnitaryGate object that you want to append to your c
def U_f() -> UnitaryGate:
unitary = np.zeros([256, 256])
for i in range(16):
for j in range(16):
input_basis_state = i * 16 + j
exponentiated_j = pow(3, i, 16) ^ j
output_basis_state = i * 16 + exponentiated_j
unitary[reverse_bits(input_basis_state), reverse_bits(output_basis_
return UnitaryGate(unitary,”U_f”)
### ======== BEGIN CODE =============
### ======== END CODE =============
order_finding_circuit.draw(output=”mpl”)
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 8/10
Suppose you measured the second register (the last 4 qubits) of the state described in
Problem 4.2. What are the possible outcomes and their probabilities? What are the
corresponding post-measurement states?
Problem 4.4
Let’s simulate the measurement of the second register and collect measurement statistics.
Write code to output the empirical probability of each measurement outcome (for example,
the integer appears of the time, the integer occurs of the time, etc. ).
Note that the convention in Qiskit is to use little-endian representation of integers: the least
significant bit goes first (so the ordering goes like ).
Problem 4.5
Now let’s get the post-measurement state conditioned on the second register measuring
for . First, suppose we measure the second register and obtain outcome . What will
the post measurement state on the first register be?
Problem 4.6
Now let’s validate empirically that the post measurement state is what we found above.
We’ve already got some skeleton code for you set up; you should fill in the rest. The result is
that the variable postmeasurement_state should be the post measurement state of the
8 qubits, conditioned on the second register being in the state (or, in binary, ).
1 X% 3 Y %
|0000⟩ , |1000⟩ , |0100⟩ , |1100⟩ , …
In [ ]: order_finding_circuit.measure([4,5,6,7], [0,1,2,3])
order_finding_circuit.draw(output=”mpl”)
In [ ]: backend = Aer.get_backend(“statevector_simulator”)
result = execute(order_finding_circuit, backend=backend, shots=1024).result()
result.get_counts()
# Note that the bitstrings are reverse order
In [ ]: ### ======== BEGIN CODE =============
### ======== END CODE =============
|3⟩ |1100⟩
In [ ]: j = 3
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 9/10
The variable postmeasurement_state is a vector of dimension 1024. We are interested
in the state of the first register (the first 5 qubits), so let’s extract that into a 32-dimensional
vector first_register .
We then plot the squares of the amplitudes of first_register .
Does the plot agree with your theoretical calculations of the post-measurement state?
Problem 4.7
Let denote the post-measurement state corresponding to the variable
first_register . Suppose we apply the -qubit Fourier Transform unitary to to
get the state .
First, compute by hand the Fourier transform of , and determine an algebraic
expression for the amplitudes of .
If we then measured in the standard basis, what outcomes are we most likely to get?
Hint: Your answers to Problem 1 may be helpful.
We now plot the squares of the amplitudes of below. Does it match your math above?
j_in_rev_binary = ‘1100’ # Note this bitstring is in reverse order. Reversing i
#just repeating this 100 times until you get the result you want (the number 10
for k in range(100):
result = execute(order_finding_circuit, backend=backend, shots=1).result()
### ==== BEGIN CODE ========================
### ====== END CODE ========================
postmeasurement_state = result.get_statevector()
In [ ]: first_register = []
for i in range(16):
index = reverse_bits(i*16 + j)
ampl = postmeasurement_state[index]
first_register.append(ampl)
plt.bar(range(16),[np.absolute(f)**2 for f in first_register])
10/20/22, 11:23 AM pset3
localhost:8888/nbconvert/html/pset3.ipynb?download=false 10/10
Problem 4.8
Suppose you had multiple copies of the state . Explain how, by measuring this state in
the standard basis multiple times, one can determine the period of the function ? This
should use the algebraic expression for the amplitudes that you obtained in Problem 4.7.
In [ ]: import numpy.fft as fft
mean = sum(first_register)/len(first_register)
fourier = fft.fft(np.array(first_register) – mean,16, axis = 0)
# have to add in the normalization because numpy doesn’t do it
fourier = fourier/np.sqrt(16)
# plot the absolute value squared of the fourier transform
plt.bar(range(16),[np.absolute(f)**2 for f in fourier])