Talk:Shor's algorithm: Difference between revisions

Revision as of 20:54, 11 February 2023

Revision as of 22:22, 14 April 2023

Line 3:

{{physics|class=c|importance=mid}}

}}

==More clarity?==

I got here from reading about encryption. I believe this algorithm exists. I think it might be faster than other ways of doing it. This article doesn't convey that in a clear manner to most folks. I think a little more clarity in a second paragraph explaining how this is better than whatever alternatives there are might be useful. <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Odoketa|Odoketa]] ([[User talk:Odoketa#top|talk]] • [[Special:Contributions/Odoketa|contribs]]) 04:43, 4 July 2022 (UTC)</span> <!--Autosigned by SineBot-->

==Time complexity of Shor's algorithm==

In Shor's original paper, he writes

"...Our quantum factoring algorithm takes asymptotically O((log n)^2 (log log n) (log log log n)) steps on a quantum computer, along with a polynomial (in log n) amount of post-processing time on a classical computer that is used to convert the output of

the quantum computer to factors of n..."

How does this compare with the O((log n)^3) figure given on the Wikipedia page? I don't believe the expression Shor gives and the expression on the Wikipedia page are equivalent, unless the definitions of ''n'' in use are different, or if Shor is measuring something else. (More importantly, how was the O((log n)^3) figure arrived at?) -[[User:Yipdw|Yipdw]] 06:02, 14 May 2006 (UTC)

: Big O notation gives an upper bound on running time, so O((log n)^3) is a weaker statment than O((log n)^2 (log log n) (log log log n)). Eg. Shor's statemtent implies the statement that is given in the Wikipedia. O((log n)^3) could have been arrived at by simply observing that O(log n) contains log log n * log log log n.

:Of course we want to give the most precise estimate possible; but if the postprocessing is O((log n)^3), we might as well summarize it as such. [[User:Dcoetzee|Dcoetzee]] 21:19, 25 September 2008 (UTC)

:To clarify (13 years later...), the O((log n)^2 (log log n) (log log log n)) figure is using the Schonhage-Strassen algorithm to perform multiplication, which is asymptotically optimal but not practical (and also seems to require a superlinear number of qubits). In practice, one expects to run the algorithm in O((log N)^3) time with a qubit cost linear in n. [[Special:Contributions/2601:647:500:406:E844:3188:155B:9E60|2601:647:500:406:E844:3188:155B:9E60]] ([[User talk:2601:647:500:406:E844:3188:155B:9E60|talk]]) 00:09, 25 April 2021 (UTC)

Hate to break it to ye, but (logN)^3 isn't smaller than exp[(logN)^(1/2)*(log(logN))^(2/3)]. Which makes the algorithm redundant ;p [[Special:Contributions/83.70.251.245|83.70.251.245]] ([[User talk:83.70.251.245|talk]]) 23:33, 24 November 2008 (UTC)

:Of course it is smaller, for large N. Which makes your comment redundant. --[[User:Roentgenium111|Roentgenium111]] ([[User talk:Roentgenium111|talk]]) 23:40, 15 November 2010 (UTC)

::Although it is a great example of a plot being misleading for small N. The functions don't actually cross until N = 92,319,930. —[[User:Keenan Pepper|Keenan Pepper]] 02:08, 16 November 2010 (UTC)

== Space Complexity ==

If N is the number to be factored rather than the number of qubits needed to represent the number, could I observe that either

:a) The O(N) space complexity is wrong: O(n) where n is the number of bits needed to represent N, or O(log N).

:b) The O(N) space complexity makes this algorithm just about useless. Can't hope to crack 512 bit encryption needing 2^513 qubits.

By my understanding, the case is (a)? --[[User:141.233.176.14|141.233.176.14]] 16:02, 30 April 2007 (UTC)

==Speed of various classical factoring algorithms==

