[Solved]: A Black Box Algorithm

Problem Detail: 

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!

Asked By : Canada Eh

Answered By : Yuval Filmus

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

Unfortunately I can't help you with part (b).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32629

 Ask a Question

 Download Related Notes/Documents