Mixing
Is there a general method to implement a 'greater than' quantum circuit?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am interesting in finding a circuit to implement the operation $f(x) > y$ for an arbitrary value of $y$. Below is the circuit I would like to build:
I use the first three qubits to encode $|x⟩$, use the other three qubits to encode $|f(x) = x⟩$, and finally I want to filter out all of the solutions for which $f(x) leq y$.
So, if we set $y = 5$, the states would be:
$$Psi_0 = |0⟩otimes|0⟩ $$
$$Psi_1 = frac1sqrt8sum_i=0^7 (|i⟩otimes|0⟩) $$
$$Psi_2 = frac1sqrt8sum_i=0^7 (|i⟩otimes|i⟩) $$
$$Psi_3 = frac1sqrt2(|6⟩otimes|6⟩ + |7⟩otimes|7⟩)$$
Is there a general method to come up with such filter, or is this non-trivial?
quantum-algorithms quantum-computer mathematics circuit-construction
asked 7 hours ago
Max
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
 |Â
show 4 more comments
up vote
1
down vote
favorite
I am interesting in finding a circuit to implement the operation $f(x) > y$ for an arbitrary value of $y$. Below is the circuit I would like to build:
I use the first three qubits to encode $|x⟩$, use the other three qubits to encode $|f(x) = x⟩$, and finally I want to filter out all of the solutions for which $f(x) leq y$.
So, if we set $y = 5$, the states would be:
$$Psi_0 = |0⟩otimes|0⟩ $$
$$Psi_1 = frac1sqrt8sum_i=0^7 (|i⟩otimes|0⟩) $$
$$Psi_2 = frac1sqrt8sum_i=0^7 (|i⟩otimes|i⟩) $$
$$Psi_3 = frac1sqrt2(|6⟩otimes|6⟩ + |7⟩otimes|7⟩)$$
Is there a general method to come up with such filter, or is this non-trivial?
quantum-algorithms quantum-computer mathematics circuit-construction
asked 7 hours ago
Max
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^-(n-2)$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable?
– Niel de Beaudrap
6 hours ago
1
Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states?
– Norbert Schuch
6 hours ago
1
@NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks!
– Max
5 hours ago
2
What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach.
– Niel de Beaudrap
5 hours ago
2
@Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ...
– Norbert Schuch
3 hours ago
 |Â
show 4 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am interesting in finding a circuit to implement the operation $f(x) > y$ for an arbitrary value of $y$. Below is the circuit I would like to build:
I use the first three qubits to encode $|x⟩$, use the other three qubits to encode $|f(x) = x⟩$, and finally I want to filter out all of the solutions for which $f(x) leq y$.
So, if we set $y = 5$, the states would be:
$$Psi_0 = |0⟩otimes|0⟩ $$
$$Psi_1 = frac1sqrt8sum_i=0^7 (|i⟩otimes|0⟩) $$
$$Psi_2 = frac1sqrt8sum_i=0^7 (|i⟩otimes|i⟩) $$
$$Psi_3 = frac1sqrt2(|6⟩otimes|6⟩ + |7⟩otimes|7⟩)$$
Is there a general method to come up with such filter, or is this non-trivial?
quantum-algorithms quantum-computer mathematics circuit-construction
asked 7 hours ago
Max
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am interesting in finding a circuit to implement the operation $f(x) > y$ for an arbitrary value of $y$. Below is the circuit I would like to build:
I use the first three qubits to encode $|x⟩$, use the other three qubits to encode $|f(x) = x⟩$, and finally I want to filter out all of the solutions for which $f(x) leq y$.
So, if we set $y = 5$, the states would be:
$$Psi_0 = |0⟩otimes|0⟩ $$
$$Psi_1 = frac1sqrt8sum_i=0^7 (|i⟩otimes|0⟩) $$
$$Psi_2 = frac1sqrt8sum_i=0^7 (|i⟩otimes|i⟩) $$
$$Psi_3 = frac1sqrt2(|6⟩otimes|6⟩ + |7⟩otimes|7⟩)$$
Is there a general method to come up with such filter, or is this non-trivial?
quantum-algorithms quantum-computer mathematics circuit-construction
quantum-algorithms quantum-computer mathematics circuit-construction
asked 7 hours ago
Max
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 hours ago
Max
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 7 hours ago
asked 7 hours ago
Max
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 hours ago
Max
1063
asked 7 hours ago
Max
1063
1063
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Max is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^-(n-2)$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable?
– Niel de Beaudrap
6 hours ago
1
Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states?
– Norbert Schuch
6 hours ago
1
@NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks!
– Max
5 hours ago
2
What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach.
– Niel de Beaudrap
5 hours ago
2
@Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ...
– Norbert Schuch
3 hours ago
 |Â
