Shor's algorithm beginning
This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that
$N^{2} leq 2^{n} leq 2N^{2}$
Why does such a number $n$ exist for any $N$?
algorithm mathematics shors-algorithm
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
add a comment |
This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that
$N^{2} leq 2^{n} leq 2N^{2}$
Why does such a number $n$ exist for any $N$?
algorithm mathematics shors-algorithm
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
add a comment |
This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that
$N^{2} leq 2^{n} leq 2N^{2}$
Why does such a number $n$ exist for any $N$?
algorithm mathematics shors-algorithm
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that
$N^{2} leq 2^{n} leq 2N^{2}$
Why does such a number $n$ exist for any $N$?
algorithm mathematics shors-algorithm
algorithm mathematics shors-algorithm
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
edited Dec 19 '18 at 19:33
Blue♦
5,67221354
5,67221354
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
asked Dec 19 '18 at 18:52
Dawn Barnaby
584
584
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:
$N^2 le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
$2^{a+1} le 2N^2 = 2(2^a+b) = 2^{a+1} + 2b$, because $b ge 0$.
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
add a comment |
If $2^k$ is less than $x$, you can increase $k$ by 1 without exceeding $2x$. Because if $2^k < x$ then $2 cdot 2^k < 2 cdot x$ and so $2^{k+1} < 2x$. If you start at $k=0$ and keep incrementing, $2^k$ will eventually exceed $x$, and at that exact moment you stop; knowing that you didn't also exceed $2x$ and so have met both criteria.
Or you can just use a closed-form definition:
$k = lceil log_2 x rceil$
Or, in the original variables:
$n = lceil log_2 N^2 rceil$
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
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%2f5017%2fshors-algorithm-beginning%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:
$N^2 le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
$2^{a+1} le 2N^2 = 2(2^a+b) = 2^{a+1} + 2b$, because $b ge 0$.
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
add a comment |
Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:
$N^2 le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
$2^{a+1} le 2N^2 = 2(2^a+b) = 2^{a+1} + 2b$, because $b ge 0$.
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
add a comment |
Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:
$N^2 le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
$2^{a+1} le 2N^2 = 2(2^a+b) = 2^{a+1} + 2b$, because $b ge 0$.
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:
$N^2 le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
$2^{a+1} le 2N^2 = 2(2^a+b) = 2^{a+1} + 2b$, because $b ge 0$.
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
answered Dec 19 '18 at 19:04
Mariia Mykhailova
1,190211
1,190211
add a comment |
add a comment |
If $2^k$ is less than $x$, you can increase $k$ by 1 without exceeding $2x$. Because if $2^k < x$ then $2 cdot 2^k < 2 cdot x$ and so $2^{k+1} < 2x$. If you start at $k=0$ and keep incrementing, $2^k$ will eventually exceed $x$, and at that exact moment you stop; knowing that you didn't also exceed $2x$ and so have met both criteria.
Or you can just use a closed-form definition:
$k = lceil log_2 x rceil$
Or, in the original variables:
$n = lceil log_2 N^2 rceil$
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
add a comment |
If $2^k$ is less than $x$, you can increase $k$ by 1 without exceeding $2x$. Because if $2^k < x$ then $2 cdot 2^k < 2 cdot x$ and so $2^{k+1} < 2x$. If you start at $k=0$ and keep incrementing, $2^k$ will eventually exceed $x$, and at that exact moment you stop; knowing that you didn't also exceed $2x$ and so have met both criteria.
Or you can just use a closed-form definition:
$k = lceil log_2 x rceil$
Or, in the original variables:
$n = lceil log_2 N^2 rceil$
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
add a comment |
If $2^k$ is less than $x$, you can increase $k$ by 1 without exceeding $2x$. Because if $2^k < x$ then $2 cdot 2^k < 2 cdot x$ and so $2^{k+1} < 2x$. If you start at $k=0$ and keep incrementing, $2^k$ will eventually exceed $x$, and at that exact moment you stop; knowing that you didn't also exceed $2x$ and so have met both criteria.
Or you can just use a closed-form definition:
$k = lceil log_2 x rceil$
Or, in the original variables:
$n = lceil log_2 N^2 rceil$
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
If $2^k$ is less than $x$, you can increase $k$ by 1 without exceeding $2x$. Because if $2^k < x$ then $2 cdot 2^k < 2 cdot x$ and so $2^{k+1} < 2x$. If you start at $k=0$ and keep incrementing, $2^k$ will eventually exceed $x$, and at that exact moment you stop; knowing that you didn't also exceed $2x$ and so have met both criteria.
Or you can just use a closed-form definition:
$k = lceil log_2 x rceil$
Or, in the original variables:
$n = lceil log_2 N^2 rceil$
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
answered Dec 19 '18 at 19:56
Craig Gidney
3,546220
3,546220
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f5017%2fshors-algorithm-beginning%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
