CO481/CS467/PHYS467 ASSIGNMENT 1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CO481/CS467/PHYS467 ASSIGNMENT 1

Due Friday March 17th at 8pm, electronically using Crowdmark

(will constitute 12% out of the 60% assignment marks)

1.  Modular arithmetic and factoring 3 marks Let r be the order of 3 mod 35.

(a) Find r .

(b) What is 3601  mod 35?

(c) Find GCD(35, 3  − 1) and GCD(35, 3  + 1).

2.  Quantum searching 3 marks

(a) Find the smallest positive p so that quantum search via amplitude amplification finds a solution with certainty using two iterations of the quantum search iterate? Also give a three decimal approximation to p.

(b)  Suppose we have a quantum algorithm A that produces a solution to f(x) = 1 with probability  . What is the smallest positive integer k so that k + 1 iterations of the quantum search iterate finds a solution with probability less than k iterations would?

3. Exact one-out-of-four searching 2 marks

Let f : {0, 1}n  '→ {0, 1} . Suppose we wish to find a string x ∈ {0, 1}n  such that f(x) = 1. Suppose further that exactly one quarter of all the strings x in {0, 1}n  satisfy f(x) = 1.

Show how to find a string x with certainty using exactly one evaluation of the black-box Uf  : |x⟩|b⟩ '→ |x⟩|b ⊕ f(x)⟩ .

4.  Quantum counting 3 marks

Suppose f : {0, 1}2n  '→ {0, 1} with a promise that the number of solutions to f(x) = 1 is either 2n  or 2n+1 .

Explain how to decide, with high probability, whether there are 2n or 2n+1 solutions using

a number of queries to Uf  : |x⟩ '→ ( − 1)f(x)|x⟩ in O(^2n ).

5.  Collision-finding 4 marks

Let f : {1, 2, . . . ,N} → X for some finite set of strings X, with the property that f is two-to-one.  That is, for each value y occurring in the range of f, there are two distinct inputs, x1 ,x2  such that f(x1 ) = f(x2 ) = y .

Suppose you are given a black-box for implementing Uf  : |x⟩|b⟩ '→  |x⟩|b ⊕ f(x)⟩, where x ∈ {1, 2, . . . ,N} and b ∈ {0, 1} .

Consider the following collision-finding algorithm:

❼  Query f(1),f(2), . . . ,f(M), for some M << N .

❼  If f(x1 ) = f(x2 ) for distinct x1 ,x2  ∈  {1, 2, . . . ,M}, then output the collision pair (x1 ,x2 ).

❼  Otherwise, perform a quantum search for a value x2  ∈ {M + 1,M + 2, . . . ,N} such

that f(x2 ) = f(x1 ) for some x1  ∈ {1, 2, . . . ,M} . Output (x1 ,x2 ).

(a) Assuming f(1),f(2), . . . ,f(M) are distinct, what is the probability p that a value x sampled uniformly at random from {M +1,M +2, . . . ,N} will satisfy f(x) = f(x1 ) for some x1  ∈ {1, 2, . . . ,M} .

(b) How many quantum queries does this algorithm need in order to find a collision with constant probability?  Express your answer in terms of N and M and using big-O notation.  (Do not forget about the queries to compute f(1),f(2), . . . ,f(M) in the first step.)

(c) Let M = Ne for some constant ϵ > 0. Find the value of the constant ϵ that minimizes the number of queries (up to constant factors) needed to find a collision with high probability.

6. Parallel quantum searching 2 marks

Suppose f : {0, 1}n  f→ {0, 1} has exactly one solution.

Let Uf  : |x⟩ f→ ( − 1)f(x) |x⟩  .

Show how to find the unique solution to f(x) = 1 with high probability using O(√2n−k) applications of the operation Uf  ⊗ Uf  ⊗ · · · ⊗ Uf  = U

7. Parallelizing phase-queries 3 marks

Let Uϕ  denote the unitary operation that maps |0⟩ f→ |0⟩ and |1⟩ f→ eiϕ |1⟩ .

Note that Ukϕ  = Uϕ(k) .  However, if a black-box process for implementing Uϕ  takes time t then implementing Ukϕ  in this serial way takes time kt.

(a) What is the result of applying Uϕ ⊗Uϕ ⊗ · · · ⊗Uϕ  = Uk to  |00 ... 0⟩+ |11 ... 1⟩ =  |0⟩⊗k +  |1⟩⊗k?

(b)  Show that it is possible to parallelize the implementation of Ukϕ  in such a way that all k of the Uϕ  gates are applied in parallel (on different qubits). You may perform standard quantum gates on the qubits before and after the application of the  k parallel phase gates.


2023-03-20