Grover's algorithm: number of searchesRigorous security proof for Wiesner's quantum moneyGrover's algorithm: where is the list?Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|Psi_0rangle$?HHL algorithm — problem with the outcome of postselectionCompact encoding of Boolean formula as oracleHow many bits do Alice and Bob needs to compare to make sure the channel is secure in BB84?Decomposition of arbitrary 2 qubit operatorBB84 attack with entangled qubits exampleGrover's algorithm oracle matrixConsequences of Grover's algorithm
Which is the best way to check return result?
Detention in 1997
Mathematica command that allows it to read my intentions
How could indestructible materials be used in power generation?
ssTTsSTtRrriinInnnnNNNIiinngg
Madden-Julian Oscillation (MJO) - How to interpret the index?
Does the Idaho Potato Commission associate potato skins with healthy eating?
What mechanic is there to disable a threat instead of killing it?
Why do bosons tend to occupy the same state?
In 'Revenger,' what does 'cove' come from?
What exploit Are these user agents trying to use?
How much of data wrangling is a data scientist's job?
What about the virus in 12 Monkeys?
How to show a landlord what we have in savings?
Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?
Can my sorcerer use a spellbook only to collect spells and scribe scrolls, not cast?
Is there an expression that means doing something right before you will need it rather than doing it in case you might need it?
How do I deal with an unproductive colleague in a small company?
What type of content (depth/breadth) is expected for a short presentation for Asst Professor interview in the UK?
How to prevent "they're falling in love" trope
Avoiding the "not like other girls" trope?
Why does this cyclic subgroup have only 4 subgroups?
How would I stat a creature to be immune to everything but the Magic Missile spell? (just for fun)
Expand and Contract
Grover's algorithm: number of searches
Rigorous security proof for Wiesner's quantum moneyGrover's algorithm: where is the list?Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|Psi_0rangle$?HHL algorithm — problem with the outcome of postselectionCompact encoding of Boolean formula as oracleHow many bits do Alice and Bob needs to compare to make sure the channel is secure in BB84?Decomposition of arbitrary 2 qubit operatorBB84 attack with entangled qubits exampleGrover's algorithm oracle matrixConsequences of Grover's algorithm
$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=fracpi4cdot sin^-1left(frac1sqrt2^nright)-0.5$$
If I just do that for the number $2^56$ (DES keysize), then it follows that you need k iterations:
$$k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-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 2 days ago
Blue♦
6,62641556
asked 2 days ago
QuantaMagQuantaMag
1426
$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=fracpi4cdot sin^-1left(frac1sqrt2^nright)-0.5$$
If I just do that for the number $2^56$ (DES keysize), then it follows that you need k iterations:
$$k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-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 2 days ago
Blue♦
6,62641556
asked 2 days ago
QuantaMagQuantaMag
1426
$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/2simeq 2^27$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
2 days ago
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^56$ wrong in the calculation: $k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-0.5=210828713$
$endgroup$
– QuantaMag
2 days ago
$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.5sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
2 days ago
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=fracpi4cdot sin^-1left(frac1sqrt2^nright)-0.5$$
If I just do that for the number $2^56$ (DES keysize), then it follows that you need k iterations:
$$k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-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 2 days ago
Blue♦
6,62641556
asked 2 days ago
QuantaMagQuantaMag
1426
$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=fracpi4cdot sin^-1left(frac1sqrt2^nright)-0.5$$
If I just do that for the number $2^56$ (DES keysize), then it follows that you need k iterations:
$$k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-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 2 days ago
Blue♦
6,62641556
asked 2 days ago
QuantaMagQuantaMag
1426
edited 2 days ago
Blue♦
6,62641556
asked 2 days ago
QuantaMagQuantaMag
1426
edited 2 days ago
Blue♦
6,62641556
edited 2 days ago
Blue♦
6,62641556
edited 2 days ago
Blue♦
6,62641556
6,62641556
asked 2 days ago
QuantaMagQuantaMag
1426
asked 2 days ago
QuantaMagQuantaMag
1426
asked 2 days ago
QuantaMagQuantaMag
1426
1426
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^55$ classical queries would become $sim 2^55/2simeq 2^27$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
2 days ago
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^56$ wrong in the calculation: $k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-0.5=210828713$
$endgroup$
– QuantaMag
2 days ago
$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.5sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
2 days ago
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/2simeq 2^27$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
2 days ago
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^56$ wrong in the calculation: $k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-0.5=210828713$
$endgroup$
– QuantaMag
2 days ago
$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.5sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
2 days ago
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^55$ classical queries would become $sim 2^55/2simeq 2^27$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
2 days ago
$begingroup$
it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^55$ classical queries would become $sim 2^55/2simeq 2^27$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
2 days ago
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^56$ wrong in the calculation: $k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-0.5=210828713$
$endgroup$
– QuantaMag
2 days ago
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^56$ wrong in the calculation: $k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-0.5=210828713$
$endgroup$
– QuantaMag
2 days ago
$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.5sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
2 days ago
$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.5sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
2 days ago
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 2 days ago
Blue♦
6,62641556
answered 2 days ago
Yijun WangYijun Wang
412
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
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
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 2 days ago
Blue♦
6,62641556
answered 2 days ago
Yijun WangYijun Wang
412
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
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
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 2 days ago
Blue♦
6,62641556
answered 2 days ago
Yijun WangYijun Wang
412
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
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
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 2 days ago
Blue♦
6,62641556
answered 2 days ago
Yijun WangYijun Wang
412
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 2 days ago
Blue♦
6,62641556
answered 2 days ago
Yijun WangYijun Wang
412
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 2 days ago
Blue♦
6,62641556
edited 2 days ago
Blue♦
6,62641556
edited 2 days ago
Blue♦
6,62641556
6,62641556
answered 2 days ago
Yijun WangYijun Wang
412
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 2 days ago
Yijun WangYijun Wang
412
answered 2 days ago
Yijun WangYijun Wang
412
412
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
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
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
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
$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
2 days ago
$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
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
$begingroup$
Yes, I think so too.
$endgroup$
– Yijun Wang
2 days ago
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/2simeq 2^27$ queries in the quantum case. That's quite different from "$185$ searches"
$endgroup$
– glS
2 days ago
$begingroup$
Ok, I think so too, but do you agree with my calculation, or is $2^56$ wrong in the calculation: $k=fracpi4cdot sin^-1left(frac1sqrt2^56right)-0.5=210828713$
$endgroup$
– QuantaMag
2 days ago
$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.5sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text?
$endgroup$
– glS
2 days ago