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 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.)
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 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
Lacoste t-shirts 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...
-
In the formula E = hf, does f stand for wave frequency, as defined in Chapter 19?
-
Explain why key central banks have shifted away from targeting money growth.
-
Simplify the irrational number \(\sqrt{330}\) and express in lowest terms. Identify the rational and irrational parts.
-
The following information is available for the pension plan of Radcliffe Company for the year 2014. Actual and expected return on plan assets ...... $ 15,000 Benefits paid to retirees ................
-
Phoenix Company reports the following fixed budget. It is basedon an expected production and sales volume of 15,400 units. PHOENIXCOMPANY Fixed Budget For Year Ended December 31 Sales $ 3,080,000Co 2...
-
The analyst in the Dorben Company made 10 independent time studies in the hand paint spraying section of the finishing department. The product line under study revealed a direct relation between...
-
6) Please help me fill out the chart with the given info, thankyou! QS 3-11 (Algo) Adjusting for unearned (deferred) revenues LO P2 For each separate case below, follow the three-step process for...
-
what opportunities are offered by new technology to boost business profitability
-
A total of 751 cal of heat is added to 5.00 g of ice at -20.0 C. What is the final temperature of the water? Tfinal =1 C Specific heat of H2O(s) Specific heat of H2O(l) Heat of fusion for HO 2.087...
-
Explain the Fama-French three factor model (show the equation). What is the difference between this model and CAPM?
-
While training, the athlete pushes a mass of 2 2 0 pounds up an inclined surface for a distance of 0 . 5 5 m at a steady pace. The incline is positioned at a 4 0 \\ deg angle above the horizontal...
-
Compare price risk (interest rate risk) and reinvestment risk in relation to bonds?
-
One of the qualities that influence the usefulness of accounting information is faithful representation, which emphasizes the need for financial statements to be produced in ways that accurately...
-
Wholesalers Ltd. deals in the sale of foodstuffs to retailers. Owing to economic depression, the firm intends to relax its credit policy to boost productivity and sales. The firms current credit...
-
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...
-
On January 1,2020 , Sharp Company purchased \(\$ 50,000\) of Sox Company \(6 \%\) bonds, at a time when the market rate was \(5 \%\). The bonds mature on December 31, 2024, and pay interest annually...
-
Referring to information in Brief Exercise 14-18, assume that Henry Inc. sold its holdings of Container Corporation bonds on July 2, 2020, for \(\$ 4,800\). a. Record the sale of the debt investment....
-
Henry Inc. purchased \(\$ 5,000\) of Container Corporation's \(5 \%\) bonds at par. The purchase is made on January 1 , 2020, and the investment is classified as a trading security. At June 30, 2020,...
Study smarter with the SolutionInn App