Grover's algorithm traditionally inputs a phase oracle, $U_\omega$ such that $U_\omega | x \rangle = (-1)^{f(x)} | x \rangle$. The task is to find some $x$ such that $f(x) = 1$. In other words, the phase of $| x \rangle$ will be $-1$.

A natural generalization is an oracle for a complex valued function $f \colon \{ 0, 1 \}^n \mapsto \mathbb{C}$ such that $| f(x) |^2 = 1$. The oracle will be $U | x \rangle = f(x) | x \rangle$.

Is there a way to find a specific complex phase in this oracle? For example, suppose we are given the oracle

$ 00 \mapsto 1 \\ 01 \mapsto i \\ 10 \mapsto i \\ 11 \mapsto \frac{1 + i}{\sqrt{2}} $

Could we isolate $11$ with the phase $\frac{1 + i}{\sqrt{2}}$ in $O(\sqrt{N})$ steps? Could we even do it in $O(N)$ steps? Of course, $N$ is the number of states, $4$, not the number of bits here, as Grover's algorithm is traditionally written as.


1 Answer 1


In your specific case, there's a very easy way: apply $U^4$ as your Grover oracle as this converts it into a "standard" oracle with $\pm 1$ eigenvalues. But that's just a lucky coincidence of your choice of example.

If you want to deal with more complex phases, certainly one approach would be to invoke phase estimation (if you have controlled-$U$), at the cost of increasing the running time (exactly how it changes depends on some parameters like the accuracy that you need to identify the phases with, and how that changes with $N$). Then you'll have a second register with a bit value representing the phase of each component. You can implement a controlled-controlled-...-controlled-phase on that second register to put a - sign on the correct terms, then undo the phase estimation.

  • $\begingroup$ I’m not sure if I completely understand; does this method boil down to just running QPE for each basis vector as the eigenvector? (This would be $O(N^2)$ if we ignore the error term). $\endgroup$ May 17, 2023 at 12:59
  • $\begingroup$ No, you only run QPE once for each iteration of Grover (well, twice, given you have to invert it later). It does everything for all the different basis states in parallel. In terms of scaling, the scaling of the QPE part, in principle, need not have much to do with $N$. For example, if your phases are drawn from a fixed set of possibles (as in your example), the auxiliary register need only be a fixed size, and therefore uses a fixed number of calls to your oracle, keeping the $O(\sqrt{N})$ scaling of Grover. $\endgroup$
    – DaftWullie
    May 18, 2023 at 7:04

Your Answer

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

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