Grover search - data representation

Question

I am a mechanical engineer conducting an undergrad research project on quantum computing so fairly new to the whole thing, forgive me if this is a silly question.

I understand the basic principles of the Grover search algorithm and am in the process of investigating some of its applications to optimisation (Grover Adaptive Search). The use of the oracle and the diffusion operator to increase the amplitude of the desired state makes sense to me, but I am confused by the physical representation of this index.

From what I understand, the process is as follows: -A unitary transformation, the oracle, is used to flip the sign of the amplitude corresponding to the desired entry. -Diffusion operator is used to amplify this amplitude, and diminish all others. -After a certain number of iterations, probability is high enough to measure the system in the computational basis and obtain the desired result.

However, I am confused as to what this measurement actually represents: in the initial superposed state, each possible outcome corresponds to an entry in the (unstructured) database. How is each data entry encoded by the qubits? Is each given state essentially just a binary string?

What determines the number of qubits needed for this process? For example, this example of Grover optimisation uses 6 qubits to find the optimum solution out of 8 possible values for a QUBO problem - but why?

Apologies for the lack of concise questions, I hope someone is able to understand what I'm getting at, else I am happy to be directed towards recommended reading. Thanks.

Answer 1

Very nice question and definitely not so obvious (and also important when thinking of Grover's algorithm in practice!)

What is typically assumed in these types of demonstrations, is that you have

1. An efficient way of encoding your data into qubits and
2. A unitary $A$ that can efficiently load your data in superposition into a quantum computer
3. An oracle unitary $U_o$ that can label your desired state efficiently by flipping the sign of the amplitude of your desired state (the same as the one you described in your question)

To understand this better, let's take a concrete example. Say you have an excel sheet with a column of $N$ names of people (Josh, Anjali, Daniela,... in that order) and an adjacent column of their corresponding ages ($26$, $41$, $32$,...) . The task: given a person's name, search through the database and find how old they are. To begin, let's re-state the same assumptions we made above, but make them more concrete to this problem:

1. There is a function $f$ that efficiently takes in any name as an input and outputs a unique bit string e.g. $f(\text{Josh}) = 01101101$. This (in principle) is actually not so different to what your excel sheet is doing anyway since ultimately everything in memory is stored as bits. For the age we will just encode in binary e.g. $32$ is just $100000$
2. Then we assume that you can construct a unitary $A$ that can efficiently create an equal superposition of the encoding of every person and their age: $$ A|00...0\rangle = \frac{1}{\sqrt{N}}\left(|f(\text{Josh})\rangle|26\rangle +|f(\text{Anjali})\rangle|41\rangle + |f(\text{Daniela})\rangle|32\rangle + ...\right)$$
3. and you can also create an oracle $U_o$ for a given name (e.g. Josh) that will efficiently label the corresponding basis state (e.g. $|f(\text{Josh})\rangle$) by giving it a negative sign

Now if you want to look up the age of Mohammed, you have two options:

1. You directly use your excel sheet and search for "Mohammed", which will take $O(N)$ time (your computer has to go through the names one-by-one to check if they match "Mohammed") or
2. you use your trusty quantum computer and your constructed unitaries $A$ and $U_o$ (which in this case labels the state $|f(\text{Mohammed})\rangle$) to perform Grover's algorithm which takes $O(\sqrt{N})$ time since it only uses $O(\sqrt{N})$ iterations of $A$ and $U_o$.

That's how it would work it in principle. Now a few remarks concerning the practicality of it:

1. To create the $A$ operator, one of the steps is to go through all the names once to encode them using the $f$ function, so this takes $O(N)$, and this might seem it defeats the purpose of the speedup. This is true if you are only looking up the age of one person. However, you only have to do this step once to create the circuit for $A$, and after that you can always straight away use Grover's algorithm with this circuit for the subsequent times you want to look up a person's age without this $O(N)$ overhead.
2. It often times will be possible to create an efficient $A$ in a technical sense i.e. with $poly(n)$ gates where $n = log_2(N)$. However creating $A$ is a) most of the time not trivial and requires some work (because it is different for every set of data), and b) even if technically efficient, in practice will still takes a lot time for a physical quantum computer to actually run (in part due to large constant overheads); often so much time that we believe that running it $O(\sqrt(N))$ times on a quantum computer will probably always take a lot more time than just looking through $N$ names on your excel sheet (see for example https://arxiv.org/pdf/2211.07629.pdf).

So for the reasons above (especially the second one), Grover's algorithm is not typically seen as something that will be a speedup in practice for searching through an unstructured database, despite being technically a speedup in the big $O$ sense. However the more interesting reason to understand Grover's algorithm is because it is often used as a subroutine in other larger algorithms for other purposes (e.g. amplitude estimation)