Grover's algorithm with W-state
up vote
3
down vote
favorite
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
edited 1 hour ago
Blue♦
5,63511352
asked 8 hours ago
tigerjack89
1735
add a comment |
up vote
3
down vote
favorite
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
edited 1 hour ago
Blue♦
5,63511352
asked 8 hours ago
tigerjack89
1735
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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
edited 1 hour ago
Blue♦
5,63511352
asked 8 hours ago
tigerjack89
1735
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 1 hour ago
Blue♦
5,63511352
asked 8 hours ago
tigerjack89
1735
edited 1 hour ago
Blue♦
5,63511352
asked 8 hours ago
tigerjack89
1735
edited 1 hour ago
Blue♦
5,63511352
edited 1 hour ago
Blue♦
5,63511352
edited 1 hour ago
Blue♦
5,63511352
5,63511352
asked 8 hours ago
tigerjack89
1735
asked 8 hours ago
tigerjack89
1735
asked 8 hours ago
tigerjack89
1735
1735
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
up vote
1
down vote
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 as a general case.
answered 8 hours ago
Gustavo Banegas
11115
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
8 hours ago
add a comment |
up vote
1
down vote
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 3 hours ago
cnada
1,691211
add a comment |
up vote
1
down vote
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 Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.
edited 1 hour ago
Blue♦
5,63511352
answered 1 hour ago
Jan Balewski
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
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',
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
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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 as a general case.
answered 8 hours ago
Gustavo Banegas
11115
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
8 hours ago
add a comment |
up vote
1
down vote
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 as a general case.
answered 8 hours ago
Gustavo Banegas
11115
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
8 hours ago
add a comment |
up vote
1
down vote
up vote
1
down vote
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 as a general case.
answered 8 hours ago
Gustavo Banegas
11115
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 as a general case.
answered 8 hours ago
Gustavo Banegas
11115
answered 8 hours ago
Gustavo Banegas
11115
answered 8 hours ago
Gustavo Banegas
11115
answered 8 hours ago
Gustavo Banegas
11115
11115
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
8 hours ago
add a comment |
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
8 hours ago
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
8 hours ago
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
8 hours ago
add a comment |
up vote
1
down vote
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 3 hours ago
cnada
1,691211
add a comment |
up vote
1
down vote
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 3 hours ago
cnada
1,691211
add a comment |
up vote
1
down vote
up vote
1
down vote
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 3 hours ago
cnada
1,691211
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 3 hours ago
cnada
1,691211
answered 3 hours ago
cnada
1,691211
answered 3 hours ago
cnada
1,691211
answered 3 hours ago
cnada
1,691211
1,691211
add a comment |
add a comment |
up vote
1
down vote
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 Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.
edited 1 hour ago
Blue♦
5,63511352
answered 1 hour ago
Jan Balewski
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
add a comment |
up vote
1
down vote
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 Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.
edited 1 hour ago
Blue♦
5,63511352
answered 1 hour ago
Jan Balewski
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
add a comment |
up vote
1
down vote
up vote
1
down vote
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 Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.
edited 1 hour ago
Blue♦
5,63511352
answered 1 hour ago
Jan Balewski
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.
edited 1 hour ago
Blue♦
5,63511352
answered 1 hour ago
Jan Balewski
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 hour ago
Blue♦
5,63511352
edited 1 hour ago
Blue♦
5,63511352
edited 1 hour ago
Blue♦
5,63511352
5,63511352
answered 1 hour ago
Jan Balewski
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 1 hour ago
Jan Balewski
162
answered 1 hour ago
Jan Balewski
162
162
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
add a comment |
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
– Blue♦
1 hour ago
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
