2
$\begingroup$

From my understanding, Grover's algorithm is often misinterpreted as being able to find elements in lists. And when people try to understand the oracle function in terms of this, it leads to confusion.

I understand that Grover's algorithm finds the input to a function that returns true in $\sqrt{n}$ steps. (And that this is the more general purpose where it's useful.) But I don't see why this can't be used to also efficiently find elements in unsorted lists.

For example, if the function is $x == 5$ (that is, it returns TRUE when the input is 5, and false otherwise) and I have the list $\{4, 8, 2, 3, 1, 9, 10, 12, 5 \}$ (so no duplicates of 5). Grover's algorithm CAN find this in 3 steps, no?

I guess the issue is that the efficiency of writing this function to return true if x==5 and return false if x $\neq 5$ is costly enough that you don't actually get speedup (similar to what is said here)?

EDIT: To try to make my question more clear. In a nutshell it is: "What exactly in the math of grover's algorithm prevents it from being used to efficiently find an element in an unsorted list?"

Possible answers:

  1. Based on this question: Grover's cannot efficiently find elements in lists because the oracle specifically requires knowing where the state is in the database, and by doing so makes it impossible to actually find something that was not already known.

My confusion: Is it really impossible to write an oracle as I've written above that simply checks for a value in a set of inputs? (If what I wrote above isn't clear, then I think it's better explained in @gIS's answer here. ) So there really is no algorithmic way of constructing a function to find a specific element in a list? Seems far fetched to say that it's impossible for a quantum computer to do this.

  1. Grover's algorithm isn't efficient because encoding the classical information to quantum data is slow and makes the overall process inefficient.

My confusion: then if everything is uploaded at first in a sort of "QuantumRAM" you only have to deal with this overhead once - so it would be efficient if multiple searches are performed.

  1. Grover's algorithm isn't efficient because the oracle function that would check for the actual desired value in the list is prohibitively costly.

My confusion: Can this be made a bit more explicitly if it's true? How costly is such a function to check an element in a list. It seems very counterintuitive such a simple function would be too costly to be worth implementing.

$\endgroup$
4
  • 2
    $\begingroup$ One downvote for no specified reason? $\endgroup$ Jan 10 at 23:37
  • $\begingroup$ What precisely is the question? $\endgroup$ Jan 12 at 0:18
  • 1
    $\begingroup$ Except for that, I fully share your sentiment: I never understood why Grover is marketed as "searching databases". It is about a quadratic speedup for general NP problems (i.e. find a satisfying assignment f(x)=1 to an (efficiently computable) function). $\endgroup$ Jan 12 at 0:20
  • $\begingroup$ @NorbertSchuch, I added an edit to try to make it more clear. Basically, I'm just trying to understand if it's even possible to use Grovers algorithm to find elements in unsorted lists. And if it's possible, why exactly is there no speedup? $\endgroup$ Jan 12 at 1:24
3
$\begingroup$

There are two issues here. The first is the input requirements of Grover's algorithm. Let's take your specified example. You've got a list, say $\{4,8,2,3,1,9,10,12,5\}$, and you want to know if the element 5 is in it. In order to run Grover's search, you need a unitary operation that is capable of producing $$ U|0\rangle=(|4\rangle+|8\rangle+|2\rangle+|3\rangle+|1\rangle+|9\rangle+|10\rangle+|12\rangle+|5\rangle)/3. $$ Let me emphasise that you do not know this list to the extent of being able to use it to create the unitary, otherwise you'd already know if 5 were in it. So, this seems like a rather big assumption.

Furthermore, it depends on what you mean by "efficiently". Normally, we'd say that if your list has $n$ elements, and your running time is $O(\sqrt{n})$, that is inefficient because we really measure running time as a function of the number of bits require to represent an element of the list, $N=\lceil\log_2(n)\rceil$, and hence the number of oracle calls is $\sim 2^{N/2}$, i.e. exponential (The running time of each oracle call in this case is $O(N)$, giving an overall run time of $~N2^{N/2}$). The key about Grover's is not that it gives you an efficient algorithm, but that the square root improvement in running time is actually really valuable.

