Grover's algorithm with W-state












4














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 $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
and that the oracle inverts only state $$|001rangle$$



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?










share|improve this question
























  • 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.
    – Gustavo Banegas
    Dec 14 at 21:44












  • @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.
    – tigerjack89
    Dec 14 at 21:55












  • 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.
    – Jan Balewski
    Dec 15 at 4:22












  • @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.
    – tigerjack89
    Dec 15 at 8:53


















4














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 $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
and that the oracle inverts only state $$|001rangle$$



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?










share|improve this question
























  • 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.
    – Gustavo Banegas
    Dec 14 at 21:44












  • @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.
    – tigerjack89
    Dec 14 at 21:55












  • 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.
    – Jan Balewski
    Dec 15 at 4:22












  • @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.
    – tigerjack89
    Dec 15 at 8:53
















4












4








4







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 $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
and that the oracle inverts only state $$|001rangle$$



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?










share|improve this 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 $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
and that the oracle inverts only state $$|001rangle$$



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?







algorithm entanglement grovers-algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 15 at 4:49









Blue

5,64521352




5,64521352










asked Dec 14 at 21:24









tigerjack89

2258




2258












  • 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.
    – Gustavo Banegas
    Dec 14 at 21:44












  • @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.
    – tigerjack89
    Dec 14 at 21:55












  • 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.
    – Jan Balewski
    Dec 15 at 4:22












  • @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.
    – tigerjack89
    Dec 15 at 8:53




















  • 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.
    – Gustavo Banegas
    Dec 14 at 21:44












  • @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.
    – tigerjack89
    Dec 14 at 21:55












  • 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.
    – Jan Balewski
    Dec 15 at 4:22












  • @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.
    – tigerjack89
    Dec 15 at 8:53


















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.
– Gustavo Banegas
Dec 14 at 21:44






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.
– Gustavo Banegas
Dec 14 at 21:44














@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.
– tigerjack89
Dec 14 at 21:55






@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.
– tigerjack89
Dec 14 at 21:55














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.
– Jan Balewski
Dec 15 at 4:22






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.
– Jan Balewski
Dec 15 at 4:22














@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.
– tigerjack89
Dec 15 at 8:53






@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.
– tigerjack89
Dec 15 at 8:53












2 Answers
2






active

oldest

votes


















3














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 $$|011rangle$$ 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. $$|001rangle$$ 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 $$|001rangle$$



Grover with W5 state and standard diffusion



Here is another example with a W5 state selecting $$|00010rangle$$ while rotating around $$|00001rangle$$.
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 $$|0000rangle$$. 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.






share|improve this answer



















  • 1




    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.
    – cnada
    Dec 15 at 15:22










  • @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.
    – tigerjack89
    Dec 15 at 15:53












  • @cnada well, it works, and after thinking about it, it seems pretty obvious.
    – tigerjack89
    Dec 15 at 16:08










  • Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
    – cnada
    Dec 15 at 16:18










  • 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.
    – tigerjack89
    Dec 15 at 16:34



















2














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 | Wrangle 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.






share|improve this answer





















  • 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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
    – tigerjack89
    Dec 15 at 8:56













Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "694"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4963%2fgrovers-algorithm-with-w-state%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









3














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 $$|011rangle$$ 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. $$|001rangle$$ 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 $$|001rangle$$



Grover with W5 state and standard diffusion



Here is another example with a W5 state selecting $$|00010rangle$$ while rotating around $$|00001rangle$$.
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 $$|0000rangle$$. 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.






share|improve this answer



















  • 1




    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.
    – cnada
    Dec 15 at 15:22










  • @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.
    – tigerjack89
    Dec 15 at 15:53












  • @cnada well, it works, and after thinking about it, it seems pretty obvious.
    – tigerjack89
    Dec 15 at 16:08










  • Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
    – cnada
    Dec 15 at 16:18










  • 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.
    – tigerjack89
    Dec 15 at 16:34
















3














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 $$|011rangle$$ 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. $$|001rangle$$ 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 $$|001rangle$$