show 4 more comments
2
Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^-(n-2)$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable?
– Niel de Beaudrap
6 hours ago
1
Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states?
– Norbert Schuch
6 hours ago
1
@NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks!
– Max
5 hours ago
2
What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach.
– Niel de Beaudrap
5 hours ago
2
@Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ...
– Norbert Schuch
3 hours ago
2
2
Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^-(n-2)$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable?
– Niel de Beaudrap
6 hours ago
Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^-(n-2)$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable?
– Niel de Beaudrap
6 hours ago
1
1
Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states?
– Norbert Schuch
6 hours ago
Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states?
– Norbert Schuch
6 hours ago
1
1
@NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks!
– Max
5 hours ago
@NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks!
– Max
5 hours ago
2
2
What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach.
– Niel de Beaudrap
5 hours ago
What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach.
– Niel de Beaudrap
5 hours ago
2
2
@Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ...
– Norbert Schuch
3 hours ago
@Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ...
– Norbert Schuch
3 hours ago
 |Â
show 4 more comments
2 Answers
2
active
oldest
votes
up vote
3
down vote
What you are looking for I think is to use a quantum circuit for doing comparison.
Those are made from adder circuits with a slight modification to have comparators.
For adders, you have for example one from Cuccaro et al. (this one give the modification to adapt for comparison) and another from Himanshu et al.
answered 5 hours ago
cnada
89518
add a comment |Â
up vote
1
down vote
Let $U$ be the circuit you stated that takes $| 0 rangle^otimes (2n)$ to $psi=frac12^n/2sum_i=0^2^n-1 | i rangle otimes | f(i) rangle $.
$S_psi = I - 2 | psi rangle langle psi | = U ( S_ 0 rangle^otimes (2n) ) U^dagger$
$S_P$ needs to be the unitary that sends $| i rangle otimes | j rangle$ to $(-1)^j>y (| i rangle otimes | j rangle)$. For example if $y$ is $2^n-1-1$, then this would be done with a $Z$ gate on the most significant index. Generally for $y$ 1 less than a power of $2$ this should be easy by combining information from all more significant indices.
Those are the requisite ingredients for amplitude amplification for $f(x) geq 2^k$ for some $k$. The number of times you need to apply $Q$ is dependent on the overlap which is dependent on how many solutions $x$ there are to $f(k) geq 2^k$. If $f$ is reversible so just giving a permutation of $2^n$, then you have the overlap in terms of $n-k$ without bothering with any details of $f$.
You won't get exactly the result you asked for because that was projecting to a subspace/not unitary, but this will get you close to that desired state given your starting setup. There is also the trouble of setting $y$ arbitrarily, but at least you can amplify the condition $f(x) geq 2^k$ as a step along the way to amplifying $f(x) geq y$ for $y geq 2^k$.
I may have misunderstood the question. You might have wanted something that works more generally, but given your small example this approach is okay. You don't have to worry about the fact that $fracpi4theta$ will get really big as $n$ grows you, if you don't let $n$ grow. Did you want to input $y$ as a quantum state as well?
I wasn't careful about checking $geq$ vs $gt$ so you should check that.
answered 51 mins ago
AHusain
683127
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
What you are looking for I think is to use a quantum circuit for doing comparison.
Those are made from adder circuits with a slight modification to have comparators.
For adders, you have for example one from Cuccaro et al. (this one give the modification to adapt for comparison) and another from Himanshu et al.
answered 5 hours ago
cnada
89518
add a comment |Â
up vote
3
down vote
What you are looking for I think is to use a quantum circuit for doing comparison.
Those are made from adder circuits with a slight modification to have comparators.
For adders, you have for example one from Cuccaro et al. (this one give the modification to adapt for comparison) and another from Himanshu et al.
answered 5 hours ago
cnada
89518
add a comment |Â
up vote
3
down vote
up vote
3
down vote
What you are looking for I think is to use a quantum circuit for doing comparison.
Those are made from adder circuits with a slight modification to have comparators.
For adders, you have for example one from Cuccaro et al. (this one give the modification to adapt for comparison) and another from Himanshu et al.
answered 5 hours ago
cnada
89518
What you are looking for I think is to use a quantum circuit for doing comparison.
Those are made from adder circuits with a slight modification to have comparators.
For adders, you have for example one from Cuccaro et al. (this one give the modification to adapt for comparison) and another from Himanshu et al.
answered 5 hours ago
cnada
89518
answered 5 hours ago
cnada
89518
answered 5 hours ago
cnada
89518
answered 5 hours ago
cnada
89518
89518
add a comment |Â
add a comment |Â
up vote
1
down vote
Let $U$ be the circuit you stated that takes $| 0 rangle^otimes (2n)$ to $psi=frac12^n/2sum_i=0^2^n-1 | i rangle otimes | f(i) rangle $.
$S_psi = I - 2 | psi rangle langle psi | = U ( S_ 0 rangle^otimes (2n) ) U^dagger$
$S_P$ needs to be the unitary that sends $| i rangle otimes | j rangle$ to $(-1)^j>y (| i rangle otimes | j rangle)$. For example if $y$ is $2^n-1-1$, then this would be done with a $Z$ gate on the most significant index. Generally for $y$ 1 less than a power of $2$ this should be easy by combining information from all more significant indices.
Those are the requisite ingredients for amplitude amplification for $f(x) geq 2^k$ for some $k$. The number of times you need to apply $Q$ is dependent on the overlap which is dependent on how many solutions $x$ there are to $f(k) geq 2^k$. If $f$ is reversible so just giving a permutation of $2^n$, then you have the overlap in terms of $n-k$ without bothering with any details of $f$.
You won't get exactly the result you asked for because that was projecting to a subspace/not unitary, but this will get you close to that desired state given your starting setup. There is also the trouble of setting $y$ arbitrarily, but at least you can amplify the condition $f(x) geq 2^k$ as a step along the way to amplifying $f(x) geq y$ for $y geq 2^k$.
I may have misunderstood the question. You might have wanted something that works more generally, but given your small example this approach is okay. You don't have to worry about the fact that $fracpi4theta$ will get really big as $n$ grows you, if you don't let $n$ grow. Did you want to input $y$ as a quantum state as well?
I wasn't careful about checking $geq$ vs $gt$ so you should check that.
answered 51 mins ago
AHusain
683127
add a comment |Â
up vote
1
down vote
Let $U$ be the circuit you stated that takes $| 0 rangle^otimes (2n)$ to $psi=frac12^n/2sum_i=0^2^n-1 | i rangle otimes | f(i) rangle $.
$S_psi = I - 2 | psi rangle langle psi | = U ( S_ 0 rangle^otimes (2n) ) U^dagger$
$S_P$ needs to be the unitary that sends $| i rangle otimes | j rangle$ to $(-1)^j>y (| i rangle otimes | j rangle)$. For example if $y$ is $2^n-1-1$, then this would be done with a $Z$ gate on the most significant index. Generally for $y$ 1 less than a power of $2$ this should be easy by combining information from all more significant indices.
Those are the requisite ingredients for amplitude amplification for $f(x) geq 2^k$ for some $k$. The number of times you need to apply $Q$ is dependent on the overlap which is dependent on how many solutions $x$ there are to $f(k) geq 2^k$. If $f$ is reversible so just giving a permutation of $2^n$, then you have the overlap in terms of $n-k$ without bothering with any details of $f$.
You won't get exactly the result you asked for because that was projecting to a subspace/not unitary, but this will get you close to that desired state given your starting setup. There is also the trouble of setting $y$ arbitrarily, but at least you can amplify the condition $f(x) geq 2^k$ as a step along the way to amplifying $f(x) geq y$ for $y geq 2^k$.
I may have misunderstood the question. You might have wanted something that works more generally, but given your small example this approach is okay. You don't have to worry about the fact that $fracpi4theta$ will get really big as $n$ grows you, if you don't let $n$ grow. Did you want to input $y$ as a quantum state as well?
I wasn't careful about checking $geq$ vs $gt$ so you should check that.
answered 51 mins ago
AHusain
683127
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $U$ be the circuit you stated that takes $| 0 rangle^otimes (2n)$ to $psi=frac12^n/2sum_i=0^2^n-1 | i rangle otimes | f(i) rangle $.
$S_psi = I - 2 | psi rangle langle psi | = U ( S_ 0 rangle^otimes (2n) ) U^dagger$
$S_P$ needs to be the unitary that sends $| i rangle otimes | j rangle$ to $(-1)^j>y (| i rangle otimes | j rangle)$. For example if $y$ is $2^n-1-1$, then this would be done with a $Z$ gate on the most significant index. Generally for $y$ 1 less than a power of $2$ this should be easy by combining information from all more significant indices.
Those are the requisite ingredients for amplitude amplification for $f(x) geq 2^k$ for some $k$. The number of times you need to apply $Q$ is dependent on the overlap which is dependent on how many solutions $x$ there are to $f(k) geq 2^k$. If $f$ is reversible so just giving a permutation of $2^n$, then you have the overlap in terms of $n-k$ without bothering with any details of $f$.
You won't get exactly the result you asked for because that was projecting to a subspace/not unitary, but this will get you close to that desired state given your starting setup. There is also the trouble of setting $y$ arbitrarily, but at least you can amplify the condition $f(x) geq 2^k$ as a step along the way to amplifying $f(x) geq y$ for $y geq 2^k$.
I may have misunderstood the question. You might have wanted something that works more generally, but given your small example this approach is okay. You don't have to worry about the fact that $fracpi4theta$ will get really big as $n$ grows you, if you don't let $n$ grow. Did you want to input $y$ as a quantum state as well?
I wasn't careful about checking $geq$ vs $gt$ so you should check that.
answered 51 mins ago
AHusain
683127
Let $U$ be the circuit you stated that takes $| 0 rangle^otimes (2n)$ to $psi=frac12^n/2sum_i=0^2^n-1 | i rangle otimes | f(i) rangle $.
$S_psi = I - 2 | psi rangle langle psi | = U ( S_ 0 rangle^otimes (2n) ) U^dagger$
$S_P$ needs to be the unitary that sends $| i rangle otimes | j rangle$ to $(-1)^j>y (| i rangle otimes | j rangle)$. For example if $y$ is $2^n-1-1$, then this would be done with a $Z$ gate on the most significant index. Generally for $y$ 1 less than a power of $2$ this should be easy by combining information from all more significant indices.
Those are the requisite ingredients for amplitude amplification for $f(x) geq 2^k$ for some $k$. The number of times you need to apply $Q$ is dependent on the overlap which is dependent on how many solutions $x$ there are to $f(k) geq 2^k$. If $f$ is reversible so just giving a permutation of $2^n$, then you have the overlap in terms of $n-k$ without bothering with any details of $f$.
You won't get exactly the result you asked for because that was projecting to a subspace/not unitary, but this will get you close to that desired state given your starting setup. There is also the trouble of setting $y$ arbitrarily, but at least you can amplify the condition $f(x) geq 2^k$ as a step along the way to amplifying $f(x) geq y$ for $y geq 2^k$.
I may have misunderstood the question. You might have wanted something that works more generally, but given your small example this approach is okay. You don't have to worry about the fact that $fracpi4theta$ will get really big as $n$ grows you, if you don't let $n$ grow. Did you want to input $y$ as a quantum state as well?
I wasn't careful about checking $geq$ vs $gt$ so you should check that.
answered 51 mins ago
AHusain
683127
answered 51 mins ago
AHusain
683127
answered 51 mins ago
AHusain
683127
answered 51 mins ago
AHusain
683127
683127
add a comment |Â
add a comment |Â
Max is a new contributor. Be nice, and check out our Code of Conduct.
Max is a new contributor. Be nice, and check out our Code of Conduct.
Max is a new contributor. Be nice, and check out our Code of Conduct.
Max is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4353%2fis-there-a-general-method-to-implement-a-greater-than-quantum-circuit%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^-(n-2)$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable?
– Niel de Beaudrap
6 hours ago
1
Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states?
– Norbert Schuch
6 hours ago
1
@NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks!
– Max
5 hours ago
2
What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach.
– Niel de Beaudrap
5 hours ago
2
@Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ...
– Norbert Schuch
3 hours ago