What is the point of Grover's algorithm, really? - Quantum Computing Stack Exchange most recent 30 from quantumcomputing.stackexchange.com 2022-01-25T23:58:20Z https://quantumcomputing.stackexchange.com/feeds/question/17454 https://creativecommons.org/licenses/by-sa/4.0/rdf https://quantumcomputing.stackexchange.com/q/17454 2 What is the point of Grover's algorithm, really? thedude https://quantumcomputing.stackexchange.com/users/15837 2021-05-11T18:03:12Z 2021-05-13T00:51:35Z <p>This is a question desguised as a rant. There is a similar question here, <a href="https://quantumcomputing.stackexchange.com/questions/2110/whats-the-point-of-grovers-algorithm-if-we-have-to-search-the-list-of-elements">What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?</a>, but the answers have not helped me much.</p> <p>I have seen a few explanations of Grover's algorithm. I do not understand it, and the problem is not the mathematics. The story told by the sources is: given states <span class="math-container">$|x\rangle$</span> and <span class="math-container">$|\psi\rangle$</span>, there is an operator <span class="math-container">$U$</span> such that you apply it so many times to <span class="math-container">$|\psi\rangle$</span> and the result is <span class="math-container">$|x\rangle$</span>.</p> <p>Surely the point of the algorithm is not to turn <span class="math-container">$|\psi\rangle$</span> into <span class="math-container">$|x\rangle$</span>, is it?</p> <p>If it is, then it should be called Grover's transformation, not Grover's search. And for that I have a much simpler algorithm: just apply the operator <span class="math-container">$\frac{|x\rangle\langle x|}{\langle x|\psi\rangle}$</span> (it requires a single run and works with 100% efficiency). Why is this not acceptable?</p> <p>I have seen an analogy with phones. Suppose you want to find out who owns a particular phone number. Classically you must search the entire phone book (this analogy is getting out of touch with reality, but never mind that for the moment). Fine. So in the quantum setting I suppose you might have the state <span class="math-container">$|\psi\rangle$</span> which is your phone book, written in terms of energy eigenstates as <span class="math-container">$|\psi\rangle=\frac{1}{\sqrt{N}}\sum_i|\phi_i\rangle$</span>, and you might ask &quot;who is the state in there with energy <span class="math-container">$E_i$</span>?&quot;, and the answer should be <span class="math-container">$\phi_i$</span>.</p> <p>But if I must know <span class="math-container">$|\phi_i\rangle$</span> in order to build the Grover operator <span class="math-container">$U$</span>, then I see no point. Can I create <span class="math-container">$U$</span> without knowing <span class="math-container">$|\phi_i\rangle$</span> beforehand?</p> https://quantumcomputing.stackexchange.com/questions/17454/-/17455#17455 3 Answer by glS for What is the point of Grover's algorithm, really? glS https://quantumcomputing.stackexchange.com/users/55 2021-05-11T18:47:04Z 2021-05-11T19:08:49Z <p>The point is indeed to &quot;turn <span class="math-container">$|\psi\rangle$</span> into <span class="math-container">$|x\rangle$</span>&quot;. More precisely, the point is to transform a given <span class="math-container">$|\psi\rangle$</span> into some (unknown) state <span class="math-container">$|x\rangle$</span> which is defined as satisfying some properties (<em>i.e.</em> it is &quot;marked&quot; by some oracle). Even more precisely, the point is to transform <span class="math-container">$|\psi\rangle$</span> into some state which, when measured, gives you a string that with good probability is the <span class="math-container">$x$</span> which solves whatever problem you are facing.</p> <p>You can call it &quot;Grover's transformation&quot; if you wish. It is indeed a &quot;transformation&quot;; but then again, any algorithm is a transformation in the same sense. It makes sense to call it a &quot;search algorithm&quot; when you think about the result it gives you. If you use it to, say, find the solution to some <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow noreferrer">SAT problem</a>, it gives you as answer some string that satisfies specific properties. You can think of these questions as more complex versions of something like &quot;<em>find the 3-bit string such that the sum of the first two bits is 0</em>&quot;. This looks very much like a &quot;search&quot; to me.</p> <p>Note that the solution to the &quot;search&quot; is obtained when you <em>measure</em> the final state, and thus obtain a classical string out of it. In other words, the &quot;state transformation&quot; part of the algorithm is such that the state it gives you, when measured, encodes the solution to the search problem.</p> <blockquote> <p>Why not just apply the operator <span class="math-container">$|x\rangle\!\langle x|$</span>?</p> </blockquote> <p>That would be useless. &quot;Applying the operator <span class="math-container">$|x\rangle\!\langle x|$</span>&quot; means to measure the state <span class="math-container">$|\psi\rangle$</span> in some measurement basis containing <span class="math-container">$|x\rangle$</span>. This amounts to asking the question &quot;what is the probability that the initial state <span class="math-container">$|\psi\rangle$</span> is found in the state <span class="math-container">$|x\rangle$</span> (assuming some suitable choice of measurement basis)?&quot;. That's not what you want. The goal is to <em>find</em> an <span class="math-container">$|x\rangle$</span> such that <span class="math-container">$f(x)=1$</span> for some given function <span class="math-container">$f$</span> (called the &quot;oracle&quot; in this context). You <em>do not</em> know what this <span class="math-container">$x$</span> is, otherwise you'd already know the solution to the problem.</p> <blockquote> <p>But if I must know <span class="math-container">$|ϕ_i⟩$</span> in order to build the Grover operator <span class="math-container">$U$</span>, then I see no point. Can I create <span class="math-container">$U$</span> without knowing <span class="math-container">$|ϕ_i⟩$</span> beforehand?</p> </blockquote> <p>Yes, that's the point. The oracle encodes the <em>constraints</em> that you want the solution to satisfy, not the solution itself.</p> <p>If I tell you to find the needle in the haystack, do you know beforehand where the needle is? No, you know that you need to search through many locations until you find the location containing the needle. It's the same thing: in this analogy, each <span class="math-container">$|x\rangle$</span> is a position potentially containing the needle, and the oracle is the function that checks whether a given position contains the needle.</p> <p>This has been discussed multiple times in the site, see <em>e.g.</em> <em><a href="https://quantumcomputing.stackexchange.com/q/1419/55">Does the oracle in Grover&#39;s algorithm need to contain information about the entirety of the database?</a></em>.</p> https://quantumcomputing.stackexchange.com/questions/17454/-/17456#17456 1 Answer by Craig Gidney for What is the point of Grover's algorithm, really? Craig Gidney https://quantumcomputing.stackexchange.com/users/119 2021-05-11T19:50:09Z 2021-05-11T19:50:09Z <blockquote> <p>Can I create <span class="math-container">$U$</span> without knowing <span class="math-container">$|\phi_i\rangle$</span> beforehand?</p> </blockquote> <p>Yes. For example, you could write down a sudoko grid with a few random hints, define <span class="math-container">$|\phi_i\rangle$</span> to be any solution (if one exists), and <span class="math-container">$U$</span> could check if a given filling of the grid is a solution matching the hints.</p> https://quantumcomputing.stackexchange.com/questions/17454/-/17485#17485 0 Answer by benrg for What is the point of Grover's algorithm, really? benrg https://quantumcomputing.stackexchange.com/users/3030 2021-05-13T00:51:35Z 2021-05-13T00:51:35Z <p>Grover's algorithm is a <a href="https://en.wikipedia.org/wiki/Circuit_satisfiability_problem" rel="nofollow noreferrer">CIRCUIT-SAT</a> solver. Given a circuit with <span class="math-container">$n$</span> boolean inputs, it finds a satisfying input in <span class="math-container">$O(2^{n/2})$</span> evaluations of the circuit in the worst case, which is interesting because no classical algorithm is known that does better than <span class="math-container">$O(2^n)$</span>, and it's conjectured that none exists.</p> <p>Lov Grover decided to call it a database search algorithm in his original paper, and there's a tendency for arbitrary terminological choices made in pioneering papers to become standards whether they make sense or not. So I suppose it will forever be taught as a database search algorithm, and students will forever be confused by it as they quite reasonably wonder how this &quot;database&quot; is encoded in the circuit and why you wouldn't just index it for <span class="math-container">$O(n)$</span> lookup while you're at it.</p> <p>Don't try to understand the &quot;database&quot;. Just forget about it. Grover's algorithm is a CIRCUIT-SAT solver.</p>