5. (8 points) (Determining a hidden dot product vector) Consider the problem where one is given...

Transcribed Image Text:

5. (8 points) (Determining a hidden "dot product vector") Consider the problem where one is given black-box access to a function f: {0, 1}" → {0, 1} such that f(x) = a-z, where a {0,1}" is unknown. (Here a-1 =₁²₁ +₂2₂ + ...+ ann mod 2, the dot product of a and z in modulo-2 arithmetic.) The goal is to determine the n-bit string a. (a) (2 points) Give a classical (i.e., not quantum) algorithm that solves this problem with n queries. (b) (2 points) Show that no classical algorithm can solve this problem with fewer than n queries. (Hint: you may use the fact that a system of k linear equations in n variables cannot have a unique solution if k <n, even in the setting of modulo-2 arithmetic.) (c) (2 points) Here and in part (d) we'll construct a quantum algorithm that solves this problem with a single query to f. The first step is to construct the (n+1)-qubit state (0) 0) 10) 11) and apply a Hadamard operation to each of the n+1 qubits. The second step is to query the oracle for f. What is the state after performing these two steps? (d) (2 points) Describe a measurement on the state obtained from part (c) whose result is the bits a10₂... (Hint: the state from part (c) is not entangled; it can be expressed as a tensor product of 1-qubit states, and it might clarify matters if you express it in such a factorized form.) 5. (8 points) (Determining a hidden "dot product vector") Consider the problem where one is given black-box access to a function f: {0, 1}" → {0, 1} such that f(x) = a-z, where a {0,1}" is unknown. (Here a-1 =₁²₁ +₂2₂ + ...+ ann mod 2, the dot product of a and z in modulo-2 arithmetic.) The goal is to determine the n-bit string a. (a) (2 points) Give a classical (i.e., not quantum) algorithm that solves this problem with n queries. (b) (2 points) Show that no classical algorithm can solve this problem with fewer than n queries. (Hint: you may use the fact that a system of k linear equations in n variables cannot have a unique solution if k <n, even in the setting of modulo-2 arithmetic.) (c) (2 points) Here and in part (d) we'll construct a quantum algorithm that solves this problem with a single query to f. The first step is to construct the (n+1)-qubit state (0) 0) 10) 11) and apply a Hadamard operation to each of the n+1 qubits. The second step is to query the oracle for f. What is the state after performing these two steps? (d) (2 points) Describe a measurement on the state obtained from part (c) whose result is the bits a10₂... (Hint: the state from part (c) is not entangled; it can be expressed as a tensor product of 1-qubit states, and it might clarify matters if you express it in such a factorized form.)

Answer rating: 100% (QA)

a One classical algorithm that solves this problem with n queries is as follows 1 Initialize an nbit ... View the full answer