Can Grover's algorithm be used to efficiently find elements in unsorted lists?

Question

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.

2. 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.

3. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.