The article said the best classical factoring algorithms are O(e^N). The author presumably meant theta rather than O. The General Number Field Sieve [http://citeseer.nj.nec.com/398050.html] is significantly faster than that, with a running time of theta(exp(((64/9)*log N)^1/3 (log log N)^2/3). I've changed the sentence to claim superpolynomial rather than exponential. --[[user:LC|LC]]

Okey dokey. You might want to make a wiki node on that. -- [[user:CYD|CYD]]

OK. It's [[:integer factorization|integer factorization]]. --[[user:LC|LC]]

Thanks! -- [[user:CYD|CYD]]

What's happening here? I'm not the only one who has noticed, but the GNFS Big-O is still all wrong on this page. O(2^((log N)^(1/3))) is too fast. The O(exp(x^(1/3)*log(x)^(2/3))) implied by the [[General_number_field_sieve|GNFS]] page is steeper than Shor's, and seems more correct. Anyone know for sure? --[[user:ProfessorThunderlips|ProfessorThunderlips]]

:...where x=log N?? Are you sure you aren't confusing an expression in terms of the "number of bits" with an expression in terms of the number itself?

:When I look at it, the [[GNFS]] article expression seems more-or-less equivalent to this article's, except saying c = log 2 and neglecting the "log log" term.

:By the way, there should certainly be a link somewhere in that third sentence. --[[User:Sbyrnes321|Steve]] ([[User talk:Sbyrnes321|talk]]) 16:50, 10 June 2008 (UTC)

==Encryption schemes not vulnerable to quantum computing==

Line 59 ⟶ 13:

::The first few lines of the description of the algorithm state that the number N '''cannot''' be the power of a prime (say P^Q). How difficult would it be to implement an encryption scheme that raised a prime number to a prime exponent? That would seem to solve the problem as well, wouldn't it? -- [[User:TheLastWordSword|TheLastWordSword]] ([[User talk:TheLastWordSword|talk]]) 22:21, 9 January 2014 (UTC)

==Definition of f() in the 'classical part'==

Shouldn't it be: :<math>f(r) = a^r\ \mbox{mod}\ N</math> ? Evan Ettinger.

== Jones' Algorithm==

Shor and Jones (Jones's Period Proxy Algorithm) use the same algorithm, however, Shor focusses on using a quantum computer and Jones looks for hyper-reduced reptends to solve in polynomial time.

[[User:166.70.15.234|166.70.15.234]] 18:10, 2 Apr 2005 (UTC)

==Error in the 'classical' part==

Isn't this wrong:

:''If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.''

It should be ''trivial'' factor, shouldn't it? I'll change it myself soon if no-one replies. [[User:Aaron McDaid|Aaron McDaid]] <small>([[User_talk:Aaron McDaid|talk]] - [[Special:Contributions/Aaron McDaid|contribs]]) </small> 10:34, 12 February 2006 (UTC)

: No. The step is correct. The chances that ''gcd(a,N) > 1'' are very small when factoring large integers. So in practice this step should always fail to find a factor. Note, however, that the remainder of the algorithm rks if ''gcd(a,N)=1''. Furthermore testing ''gcd(a,N)'' is important when factoring small integers such as 15. [[User:24.228.93.22|24.228.93.22]] 14:47, 16 February 2006 (UTC)

: ''Trivial'' factors (or divisors) of N are by definition N and 1. Nontrivial factors are all factors of N other than N and 1. So the article was correct. [[User:84.227.226.196|84.227.226.196]] 07:03, 30 May 2006 (UTC)

== External link removed ==

: I removed the external link simply because it is NOT an implementation of Shor's algorithm in php. Such an implementation is impossible because a quantum dynamical system cannot be simulated with a classical system. The implementation ignores the entire quantum portion of the algorithm.

[[User:LHon|LHon]] 09:42, 16 April 2006 (UTC)

::''...a quantum dynamical system cannot be simulated with a classical system...'' Sure it can, just not very efficiently. I'm putting the link back because it's relevant and not spam. —[[User:Keenan Pepper|Keenan Pepper]] 16:58, 16 April 2006 (UTC)

== Many Worlds Interpretation ==

Can someone fix the article so that it doesn't suggest that the many worlds interpretation has been established? I'd do it myself if I was an expert in this area.

:: I removed the offending paragraph, which was not only severly POV but blatantly false. I don't think something of this nature is even necessary in this article, but if someone wants to add something a little less POV, that would probably be ok. [[User:Grokmoo|Grokmoo]] 18:57, 16 June 2006 (UTC)

:::This entire section is uncited. Either needs a citation needed tag or to be removed. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.113.87.62|64.113.87.62]] ([[User talk:64.113.87.62|talk]]) 23:16, 27 March 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

