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:
![5. (8 points) (Determining a hidden](https://dsd5zvtm8ll6.cloudfront.net/si.experts.images/answers/2023/10/651eed88421c1_704651eed883d8c9.jpg)
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...
-
Almost two years ago, the DEF Partnership was formed when Demetrius, Ebony, and Farouk each contributed $100,000 in cash. They are equal general partners in the real estate partnership, which has a...
-
Should central banks be privately or publicly owned? Explain.
-
1. Exhibit 18.10 presents the tax reconciliation table for ToyCo, a $5 billion designer and distributor of childrens toys. Convert the tax table from percentages to millions of dollars. Separate the...
-
The following data represent trunk circumferences (in mm) for a random sample of 60 four-year-old apple trees at East Malling Agriculture Research Station in England (Reference: S. C. Pearce,...
-
Please solve both questions: QUESTION 3 Which of the following would not be used in calculating direct materials variances? O AQ X AP O AQ X SP SQ X AP OSQ X SP QUESTION 4 Helen of Troy Limited buys...
-
You are the executive assistant to the director of sales at B-Trendz, Inc., a trendy retail store that has locations in only ten states. The company is considering branching into the online retail...
-
Managing corporate Value. Can someone please help with discussing the advantages & disadvantages of economic profit & economic value added? Preferably in the manner of the CEO's perspective in...
-
In the global discourse on healthcare, the United States and England stand out as two contrasting models, each providing a distinct approach to addressing the challenges of cost , access, and...
-
2.A. Using the quotes below, answer the following questions. Exchange rate Bid Ask In New York, USD/EUR 1.2267 1.2875 In London, USD/GBP 1.6555 1.7334 2.A1. Calculate the EUR/GBP cross exchange...
-
Question 43 Part B Q1ii 20 points Save A a) A property is currently leased for $100,000 p.a. with fully recoverable outgoings. The lease has 3 years to run on the current (fixed) rent. The market...
-
Define HIPPA? What is the purpose of HIPPA? What are the 4 main rules of HIPPA?
-
Accounting for Inventories" Please respond to the following: As a Financial Accountant,determine the best type of income statement a retailer should use.Defend your suggestion. Analyze inventory...
-
Natural Gas Compositi... Forensic Linguistics - Personal Information Assessment: Part 4 Question 3 of 5 -/1 View Policies Current Attempt in Progress Suppose the 2022 income statement for McDonald's...
-
Why is it important to understand the macro-environment when making decisions about an international retail venture?
-
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...
-
The International Licensing Industry Merchandisers Association (LIMA; www.licensing.org) is an organization with offices worldwide. It supports merchandise licensing through education, networking,...
-
Suppose you are an international entrepreneur and want to open your own franchise somewhere in Europe. You decide to conduct research to identify the most promising franchise and learn how to become...
-
What are the advantages and disadvantages of licensing? LO.1
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App