5. (8 points) (Determining a hidden dot product vector) Consider the problem where one is given...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
5. (8 points) (Determining a hidden "dot product vector") Consider the problem where one is given blackbox access to a function f: {0, 1}" → {0, 1} such that f(x) = az, where a {0,1}" is unknown. (Here a1 =₁²₁ +₂2₂ + ...+ ann mod 2, the dot product of a and z in modulo2 arithmetic.) The goal is to determine the nbit 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 modulo2 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 1qubit 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 blackbox access to a function f: {0, 1}" → {0, 1} such that f(x) = az, where a {0,1}" is unknown. (Here a1 =₁²₁ +₂2₂ + ...+ ann mod 2, the dot product of a and z in modulo2 arithmetic.) The goal is to determine the nbit 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 modulo2 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 1qubit states, and it might clarify matters if you express it in such a factorized form.)
Expert Answer:
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
Related Book For
An Introduction To Statistical Methods And Data Analysis
ISBN: 9781305465527
7th Edition
Authors: R. Lyman Ott, Micheal T. Longnecker
Posted Date:
Students also viewed these programming questions

What type of analysis helps engineers, designers and decision makers asses the designs purpose and likely acceptance in the marketplace?

Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...

The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 15. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...

Lacoste tshirts come with an average price of $ 120 a piece, at their factory outlet with a std. deviation of $ 17. But at the Seasonal Sale (Discount) outlets of these t shirts, it was also...

1. What are SAP's sources of competitive advantage and how do they coincide with business model? 2. Using Porter's fiveforces model, what does the competitive structure of the standardized software...

A survey of beginning students showed that a majority strongly agreed with the statement, I am afraid of statistics. (a) Why might this attitude exist among students who have not yet taken a...

Why is interest typically charged on notes receivable, but not on accounts receivable? LO27

Brown Deer Electric sold $3,000,000, 10%, 10year bonds on January 1, 2012. The bonds were dated January 1 and pay interest July 1 and January 1. Brown Deer Electric uses the straightline method to...

Given a quadratic equation, what is the discriminant and what information does it provide about the given quadratic equation?

If the Gobblecakes bakery in Problem 2 changes the selling price for a cupcake from $3.20 to $2.75, what effect will the change have on the breakeven volume?

4 7 . Mr . Chopra returned to India after serving a British company in USA for 2 5 years. He furnishes the following particulars of his income for the year ended 3 1  3  2 0 2 3 and asks you to...

Can you find a priority list that yields an optimal schedule? 12 13 10 3 15 1, 4, 2, 5, 3, . 1, 2, 3, 4, 5, 6. , 3, 2, 4, 5, 1. 6, 3, 5, 2, 4, 1. 4 6 20 (Choose the optimal schedule from the list...

Daw a flow chart for the MIPS assembly code .data ogstate: asciiz "UCF, its athletic program, and the university's alumni and sports fans are sometimes jointly referred to as the UCF Nation, and are...

This project requires you to identify, analyse and classify cost transactions, record the transactions in the accounts and prepare cost reports in accordance with the organisational policies and...

A nonrotating force, P and a torque, T are applied to the following system, which is supported by bearings at points A and B. All dimensions are in milimeters. The torque fluctuates F15% from the...

Memphis Company anticipates total sales for April, May, and June of $ 9 1 0 , 0 0 0 , $ 1 , 0 1 0 , 0 0 0 , and $ 1 , 0 6 0 , 0 0 0 respectively. Cash sales are normally 2 0 % of total sales. Of the...

Divide and simplify to the form a + bi. 20 i 3+ i

Cable Corporation is 60% owned by Anna and 40% owned by Jim, who are unrelated. It has noncash assets, which it sells to an unrelated purchaser for $100,000 in cash and $900,000 in installment...

Refer to Exercise 3.24. Average the three group means, the three group medians, and the three group modes, and compare your results to those of part (b). Comment on your findings. In exercise Rate...

Nylon bars were tested for brittleness. Each of 280 bars was molded under similar conditions and was tested by placing a fixed stress at specified locations on the bar. Assuming that each bar has...

Refer to Exercise 10.73. For each of the four levels of frequency of purchase, compute the proportion of customers in each of the four adequacy of selection categories. Describe the trends in the...

When a product's cost is composed of both fixed and variable costs, what effect does the increase or decrease in production have on total unit cost?

Teague Corporation has the following longterm investments: 1. 60 percent of the common stock of Ariel Corporation 2. 13 percent of the common stock of Copper, Inc. 3. 50 percent of the nonvoting...

The stockholders equity section of Caritas Corporations balance sheet appeared as follows on December 31: Swanson Manufacturing Company owns 80 percent of Caritass voting stock and paid $11.20 per...
Study smarter with the SolutionInn App