Jump to content

Talk:Shor's algorithm/Archive 1

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Tapeworms27 (talk | contribs) at 22:22, 14 April 2023 (Create page and archive posts). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)
Archive 1

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. — Preceding unsigned comment added by Odoketa (talkcontribs) 04:43, 4 July 2022 (UTC)

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?) -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. 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. 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 83.70.251.245 (talk) 23:33, 24 November 2008 (UTC)

Of course it is smaller, for large N. Which makes your comment redundant. --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. —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)? --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 [1] 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. --LC

Okey dokey. You might want to make a wiki node on that. -- CYD

OK. It's integer factorization. --LC

Thanks! -- 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 GNFS page is steeper than Shor's, and seems more correct. Anyone know for sure? --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. --Steve (talk) 16:50, 10 June 2008 (UTC)

Definition of f() in the 'classical part'

Shouldn't it be: : ? 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.

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. Aaron McDaid (talk - contribs) 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. 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. 84.227.226.196 07:03, 30 May 2006 (UTC)
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.

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. —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. Grokmoo 18:57, 16 June 2006 (UTC)
This entire section is uncited. Either needs a citation needed tag or to be removed. —Preceding unsigned comment added by 64.113.87.62 (talk) 23:16, 27 March 2009 (UTC)

Deleted! 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). --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.--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. Archimerged 06:05, 7 April 2007 (UTC)
I see one reference: 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 well known that there is no objective difference between i and –i. Insisting on writing "inverse" all over the place is irrelevant detail. —The preceding unsigned comment was added by Archimerged (talkcontribs) 02:39, 10 April 2007 (UTC).
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? —Preceding unsigned comment added by 128.40.159.177 (talk) 16:38, 16 November 2007 (UTC)

Did anyone ever check this?

The period finding subroutine has been somewhat wrong since the first time it was entered by CYD at 2002-01-07T17:34:03. [2].

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.

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.
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.) —Preceding unsigned comment added by 71.141.2.57 (talk) 02:32, 21 March 2008 (UTC)

Another question about time complexity

The intro says:

"Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)3) 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? 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) --141.162.101.50 19:51, 18 April 2007 (UTC)

What about AKS then ?

cf AKS_primality_test —Preceding unsigned comment added by 86.69.23.229 (talk) 17:44, 5 September 2009 (UTC)

AKS doesn't factor integers, it just tells you if it's prime or not. --Robin (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. --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.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 Skippydo 19:02, 8 August 2007 (UTC)

Notation question

What does the notation mean? —The preceding unsigned comment was added by Davidfstr (talkcontribs) 21:07, 18 July 2007.

it is Bra-ket notation 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? Skippydo 19:05, 8 August 2007 (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. —Preceding unsigned comment added by 90.204.187.96 (talk) 19:10, 23 March 2008 (UTC)

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). —Preceding unsigned comment added by 195.176.20.45 (talk) 14:32, 2 April 2008 (UTC)

The subject of this article was mentioned on Stargate Universe, Season 1, Episode 14, "Human," within the first 5 minutes, a character quoting almost for word the current third paragraph of the current article. 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:
,
A link to modulo operation or modular arithmetic should be included here - As a non-mathematician I'd forgotton what mod meant.
I have no idea what the first clause means. Could this be changed to i.e. the order of in , in other words the smallest positive integer r for which so physicists can stop worrying about the first clause, or would that change the meaning of the sentence?

--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. —UncleDouggie (talk) 04:59, 26 January 2011 (UTC)
Cheers :)--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 is not a prime power, and this can be easily tested (as in the current version of the article, is taken to be odd).
  • If is not a prime power, then if a number has a square root modulo , 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 of , two obvious square roots being and . This leads to a proper factorization of , as explained in the current version of the article.
  • Other factorization techniques, like the quadratic sieve, use a similar approach.

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

Andreas Carter 12:01, 5 February 2011 (UTC) — Preceding unsigned comment added by Andreas Carter (talkcontribs)

Did a revision as above as IP 151.80.163.9. Andreas Carter (talk) 23:49, 5 February 2011 (UTC)
A few small fixes. 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). 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. 82.131.210.163 (talk) 11:51, 20 March 2012 (UTC)

The above source does not seem to me to be reliable. - 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. - Fartherred (talk) 15:20, 26 July 2012 (UTC)

done--agr (talk) 16:01, 26 July 2012 (UTC)

Classical part

In the 'classical part' section, it says in step 7 that gcd(ar/2 ± 1, N) is a nontrivial factor of N. Does this mean that both gcd(ar/2 + 1, N) and gcd(ar/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. BronzeRatio (talk) 17:00, 20 September 2013 (UTC)

The proof of the + part is exactly equivalent to the - part. 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? 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. 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. 87.149.72.190 (talk) 09:31, 9 October 2014 (UTC)
Stay Tuned! https://en.wikipedia.org/wiki/Quantum_computing#Timeline 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?

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? 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 should be the period of the periodic fctn . Given that a periodic function has a constant period across its whole definition range according to the Wikipedia article on periodic functions, I cannot see that is periodic with a constant period . Assuming it were periodic and r would be its period, we could write , an arbitrary integer number, hence , . Here, is not a constant but depends on our choice of . 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. 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. 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) ? Boeing720 (talk) 03:52, 21 December 2017 (UTC)

Procedure

Should this be:

 ?

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". — Preceding unsigned comment added by 82.15.21.214 (talk) 10:54, 4 July 2019 (UTC)
The text should say clearly whether "power of a prime" includes first powers and nought-th powers. — Preceding unsigned comment added by 82.15.21.214 (talk) 11:12, 4 July 2019 (UTC)

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

The article says things like "square root of 1 modulo " or . 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 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 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 " 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. 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". 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. XilOnGlennSt (talk) 14:18, 18 October 2022 (UTC)