4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think that it does not change the original Grover's algorithm idea. Let me explain better, Grover's algorithm does make any distinction about the input or the original state. See figure attached for better representation. I think it will work in the general case. $\endgroup$ – Gustavo Banegas Dec 14 '18 at 21:44
  • $\begingroup$ @GustavoBanegas Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input. $\endgroup$ – tigerjack89 Dec 14 '18 at 21:55
  • $\begingroup$ I think, if one starts with the $W$ state which contains only $3$ out of $8$ possible $3$-bit strings then the Grover algorithm will work correctly only of the secret is one of those $3$ strings. If secret has $2$ or $3$ $1$-bits , say 011 there is no matched initial state to amplify. There is a reason Grover starts with $n$ Hadamard gates applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret. $\endgroup$ – Jan Balewski Dec 15 '18 at 4:22
  • $\begingroup$ @JanBalewski As said, obviously the oracle should only invert the sign of one of the specific states. I don't get the reason you're referring to by the way. $\endgroup$ – tigerjack89 Dec 15 '18 at 8:53
3
$\begingroup$

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:

Grover, selecting 011 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:

enter image description here

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$$. enter image description here

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 enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ It depends on what you want. I think you show what happen with an usual Grover in the case you don't have a uniform superposition. But the probability, especially in the $W5$ case is pretty low. The others have still a non-negligeable probability to get measured. But I think this is a good exercise you give to yourself. $\endgroup$ – cnada Dec 15 '18 at 15:22
  • $\begingroup$ @cnada yeah, it's quite a task, expecially because it's part of a bigger picture. But maybe I found a more clever solution. Just rethinking about it before editing my question. $\endgroup$ – tigerjack89 Dec 15 '18 at 15:53
  • $\begingroup$ @cnada well, it works, and after thinking about it, it seems pretty obvious. $\endgroup$ – tigerjack89 Dec 15 '18 at 16:08
  • $\begingroup$ Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator. $\endgroup$ – cnada Dec 15 '18 at 16:18
  • $\begingroup$ Right, but being part of a bigger circuit, it didn't work when I just inverted the W state; I have to invert all the prepared input, not just the W state. It seems obvious now. $\endgroup$ – tigerjack89 Dec 15 '18 at 16:34
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was thinking pretty much the same. Another insight, with a big maybe, is that the reflection about the superposition you've written in the first formula is implemented as a reflection about $$|0\rangle$$ using something like $$H (2|0\rangle\langle 0| - I)H.$$ Maybe, in this case, I should just use the conjugate transpose $\langle W|$ and one of the base states of the W state and invert about it? Not at home btw, I'll read the paper in a couple of hours. $\endgroup$ – tigerjack89 Dec 15 '18 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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