How to implement Grover's diffusion operator when starting with a W state?

Question

In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example the W state, and the oracle only inverts the phase of one of the basis.

To make it more concrete, let's say we have in input a $W_3$ state $$|W\rangle = \frac{1}{\sqrt{3}} (|001\rangle + |010\rangle + |100\rangle)$$ and that the oracle inverts only state $$|001\rangle$$

At this point, how can we implement the diffusion operator? In other words, how can we amplify only this state in order to obtain the right output with an high probability?

Answer 1

Say $ | \psi \rangle $ represents the uniform suposition.

Then, the Grover diffusion operator is written : $$ 2 | \psi \rangle \langle \psi | - I$$

Now to act on a subset of a superposition, you would need to implement : $$ 2 | W\rangle \langle W | - I$$

I am not sure if someone had really looked into how decompose this operation as a circuit. I guess it would be too dependent on the initial state.

This paper however shows a trick to still get the state you want with a high probability. Check section 3.3.1 . The idea is to start with $ | W \rangle $ and use a first Grover iteration to inverse amplitudes about average by only marking the target state. Then you would mark the computational basis states that are present initially in $ | \psi \rangle $ and use inversion about average again. Finally, you would continue with usual Grover iterations. They provide an example to help you visualize the effect of the steps. The target should have a high probability of being measured, even if others states not present in $ | W \rangle $ can be measured.

Answer 2

Okay I think I have a potential solution, but I don't know if it's plausible or theoretically correct.

Standard Grover's algorithm

Here is an example of the original Grover's algorithm with just three qubits; the oracle negates the phase of $$|011\rangle$$ I'll post the image also:

At the various steps you can see the probabilities and the amplitudes. In particular, after the oracle, you can see that there is precisely one state whose phase is negated, the 011 one. Then the oracle rotates all the qubits around the superposition, by amplifying the 000 state. After one repetition of Grover's algorithm we have a 78% chance of reading the right state, which grows to 94.5% after two repetition.

Grover with W3 and standard diffusion

The trick should be to rotate around one of the basis states, say the first one i.e. $$|001\rangle$$ Here is the circuit representing it:

Because we only have 3 overall possible states, a single iteration should suffice. The above circuits correctly select the state $$|001\rangle$$

Grover with W5 state and standard diffusion

Here is another example with a W5 state selecting $$|00010\rangle$$ while rotating around $$|00001\rangle$$.

As we can see, in both cases the standard diffusion selects the right amplitude with a not so huge probability

Grover with W4 and W4 conjugate transpose

A much better algorithm is the one described by this circuit

The idea is pretty similar to the original Grover algorithm. Basically, you apply the conjugate transpose of the W4 state (and in the general case, the conjugate transpose of whatever you have applied to obtain the initial state of the Grover's algorithm). In this way, you have a non zero probability of obtaining the all zero state, which in this case is $$|0000\rangle$$. Then, you invert about this state and reapply the W4 state. In this case, because we starts with 4 possible answers, the Grover's algorithm works 100% of the time.