Deleted! [[User:Skippydo|Skippydo]] ([[User talk:Skippydo|talk]]) 21:13, 28 March 2009 (UTC)

== QFT? ==

Throughout the article, it is stated many times that Shor's Algorithm uses the Quantum Fourier Transform (QFT). In fact, it uses the inverse of the QFT (the same circuit, only backwards). I haven't changed it myself because I want to make sure I'm not completely off-base here.

Can anyone else either support or refute this (I don't care if I'm wrong, so long as the article is correct).

--[[User:RckmRobot|RckmRobot]] 14:48, 16 June 2006 (UTC)

*After looking into this, I found out that it ''is'' in fact the inverse QFT rather than the "normal" QFT that is used in implementing Shor's Algorithm. I fixed the article accordingly.--[[User:RckmRobot|RckmRobot]] 17:54, 21 June 2006 (UTC)

::Can you give a source for this? Shor's original paper uses forward transform. Besides, there is little difference. It just needs to be consistent, use forward then back, or back then forward. [[User:Archimerged|Archimerged]] 06:05, 7 April 2007 (UTC)

::I see one reference: [http://people.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf Mermin] p. 14. But on p. 15, Mermin writes "This is precisely the form (3.44) of UFT itself, except that each V is replaced by its adjoint, which (3.40) shows amounts to replacing each ''i'' by ''–i'' in the arguments of all the phase factors. This is exactly what one does to invert the ordinary functional Fourier transform." It is [[Imaginary_unit#i_and_.E2.88.92i|well known]] that there is no objective difference between ''i'' and ''–i''. Insisting on writing "inverse" all over the place is irrelevant detail. <small>—The preceding [[Wikipedia:Sign your posts on talk pages|unsigned]] comment was added by [[User:Archimerged|Archimerged]] ([[User talk:Archimerged|talk]] • [[Special:Contributions/Archimerged|contribs]]) 02:39, 10 April 2007 (UTC).</small><!-- HagermanBot Auto-Unsigned -->

:::Although Mermin does point out that there's no change to the magnitude of any of the phases (hence whether we use inverse or not before measuring the first register doesn't really make a difference), I think a reference to the equivalence of the forward and inverse transforms at the appropriate point in the article would be a good idea to help avoid confusion. What do the rest of you think? <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/128.40.159.177|128.40.159.177]] ([[User talk:128.40.159.177|talk]]) 16:38, 16 November 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

==Implementation==

Line 116 ⟶ 26:

:::Though I certainly don't understand the details, if you read the paper [http://cryptome.org/shor-nature.pdf] it explains that a clever choice of <math>a</math> in the modular exponentiation <math>f(x)=a^x Mod(N)</math>, allows one of the two registers to be reduced to just 2 qubits, so in principle just 6qubits are needed for the experiment, they used 7 qubits because it was in some way more rigorous (to do with finding extra periodicities in f(x)). [[User:Sbandrews|sbandrews]] 17:25, 17 December 2006 (UTC)

== Did anyone ever check this? ==

The period finding subroutine has been somewhat wrong since the first time it was entered by [[User:CYD|CYD]] at 2002-01-07T17:34:03. [http://en.wikipedia.org/w/index.php?title=Shors_algorithm&oldid=285882].

If you look at Shor's paper, page 16, note that the Finite Fourier Transform is performed on q points, where n^2 < q <= 2n^2. This article has it on N points. I am correcting it.

[[User:Archimerged|Archimerged]] 05:11, 7 April 2007 (UTC)

:I added {fact} after changing an N to a Q because I'm not sure in that case if the change is correct. Probably the correct citation is Shor's paper but it must be checked.

:[[User:Archimerged|Archimerged]] 03:30, 10 April 2007 (UTC)

Although it is incorrect, describing the algorithm with the QFT mod N probably makes more sense for most readers, since it avoids error estimates. These error estimates are the most technical, but least important, part of Shor's paper. (The problem of course is that we don't know an efficient implementation of the QFT mod N.) <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/71.141.2.57|71.141.2.57]] ([[User talk:71.141.2.57|talk]]) 02:32, 21 March 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Another question about time complexity ==

The intro says:

:"''Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)³) time''"

and then says:

:"''One way to crack RSA encryption is by factoring N ... Shor's algorithm can crack RSA in polynomial time''"

