Need some explanation about a notation in Grover's algorithm

Question

I was reading a wonderful lecture from John Wright on Grover's algorithm. In section 2.3, he makes some simplifications :

Lastly, we are also going to assume that the data is labeled as $n$-bit boolean strings in $\{0,1\}^n$ rather than being indexed from 1 to $N$

This is the part that I have trouble understanding. Does that mean that every item in the list is labeled with a binary number ? Or is it something else, because the black box function is said to do this : $$f:\{0,1\}^n \rightarrow \{0,1\}$$ Which means it either outputs 0 or 1. But then I can't understand the first part. Could someone please explain this to me ?

Edit : thanks for all the answers, I will just explain what I didn't understand. Basically, putting a set to a power of $n$ means that you apply the Cartesian product $n$ times. In this case $\{0,1\}^n$ means all the different combinations of bits you can do of size $n$.

Answer 1

A black box function (or so-called oracle) in Grovers algrorithm produces state $|1\rangle$ when an input fulfil some requirements imposed on it (searching conditions). This means that such input is marked.

Rest of the algorithm increase probability of this input. As a result you have significantly higher probability of this input in comparison with others and this one is that you looked for.

Regarding your question on labeling. Yes, each input is labeled with binary number as the black box is a logical function. Switching from indexes 1 to $N$ (or rather 0 to $N-1$) to binary number is straighforward as any decimal number can be expressed as a binary string (see here).

Answer 2

According to this link's definition, $\{0,1\}^n$ is set of all bit strings of length n (all bit strings from $00...0$ to $11...1$). How I understand, the mentioned $f$ function takes an input bit string from $\{0,1\}^n$ set and returns an output bit string from $\{0,1\}^1 = \{0,1\}$ set ($0$ or $1$).

Answer 3

I am a noob but I will attempt an answer. I like “Davit Khachatryan”’s answer. I am writing this just to explain the function “f”. Please see below.

The key point is that they are taking existing terminology and syntax, and repurposing it for quantum computing. That is… I, for one, have not seen a set raised to a power; maybe that is just my naïvety.

$$\{0,1\}^n$$

$\{0,1\}^n$ is about the q-bits.  Think of it as being the hardware — supporting 2 states (0 or 1) — rather than the software — either a 0 or a 1.

Note that one needs to keep in mind, in all such cases, whether the starting value is 0 or 1 (for $n$).  I am taking it that it is 1, here.

In the case that $n=8$, this can be thought of as an 8-bit byte.  (Note that this represents $2^n$ possibilities).  It represents every possibility from 00000000 to 11111111.  The idea is that we compound the first bit (2 possibilities) with the second (now $2^2=4$ possibilities), and we compound that with the third bit (now $2^3=8$ possibilities), and so on.

“$n$-bit boolean strings”

The idea of a “string” here is like a string of beads [as opposed to, for instance, a text string], with each bead being (here) a qubit.  Thus for $n=8$ any one string might be, for instance, $\{0,0,1,1,1,0,1,0\}$ among the full list from 00000000 to 11111111.  The above formula represents all of these “strings” as a group.

$$f:{0,1}^n\rightarrow{0,1}$$

The core of this is the above group of $2^n$ strings (00000000 to 11111111, for $n=8$).  The formula is about a function $f$, that is about this group.

The typical example is where we are talking about something like Grover’s Algorithm, where there is one correct answer — say $\{0,0,1,1,1,0,1,0\}$ — again stipulating $n=8$.  In that case, the function $f$ will return $1$ as the output, if the input is $\{0,0,1,1,1,0,1,0\}$ and for any other input [in this example] it will return $0$.

Generally, the idea this that the function $f$ will return either a 0 or a 1, for each and every input case.  For instance, $00000000 \rightarrow 1$, $00000001 \rightarrow 0$, $00000010 \rightarrow 0$ and so on.

For my money, this is inconsistent terminology. Consider the case that $n=1$. In this case, the $\{0,1\}$ on the left represents both 0 and but the $\{0,1\}$ on the right represents either 0 or 1.  It means, for instance
$0 \rightarrow 0$ and $1 \rightarrow 0$ not $0 \rightarrow 0$, $0 \rightarrow 1$, $1\rightarrow 0$ and $1\rightarrow 1$

For instance, except that every possibility is covered.  Generally, it would mean that the function returned both 0 and 1 (separately) for every input.  In the postmodern era, no one cares about whether or not language makes sense; you just memorise what it is supposed to mean.  It is confusing, on the one hand, because your brain picks this up but on the other hand, your brain can cope with it following an arbitrary convention.

The other objection — or at least it was confusing to me — is that this thing that looks like the definition of the function… is not.  It tells you what inputs the function $f$ takes, and it tells you the format of the output it gives [glossing over the fact that it fails there, as noted], but it does not bother actually defining, for instance that $f(00111010)=1$, and that $f(10011011)=0$, and so on.  That is written with a vertical line and a list; search “discrete function”. I do not know why they use $ \rightarrow $ instead of $=$; possibly that is correct for defining the structure.

Actually this is often an “unknown” function, so it would often be correct to not specify the function in the foregoing sense.

$$f(x)$$

Given that $00111010 = 58$ thus, $f(x)$ means for instance in the case that $x = 58\%$, $f(x) = 1$… and in the case that $x = 39$, $f(x) = 0$ and so on — reprising the above example. Noting again that, in the case of an “unknown” function, the idea is that we do not actually know what any given $f(x)$ actually is.  In this case, we write $f(1)$, $f(2)$ and so on, but the represented values are not known.