Talk:Shor's algorithm: Difference between revisions

Revision as of 05:04, 5 December 2006

Latest revision as of 15:44, 13 May 2025

(267 intermediate revisions by 91 users not shown)

Line 1:

{{talkheader}}

{{physics|class=|importance=}}

{{WikiProject banner shell|class=B|

==Time complexity of Shor's algorithm==

{{WikiProject Mathematics|priority=mid}}

In Shor's original paper, he writes

{{physics|class=WikiProject Physics|importance=mid}}

{{WikiProject Computer science|importance=mid}}

"...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..."

{{Archives}}

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.

==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]]

==Encryption schemes not vulnerable to quantum computing==

Line 28 ⟶ 15:

: This is briefly discussed at [[quantum computer#The power of quantum computers]]. At the present time, ''only'' factorisation and discrete log based ciphers are known to be seriously affected (if a QC of sufficient size could be built). A quantum computer could be used to attack a symmetric cipher, but it's speed up is "only" to take the square root of the number of steps. This is a huge speed up for typical block ciphers, but is trivially defeated by doubling the key size. There exists a standard, thoroughly studied method to double the key size of any block cipher, namely triple encryption. Further, the most common key size used today - 128 bits - would only be reduced to a work factor of the order of <math>2^{64}</math>, which is still quite a tough job unless the information is extremely valuable. And the AES already has 192 and 256 bit modes built in. So, at our present level of knowledge, QC poses essentially no threat to symmetric encryption. [[User:Securiger|Securiger]] 07:40, 6 Oct 2004 (UTC)

::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)

:::{{ping|TheLastWordSword}} A power of prime, and any other perfect power for that matter, is trivial to factor by taking roots up to the log-base-2-of-Nth root of N, a polynomial time operation.--[[User:Jasper Deng|Jasper Deng]] [[User talk:Jasper Deng|(talk)]] 06:48, 19 October 2023 (UTC)

==Nature article==

== 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)

In "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (p. 883-884), the IBM team appears to make a clear claim to have constructed a quantum computer: "In the experiment, an ensemble of independent quantum computers rather than a single quantum computer was used…"

== 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)

They are also clear about their state preparation: "The desired initial state of the seven qubits is <math>|\psi_1></math> ˆ|0000001> (Fig. 1). However, experimentally we start from thermal equilibrium. The density matrix is then given by <math>\rho_{th}=e^{H_0/k_BT}/2^7,</math> with <math>k_BT >>\hbar\omega_i</math> at room temperature so each spin is in a statistical mixture of |0> and |1> (Fig. 3a). We converted <math>\rho_{th}</math> into a 7-spin effective pure state <math>\rho_1</math> via temporal averaging…"

::''...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)

There may be doubts about the nature of the calculation, but I think it's clear that the team did claim to build a quantum computer. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 17:46, 4 June 2008 (UTC)

[[Category:To do]]

:Lear from nature, and you will nothing to learn. <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Weekwhom|Weekwhom]] ([[User talk:Weekwhom|talk]] • [[Special:Contributions/Weekwhom|contribs]]) </span></small><!-- Template:Unsigned -->

== Many Worlds Interpretation ==

== Archive and other stuff ==

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.

So I've gone ahead and archived most of the rest of the posts on this page. There were multiple long discussions, many from literally 15 years ago, ~2006-2008, and I figured they weren't worth keeping. @[[User:Qq8|Qq8]], @[[User:Luca Innocenti|Luca Innocenti]], I noticed you two were talking on one the of the older posts, but the discussion wasn't really relevant to the older post, so I figured I could archive it, and you guys could make a new post. Your guyses edits to the page have been very good! The page looks a lot better than when I first saw it.

:: 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)

A few months ago in April, I made a drastic series of edits to the page, pretty much wiping out most of the algorithm explanation and replacing it with the baseline of what the article is right now, which is largely based off the quantum phase estimation formulation of the algorithm. The explanation for the quantum subroutine of the algorithm from before seemed mostly like giberish, so I just decided to get rid of it. I meant to look into it at some point, to see if there was some value there, but I haven't bothered, so if anybody else wants to look into that, go right ahead :)

== QFT? ==

Also, it may be a good idea to include information on the original formulation of Shor's algorithm without phase estimation. I think the original body of this article explained it that way (but again it was pretty bad). [[User:Tapeworms27|Tapeworms27]] ([[User talk:Tapeworms27|talk]]) 23:41, 5 August 2023 (UTC)

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.

:Also should we update the Wikiproject template quality levels? I'd like to think that the article has been improved a lot. I'm not familiar with assessing that, so that's a thing that could be done if anybody wants to. [[User:Tapeworms27|Tapeworms27]] ([[User talk:Tapeworms27|talk]]) 23:43, 5 August 2023 (UTC)

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

::@[[User:Tapeworms27|Tapeworms27]] thanks! I mostly agree with your changes, and archiving most of the old discussions here which were either stale or outdated with the current version of the wiki anyway.

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

::I'm not very familiar with quality assessment levels, but having had a quick look at [[Wikipedia:Content assessment]], I'm not so sure I'd rate the current version of this page as more than C. I think there's still plenty that can be done, both in quality of writing for some of the sections, and in additional content to add. For example, adding how the algorithm works out in an explicit toy example would help a lot digesting the material. Also some additional detail about the number of qubits required in the first register is needed: currently the article just says "2n is sufficient" without saying why.   [[User:Luca Innocenti|Luca]] ([[User talk:Luca Innocenti|talk]]) 20:58, 6 August 2023 (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)

== Simple Animation of Shor's ==

==Implementation==

There are many who don't accept the factorization of 15 as a valid "true quantum" implementation. Would an expert like to comment on why no one has gone beyond 15 in hardware implementations in the last 5 years? [[User:Lotte Monz|Lotte Monz]] 04:07, 7 July 2006 (UTC)

https://www.youtube.com/watch?v=nvk8xU2BNnY [[User:Doug youvan|Doug youvan]] ([[User talk:Doug youvan|talk]]) 15:34, 13 February 2024 (UTC)

:Any reference to these concerns? Also how many qbits does it take factor 21 and what is the maximum number of qbits have been implemented in a quantum computer? [[User:C-randles|crandles]] 15:16, 21 September 2006 (UTC)

== Added short section entitled Shor's algorithm Qiskit implementation ==

:It takes 2n qubits to factor a number n bits long. 21 requires 5 bits to represent and therefore would require a quantum computer with atleast 10 qubits to factor. [[User:198.37.27.79|198.37.27.79]] 03:04, 27 October 2006 (UTC)

I made modifications that I trust are acceptable. [[User:JavaFXpert|JavaFXpert]] ([[User talk:JavaFXpert|talk]]) 22:40, 20 February 2025 (UTC)

::Thanks. Though it does rather prompt the question of how 15 was factored with 7 qubits.[[User:C-randles|crandles]] 11:07, 27 October 2006 (UTC)