Are these two quotes not contradictory? [[User:Oli Filth|Oli Filth]] 18:26, 17 April 2007 (UTC)

: Polynomial in the size of the input, which is log N bits (because you need that many to input N) --[[User:141.162.101.50|141.162.101.50]] 19:51, 18 April 2007 (UTC)

'''What about AKS then ?'''

cf AKS_primality_test <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.69.23.229|86.69.23.229]] ([[User talk:86.69.23.229|talk]]) 17:44, 5 September 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:AKS doesn't factor integers, it just tells you if it's prime or not. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 19:44, 5 September 2009 (UTC)

== Ruby implementation stuff ==

Why is ''shor_fact'' computing ''a1 = gcd(a ** (r/2) ,n)'', and then testing whether that is a non-trivial factor of N? We already know that gcd(a, n) = 1, so a1 will most certainly be 1 too. It also occasionally tries a = 1: this is most certainly useless.

''find_r'' is also fairly inefficient - it computes a full power a**r, takes the remainder mod n, then computes the next full power a ** (r+1), takes the remainder..., etc - resulting in O(answer^2) behavior. Something like:

def find_r(a,n)

cand = a % n

r = 1

while cand != 1

cand = (cand * a) % n

r += 1

end

return r

end

will work much better.

I know this is a proof-of-concept implementation, but it should at least look vaguely efficient. Quantum computing should not be used to make up for bad code :P.

--[[User:141.162.101.50|141.162.101.50]] 20:24, 18 April 2007 (UTC)

This implementation does not belong here. It does not implement the quantum portion shor's algorithm which cannot be done in Ruby. There is a set of "quantum c" libs complete with proper quantum implementations of various algorithms if anyone was curious.[[User:125.14.79.216|125.14.79.216]] 12:57, 2 May 2007 (UTC)

== Probability ==

with what probability Shor's algorithm gives corect answer?

:See http://www.cs.uwaterloo.ca/~watrous/lecture-notes.html [[User:Skippydo|Skippydo]] 19:02, 8 August 2007 (UTC)

== Notation question ==

What does the notation <math>\left|x\right\rangle</math> mean? <small>—The preceding [[Wikipedia:Signatures|unsigned]] comment was added by [[User:Davidfstr|Davidfstr]] ([[User talk:Davidfstr|talk]] • [[Special:Contributions/Davidfstr|contribs]]){{#if:21:07, 18 July 2007|&#32;21:07, 18 July 2007}}.</small><!-- Template:Unsigned -->

:it is [[Bra-ket notation]] [[user:sbandrews|sbandrews]] ([[user_talk:sbandrews|t]]) 21:15, 18 July 2007 (UTC)

== Quantum simulation also use QFT ==

Why isnt article about quantum simulation with quantum computer? This algorithm gives exponentional spedup and use quantum furie transform like Shor algorithm. [[Cnotgate]]

:Agreed, there should be one. I would make a stub myself but I know absolutely nothing about the subject. You should start an article [[Quantum Simulation]] if you happen to have knowledge on the subject. By the way, do you understand what I mean when I say ''sign your posts''? [[User:Skippydo|Skippydo]] 19:05, 8 August 2007 (UTC)

== Article is confusing ==

Line 218 ⟶ 57:

Although the article is difficult, what do you expect, if you don't know the subject? The problem is, we would have to explain a load of of mathematics (already covered in other articles) to get there. It's easier to use a hyperlink. If we write an article about Windows 98, we aren't going to include the whole history of Microsoft, even though you might need to know it, to understand why Win98 was necessary to make, or what came before and after it. Sometimes you have to click your mouse and read. [[Special:Contributions/2A00:23C5:FE18:2701:D405:F957:2002:B538|2A00:23C5:FE18:2701:D405:F957:2002:B538]] ([[User talk:2A00:23C5:FE18:2701:D405:F957:2002:B538|talk]]) 06:25, 15 August 2022 (UTC)

== Need to redirect because of apostrophe ==

The wikipedia page at "Shor's_algorithm" needs to be redirected to the one at "Shor%27s_algorithm". I don't know how to do this myself but the former page is older and has errors.... Eh? I just tried this again and can't reproduce this error. Nevermind. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/90.204.187.96|90.204.187.96]] ([[User talk:90.204.187.96|talk]]) 19:10, 23 March 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Possibly Incorrect Reference ==

