Problem 4) Determining the "slope" of a linear function over Z4

Problem 4) Determining the "slope" of a linear function over Z4. Let Z4 : {0,1,2,3}, with arithmetic operations of addition and multiplication de?ned with respect to modulo 4 arithmetic on this set. Suppose that we are given a black—box computing a linear function f : Z4 —> Z4, which of the form f (m) : arc+b, with unknown coef?cients a, b E Z4 (throughout this question, multiplication and addition mean these operations in modulo 4 arithmetic). Let our goal be to determine the coef?cient a (the "slope" of the function). We will consider the number of quantum and classical queries needed to solve this problem. Assume that what we are given is a black box for the function f that is in reversible form in the following sense. For each Ly E Z4, the black box maps (any) to (21,3; + f(:c)) in the classical case; and |.'L') |y) to |a:) |y + f (33)) in the quantum case (which is unitary). Also, note that we can encode the elements of Z4 into 2—bit strings, using the usual representation of integers as a binary strings (00 = 0, 01 = 1, 10 = 2, 11 = 3). With this encoding, we can view f as a function on 2—bit strings f : {0,1}2 —> {0,1}2. When refering to the elements of Z4, we use the notation {0, 1, 2, 3} and {00, 01,10,11} interchangeably. (1) ( 5 points) Prove that every classical algorithm for solving this problem must make two queries. (2) ( 5 points) Consider the 2—qubit unitary operation A corresponding to "add 1", such that A |$) = |$ + 1) for all m E Z4. It is easy to check that 0 0 0 0 1 0 0 1 SOHO OOOH Let |1/2) : %(|00) +i|01) —1—i2 |10) +i3 |11)), where i = \/—1. Prove that AW) : —i |1/2).

(3) (5 points) Show how to create the state %((—i)f(00) |00) + (—i)f(01) |01) +(—i)f(10) |10) + (—i)f(11) |1l)) With a single query to U f. (Hint: you may use the result in part (2) for this.) (4) ( 5 points) Show how to solve the problem (i.e., determine the coef?cient a E Z4) with a single quantum query to f. (Hint: you may use the result in part (3) for this.)