Grover with W5 state and standard diffusion



Here is another example with a W5 state selecting $$|00010rangle$$ while rotating around $$|00001rangle$$.
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 $$|0000rangle$$. 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.






share|improve this answer



















  • 1




    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.
    – cnada
    Dec 15 at 15:22










  • @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.
    – tigerjack89
    Dec 15 at 15:53












  • @cnada well, it works, and after thinking about it, it seems pretty obvious.
    – tigerjack89
    Dec 15 at 16:08










  • Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
    – cnada
    Dec 15 at 16:18










  • 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.
    – tigerjack89
    Dec 15 at 16:34














3












3








3






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 $$|011rangle$$ 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. $$|001rangle$$ 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 $$|001rangle$$



Grover with W5 state and standard diffusion



Here is another example with a W5 state selecting $$|00010rangle$$ while rotating around $$|00001rangle$$.
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 $$|0000rangle$$. 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.






share|improve this answer














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 $$|011rangle$$ 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. $$|001rangle$$ 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 $$|001rangle$$



Grover with W5 state and standard diffusion



Here is another example with a W5 state selecting $$|00010rangle$$ while rotating around $$|00001rangle$$.
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 $$|0000rangle$$. 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.







share|improve this answer














share|improve this answer



share|improve this answer








edited Dec 15 at 16:07

























answered Dec 15 at 14:04









tigerjack89

2258




2258








  • 1




    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.
    – cnada
    Dec 15 at 15:22










  • @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.
    – tigerjack89
    Dec 15 at 15:53












  • @cnada well, it works, and after thinking about it, it seems pretty obvious.
    – tigerjack89
    Dec 15 at 16:08










  • Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
    – cnada
    Dec 15 at 16:18










  • 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.
    – tigerjack89
    Dec 15 at 16:34














  • 1




    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.
    – cnada
    Dec 15 at 15:22










  • @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.
    – tigerjack89
    Dec 15 at 15:53












  • @cnada well, it works, and after thinking about it, it seems pretty obvious.
    – tigerjack89
    Dec 15 at 16:08










  • Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
    – cnada
    Dec 15 at 16:18










  • 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.
    – tigerjack89
    Dec 15 at 16:34








1




1




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.
– cnada
Dec 15 at 15:22




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.
– cnada
Dec 15 at 15:22












@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.
– tigerjack89
Dec 15 at 15:53






@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.
– tigerjack89
Dec 15 at 15:53














@cnada well, it works, and after thinking about it, it seems pretty obvious.
– tigerjack89
Dec 15 at 16:08




@cnada well, it works, and after thinking about it, it seems pretty obvious.
– tigerjack89
Dec 15 at 16:08












Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
– cnada
Dec 15 at 16:18




Yes you well illustrated the $ 2|W⟩⟨W|−I $ operator.
– cnada
Dec 15 at 16:18












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.
– tigerjack89
Dec 15 at 16:34




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.
– tigerjack89
Dec 15 at 16:34













2














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 | Wrangle 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.






share|improve this answer





















  • 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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
    – tigerjack89
    Dec 15 at 8:56


















2














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 | Wrangle 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.






share|improve this answer





















  • 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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
    – tigerjack89
    Dec 15 at 8:56
















2












2








2






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 | Wrangle 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.






share|improve this answer












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 | Wrangle 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.







share|improve this answer












share|improve this answer



share|improve this answer










answered Dec 15 at 2:16









cnada

1,794211




1,794211












  • 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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
    – tigerjack89
    Dec 15 at 8:56




















  • 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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
    – tigerjack89
    Dec 15 at 8:56


















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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
– tigerjack89
Dec 15 at 8:56






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 $$|0rangle$$ using something like $$H (2|0ranglelangle 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.
– tigerjack89
Dec 15 at 8:56




















draft saved

draft discarded




















































Thanks for contributing an answer to Quantum Computing Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4963%2fgrovers-algorithm-with-w-state%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Сан-Квентин

Алькесар

Josef Freinademetz