Introduction to Ouantum Information Science Homework 10
1. Shor’s Algorithm
-Anything That Can Go Wrong Will Go Wrong
Copyright By PowCoder代写 加微信 powcoder
a) [3 Points] What can go wrong if the function f satisfies that if s divides p
– q then f(p) = f(g), but
it’s not an “if and only if”: i.e. we could have f(p) = f(g) even when s doesn’t divide p
Illustrate with an example, describing a specific function f and the states of the quantum registers in
Shor’s algorithm.
Note that this does not happen for the function in Shor’s factoring algorithm, but it could happen
when attempting period finding on an arbitrary function.
2. Continued fractions
In the continued fraction step of Shor’s algorithm, we need the following key
fact: if a given real number 2 is sufficiently close to a rational number a/b with a
“conspicuously small
denominator”, then that rational number is unique.
a) [3 Points Prove that, indeed, for all real numbers 2, there can be at most one rational a/b, with a
and b coprime positive integers, that’s at most 8 away from 2 and satisfies b < 1/V28. Give a rigorous
proof for full points.
b) 3 Points Explain how this relates to the choice, in Shor's algorithm, to choose Q to be quadratically
larger than the integer N that we're trying to factor. In other words, what goes wrong in continued
fractions if O is smaller?
Give a formal proof or analysis relating part (a), continued fractions, and this issue.
3. Breaking Diffie- the following problem we'll be stepping through the adaptation of
Shor's period finding algorithm to breaking Diffie-Hellman public-key encryption.
The Diffie-Hellman
encryption scheme is based on the conjectured hardness of the Discrete Logarithm Problem.
The Discrete Logarithm Problem is as follows: let p be a prime number, a be an element of the
multiplicative group Z;
, and g be a generator of 2.;
that is, an element such that all other members
of Ze; equal some power of g modulus p
find the integer a such that gl
= a (mod p).
a) [2 Points The first step we need to accomplish is a reduction of the Discrete Logarithm Problem
to Period Finding. To do so, given some instance of Discrete Logarithm, we'll introduce a new function
f: ZR × 2R + 2; defined by f(21,22) = a" ge (mod p) and where R = |2,; |.
Show that this function is periodic in 21 and r2. In other words, show there exists a pair of integers (1, m)
such that f(21,22) = f(x1 + 1,22 + m).
b) [1 Point] How would knowledge of the period allow us to solve the Discrete Logarithm Problem?
(We will refer to multiple periods of a function as simply "the period'.)
c) [1 Point] Is this function efficiently computable? If so, how?
d) [1 Point] Next we'll step through the adaptation of Shor's Period Finding algorithm to find the
period of f defined above. Assume our state is initialized in the superposition
(21) |22) |0).
We then make an XOR query to f, writing the result into the third register. What is the state of the
system following the query? Write your final answer without using a.
) 2 Points Suppose we now measure the third register and observe the value g° for some (unknown)
integer c. What state do the input registers collapse to? Rearrange your answer so that it is in terms of
2 but not 22.
£) 1 Pointsl We now apply the inverse Quantiur Fourier Transform, QrTH lu) = 二8-6w-2y150,
to each input register. What is the resulting state?
g) [2 Points] Finally, we measure the input registers. Which pairs |=1) |z2) could be measured with
nonzero probability?
4. Grover's Algorithm with Multiple Marked Items:
a) [3 Points] Recall (and assume) Grover's algorithm is optimal for the single marked item case, as
proved in class. Prove that it's optimal for the multiple marked item case as well. In other words, show
that for all N and K, any quantum algorithm that finds a marked item with constant probability for any
N-element unordered list containing K marked items must use N(V N/K) queries to the list.
Hint: Suppose there exists some some value of N and K for which an algorithm succeeds with strictly
fewer queries, but not values of your choice (i.e. you can't just say
"when K = 1, contradiction!"), and
derive a contradiction using a reduction.
b) 3 Points Now suppose you want to find not just any one of the K marked items in a list of N
items, but you want to find all of them. Show that Grover's algorithm can be used to do that as well
with constant success probability using O(V NK log (N)) queries.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com