# Grover's algorithm for multiple solutions complexity

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...

• Can you clarify what kind of object $X$ is? I'm not sure what problem you are trying to solve. Commented Feb 6, 2023 at 12:04
• 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. Commented Feb 6, 2023 at 13:52