# Learning k positions of a Boolean function with a quantum computer

Consider a Boolean function with multiple outputs $$f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$$, and consider being given oracle access to the function $$f$$. Let us denote the oracle by $$O_f$$. For an $$x \in \{0, 1\}^{n}$$ and $$b \in \{0, 1\}^{m}$$,

$$$$O_f |x\rangle |b\rangle = |x\rangle|b\oplus f(x)\rangle,$$$$

where $$\oplus$$ is the bitwise XOR operator. Now, let's say we have a quantum computer and we want to learn the value of $$f$$ in $$k$$ positions, $$x_1, x_2, \ldots, x_k \in \{0, 1\}^{n}$$. Let's also say that we know these positions beforehand.

I want to prove that for a worst case function $$f$$, it takes the quantum computer at least $$k$$ queries to $$O_f$$ to do this. If that is not true, what is the lower bound on the number of queries?

The problem is that the quantum computer can generate superpositions like $$$$\sum_{x \in \{0,1\}^{n}} \alpha_{x} |x \rangle |f(x)\rangle,$$$$ where $$\alpha_{x} \in \mathbb{C}$$, for each $$x \in \{0, 1\}^{n}$$. Do these reveal sufficient information about the function to solve the task I mentioned with less than $$k$$ queries?

What you're asking to do is at least as hard as the following problem: Given oracle access to $$f$$ such that either (a): $$f(x)=0 \, \forall \, x$$ or (b): $$\exists z: f(x) = \delta_x^z$$ for $$x,z \in \{0, \dots k\}$$. Specifically, in your problem statement set $$m=1$$ and relax the requirement from using $$n$$ qubits to instead just using a $$k$$ dimensional space. Then, "learning the value of $$f$$ in $$k$$ positions" is at least as difficult as "learning the value of $$f$$ in $$k$$ positions given that $$f$$ satisfies either (a) or (b)". The latter task requires $$\Omega(\sqrt{k})$$ queries to $$O_f$$ - for example see Theorem 9.3.2 in (Kaye, Laflamme, Mosca) - so this certainly places a lower bound on your problem in a special case.
However if the task is to just evaluate $$f(x)$$ for $$x\in\{0, \dots, k\}$$ with no additional structure on $$f$$, then I think you can just apply Holevo's theorem: each use of $$U_f$$ encodes information about $$f(x)$$ in $$m$$ qubits, from which you cannot retrieve more than $$m$$ bits of classical information (which is the number of bits required to specify the value of $$f$$). So to learn $$k$$ values of $$f$$ would require $$km$$ classical bits of information, which requires at least $$km$$ qubits or $$k$$ uses of $$U_f$$ as its currently specified.