2
$\begingroup$

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 carthesian product $n$ times. In this case $\{0,1\}^n$ means all the different combinations of bits you can do of size $n$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot, I just wanted to know whay it meant to put a set to a power $\endgroup$ – BrockenDuck Apr 2 '20 at 17:39
1
$\begingroup$

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$).

$\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.