How is the oracle in Grover's search algorithm implemented?

How is the oracle in Grover's search algorithm implemented? Ask Question Asked 8 years ago Modified 7 days ago Viewed 11k times 48 Grover's search algorithm provides a provable quadratic speed-up for unsorted database search. The algorithm is usually expressed by the following quantum circuit: In most representations, a crucial part of the protocol is the "oracle gate" U ω 𝑈 𝜔 , which "magically" performs the operation |x⟩↦(−1 ) f(x) |x⟩ | 𝑥 ⟩ ↦ ( − 1 ) 𝑓 ( 𝑥 ) | 𝑥 ⟩ . It is however often left unsaid how difficult realizing such a gate would actually be. Indeed, it could seem like this use of an "oracle" is just a way to sweep the difficulties under the carpet. How do we know whether such an oracular operation is indeed realizable? And if so, what is its complexity (for example in terms of complexity of gate decomposition)? quantum-algorithmscircuit-constructiongrovers-algorithmcomplexity-theoryoracles Share Improve this question Follow edited May 30, 2021 at 20:10 asked Mar 17, 2018 at 2:26 glS♦ 28k7 7 gold badges 43 43 silver badges 139 139 bronze badges 6 That's something I wondered about, too. In this experiment for example they hard-wire the solution into the oracle, which tastes a bit like cheating to me... –  M. Stern Commented Mar 17, 2018 at 2:48 Another great answer to this question is provided in this answer on CS Theory SE. –  glS ♦ Commented Jun 16, 2018 at 12:51 Add a comment 2 Answers Sorted by: Highest score (default) Date modified (newest first) Date created (oldest first) 34 The function f 𝑓 is simply an arbitrary boolean function of a bit string: f:{0,1 } n →{0,1} 𝑓 : { 0 , 1 } 𝑛 → { 0 , 1 } . For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as x↦{ 1, 0, if SHA-256(x)=y; otherwise, 𝑥 ↦ { 1 , if  S H A - 256 ⁡ ( 𝑥 ) = 𝑦 ; 0 , otherwise, for fixed y 𝑦 , which has no structure we can exploit for a classical search, unlike, say, the function x↦{ 1, 0, if  2 x ≡y(mod 2 2048 −1942289), otherwise, 𝑥 ↦ { 1 , if  2 𝑥 ≡ 𝑦 ( mod 2 2048 − 1942289 ) , 0 , otherwise , which has structure that can be exploited to invert it faster even on a classical computer. The question of the particular cost can't be answered in general because f 𝑓 can be any circuit—it's just a matter of making a quantum circuit out of a classical circuit. But usually, as in the example above, the function f 𝑓 is very cheap to evaluate on a classical computer, so it shouldn't pose a particularly onerous burden on a quantum computer for which everything else about Grover's algorithm is within your budget. The only general cost on top of f 𝑓 is an extra conditional NOT gate C:|a⟩|b⟩→|a⟩|a⊕b⟩ 𝐶 : | 𝑎 ⟩ | 𝑏 ⟩ → | 𝑎 ⟩ | 𝑎 ⊕ 𝑏 ⟩ where ⊕ ⊕ is xor, and an extra ancillary qubit for it. In particular, if we have a circuit F:|x⟩|a⟩|junk⟩↦|x⟩|a⊕f(x)⟩| junk ′ ⟩ 𝐹 : | 𝑥 ⟩ | 𝑎 ⟩ | junk ⟩ ↦ | 𝑥 ⟩ | 𝑎 ⊕ 𝑓 ( 𝑥 ) ⟩ | junk ′ ⟩ built out of C 𝐶 and the circuit for f 𝑓 , then if we apply it to |x⟩ | 𝑥 ⟩ together with an ancillary qubit initially in the state |−⟩=H|1⟩=(1/ 2 – √ )(|0⟩−|1⟩) | − ⟩ = 𝐻 | 1 ⟩ = ( 1 / 2 ) ( | 0 ⟩ − | 1 ⟩ ) where H 𝐻 is a Hadamard gate, then we get F|x⟩|−⟩|junk⟩ = 1 2 – √ (F|x⟩|0⟩|junk⟩−F|x⟩|1⟩|junk⟩) = 1 2 – √ (|x⟩|f(x)⟩| junk ′ ⟩−|x⟩|1⊕f(x)⟩| junk ′ ⟩). 𝐹 | 𝑥 ⟩ | − ⟩ | junk ⟩ = 1 2 ( 𝐹 | 𝑥 ⟩ | 0 ⟩ | junk ⟩ − 𝐹 | 𝑥 ⟩ | 1 ⟩ | junk ⟩ ) = 1 2 ( | 𝑥 ⟩ | 𝑓 ( 𝑥 ) ⟩ | junk ′ ⟩ − | 𝑥 ⟩ | 1 ⊕ 𝑓 ( 𝑥 ) ⟩ | junk ′ ⟩ ) . If f(x)=0 𝑓 ( 𝑥 ) = 0 then 1⊕f(x)=1 1 ⊕ 𝑓 ( 𝑥 ) = 1 , so by simplifying we obtain F|x⟩|−⟩|junk⟩=|x⟩|−⟩| junk ′ ⟩, 𝐹 | 𝑥 ⟩ | − ⟩ | junk ⟩ = | 𝑥 ⟩ | − ⟩ | junk ′ ⟩ , whereas if f(x)=1 𝑓 ( 𝑥 ) = 1 then 1⊕f(x)=0 1 ⊕ 𝑓 ( 𝑥 ) = 0 , so F|x⟩|−⟩|junk⟩=−|x⟩|−⟩| junk ′ ⟩, 𝐹 | 𝑥 ⟩ | − ⟩ | junk ⟩ = − | 𝑥 ⟩ | − ⟩ | junk ′ ⟩ , and thus in general F|x⟩|−⟩|junk⟩=(−1 ) f(x) |x⟩|−⟩| junk ′ ⟩. 𝐹 | 𝑥 ⟩ | − ⟩ | junk ⟩ = ( − 1 ) 𝑓 ( 𝑥 ) | 𝑥 ⟩ | − ⟩ | junk ′ ⟩ . Share Improve this answer Follow edited Nov 18, 2019 at 19:07 answered Mar 17, 2018 at 2:45 Squeamish Ossifrage 1,0988 8 silver badges 11 11 bronze badges Add a comment 8 Well, Grover's original paper, "Quantum mechanics helps in searching for a needle in a haystack" clearly states, it assumes that C(S) can be evaluated in a constant time. Grover's search is not concerned about the implementability, but the polynomial reduction in what's called a query complexity (how many times you consult the oracle, like a classical database) In fact, the concept of oracle in computing was proposed by Alan Turing to describe constructs for which a description on a UTM might not be realizable (Wikipedia). It is in some sense magical. But of course, coming back to your question, how do we then actually make the circuit for Grover search (or any oracular) algorithm? Do we need to know the answer in advance to search the result? Well, in some sense you need to. That is exactly what clever improvements on Grover search tries to work on, such that, we need not know the exact answer in advance, but some properties of it. Let me illustrate with an example. For the pattern recognition problem using Grover's search, if I have 4 patterns on 2 qubits (00, 01, 10, 11) and I want to mark and amplify 11, the diagonal of my oracle unitary should be like (1,1,1,-1) to take care of the pi phase shift for the solution. So, for this simple implementation, for construction the unitary, you need to know the full answer in advance. A clever improvement of pattern completion if given in the paper "Quantum pattern matching" by Mateas and Omar. In essence, it constructs as many fixed oracles as there are alphabets in the set. So for our binary string, there will be an oracle which marks out all 1s, and another that marks out all 0s. The oracles are invoked conditionally based on what I want to search. If I want to search 11, I call oracle 1 on the LSqubit, and oracle 1 again on the MSqubit. By the first oracle, I would amplify the states (01, 11), i.e. states with LSQ as 1, and in the 2nd call, it would amplify (10, 11). So as you see, 11 is the only state that gets amplified twice, ending in a higher measurement probability. Though the compiled quantum circuit would change based on what my input search pattern is, a high-level description of the quantum algorithm remains the same. You can think of the oracles as function calls based on a switch case of the alphabet set invoked for each character in the search string. Share Improve this answer Follow edited Mar 29, 2018 at 11:38 glS♦ 28k7 7 gold badges 43 43 silver badges 139 139 bronze badges answered Mar 29, 2018 at 8:19 Aritra 3331 1 silver badge 8 8 bronze badges Add a comment Start asking to get answers Find the answer to your question by asking. Ask question Explore related questions quantum-algorithmscircuit-constructiongrovers-algorithmcomplexity-theoryoracles See similar questions with these tags. The Overflow Blog Open source for awkward robots Domain expertise still wanted: the latest trends in AI-assisted knowledge for... Featured on Meta Logo updates to Stack Overflow's visual identity Linked 38 Is there a layman's explanation for why Grover's algorithm works? 38 Can a quantum computer simulate a normal computer? 17 Grover's algorithm: a real life example? 12 Grover's algorithm in a nutshell 10 What is the simplest algorithm to demonstrate intuitively quantum speed-up? 10 Does the oracle in Grover's algorithm need to contain information about the entirety of the database? 6 How do we know a "quantum function call" is worth the same amount of time as a "classical function call?" 4 How Grover's algorithm retrieves a value from an unsorted list in O( N − − √ ) 𝑂 ( 𝑁 ) steps, if the iterator is consisted of more than O(1) 𝑂 ( 1 ) steps? 5 How does an oracle function in Grover's algorithm actually work? 3 What is the point of Grover's algorithm, really? See more linked questions Related 10 Does the oracle in Grover's algorithm need to contain information about the entirety of the database? 11 Grover's algorithm: what to input to Oracle? 5 How does an oracle function in Grover's algorithm actually work? 10 Grover algorithm for a database search: where is the quantum advantage? 8 In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed? 1 How to implement *nested* Grover search (in Quirk)? 4 How Grover's algorithm retrieves a value from an unsorted list in O( N − − √ ) 𝑂 ( 𝑁 ) steps, if the iterator is consisted of more than O(1) 𝑂 ( 1 ) steps? 6 Grover's algorithm not under an oracle? Hot Network Questions For small island states, would a few nukes be enough to serve as MAD nuclear deterrence? Topology Fix for Stylized Fox Ears Best way to control a voltage divider using GPIO How should I compare two survival prediction models when a predictor’s definition drifts over time? SAT Solver Using Rubik's Cube What does "Probability content" of an interval mean? Why were two different Hebrew words used for "first" in Genesis 8:13? Vertical asymptote Add two rational numbers... esoterically Which Elder Scrolls location is this? ATTiny816 - How are these two code fragments different? Wrap bracelets around a cube Tkinter - Demonstration of the Graham-Scan (Convex hull) Arbitrary precision calculator for π in Python using only integer arithmetic "Out of malice"? Cardinality of the set of isomorphism classes of 2-generated groups Relation between sign of electrode potential and oxidising/reducing nature of species Space Knights, radiation treatment that froze their growth cells Six-Variable Logic Puzzle - How to solve with a forced logical path In "Mecha Marathon" does it matter how many times the player winds up the racer? How can I remove the handle from my faucet? How does user-configurable SRAM/flash size work? LTSpice model of IRF520 body diode How can I diff two huge (250MB+) XML files with only minor changes? Question feed By continuing to use this website, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. By exiting this window, default cookies will be accepted. To reject cookies, select an option from below. Customize settings Cookie Consent Preference Center When you visit any of our websites, it may store or retrieve information on your browser, mostly in the form of cookies. This information might be about you, your preferences, or your device and is mostly used to make the site work as you expect it to. The information does not usually directly identify you, but it can give you a more personalized experience. Because we respect your right to privacy, you can choose not to allow some types of cookies. Click on the different category headings to find out more and manage your preferences. Please note, blocking some types of cookies may impact your experience of the site and the services we are able to offer. Cookie Policy Accept all cookies Manage Consent Preferences Strictly Necessary Cookies Always Active These cookies are necessary for the website to function and cannot be switched off in our systems. They are usually only set in response to actions made by you which amount to a request for services, such as setting your privacy preferences, logging in or filling in forms. You can set your browser to block or alert you about these cookies, but some parts of the site will not then work. These cookies do not store any personally identifiable information. Targeting Cookies Targeting Cookies These cookies are used to make advertising messages more relevant to you and may be set through our site by us or by our advertising partners. They may be used to build a profile of your interests and show you relevant advertising on our site or on other sites. They do not store directly personal information, but are based on uniquely identifying your browser and internet device. Performance Cookies Performance Cookies These cookies allow us to count visits and traffic sources so we can measure and improve the performance of our site. They help us to know which pages are the most and least popular and see how visitors move around the site. All information these cookies collect is aggregated and therefore anonymous. If you do not allow these cookies we will not know when you have visited our site, and will not be able to monitor its performance. Functional Cookies Functional Cookies These cookies enable the website to provide enhanced functionality and personalisation. They may be set by us or by third party providers whose services we have added to our pages. If you do not allow these cookies then some or all of these services may not function properly. Cookie List Clear checkbox label label Apply Cancel Consent Leg.Interest checkbox label label checkbox label label checkbox label label Necessary cookies only Confirm My Choices