Within the context of Grover's algorithm,  if there are  $N/4$  elements marked instead of just one ($N = 2^n$) , if we run one iteration of Grover's algorithm (one phase inversion and one inversion about the mean ) and then measure, the probability that we see a marked element is 1 (simple calculation). 

I propose the following extension. 

The extension of Grover's algorithm. 

First iteration.  We use an oracle that marks  $2^{n-2} - 1$ elements (chosen at random or otherwise) plus the element x* that we are interested in.  We run one iteration of Grover and we end up with a superposition of $2^{n-2}$ marked states including  x*.

Second iteration.  We use another oracle that marks  $2^{n-4}-1$  elements (from the  $2^{n-2}-1$  above) and x*. We run another Grover iteration and we end up with a superposition of $2^{n-4}$  marked states including x*.

And so on..........

At the k-th step we use an oracle that marks $ 2^{n-2k}-1$  elements and x* and we end up with a superposition of  $2^{n-2k}$  marked states, including x*.

We continue this process for about  O(log N ) = O(n) steps. The difference is that at each iteration we use a different oracle.  

At the end, when we measure we will find x* with high probability. 

If correct (big IF here ) this would be an exponential speedup compared to Grover.

Question.  What am I missing  here? Is implementation possible?

  • $\begingroup$ Well, Grover's already operates in $O(\sqrt{N})$, so it's doubtful that there would be an exponential speedup. I also believe Grover's is asymptotically optimal... this paper might help. (If you want further community look over, it'd be helpful to have a description how this would yield speedups, so naming the states step-by-step could help) $\endgroup$
    – C. Kang
    Commented Aug 9, 2020 at 4:09
  • $\begingroup$ Note that this is not exactly Grover's algorithm, it's an extension of Grover's algorithm. This answer is interesting: cstheory.stackexchange.com/a/38551/18017 It seems to allow different oracles for each step. $\endgroup$ Commented Aug 9, 2020 at 4:33
  • $\begingroup$ I think that article isn't as relevant, as it's talking about the explicit circuit construction of the marking oracle. I thought you were asking about the asymptotic runtime of Grover's with a modified oracle? $\endgroup$
    – C. Kang
    Commented Aug 9, 2020 at 4:36
  • $\begingroup$ In the original Grover's algorithm the oracle is called once , then it's all about phase inversion and inversion about the mean, itetatively, and it can be proved optimal. I am talking about a modification of Grover's algorithm where at each step you use a different oracle, it seems possible to implement. $\endgroup$ Commented Aug 9, 2020 at 5:23
  • $\begingroup$ Actually I'm trying to take advantage of the fact that if N/4 elements in the database are marked , then the output is a superposition of only marked elements (can be easily verified by calculation). At later stages if the input is a superposition of K states and K/4 states are marked, then the output is a superposition of only marked states. I am trying to decrease the number of marked states at every steps but making sure that the state that I am reallly/actually looking for x* is always included in this set. $\endgroup$ Commented Aug 9, 2020 at 5:55

2 Answers 2


What am I missing here? Is implementation possible?

The problem with this idea is that the diffusion operation you use is supposed to match the initial state of the search. If your initial state is $|v\rangle$ then your diffusion operation is $I - 2|v\rangle\langle v|$. This operation is only cheap to implement when $|v\rangle$ is simple. For example, typically $|v\rangle$ would be $|+\rangle^{\otimes n}$ since you can implement $I - 2|+\rangle^{\otimes n}\langle +|^{\otimes n}$ using a multi-controlled NOT with some Hadamards around it.

When you switch oracles halfway through your search, the initial state for the second half of the search is the superposition of classical states meeting the oracle from the first half: $\sum_{k | P_1(k)} |k\rangle$. The problem is that it is not cheap to implement $I - 2\sum_{k | P_1(k)} |k\rangle\langle k|$. You will find that each oracle call during the second half of the search is as expensive as the whole first half of the search.

Basically, you're right that the number of oracles calls is going to decrease exponentially as the algorithm progresses but the cost of each call is going up exponentially. You end up not getting any benefit.

  • $\begingroup$ I understand that the cost of each call is going up but I have trouble understanding the exponential increase in complexity. I suspect that if the complexity of the initial states increases exponentially then the cost of the implementation of the diffusion operator would follow the same trend. In our case though the initial states are still just uniform superpositions of marked states (not all, a restricted/decreasing number of marked states ) from the previous iteration. Feedback appreciated @CraigGidney $\endgroup$ Commented Aug 11, 2020 at 7:22
  • $\begingroup$ And the way we choose a quarter of the states (including x*) from the currently active states, to be marked at the next iteration would follow a simple predefined algorithm. In other words, from an algorithmic perspective I don't see why the complexity should scale exponentially here. Considering your expertise and experience, I don't argue against your answer, I just don't get the exponential scaling argument but I have no doubt that it would have to be a complex implementation. $\endgroup$ Commented Aug 11, 2020 at 8:09
  • $\begingroup$ @CristianDumitrescu Try to implement the invert-superposition-of-marked-elements and you'll see it more clearly. $\endgroup$ Commented Aug 11, 2020 at 15:47
  • $\begingroup$ For phase inversion of a superposition of marked states we just use some Control - Z gates using as controls some ancillary qubits with certain values (at each step) that reflect the algorithm that we use to select a quarter of the active states to be marked at the next iteration. This selection process needs at most O(1) gates at each step (apart from phase inversion cost ). $\endgroup$ Commented Aug 12, 2020 at 6:36
  • $\begingroup$ For the inversion about the mean, that's when we need to invert the superposition of marked states (basically revert the unitary gates from all previous steps ), use Hadamard on n qubits, rebuild , and so on. I estimate at most a quadratic number of gates necessary, at each step. So inversion about the mean needs at most $O(n^2)$ gates at each step. In total (to run $O(n)$ iterations) at most $O(n^3)$ gates are sufficient. We might get away with $O(n^2)$ actually, but let's be safe. $\endgroup$ Commented Aug 12, 2020 at 6:37

See this video here professor Vazirani explains why you cannot have less than sqrt(N) steps if you want at least a constant probability.

  • $\begingroup$ Watch carefully what Professor Vazirani says between time:4:18 to time:4:40. That's what I am doing here, designing efficient oracles. $\endgroup$ Commented Aug 12, 2020 at 6:45
  • $\begingroup$ Unfortunately it doesn't work. $\endgroup$ Commented Aug 13, 2020 at 4:42
  • $\begingroup$ Yeah that's unfortunate but don't worry keep going. Maybe next-time you'll succeed. :) $\endgroup$
    – Heriotic
    Commented Aug 13, 2020 at 5:01

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.