Talk:Shor's algorithm

Encryption schemes not vulnerable to quantum computing

"Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer."

Are there any encryption systems that would not be obsolete if a quantum computer becomes practical? That would be useful information to add here, if anyone knows. I have been trying to look this information up but nothing so far, anyone have any clues?--ShaunMacPherson 22:06, 12 Apr 2004 (UTC)

One time pads would be unaffected. Richard Farmbrough.

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 $2^{64}$, 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. 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? -- TheLastWordSword (talk) 22:21, 9 January 2014 (UTC)

@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.--Jasper Deng (talk) 06:48, 19 October 2023 (UTC)

Nature article

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

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

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. CRGreathouse (t | c) 17:46, 4 June 2008 (UTC)

Lear from nature, and you will nothing to learn. —Preceding unsigned comment added by Weekwhom (talk • contribs)

Archive and other stuff

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. @Qq8, @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.

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

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). Tapeworms27 (talk) 23:41, 5 August 2023 (UTC)

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. Tapeworms27 (talk) 23:43, 5 August 2023 (UTC)

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

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.   Luca (talk) 20:58, 6 August 2023 (UTC)

Simple Animation of Shor's

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