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}$,

\begin{equation} O_f |x\rangle |b\rangle = |x\rangle|b\oplus f(x)\rangle, \end{equation}

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 \begin{equation} \sum_{x \in \{0,1\}^{n}} \alpha_{x} |x \rangle |f(x)\rangle, \end{equation} 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.