I am not quite sure what the wiki etiquette is here: I sort of suspect that the "David Beckman" linked to in the references is not the same as the author of the paper referenced (I doubt that there are too many professional football coaches writing papers on quantum computation). <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/195.176.20.45|195.176.20.45]] ([[User talk:195.176.20.45|talk]]) 14:32, 2 April 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Shor NMR ==

Line 618 ⟶ 449:

The Bristol team's approach makes use of waveguides...</blockquote>

I'll let the more expert and more up to date of you add something from/about this as you see fit..sounds like a step forward :-) --[[User:Harel|Harel]] ([[User talk:Harel|talk]]) 02:55, 6 September 2009 (UTC)

== References In Popular Culture ==

The subject of this article was mentioned on [[Stargate Universe]], Season 1, Episode 14, "[[Human_(Stargate_Universe)|Human]]," within the first 5 minutes, a character quoting almost for word the current third paragraph of the current article.

[[Special:Contributions/99.155.82.102|99.155.82.102]] ([[User talk:99.155.82.102|talk]]) 06:52, 4 September 2010 (UTC)

==Edit requests, detailed feedback==

I'm a physicist trying to understand what quantum computers are useful for. This article has a lot of good points, the lead was interesting, but I wanted to point out the points where a reader who doesn't have a maths degree will get lost. I'd edit it myself but I don't want to accidentally introduce inaccuracies, I hope another editor can help.

* The problem we are trying to solve is: given a '''(without loss of generality odd)''' composite number N... ''Does this mean N has to be odd? Is this simply because if it were even it would obviously have 2 as a factor? Could this briefly be explained in a footnote please?''

* 4.Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:

:<math>f(x) = a^x\ \mbox{mod}\ N</math>,

:''A link to [[modulo operation]] or [[modular arithmetic]] should be included here - As a non-mathematician I'd forgotton what mod meant.''

* i.e. the [[order (group theory)|order]] <math>r</math> of <math>a</math> in [[Multiplicative group of integers modulo n|<math>(\mathbb{Z}_N)^\times</math>]], or the smallest positive integer ''r'' for which <math>f(x+r) = f(x)</math>

</li>

:''I have no idea what the first clause means. Could this be changed to'' i.e. the [[order (group theory)|order]] <math>r</math> of <math>a</math> in [[Multiplicative group of integers modulo n|<math>(\mathbb{Z}_N)^\times</math>]], '''in other words''' the smallest positive integer ''r'' for which <math>f(x+r) = f(x)</math></li>''so physicists can stop worrying about the first clause, or would that change the meaning of the sentence?''

--[[User:Physics is all gnomes|Physics is all gnomes]] ([[User talk:Physics is all gnomes|talk]]) 00:54, 27 December 2010 (UTC)

:{{done}} I added the link to [[modular arithmetic]] on step 6 instead of step 4 because step 4 is a LaTeX graphic that can't support a link. I also linked the alternate [[modulo operation]] further down where it is used for clarity. —[[User:UncleDouggie|UncleDouggie]]&nbsp;([[User talk:UncleDouggie|talk]]) 04:59, 26 January 2011 (UTC)

::Cheers :)--[[User:Physics is all gnomes|Physics is all gnomes]] ([[User talk:Physics is all gnomes|talk]]) 12:26, 26 January 2011 (UTC)

==Will be doing some editing on the number-theoretic part==

In the next few days I plan to do some minor edit work on the number-theoretic part of this otherwise excellent article. I want to make clear a few points:

* The algorithm works if and only if <math>N</math> is not a prime power, and this can be easily tested (as in the current version of the article, <math>N</math> is taken to be odd).

* If <math>N</math> is not a prime power, then if a number <math>c</math> has a square root modulo <math>N</math>, it has at least four such square roots. (This follows from the [[Chinese remainder theorem]].) The algorithm aims at finding more than two square roots modulo <math>N</math> of <math>c = 1</math>, two obvious square roots being <math>1</math> and <math>-1</math>. This leads to a proper factorization of <math>N</math>, as explained in the current version of the article.

* Other factorization techniques, like the [[quadratic sieve]], use a similar approach.

At one point, <math>N</math> appears to be taken as the product of two primes, one of which is unfortunately called <math>q</math>. Will clear up that too.

