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!