# A Black Box Algorithm

I'm taking an introductory quantum computations class and I am attempting to solve the following question(s), but we haven't touched on black box algorithms like this in class, and I honestly don't know how to solve the question at all. Would it be possible to help me through the steps?

Question. Consider the set of all functions $f:\{0,1\}^n \rightarrow \{0,1\}$ that are of the form $f(x_1,x_2,...,x_n)=x{_j{_1}} \oplus x{_j{_2}} \in \{1,2,...,n\}$ with $j_1 \neq j_2$. Suppose we are given such a function as a black box (without information about $j_1,j_2$ and our task is to determine the set $\{j_1,j_2\}$.

(a) Show that any classical algorithm must male at least $\Omega(log(n))$ queries to f to solve this problem exactly. (We have used the $\Omega$ notation to give lower bounds, defined as following: Suppose $f(n), g(n)$ are functions form the positive integers to the real numbers. Then we say $f(n) \in \Omega(g(n))$ if there exists a positive, real c, and an integer $n_o$ such that for all $n>n_o, f(n)\geq cg(n)$.

We are also given the following hint: Note that the data that a k-query classical algorithm obtains is a k-bit string. Next, consider how big k needs to be so that there are enough k-bit strings to be uniquely assigned to each $\{j_1,j_2\}$.

(b) Give a quantum algorithm in the black box model that solves ths problems exactly with a single query to f.

Any possible assistance would be amazing. Thank you!

• Which part are you stuck at? Part (a)? Part (b)? If stuck at part (a), have you tried following the hint? – Yuval Filmus Nov 3 '14 at 3:38
• I'm stuck at both (although I assume part (a) is required to complete part (b)). I'm not really certain as to how to apply the hint in this case. – Canada Eh Nov 3 '14 at 3:43
• Why do you want us to "help you through the steps" if you admittedly have not covered the necessary material (in class) yet? – Raphael Nov 3 '14 at 7:39
• I don't think part (a) is required to complete part (b). The point of the exercise is to give an example in which quantum is provably more efficient than classical. – Yuval Filmus Nov 3 '14 at 15:24
• My apologies. I didn't appropriately express my knowledge of black box algorithms. We HAVE discussed them in class, but we've never actually attempted to solve anything of this sort (we've done different applications of the Hadamard, but further than that is where I start to get a little confused). I'm confused about how to approach the problem overall. – Canada Eh Nov 3 '14 at 21:49

Regarding part (a): just like in the classical lower bound for sorting, any black box algorithm which queries $f$ can be described as a binary decision tree whose leaves contain the correct answer $\{j_1,j_2\}$. Every pair $\{j_1,j_2\}$ is possible, so the tree must have at least $\binom{n}{2}$ leaves, hence it must have height at least $\log_2 \binom{n}{2} = \Omega(\log n)$.
If you don't understand the argument, look up the $\Omega(n\log n)$ lower bound on sorting in the comparison model (also known as the decision tree model).
Can we do it with $O(\log n)$ queries? Suppose for simplicity that $n = 2^k$ is a power of $2$. If we feed the algorithm the bit string $x(b_{k-1}\ldots b_0) = b_i$ then we get the $i$th bit of $j_1 \oplus j_2$, so using $\log_2 n$ queries we can find $j_1 \oplus j_2$. Suppose for simplicity that $j_1 \oplus j_2 = 1$. If we feed the algorithm the bit string defined by $x(b_{k-1}\ldots b_1 0) = 0$, $x(b_{k-1}\ldots b_1 1) = b_i$, then we recover the $i$th bit of $j_1$ (or $j_2$), so using $\log_2 n - 1$ more queries, we recover $j_1,j_2$. In total, we used $2\log_2 n - 1$ queries, which practically matches the lower bound $\log_2 n + \log_2 (n-1) - 1$.