I'm reading Nielsen&Chuang book (for myself) and I'm completely stuck with one of the problems, 6.3(Database retrieval):

Given a quantum oracle which returns $\left|{k, y \bigoplus X(k)}\right>$ given an $n$ qubit query (and one scratchpad qubit) $\left|{k, y}\right>$, show that with high probability, all $N = 2^{n}$ bits of $X$ can be obtained using only $N/2 + \sqrt(N)$ queries.

The obvious way to obtain all $X$ bits is: we run the quantum counting algorithm to find number of 1's in our $X$ and then we run a loop: find random $\left|{k}\right>$ for which ${X(k)=1}$ via standard Grover algorithm, augment our oracle to ignore decision $\left|{k}\right>$, find next one and so on. It must work (for cases when there are more 1's then 0's we just add $NOT$ in our oracle scratchpad qubit), but the problem is: total number of oracle queries is more then $N/2+\sqrt{N}$. The worst-case scenario is (almost) balanced $X$ function, so we will run our algorithm $N/2$ times. Each iteration uses $\lceil\frac{\pi}{4}\sqrt{\frac{N}{t}}\rceil$ oracle queries, where $t$ is remaining 1's total, so even for $t=\frac{N}{2}$, the simplest iteration with minimum queries, this number will be 2(because $4<\pi*\sqrt{2}<8$), and since we have $\frac{N}{2}$ iterations, total queries count will be greater then $\frac{N}{2}*2=N$(actually if we do some math we could estimate number of queries as something like $\frac{\pi^4+48}{96}N$ for rather big $N$, or slightly greater than $\frac{3}{2}N$).

The question is: am I missing something? Or maybe am I somehow misunderstanding this problem? I'm really confused because if Grover's algorithm is a key here than it must be possible to retrieve single solution for just one oracle query (on average for multi-solution case), which is contradicting to way it works...

  • $\begingroup$ Can you clarify what kind of object $X$ is? I'm not sure what problem you are trying to solve. $\endgroup$
    – Sam Jaques
    Commented Feb 6, 2023 at 12:04
  • $\begingroup$ I think that $X$ is just binary function, but maybe I'm wrong(especially because of problem's name, "Database retrieval"). The second paragraph(Given a quantum oracle...) is exact quotation from Nielsen&Chuang book, no additional explanations about $X$ given there. $\endgroup$ Commented Feb 6, 2023 at 13:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.