Andreas Carter 12:01, 5 February 2011 (UTC) <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Andreas Carter|Andreas Carter]] ([[User talk:Andreas Carter|talk]] • [[Special:Contributions/Andreas Carter|contribs]]) </span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

:Did a revision as above as IP 151.80.163.9. [[User:Andreas Carter|Andreas Carter]] ([[User talk:Andreas Carter|talk]]) 23:49, 5 February 2011 (UTC)

::A few small fixes. [[User:Andreas Carter|Andreas Carter]] ([[User talk:Andreas Carter|talk]]) 10:51, 6 February 2011 (UTC)

== Specify types of mathematical entities ==

Near the bottom: ''"For simplicity assume that there is a y such that yr/Q is an integer"''

If y, r and Q are all real numbers, then y trivially exists. What are they, then? Matrices or something? Perhaps this could be specified in the article (or made easier to find or re-mentioned at this point if it is already specified). <span style="color:Purple; font-size:13pt;">☺</span>[[User:Coppertwig|Coppertwig]] ([[User talk:Coppertwig|talk]]) 15:45, 18 September 2011 (UTC)

== In soviet America, Cryptome decrypts you. ==

Has USA possesed practical QC Shor AL since 1995?

Though this be madness, yet there is method in it: http://cryptome.org/2012/03/qc-footprint.htm

Cognitive footprint biometric application in a real-world-functional implementation requires an advanced recurrent neural network.

The recurrent neural network is related to or descended from a classified system for cracking public-private key cryptography in the 1990s.

Anglo-americans have had access to practical, production use quantum computer power since about 1995. I strongly suspect that both China and Russia later developed operational QCs along similar principles.

The QC approach that actually works, is production-ready and scale-able: to run a virtual Turing machine atop a winner-take-all-style teleportation/entanglement-based recurrent topological quantum neural network (QNN).

Even a basic neural network is Turing Complete, because a NN can perfectly emulate an XOR gate. Multiple XOR gates can be used to construct a Turing machine and a quantum neural network can emulate a quantum Turing machine.

The underlying physical system for this type of QNN is interactions between non-abelian anyons in a two dimensional electron gas (2DEG). The primary math required is Braid Theory, a branch of the Knot Theory.

The primary purpose of this system, from the anglo-american perspective, is to run Shor's algorithm to crack public/private key cryptography.

A perusal of current known quantum algorithms, combined with a survey of current advanced AI applications, may suggest other uses. [[Special:Contributions/82.131.210.163|82.131.210.163]] ([[User talk:82.131.210.163|talk]]) 11:51, 20 March 2012 (UTC)

:The above source does not seem to me to be reliable. - [[User:Fartherred|Fartherred]] ([[User talk:Fartherred|talk]]) 15:20, 26 July 2012 (UTC)

==Making clear the conjectural nature of the use of Shor's algorithm==

Instead of "...Shor's algorithm can be used to break public-key cryptography schemes..." the verb could should be used to make it clear that the article is referring to a conjectural device. - [[User:Fartherred|Fartherred]] ([[User talk:Fartherred|talk]]) 15:20, 26 July 2012 (UTC)

:done--[[User:ArnoldReinhold|agr]] ([[User talk:ArnoldReinhold|talk]]) 16:01, 26 July 2012 (UTC)

== Classical part ==

In the 'classical part' section, it says in step 7 that gcd(a^''r''/2 ± 1, ''N'') is a nontrivial factor of ''N''. Does this mean that both gcd(a^''r''/2 + 1, ''N'') and gcd(a^''r''/2 - 1, ''N'') are nontrivial factors of ''N''? In the 'Obtaining factors from period' section further down it only seems to demonstrate the ''-'' case.

Also the example at the end of the 'classical part' section doesn't appear to be finished. [[User:BronzeRatio|BronzeRatio]] ([[User talk:BronzeRatio|talk]]) 17:00, 20 September 2013 (UTC)

The proof of the + part is exactly equivalent to the - part.

[[User:O.mangold|O.mangold]] ([[User talk:O.mangold|talk]]) 11:41, 16 January 2017 (UTC)

== Factoring 4096-bit number ==

I'm skeptical that "factoring of a 4096-bit number requires 4,947,802,324,992 quantum gates." It seems like it needs more on the order of log2(4096)^3 = 1728 gates.

