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(nlog 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 $2log_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
