Can we use different oracles for each (extended) Grover iteration?

Question

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?

Answer 1

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.

Answer 2

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