Grover's algorithm with W-state
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
add a comment |
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
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 , say011
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
add a comment |
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
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
algorithm entanglement grovers-algorithm
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 , say011
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
add a comment |
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 , say011
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
add a comment |
2 Answers
2
active
oldest
votes
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:
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:
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$$.
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 $$|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.
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
add a comment |
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.
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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:
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:
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$$.
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 $$|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.
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
add a comment |
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:
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:
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$$.
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 $$|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.
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
add a comment |
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:
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:
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$$.
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 $$|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.
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:
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:
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$$.
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 $$|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.
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
add a comment |
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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