Grover's diffusion on subset of input spaceGrover's algorithm: where is the list?Clarification needed regarding quantum “black-box” circuitsGrover's algorithm: a real life example?Why does Grover's search invert about the mean?Grover's algorithm with W-stateWhat happens in Deutsch algorithm if I use equal input bits?Is the $|-rangle$ state the only one that can do the trick for Grover's algorithm?N&C quantum circuit for Grover's algorithmGrover's algorithm returns skewed probability distributionSuccess probability in Grover's algorithm where there are multiple targets
Is my Rep in Stack-Exchange Form?
Cascading Repair Costs following Blown Head Gasket on a 2004 Subaru Outback
Alphabet completion rate
Do equal angles necessarily mean a polygon is regular?
Do sudoku answers always have a single minimal clue set?
Find smallest index that is identical to the value in an array
Correct spacing in the alignat*-environment
The use of "I" and "we" used in the same sentence and other questions
Does the Paladin's Aura of Protection affect only either her or ONE ally in range?
What is this opening trap called, and how should I play afterwards? How can I refute the gambit, and play if I accept it?
Does the posterior necessarily follow the same conditional dependence structure as the prior?
How to positively portray high and mighty characters?
What determines the "strength of impact" of a falling object on the ground, momentum or energy?
Fedora boot screen shows both Fedora logo and Lenovo logo. Why and How?
Procedurally generate regions on island
In the Marvel universe, can a human have a baby with any non-human?
Why does Darth Sidious need bodyguards?
Why would people reject a god's purely beneficial blessing?
What is the line crossing the Pacific Ocean that is shown on maps?
Simple object validator with a new API
STM Microcontroller burns every time
Is there a short way to compare many values mutually at same time without using multiple 'and's?
Why is C++ initial allocation so much larger than C's?
Is it possible to buy a train ticket CDG airport to Paris truly online?
Grover's diffusion on subset of input space
Grover's algorithm: where is the list?Clarification needed regarding quantum “black-box” circuitsGrover's algorithm: a real life example?Why does Grover's search invert about the mean?Grover's algorithm with W-stateWhat happens in Deutsch algorithm if I use equal input bits?Is the $|-rangle$ state the only one that can do the trick for Grover's algorithm?N&C quantum circuit for Grover's algorithmGrover's algorithm returns skewed probability distributionSuccess probability in Grover's algorithm where there are multiple targets
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Is it possible to run grover's diffusion step on a subset of the possible input space?
By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of all states.
Let's say I have a 2 qubit system in a equal superposition of states $left|00right>$, $left|01right>$ and $left|10right>$, but have exactly a 0 probability of measuring a $left|11right>$. Also, let's say I have a function $f$ that only outputs a 1 for the input 00. Is there a modification to Grover's where I can do the diffusion only on the $left|00right>$, $left|01right>$ and $left|10right>$ states and leave the $left|11right>$ state unchanged?
If that is possible, does it speedup the diffusion? Say I have a state with $n$ qubits but $2^x$ non-zero states where $x < n$, does this modified grover's algorithm still run in $mathcal O(2^n/2)$, or can it run in $mathcal O(2^x/2)$?
algorithm grovers-algorithm
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
$endgroup$
add a comment |
$begingroup$
Is it possible to run grover's diffusion step on a subset of the possible input space?
By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of all states.
Let's say I have a 2 qubit system in a equal superposition of states $left|00right>$, $left|01right>$ and $left|10right>$, but have exactly a 0 probability of measuring a $left|11right>$. Also, let's say I have a function $f$ that only outputs a 1 for the input 00. Is there a modification to Grover's where I can do the diffusion only on the $left|00right>$, $left|01right>$ and $left|10right>$ states and leave the $left|11right>$ state unchanged?
If that is possible, does it speedup the diffusion? Say I have a state with $n$ qubits but $2^x$ non-zero states where $x < n$, does this modified grover's algorithm still run in $mathcal O(2^n/2)$, or can it run in $mathcal O(2^x/2)$?
algorithm grovers-algorithm
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
$endgroup$
1
$begingroup$
It seems like with your toy example you want to have a superposition of two qubits having the $mathsfNAND$ being equal to $1$. You could calculate the $mathsfNAND$ and post-select on the $mathsfNAND$ of the two qubits being $1$, then run Grover's algorithm on the $mathsfNOR$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $mathsfNOR$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $mathsfNOR$ being $1$ and another output being $mathsfNAND$ being $1$?
$endgroup$
– Mark S
Jun 9 at 0:53
add a comment |
$begingroup$
Is it possible to run grover's diffusion step on a subset of the possible input space?
By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of all states.
Let's say I have a 2 qubit system in a equal superposition of states $left|00right>$, $left|01right>$ and $left|10right>$, but have exactly a 0 probability of measuring a $left|11right>$. Also, let's say I have a function $f$ that only outputs a 1 for the input 00. Is there a modification to Grover's where I can do the diffusion only on the $left|00right>$, $left|01right>$ and $left|10right>$ states and leave the $left|11right>$ state unchanged?
If that is possible, does it speedup the diffusion? Say I have a state with $n$ qubits but $2^x$ non-zero states where $x < n$, does this modified grover's algorithm still run in $mathcal O(2^n/2)$, or can it run in $mathcal O(2^x/2)$?
algorithm grovers-algorithm
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
$endgroup$
Is it possible to run grover's diffusion step on a subset of the possible input space?
By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of all states.
Let's say I have a 2 qubit system in a equal superposition of states $left|00right>$, $left|01right>$ and $left|10right>$, but have exactly a 0 probability of measuring a $left|11right>$. Also, let's say I have a function $f$ that only outputs a 1 for the input 00. Is there a modification to Grover's where I can do the diffusion only on the $left|00right>$, $left|01right>$ and $left|10right>$ states and leave the $left|11right>$ state unchanged?
If that is possible, does it speedup the diffusion? Say I have a state with $n$ qubits but $2^x$ non-zero states where $x < n$, does this modified grover's algorithm still run in $mathcal O(2^n/2)$, or can it run in $mathcal O(2^x/2)$?
algorithm grovers-algorithm
algorithm grovers-algorithm
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
edited Jun 9 at 8:14
Sanchayan Dutta
7,8774 gold badges16 silver badges62 bronze badges
7,8774 gold badges16 silver badges62 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
asked Jun 8 at 20:24
Chase RobertsChase Roberts
312 bronze badges
312 bronze badges
1
$begingroup$
It seems like with your toy example you want to have a superposition of two qubits having the $mathsfNAND$ being equal to $1$. You could calculate the $mathsfNAND$ and post-select on the $mathsfNAND$ of the two qubits being $1$, then run Grover's algorithm on the $mathsfNOR$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $mathsfNOR$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $mathsfNOR$ being $1$ and another output being $mathsfNAND$ being $1$?
$endgroup$
– Mark S
Jun 9 at 0:53
add a comment |
1
$begingroup$
It seems like with your toy example you want to have a superposition of two qubits having the $mathsfNAND$ being equal to $1$. You could calculate the $mathsfNAND$ and post-select on the $mathsfNAND$ of the two qubits being $1$, then run Grover's algorithm on the $mathsfNOR$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $mathsfNOR$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $mathsfNOR$ being $1$ and another output being $mathsfNAND$ being $1$?
$endgroup$
– Mark S
Jun 9 at 0:53
1
1
$begingroup$
It seems like with your toy example you want to have a superposition of two qubits having the $mathsfNAND$ being equal to $1$. You could calculate the $mathsfNAND$ and post-select on the $mathsfNAND$ of the two qubits being $1$, then run Grover's algorithm on the $mathsfNOR$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $mathsfNOR$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $mathsfNOR$ being $1$ and another output being $mathsfNAND$ being $1$?
$endgroup$
– Mark S
Jun 9 at 0:53
$begingroup$
It seems like with your toy example you want to have a superposition of two qubits having the $mathsfNAND$ being equal to $1$. You could calculate the $mathsfNAND$ and post-select on the $mathsfNAND$ of the two qubits being $1$, then run Grover's algorithm on the $mathsfNOR$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $mathsfNOR$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $mathsfNOR$ being $1$ and another output being $mathsfNAND$ being $1$?
$endgroup$
– Mark S
Jun 9 at 0:53
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm.
If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$left |phiright> = frac1sqrtNsum_x in Sleft|xright>$$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $left|psiright>$: $$2left|psiright>left<psiright| - I$$
into:
$$2left|phiright>left<phiright| - I$$
A common way of composing the Grover diffusion operator for an $n$-qubit system without fancy gates is to make it out of two Hadamards and some implementation of the diagonal matrix $2left|0right>left<0right| - I$ via:
$$H^otimes n(2 left|0right>left<0right| - I)H^otimes n$$.
To get our new diffusion operator, we just need to replace the left Hadamard gate with a gate $B$ and the right Hadamard with $B^*$ (if they are not the same) where $Bleft|0right> = left|phiright>$
From a fully general perspective, if your subset selection method is weird, like all prime-numbered states, I suspect realistically implementing $B$ (and having $left|phiright>$ in the first place) on, say, IBM Q may be difficult to the point of voiding the advantage of the algorithm, since you'd have to include individual gates to zero the probability of all the specific irrelevant states in the implementation of $B$.
Assuming no difficulty with $B$, it will run in $mathcalO(sqrtN)$ with your new $N$. The ideal stopping point will also still be $approx fracpi4sqrtN$ iterations.
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
$endgroup$
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
add a comment |
Your Answer
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%2f6383%2fgrovers-diffusion-on-subset-of-input-space%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm.
If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$left |phiright> = frac1sqrtNsum_x in Sleft|xright>$$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $left|psiright>$: $$2left|psiright>left<psiright| - I$$
into:
$$2left|phiright>left<phiright| - I$$
A common way of composing the Grover diffusion operator for an $n$-qubit system without fancy gates is to make it out of two Hadamards and some implementation of the diagonal matrix $2left|0right>left<0right| - I$ via:
$$H^otimes n(2 left|0right>left<0right| - I)H^otimes n$$.
To get our new diffusion operator, we just need to replace the left Hadamard gate with a gate $B$ and the right Hadamard with $B^*$ (if they are not the same) where $Bleft|0right> = left|phiright>$
From a fully general perspective, if your subset selection method is weird, like all prime-numbered states, I suspect realistically implementing $B$ (and having $left|phiright>$ in the first place) on, say, IBM Q may be difficult to the point of voiding the advantage of the algorithm, since you'd have to include individual gates to zero the probability of all the specific irrelevant states in the implementation of $B$.
Assuming no difficulty with $B$, it will run in $mathcalO(sqrtN)$ with your new $N$. The ideal stopping point will also still be $approx fracpi4sqrtN$ iterations.
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
$endgroup$
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
add a comment |
$begingroup$
This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm.
If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$left |phiright> = frac1sqrtNsum_x in Sleft|xright>$$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $left|psiright>$: $$2left|psiright>left<psiright| - I$$
into:
$$2left|phiright>left<phiright| - I$$
A common way of composing the Grover diffusion operator for an $n$-qubit system without fancy gates is to make it out of two Hadamards and some implementation of the diagonal matrix $2left|0right>left<0right| - I$ via:
$$H^otimes n(2 left|0right>left<0right| - I)H^otimes n$$.
To get our new diffusion operator, we just need to replace the left Hadamard gate with a gate $B$ and the right Hadamard with $B^*$ (if they are not the same) where $Bleft|0right> = left|phiright>$
From a fully general perspective, if your subset selection method is weird, like all prime-numbered states, I suspect realistically implementing $B$ (and having $left|phiright>$ in the first place) on, say, IBM Q may be difficult to the point of voiding the advantage of the algorithm, since you'd have to include individual gates to zero the probability of all the specific irrelevant states in the implementation of $B$.
Assuming no difficulty with $B$, it will run in $mathcalO(sqrtN)$ with your new $N$. The ideal stopping point will also still be $approx fracpi4sqrtN$ iterations.
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
$endgroup$
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
add a comment |
$begingroup$
This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm.
If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$left |phiright> = frac1sqrtNsum_x in Sleft|xright>$$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $left|psiright>$: $$2left|psiright>left<psiright| - I$$
into:
$$2left|phiright>left<phiright| - I$$
A common way of composing the Grover diffusion operator for an $n$-qubit system without fancy gates is to make it out of two Hadamards and some implementation of the diagonal matrix $2left|0right>left<0right| - I$ via:
$$H^otimes n(2 left|0right>left<0right| - I)H^otimes n$$.
To get our new diffusion operator, we just need to replace the left Hadamard gate with a gate $B$ and the right Hadamard with $B^*$ (if they are not the same) where $Bleft|0right> = left|phiright>$
From a fully general perspective, if your subset selection method is weird, like all prime-numbered states, I suspect realistically implementing $B$ (and having $left|phiright>$ in the first place) on, say, IBM Q may be difficult to the point of voiding the advantage of the algorithm, since you'd have to include individual gates to zero the probability of all the specific irrelevant states in the implementation of $B$.
Assuming no difficulty with $B$, it will run in $mathcalO(sqrtN)$ with your new $N$. The ideal stopping point will also still be $approx fracpi4sqrtN$ iterations.
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
$endgroup$
This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm.
If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$left |phiright> = frac1sqrtNsum_x in Sleft|xright>$$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $left|psiright>$: $$2left|psiright>left<psiright| - I$$
into:
$$2left|phiright>left<phiright| - I$$
A common way of composing the Grover diffusion operator for an $n$-qubit system without fancy gates is to make it out of two Hadamards and some implementation of the diagonal matrix $2left|0right>left<0right| - I$ via:
$$H^otimes n(2 left|0right>left<0right| - I)H^otimes n$$.
To get our new diffusion operator, we just need to replace the left Hadamard gate with a gate $B$ and the right Hadamard with $B^*$ (if they are not the same) where $Bleft|0right> = left|phiright>$
From a fully general perspective, if your subset selection method is weird, like all prime-numbered states, I suspect realistically implementing $B$ (and having $left|phiright>$ in the first place) on, say, IBM Q may be difficult to the point of voiding the advantage of the algorithm, since you'd have to include individual gates to zero the probability of all the specific irrelevant states in the implementation of $B$.
Assuming no difficulty with $B$, it will run in $mathcalO(sqrtN)$ with your new $N$. The ideal stopping point will also still be $approx fracpi4sqrtN$ iterations.
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
answered Jun 9 at 5:18
Joseph GeipelJoseph Geipel
613 bronze badges
613 bronze badges
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
add a comment |
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x in S$ and 0 otherwise. If we assume I already have my qubits in $|phirangle$. Could I use an extra qubit to conditionally apply $2|0ranglelangle0| - I$ based on $|0oplus g(x)rangle$?Would this still leave all of the 0 elements of $|phirangle$ as 0s?
$endgroup$
– Chase Roberts
Jun 10 at 14:57
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
$begingroup$
I'm not sure I understand. What is the goal there?
$endgroup$
– Joseph Geipel
Jun 11 at 1:09
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.
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%2f6383%2fgrovers-diffusion-on-subset-of-input-space%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
1
$begingroup$
It seems like with your toy example you want to have a superposition of two qubits having the $mathsfNAND$ being equal to $1$. You could calculate the $mathsfNAND$ and post-select on the $mathsfNAND$ of the two qubits being $1$, then run Grover's algorithm on the $mathsfNOR$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $mathsfNOR$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $mathsfNOR$ being $1$ and another output being $mathsfNAND$ being $1$?
$endgroup$
– Mark S
Jun 9 at 0:53