Mixing
How is the Deutsch algorithm faster than classical for practical implementation?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
There is something I really misunderstand about the Deutch-Algorithm.
To check if $f$ is balanced or constant, we use the following algorithm :
Where $U_f$ gives $(x,y) rightarrow (x, y oplus f(x))$.
Let's take $n=1$ for simplicity (thus the function $f$ is defined on $(0,1)$).
We have $4$ possible $U_f$ associated to $2$ constants possibility ($f$ equal to $0$ or $1$), and two balanced possibilities.
So, in practice, if I want to implement this in a circuit, I have to know exactly the "matrix" of $U_f$. And to do it I have to compute $f$ $2$ times. Thus, I know if $f$ is balanced or constant even before having applied the quantum algorithm. So for a practical aspect, I don't understand what is the point of this.
Said differently, if I am given $U_f$ I agree that in $1$ step I will know if $f$ is balanced or constant. But if I know $U_f$ I already know the answer to this question.
I am a little confused...
quantum-algorithms deutsch-algorithm
edited 1 hour ago
Blue
5,49511148
asked 2 hours ago
StarBucK
1283
New contributor
StarBucK 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
2
down vote
favorite
There is something I really misunderstand about the Deutch-Algorithm.
To check if $f$ is balanced or constant, we use the following algorithm :
Where $U_f$ gives $(x,y) rightarrow (x, y oplus f(x))$.
Let's take $n=1$ for simplicity (thus the function $f$ is defined on $(0,1)$).
We have $4$ possible $U_f$ associated to $2$ constants possibility ($f$ equal to $0$ or $1$), and two balanced possibilities.
So, in practice, if I want to implement this in a circuit, I have to know exactly the "matrix" of $U_f$. And to do it I have to compute $f$ $2$ times. Thus, I know if $f$ is balanced or constant even before having applied the quantum algorithm. So for a practical aspect, I don't understand what is the point of this.
Said differently, if I am given $U_f$ I agree that in $1$ step I will know if $f$ is balanced or constant. But if I know $U_f$ I already know the answer to this question.
I am a little confused...
quantum-algorithms deutsch-algorithm
edited 1 hour ago
Blue
5,49511148
asked 2 hours ago
StarBucK
1283
New contributor
StarBucK 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
2
down vote
favorite
up vote
2
down vote
favorite
There is something I really misunderstand about the Deutch-Algorithm.
To check if $f$ is balanced or constant, we use the following algorithm :
Where $U_f$ gives $(x,y) rightarrow (x, y oplus f(x))$.
Let's take $n=1$ for simplicity (thus the function $f$ is defined on $(0,1)$).
We have $4$ possible $U_f$ associated to $2$ constants possibility ($f$ equal to $0$ or $1$), and two balanced possibilities.
So, in practice, if I want to implement this in a circuit, I have to know exactly the "matrix" of $U_f$. And to do it I have to compute $f$ $2$ times. Thus, I know if $f$ is balanced or constant even before having applied the quantum algorithm. So for a practical aspect, I don't understand what is the point of this.
Said differently, if I am given $U_f$ I agree that in $1$ step I will know if $f$ is balanced or constant. But if I know $U_f$ I already know the answer to this question.
I am a little confused...
quantum-algorithms deutsch-algorithm
edited 1 hour ago
Blue
5,49511148
asked 2 hours ago
StarBucK
1283
New contributor
StarBucK is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
There is something I really misunderstand about the Deutch-Algorithm.
To check if $f$ is balanced or constant, we use the following algorithm :
Where $U_f$ gives $(x,y) rightarrow (x, y oplus f(x))$.
Let's take $n=1$ for simplicity (thus the function $f$ is defined on $(0,1)$).
We have $4$ possible $U_f$ associated to $2$ constants possibility ($f$ equal to $0$ or $1$), and two balanced possibilities.
So, in practice, if I want to implement this in a circuit, I have to know exactly the "matrix" of $U_f$. And to do it I have to compute $f$ $2$ times. Thus, I know if $f$ is balanced or constant even before having applied the quantum algorithm. So for a practical aspect, I don't understand what is the point of this.
Said differently, if I am given $U_f$ I agree that in $1$ step I will know if $f$ is balanced or constant. But if I know $U_f$ I already know the answer to this question.
I am a little confused...
quantum-algorithms deutsch-algorithm
quantum-algorithms deutsch-algorithm
edited 1 hour ago
Blue
5,49511148
asked 2 hours ago
StarBucK
1283
New contributor
StarBucK 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,49511148
asked 2 hours ago
StarBucK
1283
New contributor
StarBucK 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,49511148
edited 1 hour ago
Blue
5,49511148
edited 1 hour ago
Blue
5,49511148
5,49511148
asked 2 hours ago
StarBucK
1283
New contributor
StarBucK is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 hours ago
StarBucK
1283
asked 2 hours ago
StarBucK
1283
1283
New contributor
StarBucK is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
StarBucK is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
StarBucK 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 |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer.
However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the function, that is having a sequence of gates representing the operation, you can just apply it without having a knowledge of the unitary.
Let us give you an example just on n=3:
$$ f(x) = x_0 oplus x_1 x_2 $$
To apply $ U_f $, we just need a $CNOT$ and a Toffoli gate representing the different operations of $f$, and apply directly, without necessarily having a knowledge of the unitary to build it (just decomposing into "simple" operations). You can extend to examples where $n$ is very large.
answered 1 hour ago
cnada
1,29619
add a comment |Â
up vote
1
down vote
I think there are probably two points to make here:
The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be exponential). Instead, as cnada says, the computation is itself built out of simple gates. The simplest is "do nothing" which is a perfectly good example of a constant algorithm. I don't need to see the unitary to build that!
The context of an oracle is that you don't build it yourself, so you don't know the unitary. Somebody else gives it to you (or perhaps you'll have built it as the result of another computation), with certain promised properties, and it is your job to determine the relevant parameters. Of course, if you want to practically test whether that works, you'll build it all yourself. But then, you don't care about the efficiency saving during the test, because of course you know what you've built. Indeed, you need to know what you've built because otherwise your test cannot work; you don't know what to check the outcome against.
Incidentally, I think this question is closely related.
answered 1 hour ago
DaftWullie
9,8271332
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer.
However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the function, that is having a sequence of gates representing the operation, you can just apply it without having a knowledge of the unitary.
Let us give you an example just on n=3:
$$ f(x) = x_0 oplus x_1 x_2 $$
To apply $ U_f $, we just need a $CNOT$ and a Toffoli gate representing the different operations of $f$, and apply directly, without necessarily having a knowledge of the unitary to build it (just decomposing into "simple" operations). You can extend to examples where $n$ is very large.
answered 1 hour ago
cnada
1,29619
add a comment |Â
up vote
2
down vote
If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer.
However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the function, that is having a sequence of gates representing the operation, you can just apply it without having a knowledge of the unitary.
Let us give you an example just on n=3:
$$ f(x) = x_0 oplus x_1 x_2 $$
To apply $ U_f $, we just need a $CNOT$ and a Toffoli gate representing the different operations of $f$, and apply directly, without necessarily having a knowledge of the unitary to build it (just decomposing into "simple" operations). You can extend to examples where $n$ is very large.
answered 1 hour ago
cnada
1,29619
add a comment |Â
up vote
2
down vote
up vote
2
down vote
If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer.
However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the function, that is having a sequence of gates representing the operation, you can just apply it without having a knowledge of the unitary.
Let us give you an example just on n=3:
$$ f(x) = x_0 oplus x_1 x_2 $$
To apply $ U_f $, we just need a $CNOT$ and a Toffoli gate representing the different operations of $f$, and apply directly, without necessarily having a knowledge of the unitary to build it (just decomposing into "simple" operations). You can extend to examples where $n$ is very large.
answered 1 hour ago
cnada
1,29619
If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer.
However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the function, that is having a sequence of gates representing the operation, you can just apply it without having a knowledge of the unitary.
Let us give you an example just on n=3:
$$ f(x) = x_0 oplus x_1 x_2 $$
To apply $ U_f $, we just need a $CNOT$ and a Toffoli gate representing the different operations of $f$, and apply directly, without necessarily having a knowledge of the unitary to build it (just decomposing into "simple" operations). You can extend to examples where $n$ is very large.
answered 1 hour ago
cnada
1,29619
answered 1 hour ago
cnada
1,29619
answered 1 hour ago
cnada
1,29619
answered 1 hour ago
cnada
1,29619
1,29619
add a comment |Â
add a comment |Â
up vote
1
down vote
I think there are probably two points to make here:
The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be exponential). Instead, as cnada says, the computation is itself built out of simple gates. The simplest is "do nothing" which is a perfectly good example of a constant algorithm. I don't need to see the unitary to build that!
The context of an oracle is that you don't build it yourself, so you don't know the unitary. Somebody else gives it to you (or perhaps you'll have built it as the result of another computation), with certain promised properties, and it is your job to determine the relevant parameters. Of course, if you want to practically test whether that works, you'll build it all yourself. But then, you don't care about the efficiency saving during the test, because of course you know what you've built. Indeed, you need to know what you've built because otherwise your test cannot work; you don't know what to check the outcome against.
Incidentally, I think this question is closely related.
answered 1 hour ago
DaftWullie
9,8271332
add a comment |Â
up vote
1
down vote
I think there are probably two points to make here:
The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be exponential). Instead, as cnada says, the computation is itself built out of simple gates. The simplest is "do nothing" which is a perfectly good example of a constant algorithm. I don't need to see the unitary to build that!
The context of an oracle is that you don't build it yourself, so you don't know the unitary. Somebody else gives it to you (or perhaps you'll have built it as the result of another computation), with certain promised properties, and it is your job to determine the relevant parameters. Of course, if you want to practically test whether that works, you'll build it all yourself. But then, you don't care about the efficiency saving during the test, because of course you know what you've built. Indeed, you need to know what you've built because otherwise your test cannot work; you don't know what to check the outcome against.
Incidentally, I think this question is closely related.
answered 1 hour ago
DaftWullie
9,8271332
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I think there are probably two points to make here:
The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be exponential). Instead, as cnada says, the computation is itself built out of simple gates. The simplest is "do nothing" which is a perfectly good example of a constant algorithm. I don't need to see the unitary to build that!
The context of an oracle is that you don't build it yourself, so you don't know the unitary. Somebody else gives it to you (or perhaps you'll have built it as the result of another computation), with certain promised properties, and it is your job to determine the relevant parameters. Of course, if you want to practically test whether that works, you'll build it all yourself. But then, you don't care about the efficiency saving during the test, because of course you know what you've built. Indeed, you need to know what you've built because otherwise your test cannot work; you don't know what to check the outcome against.
Incidentally, I think this question is closely related.
answered 1 hour ago
DaftWullie
9,8271332
I think there are probably two points to make here:
The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be exponential). Instead, as cnada says, the computation is itself built out of simple gates. The simplest is "do nothing" which is a perfectly good example of a constant algorithm. I don't need to see the unitary to build that!
The context of an oracle is that you don't build it yourself, so you don't know the unitary. Somebody else gives it to you (or perhaps you'll have built it as the result of another computation), with certain promised properties, and it is your job to determine the relevant parameters. Of course, if you want to practically test whether that works, you'll build it all yourself. But then, you don't care about the efficiency saving during the test, because of course you know what you've built. Indeed, you need to know what you've built because otherwise your test cannot work; you don't know what to check the outcome against.
Incidentally, I think this question is closely related.
answered 1 hour ago
DaftWullie
9,8271332
answered 1 hour ago
DaftWullie
9,8271332
answered 1 hour ago
DaftWullie
9,8271332
answered 1 hour ago
DaftWullie
9,8271332
9,8271332
add a comment |Â
add a comment |Â
StarBucK is a new contributor. Be nice, and check out our Code of Conduct.
StarBucK is a new contributor. Be nice, and check out our Code of Conduct.
StarBucK is a new contributor. Be nice, and check out our Code of Conduct.
StarBucK 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%2f4628%2fhow-is-the-deutsch-algorithm-faster-than-classical-for-practical-implementation%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