I think the problem is that the lede uses 'N' both as the integer to be factored and it's length in bits. Any comments from quantum gurus? [[User:Sanpitch|Sanpitch]] ([[User talk:Sanpitch|talk]]) 16:14, 22 September 2014 (UTC)

:: OK, after re-reading it I think I'm ok with the use of N, and the large number of gates ("4,947,802,324,992") may be correct as well, though the reference for it just cites a third party for whom the link is dead. [[User:Sanpitch|Sanpitch]] ([[User talk:Sanpitch|talk]]) 00:58, 23 September 2014 (UTC)

:: If you need 4,947,802,324,992 (aka almost 5 TRILLION !!!!) gates and "custom circuits" for each choice of N (so you have to design an entirely new chip for each integer you want to factor?), Shor's algorithm will never break RSA. Haswell architecture has 1.4 billion transistors, which is more than three orders of magnitude lower and most of them are probably rather simple flip-flops for SRAM cache. [[Special:Contributions/87.149.72.190|87.149.72.190]] ([[User talk:87.149.72.190|talk]]) 09:31, 9 October 2014 (UTC)

::: Stay Tuned! https://en.wikipedia.org/wiki/Quantum_computing#Timeline [[Special:Contributions/47.142.131.89|47.142.131.89]] ([[User talk:47.142.131.89|talk]]) 20:54, 9 February 2017 (UTC)

== relating period to phi (euler totient) function ==

when n has 2 factors p and q, it is my understanding that the period will be (p-1)(q-1)/2

including this statement may make the explanation of period finding more apporachable. §

== Planck limits? ==

Do planck limits come into play in the QFT?

If ω is a Q'th root of unity, suppose the "circle" is the circumference of a 1 angstrom wide atom, or about 3 angstroms. If I did the math right, a value of Q around 2e25 will cause adjacent roots to be a planck distance apart. Wouldn't significantly higher values of Q start making nearby roots indistinguishable?

With Q ~ N^2, limiting Q to 2e25 limits N to about 5e12, which is far far smaller than values used by RSA, etc. Scaling to more macroscopic than an angstrom-sized atom doesn't change the numbers much.

Or does the QFT somehow bypass placnk limit considerations?

[[Special:Contributions/73.159.235.173|73.159.235.173]] ([[User talk:73.159.235.173|talk]]) 22:36, 26 November 2015 (UTC) David Linden

== Classical part description? ==

...that description can't be right, because it makes it look like random numbers are chosen until one is found one away from a number not coprime to N? [[User:Twin Bird|Twin Bird]] ([[User talk:Twin Bird|talk]]) 08:46, 4 September 2016 (UTC)

== Classical Part, Period and Periodic Function ==

I am not a mathematician, just trying to understand what's done. Reading that <math>r</math> should be the period of the periodic fctn <math>f(x)=a^x \bmod N</math>. Given that a periodic function has a constant period across its whole definition range according to the [[Periodic Function|Wikipedia article on periodic functions]], I cannot see that <math>f(x)</math> is periodic with a constant period <math>r</math>.

Assuming it were periodic and r would be its period, we could write

<math>a^{x+Ar}+AN=a^x</math>, <math>A</math> an arbitrary integer number, hence <math>x+Ar+\log_a(AN)=x</math>, <math>r=\log_a(AN)/A</math>.

Here, <math>r</math> is not a constant but depends on our choice of <math>A</math>. So either the definition of periodic functions is odd, or the statement in the article is, or I am wrong ... In that case, I might not be the only one and this again might deserve some clarification. [[User:Ufalke|Ufalke]] ([[User talk:Ufalke|talk]]) 16:59, 12 April 2017 (UTC)

== Quantum part, step 3 ==

:Let y be one of the r possible integers modulo Q such that yr/Q is an integer

To me that looks wrong somehow. As Q is a power of 2, chances are that GCD(Q,r) is very small. The condition requires that y is an integer multiple of Q/GCD(Q,r), thus there are only GCD(Q,r) y's in [0,Q-1] not r ones.

[[User:O.mangold|O.mangold]] ([[User talk:O.mangold|talk]]) 06:23, 12 October 2017 (UTC)

== About making the math accessible to more readers ==

