Mixing
How would I implement the quantum oracle in Deutsch's algorithm?
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to function, without defeating the purpose of the algorithm and "looking" at what the inputted function is, by evaluating the function.
quantum-algorithms simulation
edited 4 hours ago
Blue
5,43811148
asked 8 hours ago
Jack Ceroni
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
5
down vote
favorite
I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to function, without defeating the purpose of the algorithm and "looking" at what the inputted function is, by evaluating the function.
quantum-algorithms simulation
edited 4 hours ago
Blue
5,43811148
asked 8 hours ago
Jack Ceroni
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645
– meowzz
8 hours ago
Why not pick it at random each time you run the test? That way you can't know.
– DaftWullie
8 hours ago
@DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle.
– Jack Ceroni
8 hours ago
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to function, without defeating the purpose of the algorithm and "looking" at what the inputted function is, by evaluating the function.
quantum-algorithms simulation
edited 4 hours ago
Blue
5,43811148
asked 8 hours ago
Jack Ceroni
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to function, without defeating the purpose of the algorithm and "looking" at what the inputted function is, by evaluating the function.
quantum-algorithms simulation
quantum-algorithms simulation
edited 4 hours ago
Blue
5,43811148
asked 8 hours ago
Jack Ceroni
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
Blue
5,43811148
asked 8 hours ago
Jack Ceroni
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
Blue
5,43811148
edited 4 hours ago
Blue
5,43811148
edited 4 hours ago
Blue
5,43811148
5,43811148
asked 8 hours ago
Jack Ceroni
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
Jack Ceroni
413
asked 8 hours ago
Jack Ceroni
413
413
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Jack Ceroni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645
– meowzz
8 hours ago
Why not pick it at random each time you run the test? That way you can't know.
– DaftWullie
8 hours ago
@DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle.
– Jack Ceroni
8 hours ago
add a comment |Â
This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645
– meowzz
8 hours ago
Why not pick it at random each time you run the test? That way you can't know.
– DaftWullie
8 hours ago
@DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle.
– Jack Ceroni
8 hours ago
This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645
– meowzz
8 hours ago
This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645
– meowzz
8 hours ago
Why not pick it at random each time you run the test? That way you can't know.
– DaftWullie
8 hours ago
Why not pick it at random each time you run the test? That way you can't know.
– DaftWullie
8 hours ago
@DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle.
– Jack Ceroni
8 hours ago
@DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle.
– Jack Ceroni
8 hours ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
There are two questions here. The first is asking how you might actually implement this in code. Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. Here it is, implemented in Q#:
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
body
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
The second question asks why this function is at all interesting if you know which black box you're passing in ahead of time. There are two answers here: the first is from the standpoint of query complexity, which is computational complexity as measured by how many times a function has to query an oracle. The reason the Deutsch Oracle problem is interesting is because the quantum solution only has to query the black box once, while the classical solution has to query it twice. The difference is made stark in the generalized Deutsch-Josza problem, where instead of a function on $1$ bit the black box is a function on $n$ bits which is either constant or balanced. Here, the quantum solution still only has to query the black box once, but the classical solution has to query it $2^n-1$ times!
There's also an answer we can give about how this function might be useful in real life, which comes down to a property of linear algebra called the associativity of matrix multiplication. If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:
Identity: $C_1,0$
Negation: $X_0C_1,0$
Constant-0: $mathbbI_4$
Constant-1: $X_0$
However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:
$H_0Z_0H_0$
It turns out that, for any input you could ever give:
$H_0Z_0H_0|psirangle = X_0|psirangle$
This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $X_0$:
$H_0Z_0H_0 =
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix
beginbmatrix
1 & 0 \
0 & -1
endbmatrix
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix =
beginbmatrix
0 & 1 \
1 & 0
endbmatrix = X_0$
So we have:
$(H_0(Z_0(H_0|psirangle))) = (((H_0Z_0)H_0)|psirangle) = X_0|psirangle$
How this relates to the Deutsch Oracle problem is you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are.
As a final aside, I unfortunately have to let you down: there's something called the Gottesman-Knill theorem which tells us the Deutsch Oracle problem isn't actually useful for applications outside of teaching students their first quantum algorithm, because we can efficiently simulate it on a classical computer.
answered 7 hours ago
ahelwer
83010
add a comment |Â
up vote
2
down vote
I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.
The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.
Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.
answered 7 hours ago
Mariia Mykhailova
967110
add a comment |Â
up vote
1
down vote
You have two examples on the IBM Q Experience page about the algorithm.
They show an example of a function. This could inspire you for your simulations I hope.
answered 7 hours ago
cnada
1,16119
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
There are two questions here. The first is asking how you might actually implement this in code. Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. Here it is, implemented in Q#:
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
body
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
The second question asks why this function is at all interesting if you know which black box you're passing in ahead of time. There are two answers here: the first is from the standpoint of query complexity, which is computational complexity as measured by how many times a function has to query an oracle. The reason the Deutsch Oracle problem is interesting is because the quantum solution only has to query the black box once, while the classical solution has to query it twice. The difference is made stark in the generalized Deutsch-Josza problem, where instead of a function on $1$ bit the black box is a function on $n$ bits which is either constant or balanced. Here, the quantum solution still only has to query the black box once, but the classical solution has to query it $2^n-1$ times!
There's also an answer we can give about how this function might be useful in real life, which comes down to a property of linear algebra called the associativity of matrix multiplication. If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:
Identity: $C_1,0$
Negation: $X_0C_1,0$
Constant-0: $mathbbI_4$
Constant-1: $X_0$
However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:
$H_0Z_0H_0$
It turns out that, for any input you could ever give:
$H_0Z_0H_0|psirangle = X_0|psirangle$
This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $X_0$:
$H_0Z_0H_0 =
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix
beginbmatrix
1 & 0 \
0 & -1
endbmatrix
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix =
beginbmatrix
0 & 1 \
1 & 0
endbmatrix = X_0$
So we have:
$(H_0(Z_0(H_0|psirangle))) = (((H_0Z_0)H_0)|psirangle) = X_0|psirangle$
How this relates to the Deutsch Oracle problem is you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are.
As a final aside, I unfortunately have to let you down: there's something called the Gottesman-Knill theorem which tells us the Deutsch Oracle problem isn't actually useful for applications outside of teaching students their first quantum algorithm, because we can efficiently simulate it on a classical computer.
answered 7 hours ago
ahelwer
83010
add a comment |Â
up vote
3
down vote
There are two questions here. The first is asking how you might actually implement this in code. Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. Here it is, implemented in Q#:
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
body
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
The second question asks why this function is at all interesting if you know which black box you're passing in ahead of time. There are two answers here: the first is from the standpoint of query complexity, which is computational complexity as measured by how many times a function has to query an oracle. The reason the Deutsch Oracle problem is interesting is because the quantum solution only has to query the black box once, while the classical solution has to query it twice. The difference is made stark in the generalized Deutsch-Josza problem, where instead of a function on $1$ bit the black box is a function on $n$ bits which is either constant or balanced. Here, the quantum solution still only has to query the black box once, but the classical solution has to query it $2^n-1$ times!
There's also an answer we can give about how this function might be useful in real life, which comes down to a property of linear algebra called the associativity of matrix multiplication. If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:
Identity: $C_1,0$
Negation: $X_0C_1,0$
Constant-0: $mathbbI_4$
Constant-1: $X_0$
However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:
$H_0Z_0H_0$
It turns out that, for any input you could ever give:
$H_0Z_0H_0|psirangle = X_0|psirangle$
This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $X_0$:
$H_0Z_0H_0 =
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix
beginbmatrix
1 & 0 \
0 & -1
endbmatrix
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix =
beginbmatrix
0 & 1 \
1 & 0
endbmatrix = X_0$
So we have:
$(H_0(Z_0(H_0|psirangle))) = (((H_0Z_0)H_0)|psirangle) = X_0|psirangle$
How this relates to the Deutsch Oracle problem is you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are.
As a final aside, I unfortunately have to let you down: there's something called the Gottesman-Knill theorem which tells us the Deutsch Oracle problem isn't actually useful for applications outside of teaching students their first quantum algorithm, because we can efficiently simulate it on a classical computer.
answered 7 hours ago
ahelwer
83010
add a comment |Â
up vote
3
down vote
up vote
3
down vote
There are two questions here. The first is asking how you might actually implement this in code. Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. Here it is, implemented in Q#:
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
body
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
The second question asks why this function is at all interesting if you know which black box you're passing in ahead of time. There are two answers here: the first is from the standpoint of query complexity, which is computational complexity as measured by how many times a function has to query an oracle. The reason the Deutsch Oracle problem is interesting is because the quantum solution only has to query the black box once, while the classical solution has to query it twice. The difference is made stark in the generalized Deutsch-Josza problem, where instead of a function on $1$ bit the black box is a function on $n$ bits which is either constant or balanced. Here, the quantum solution still only has to query the black box once, but the classical solution has to query it $2^n-1$ times!
There's also an answer we can give about how this function might be useful in real life, which comes down to a property of linear algebra called the associativity of matrix multiplication. If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:
Identity: $C_1,0$
Negation: $X_0C_1,0$
Constant-0: $mathbbI_4$
Constant-1: $X_0$
However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:
$H_0Z_0H_0$
It turns out that, for any input you could ever give:
$H_0Z_0H_0|psirangle = X_0|psirangle$
This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $X_0$:
$H_0Z_0H_0 =
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix
beginbmatrix
1 & 0 \
0 & -1
endbmatrix
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix =
beginbmatrix
0 & 1 \
1 & 0
endbmatrix = X_0$
So we have:
$(H_0(Z_0(H_0|psirangle))) = (((H_0Z_0)H_0)|psirangle) = X_0|psirangle$
How this relates to the Deutsch Oracle problem is you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are.
As a final aside, I unfortunately have to let you down: there's something called the Gottesman-Knill theorem which tells us the Deutsch Oracle problem isn't actually useful for applications outside of teaching students their first quantum algorithm, because we can efficiently simulate it on a classical computer.
answered 7 hours ago
ahelwer
83010
There are two questions here. The first is asking how you might actually implement this in code. Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. Here it is, implemented in Q#:
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
body
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
The second question asks why this function is at all interesting if you know which black box you're passing in ahead of time. There are two answers here: the first is from the standpoint of query complexity, which is computational complexity as measured by how many times a function has to query an oracle. The reason the Deutsch Oracle problem is interesting is because the quantum solution only has to query the black box once, while the classical solution has to query it twice. The difference is made stark in the generalized Deutsch-Josza problem, where instead of a function on $1$ bit the black box is a function on $n$ bits which is either constant or balanced. Here, the quantum solution still only has to query the black box once, but the classical solution has to query it $2^n-1$ times!
There's also an answer we can give about how this function might be useful in real life, which comes down to a property of linear algebra called the associativity of matrix multiplication. If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:
Identity: $C_1,0$
Negation: $X_0C_1,0$
Constant-0: $mathbbI_4$
Constant-1: $X_0$
However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:
$H_0Z_0H_0$
It turns out that, for any input you could ever give:
$H_0Z_0H_0|psirangle = X_0|psirangle$
This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $X_0$:
$H_0Z_0H_0 =
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix
beginbmatrix
1 & 0 \
0 & -1
endbmatrix
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix =
beginbmatrix
0 & 1 \
1 & 0
endbmatrix = X_0$
So we have:
$(H_0(Z_0(H_0|psirangle))) = (((H_0Z_0)H_0)|psirangle) = X_0|psirangle$
How this relates to the Deutsch Oracle problem is you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are.
As a final aside, I unfortunately have to let you down: there's something called the Gottesman-Knill theorem which tells us the Deutsch Oracle problem isn't actually useful for applications outside of teaching students their first quantum algorithm, because we can efficiently simulate it on a classical computer.
answered 7 hours ago
ahelwer
83010
answered 7 hours ago
ahelwer
83010
answered 7 hours ago
ahelwer
83010
answered 7 hours ago
ahelwer
83010
83010
add a comment |Â
add a comment |Â
up vote
2
down vote
I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.
The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.
Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.
answered 7 hours ago
Mariia Mykhailova
967110
add a comment |Â
up vote
2
down vote
I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.
The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.
Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.
answered 7 hours ago
Mariia Mykhailova
967110
add a comment |Â
up vote
2
down vote
up vote
2
down vote
I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.
The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.
Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.
answered 7 hours ago
Mariia Mykhailova
967110
I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.
The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.
Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.
answered 7 hours ago
Mariia Mykhailova
967110
answered 7 hours ago
Mariia Mykhailova
967110
answered 7 hours ago
Mariia Mykhailova
967110
answered 7 hours ago
Mariia Mykhailova
967110
967110
add a comment |Â
add a comment |Â
up vote
1
down vote
You have two examples on the IBM Q Experience page about the algorithm.
They show an example of a function. This could inspire you for your simulations I hope.
answered 7 hours ago
cnada
1,16119
add a comment |Â
up vote
1
down vote
You have two examples on the IBM Q Experience page about the algorithm.
They show an example of a function. This could inspire you for your simulations I hope.
answered 7 hours ago
cnada
1,16119
add a comment |Â
up vote
1
down vote
up vote
1
down vote
You have two examples on the IBM Q Experience page about the algorithm.
They show an example of a function. This could inspire you for your simulations I hope.
answered 7 hours ago
cnada
1,16119
You have two examples on the IBM Q Experience page about the algorithm.
They show an example of a function. This could inspire you for your simulations I hope.
answered 7 hours ago
cnada
1,16119
answered 7 hours ago
cnada
1,16119
answered 7 hours ago
cnada
1,16119
answered 7 hours ago
cnada
1,16119
1,16119
add a comment |Â
add a comment |Â
Jack Ceroni is a new contributor. Be nice, and check out our Code of Conduct.
Jack Ceroni is a new contributor. Be nice, and check out our Code of Conduct.
Jack Ceroni is a new contributor. Be nice, and check out our Code of Conduct.
Jack Ceroni 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%2f4576%2fhow-would-i-implement-the-quantum-oracle-in-deutschs-algorithm%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
This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645
– meowzz
8 hours ago
Why not pick it at random each time you run the test? That way you can't know.
– DaftWullie
8 hours ago
@DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle.
– Jack Ceroni
8 hours ago