Motivation

Finding a Needle in a Haystack

Suppose we have a function $f:\{0,1\}^n\rarr \{0,1\}$ with the property that for some string $a \in \{0,1\}^n$ the following holds for every string $x \in \{0,1\}^n$:

$$ f(x) = \begin{cases} 1 &\text{if }x = a \\ 0 &\text{otherwise} \end{cases} $$

Our goal is to discover what is $a$ (that is, the needle)

For this we are allowed to query the value of $f$ at specific strings. What is the value of $f$ at string $x$? That is, what is $f(x)$?

The goal is to discover what is $a$ by asking as few queries as possible.

Query Complexity

With certainty:

• $2^n-1$ queries.
• If we ask $2^n-2$ queries and the answer is 0 on every query, we would still need to determine which of the 2 remaining strings sends $f$ to 1.

Randomly (with prob $\geq \frac23$):

$$ ⁍ $$

Quantumly, we can solve this problem using

$$ ⁍ $$

queries.

→ This is a great improvement!

Suppose $n=20$.

• Classically: About $2^{20}\approx$ 1 million queries
• Quantumly: about $\sqrt{2^{20}}\approx 1$ thousand queries.