$\endgroup$
6
  • $\begingroup$ Thanks for the answer, but I don't quite understand why the number of oracle calls is $2^{N/2}$. I get that the size of the Hilbertspace is $2^N$ but if I don't see how that connects with the oracle calls. Is the point that the possibility space so large that checking everything in the possibility space is costly? (Then isn't that just a mistake in how many qubits are being considered?) $\endgroup$ Jan 11 at 19:56
  • $\begingroup$ How would such a unitary help (and what does the separate equation actually say)? Does it allow to implement a reflection about the "database state"? Or do you actually mean a unitary which implements this reflection? $\endgroup$ Jan 12 at 0:22
  • $\begingroup$ @NorbertSchuch Ah, thanks for spotting the typo. Yes, a unitary that allows the reflection to be implemented. $\endgroup$
    – DaftWullie
    Jan 12 at 7:49
  • $\begingroup$ @StevenSagona The number of calls is exactly the same as you stated them. There's no mystery there. The issue is simply that I've expressed the function in terms of $N$ instead of $n$. This is because the polynomial/exponential issue of efficiency is decided based on the number of (qu)bits ($N$) not the size of the search space ($n$). $\endgroup$
    – DaftWullie
    Jan 12 at 7:51
  • $\begingroup$ @DaftWullie Still don't get it how preparing a state $|\psi\rangle$ would allow you to reflect about it. Then final unitary you want would be $U=I-2|\psi\rangle\langle\psi|$. $\endgroup$ Jan 12 at 9:39
2
$\begingroup$

If I understand your question correctly, you want to know if you could use Grover's Algorithm to determine whether an unsorted list contains an element or not.

Grover's Algorithm works by amplifying the amplitude of the state that produces the desired output. In this case, you are describing a quantum operation that "returns true" (i.e. flips a target qubit) when the input "==5" (perhaps the input is a four-qubit register and 5 is encoded with $|0101\rangle$). That is very easy to implement.

Where the question becomes trickier is when you introduce the concept of an "unsorted list". If you want to perform a search with Grover's Algorithm, you would need to encode the elements of this list in a qubit register (e.g. $\frac{1}{\sqrt{n}}(|4\rangle + |8\rangle + ...)$). After running the algorithm for $\frac{\pi\sqrt{n}}{4}$ iterations and measuring the input register, you will get $|5\rangle$ with high probability if it was part of the original superposition.

So, you still need to go though all the elements of the list and encode it into the qubit register, which is $O(n)$, so you don't get a speedup. That is, unless the list is already encoded as a quantum register.

Tl;dr: No, this is not a good application of Grover's Algorithm.

$\endgroup$
3
  • 1
    $\begingroup$ Okay but if the information was already encoded, then would it experience speedup? Martin in one of the answers is suggesting that the oracle is the part that slows things down. $\endgroup$ Jan 11 at 19:57
  • $\begingroup$ Respectfully, I think you are confused about how information is encoded in a quantum computer. It is very different than a classical computer. An "unsorted list" is a classical concept. You have to be clear about what it means in a quantum context. If the information is already encoded as I described, then you may be able to answer the specific question of whether the "list" contains an "element" with a speedup. The oracle doesn't necessarily "slow things down" – it depends on the complexity of the oracle. $\endgroup$
    – R. Preston
    Jan 12 at 21:13
  • $\begingroup$ Of course I have to emphasize that encoding a list of numbers into a qubit register is O(n). I'm not sure how you plan to get around this. $\endgroup$
    – R. Preston
    Jan 12 at 21:18
0
$\begingroup$

Just to add few words. The Grover algorithm complexity is $O(\sqrt{n})$ but the probem is complexity of the oracle. In this case, if you want to mark number 5, it can be done easily with logical function $f(5) = 1$ and $f(x) = 0$ for $x \ne 5$. Such function can be implemented with four-input AND gate, which is CCCC-NOT gate in quantum world. This gate can be composed of Toffoli gates. You would need three Toffoli gates to make implement 4 input AND and two Toffoli gate to uncompute ancilla qubits. As you probably know, Toffoli gates increases complexity of a quantum circuit and in current state of quantum computer development such circuit would suffer heavily from decoherence.

$\endgroup$
2
  • $\begingroup$ Ignoring decoherence for now, Grover's reduces the total number of times this function you described is called. Do you have an idea how fast it would be to check all of the elements for this value? (with and without Grovers?) That is, what would the speedup/slowdown be: $O(?)$ $\endgroup$ Jan 11 at 20:10
  • $\begingroup$ @StevenSagona: Sorry, I am afraind I cannot provide detailed analysis. Just only these "ideas". $\endgroup$ Jan 12 at 11:45
0
$\begingroup$

The problem is that you simplified the question too much, to the point of uselessness. What does it even mean to "find" the element 5? What are you searching for? Don't you already know that the answer is 5?

Perhaps what you have in mind is a phone-book search, where you have an unsorted database of pairs "person"-"phone number"? In this case the question makes sense: your oracle recognizes the "person", and with Grover you find their associated "phone number". The "possible answer 1" poses no obstacle, an oracle can be easily constructed that returns 1 if the person is the one you want, and you don't need to know their phone number in order to construct the oracle. The "possible answer 3" also poses no obstacle, the oracle is obviously efficient.

There are several problems with making Grover work here, though. The first is "possible answer 2": you need first to read this data, which takes time $n$, which is the same time you need to actually find the phone number, and is anyway larger than Grover's $\sqrt{n}$.

You mention the possibility of pre-loading this data, so that Grover would be actually useful if you make several queries to the database. It's not. First of all, you need to create efficiently the huge superposition of all the database entries. How are you going to do that efficiently? In the case where Grover is actually useful you just need to create a superposition of all bitstrings, and that is very easy to do, you just apply a Hadamard in each qubit individually.

Furthermore, if you want to do several queries to your database, what you should actually do is sort it. It takes time $O(n\log n)$, and subsequent queries take time $O(\log n)$ each. With Grover you'd need time $O(n)$ to read the database, and subsequent queries would take time $O(\sqrt{n})$ each.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.