Modular arithmetic and factoring 3 marks
Let r be the order of 3 mod 35.
(a) Find r.
(b) What is 3601 mod 35?
Copyright By PowCoder代写 加微信 powcoder
(c) Find GCD(35,34 – 1) and GCD(35,34 + 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)
probability 10000-
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
3. Exact one-out-of-four searching 2 marks
Let f : {0,1}” > {0,1}. Suppose we wish to find a string 2 € {0, 1}” such that f(x)
Suppose further that exactly one quarter of all the strings 2 in {0, 1}” satisfy f(2) = 1
Show how to find a string a with certainty using exactly one evaluation of the black-box
4. Quantum counting 3 marks
Suppose f: {0, 112 > {0, 1} with a promise that the number of solutions to f(x) = 1 is
either 2″ or 21+1
Explain how to decide, with high probability, whether there are 2″ or 2″+1 solutions using
a namber of queries to Ur : l2) – (-11(0lay inO6v2n).
5. Collision-finding 4 marks
Let f: {1,2,
› 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, 22 such that f(x1) = f(x2) = y.
Suppose you are given a black-box for implementing Up : 12) 1B) 11216④f(2),where
., N} and bE {0, 1}.
Consider the following collision-finding algorithm:
• Query f(1), f(2), . . . , f(M), for some M << N
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com