# Is it possible to perform search with $O(\sqrt{N})$ copies of a "resource" state rather than an oracle?

Suppose that we wish to find $$x$$ s.t. $$f(x) = 1$$. Instead of having access to an oracle like $$U_f: |i\rangle \mapsto (-1)^{f(i)}|i\rangle$$ or $$U_f: |i\rangle|z\rangle \mapsto |i\rangle|z\oplus f(i)\rangle$$, suppose we have access to copies of a state prepared using the oracle in a simple way, e.g. $$\sum_i (-1)^{f(i)}|i\rangle$$ or $$\sum_i |i\rangle|f(i)\rangle$$.

Is there a way to use these states to perform a search algorithm that uses $$O(\sqrt{N})$$ copies of the state, where $$N$$ is the size of the search space (the range of values $$i$$ can take)?

No.

Intuitively, we don't use properties of the oracle $$U_f$$, we're just making a quantum tomography of a state which equals $$|\psi_f\rangle = \frac{1}{\sqrt{N}}\sum_i (-1)^{f(i)}|i\rangle$$ for some $$f$$ (and there are $$N$$ possible $$f$$).

Let's also denote $$|\psi_0\rangle = \frac{1}{\sqrt{N}}\sum_i |i\rangle$$.

One can use the proof of Grover's algorithm optimality to derive the bound on the number of copies needed for tomography.

There is an inequality which gives

$$2N-2\sqrt{N}\sqrt{p} - 2\sqrt{N}\sqrt{N-1}\sqrt{1-p} \le$$ $$\le \sum_f ||\psi_{f}\rangle^{\otimes K} - |\psi_{0}\rangle^{\otimes K}|^2,$$

for the average success probability $$p$$ of determining $$f$$ from $$K$$ copies of $$|\psi_{f}\rangle$$.

But $$\langle \psi_0 | \psi_f \rangle = \frac{N-2}{N},$$ and $$||\psi_{f}\rangle^{\otimes K} - |\psi_{0}\rangle^{\otimes K}|^2 = 2-2{\rm Re}\langle \psi_0 | \psi_f \rangle^K,$$ so that $$2N - 2\sqrt{N} \le N(2 - 2 (\frac{N-2}{N})^K),$$ if we want $$p$$ to be close to 1.

Thus $$\frac{1}{\sqrt{N}} \ge (\frac{N-2}{N})^K \ge 1-\frac{2K}{N} ,$$ hence $$K \ge (N-\sqrt{N})/2,$$ which means the complexity is $$O(N)$$ at least.

• How does one prove that the tomography you describe is the optimal method for finding $i$ such that $\langle i| \psi_f\rangle = 1$? Apr 2 at 21:58
• The proof of the inequality is in the appendix of that paper. Essentially, for a tomography we can't do anything better than a von Neumann measurement in some enlarged Hilbert space. Apr 3 at 7:02