Grover's algorithm: number of searches
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
I would like to start my question with a quote:
If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second, by comparison, Grover's algorithm could find the key after only 185 searches.
This quote is from A Brief History of Quantum Computing By Simon Bone and Matias Castro
As a reader, I wonder how the authors got the magic number of 185. Unfortunately, that is not justified.
I thought about it myself. To calculate the number of iterations, the Grover algorithm uses this formula:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^n}}right)}-0.5$$
If I just do that for the number $2^{56}$ (DES keysize), then it follows that you need k iterations:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$$
That's still not the number the authors suggest. Therefore I ask here, if anyone can imagine, how the authors came to the number. Is my consideration correct?
Assuming it were $2^{16}$, then you would need about 200 iterations, which are still not 185. I am not aware of a cryptographic system with a key length of $2^{16} $ ...
algorithm grovers-algorithm cryptography
edited Apr 1 at 10:26
Blue♦
6,63141556
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
$endgroup$
add a comment |
$begingroup$
I would like to start my question with a quote:
If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second, by comparison, Grover's algorithm could find the key after only 185 searches.
This quote is from A Brief History of Quantum Computing By Simon Bone and Matias Castro
As a reader, I wonder how the authors got the magic number of 185. Unfortunately, that is not justified.
I thought about it myself. To calculate the number of iterations, the Grover algorithm uses this formula:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^n}}right)}-0.5$$
If I just do that for the number $2^{56}$ (DES keysize), then it follows that you need k iterations:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$$
That's still not the number the authors suggest. Therefore I ask here, if anyone can imagine, how the authors came to the number. Is my consideration correct?
Assuming it were $2^{16}$, then you would need about 200 iterations, which are still not 185. I am not aware of a cryptographic system with a key length of $2^{16} $ ...
algorithm grovers-algorithm cryptography
edited Apr 1 at 10:26
Blue♦
6,63141556
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
$endgroup$
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $sim 2^{55/2}simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
Apr 1 at 11:30
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$
$endgroup$
– QuantaMag
Apr 1 at 11:38
$begingroup$
well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
Apr 1 at 16:38
add a comment |
$begingroup$
I would like to start my question with a quote:
If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second, by comparison, Grover's algorithm could find the key after only 185 searches.
This quote is from A Brief History of Quantum Computing By Simon Bone and Matias Castro
As a reader, I wonder how the authors got the magic number of 185. Unfortunately, that is not justified.
I thought about it myself. To calculate the number of iterations, the Grover algorithm uses this formula:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^n}}right)}-0.5$$
If I just do that for the number $2^{56}$ (DES keysize), then it follows that you need k iterations:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$$
That's still not the number the authors suggest. Therefore I ask here, if anyone can imagine, how the authors came to the number. Is my consideration correct?
Assuming it were $2^{16}$, then you would need about 200 iterations, which are still not 185. I am not aware of a cryptographic system with a key length of $2^{16} $ ...
algorithm grovers-algorithm cryptography
edited Apr 1 at 10:26
Blue♦
6,63141556
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
$endgroup$
I would like to start my question with a quote:
If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second, by comparison, Grover's algorithm could find the key after only 185 searches.
This quote is from A Brief History of Quantum Computing By Simon Bone and Matias Castro
As a reader, I wonder how the authors got the magic number of 185. Unfortunately, that is not justified.
I thought about it myself. To calculate the number of iterations, the Grover algorithm uses this formula:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^n}}right)}-0.5$$
If I just do that for the number $2^{56}$ (DES keysize), then it follows that you need k iterations:
$$k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$$
That's still not the number the authors suggest. Therefore I ask here, if anyone can imagine, how the authors came to the number. Is my consideration correct?
Assuming it were $2^{16}$, then you would need about 200 iterations, which are still not 185. I am not aware of a cryptographic system with a key length of $2^{16} $ ...
algorithm grovers-algorithm cryptography
algorithm grovers-algorithm cryptography
edited Apr 1 at 10:26
Blue♦
6,63141556
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
edited Apr 1 at 10:26
Blue♦
6,63141556
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
edited Apr 1 at 10:26
Blue♦
6,63141556
edited Apr 1 at 10:26
Blue♦
6,63141556
edited Apr 1 at 10:26
Blue♦
6,63141556
6,63141556
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
asked Apr 1 at 9:19
QuantaMagQuantaMag
1626
1626
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $sim 2^{55/2}simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
Apr 1 at 11:30
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$
$endgroup$
– QuantaMag
Apr 1 at 11:38
$begingroup$
well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
Apr 1 at 16:38
add a comment |
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $sim 2^{55/2}simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
Apr 1 at 11:30
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$
$endgroup$
– QuantaMag
Apr 1 at 11:38
$begingroup$
well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
Apr 1 at 16:38
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $sim 2^{55/2}simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
Apr 1 at 11:30
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $sim 2^{55/2}simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
Apr 1 at 11:30
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$
$endgroup$
– QuantaMag
Apr 1 at 11:38
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$
$endgroup$
– QuantaMag
Apr 1 at 11:38
$begingroup$
well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
Apr 1 at 16:38
$begingroup$
well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
Apr 1 at 16:38
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.
Although it is different from the results you calculated, but it looks much better than 185.
edited Apr 1 at 14:25
Blue♦
6,63141556
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "694"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
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%2f5824%2fgrovers-algorithm-number-of-searches%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$
I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.
Although it is different from the results you calculated, but it looks much better than 185.
edited Apr 1 at 14:25
Blue♦
6,63141556
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
add a comment |
$begingroup$
I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.
Although it is different from the results you calculated, but it looks much better than 185.
edited Apr 1 at 14:25
Blue♦
6,63141556
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
add a comment |
$begingroup$
I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.
Although it is different from the results you calculated, but it looks much better than 185.
edited Apr 1 at 14:25
Blue♦
6,63141556
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.
Although it is different from the results you calculated, but it looks much better than 185.
edited Apr 1 at 14:25
Blue♦
6,63141556
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 1 at 14:25
Blue♦
6,63141556
edited Apr 1 at 14:25
Blue♦
6,63141556
edited Apr 1 at 14:25
Blue♦
6,63141556
6,63141556
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
answered Apr 1 at 14:22
Yijun WangYijun Wang
512
512
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Yijun Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
add a comment |
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key.
$endgroup$
– QuantaMag
Apr 1 at 14:31
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
Apr 1 at 14:37
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%2f5824%2fgrovers-algorithm-number-of-searches%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
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $sim 2^{55/2}simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
Apr 1 at 11:30
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=frac{pi}{4cdot sin^{-1}left(frac{1}{sqrt{2^{56}}}right)}-0.5=210828713$
$endgroup$
– QuantaMag
Apr 1 at 11:38
$begingroup$
well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
Apr 1 at 16:38