If it's not possible to use an example in hard numbers, perhaps a C-code program could help (some, at least) ? [[User:Boeing720|Boeing720]] ([[User talk:Boeing720|talk]]) 03:52, 21 December 2017 (UTC)

== Procedure ==

<math> k \leq {\log_{2}}(N) </math>

Should this be:

<math> 1 > k \leq {\log_{2}}(N) </math> ?

Because, otherwise in the preceding test the first integer k to be evaluated is 1, which trivially yields the integer N under test of 1th root. This is a false positive result that ought to be eliminated.

:"1 > k" might be a mistake for "1 < k". <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/82.15.21.214|82.15.21.214]] ([[User talk:82.15.21.214#top|talk]]) 10:54, 4 July 2019 (UTC)</small> <!--Autosigned by SineBot-->

::The text should say clearly whether "power of a prime" includes first powers and nought-th powers. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/82.15.21.214|82.15.21.214]] ([[User talk:82.15.21.214#top|talk]]) 11:12, 4 July 2019 (UTC)</small> <!--Autosigned by SineBot-->

== Please define "size of the integer" in opening paragraphs? ==

Line 761 ⟶ 455:

: It's the entropy of the search space in bits. [[User:Vecr|Vecr]] ([[User talk:Vecr|talk]]) 07:47, 22 September 2020 (UTC)

== Am I the only one confused by the "1 mod N" notation? ==

The article says things like "square root <math>b</math> of 1 modulo <math>N</math>" or <math>a^r \equiv 1 \;\rm{mod} \; N</math>. Maybe I'm just being thick, or too much of a programmer, but without an explanation of that notation, or at least parentheses to bring it in line with the linked [[Modular arithmetic|modulo]] page, I find it confusing. I read "1 mod N" as "the remainder when you divide 1 by N", which is always 1 if N is a positive integer, but that's obviously not right in context. I guess it means something like <math>a^r \; \rm{mod} \; N = 1</math> in the notation I'm used to. If people feel that more traditional notation would decrease clarity or accuracy, I suggest adding parentheses around "mod <math>N</math>" and a sentence or two explaining that it applies to both sides of the equation (as done in [[Modular arithmetic]]) or at least an explanation of the notation used and why it's different from other texts. [[Special:Contributions/207.224.243.154|207.224.243.154]] ([[User talk:207.224.243.154|talk]]) 20:29, 31 August 2022 (UTC)

== inconsistency in register sizes ==

I think there is a minor error in sizing of the second register, apologies if not, I found the notation confusing!

There is a statement "The input and output qubit registers need to hold superpositions of values from 0 to Q-1, and so have q qubits each". Also the equation under point 2 in section "Quantum part: period-finding subroutine" indicates the second register initially has "q" qubits. But immediately following that is the sentence: "However, the (q+n) qubits, i.e, the q input qubits and n (>log2(N)) output qubits, are now entangled or not..." This sentence implies the second register has "n" qubits. Also the figure indicates the second register has "n" qubits.

I suspect the second register using "n" qubits is correct, since it only needs to store a number of maximum size approximately N (as the computations into that register are mod N). The first register needs to be able to store numbers of maximum size Q which is somewhere between N^2 and 2N^2 and therefore needs more (ie "q~log2(Q)") qubits. But this is assuming what is meant by "n" is the the number of bits to represent N, that is, n=floor(log2(N))+1, which is a common notation? I couldn't see it defined per se. If this is correct then the subscript on the QFT^{-1} in the figure should also be fixed, the QFT is over N not 2n.

As a separate issue I would also quibble with the statement about phase kickback. At that point in the algorithm all phases are still +1. Phase kickback refers to cases where the phase of a state has a form something like (-1)^f(x), or exp(i*f(x)) or similar. Here I think its misleading to call the evaluation into the second register "phase kickback". [[Special:Contributions/86.11.100.180|86.11.100.180]] ([[User talk:86.11.100.180|talk]]) 05:33, 13 October 2022 (UTC)

== Both A or B ? ==

The "Classical" section step 7 is logically confusing. "Both" implies A and B. If it's really A or B, then just state that. This is just a nit, but when I'm reading for detail, I get derailed by such things. [[User:XilOnGlennSt|XilOnGlennSt]] ([[User talk:XilOnGlennSt|talk]]) 14:18, 18 October 2022 (UTC)