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)?


1 Answer 1



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.

  • $\begingroup$ How does one prove that the tomography you describe is the optimal method for finding $i$ such that $\langle i| \psi_f\rangle = 1$? $\endgroup$
    – forky40
    Apr 2 at 21:58
  • $\begingroup$ 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. $\endgroup$
    – Danylo Y
    Apr 3 at 7:02

Your Answer

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

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