Talk:Shor's algorithm/Archive 1

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 (talk • contribs) 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: :$f(r)=a^{r}\ {\mbox{mod}}\ N$ ? 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)

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.

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 (talk • contribs) 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)³) 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 $\left|x\right\rangle$ mean? —The preceding unsigned comment was added by Davidfstr (talk • contribs) 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)

References In Popular Culture

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:

$f(x)=a^{x}\ {\mbox{mod}}\ N$,

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 $r$ of $a$ in $(\mathbb {Z} _{N})^{\times }$, or the smallest positive integer r for which $f(x+r)=f(x)$

I have no idea what the first clause means. Could this be changed to i.e. the order $r$ of $a$ in $(\mathbb {Z} _{N})^{\times }$, in other words the smallest positive integer r for which $f(x+r)=f(x)$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 $N$ is not a prime power, and this can be easily tested (as in the current version of the article, $N$ is taken to be odd).
• If $N$ is not a prime power, then if a number $c$ has a square root modulo $N$, 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 $N$ of $c=1$, two obvious square roots being $1$ and $-1$. This leads to a proper factorization of $N$, as explained in the current version of the article.
• Other factorization techniques, like the quadratic sieve, use a similar approach.

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

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

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(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. 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 $r$ should be the period of the periodic fctn $f(x)=a^{x}{\bmod {N}}$. 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 $f(x)$ is periodic with a constant period $r$. Assuming it were periodic and r would be its period, we could write $a^{x+Ar}+AN=a^{x}$, $A$ an arbitrary integer number, hence $x+Ar+\log _{a}(AN)=x$, $r=\log _{a}(AN)/A$. Here, $r$ is not a constant but depends on our choice of $A$. 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

$k\leq {\log _{2}}(N)$

Should this be:

$1>k\leq {\log _{2}}(N)$  ?

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 $b$ of 1 modulo $N$" or $a^{r}\equiv 1\;{\rm {{mod}\;N}}$. 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 $a^{r}\;{\rm {{mod}\;N=1}}$ 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 $N$" 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)

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? Lotte Monz 04:07, 7 July 2006 (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? crandles 15:16, 21 September 2006 (UTC)

"Macro systems that have been used as model quantum computing systems [14, 33,34] appear to implement not pure states but mixtures. Thus it appears that the NMR experiments do not validate quantum algorithm" - found in [3] sbandrews 19:22, 18 December 2006 (UTC)

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. 198.37.27.79 03:04, 27 October 2006 (UTC)

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

Though I certainly don't understand the details, if you read the paper [4] it explains that a clever choice of $a$ in the modular exponentiation $f(x)=a^{x}Mod(N)$, 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)). sbandrews 17:25, 17 December 2006 (UTC)

Article is confusing

Article "confusing" template added to top of the article, please rectify or discuss here before removing.

According to WikiProject Physics an article should "be accessible to the lay reader and yet are also useful to the professional working in the field.". This article is most surely not accessible to the lay reader. It does not explain to the layman what Shor's algorithm is and consists almost entirely of formulas and technical details for physicists. Look at the first line of the introduction "Shor's algorithm is a quantum algorithm for factoring an integer N in O((log N)3) time and O(log N) space, named after Peter Shor." - this is full of jargon. The layman will gain nothing by reading this article.

I suggest at least half the article be written for the layman explaining in simple terms what the algorithm is, what it can do, and why it may excel over classical algorithms. Layman will likely wonder exactly what quantum computing can do better than classical, and especially how it works.

One of the references, scottarronson blog, could provide clues for explaining it to the man in the street. 190.76.28.253 (talk) 05:19, 19 November 2007 (UTC)

It clearly states that Shor's algorithm is a factoring algorithm. Unfortunately, this is all a layperson could hope to understand about the algorithm. If you would provide more specific objections or suggest some alterations that could be made, I would be pleased to edit the article with you. Skippydo (talk) 05:48, 20 November 2007 (UTC)

Why did you add this template on a page that is NOT directly related to physics. It's true that it will look confusing for a physician because NOTHING in the article speaks about physics. This is about an algorithm, not currently implemtend in coimputer so it is still vaguely to computing. This is an article of mathematics. And for mathematicians, and computer theorists, this is quite clear. There are some approximations that are being corrected because mathematicians want exactness or prior definitions of the concepts when they are missing. But it is very clear at the mathematical level.

The article should not have this tag, even if there may be some link from an article speaking about quantum in physics, the quanta in physics are phenomens represented and modelized with mathematical models according to a physics theory, and *some proof* that this works remarkably well with experience, but *no proof* that this is the reality of physics (we are speaking in terms of probablities, and not truth, and this is the key element of today's scientific proof).

Where is the physical penomenom that is being studied in this article? Nowhere. Quanta belong to the domain of mathematics, not physics, even if physics use them. Here this algorithm is discussed to solve pure mathematical problems using mathemetical concepts. Computer cryptography just appears to use those mathematial problems.

But the article is purely about the mathematical construction of the algorithm, independantly of its implementation that still does not exist and that offers no solution for implemening it in a quantum computer, notably for extending the number of qubits (as said in the article attempts to build more than 7 qubits have failed because the additional qubits were not independant but mixing states of other qubits.

May be this is physics that is limiting the implementation of more than 7 qubits, and this difficulty for building more than 7 qubits is posibly demonstrating that this is caused by the nature of the physical phenomenoms that we can observe and measure or which we can see producing some effects. It seems strage than this number (7) is quite related to the known number of interactions: gravitation, magnetism, charge, spin... And may be we'll never have more than a dozen of measurable qubits. This reminds me the ongoing physical search for the "Big Unification"; the more we advance, the more we see that phenomenoms are correlated nad this reduces the number of fundamantal interactions, but at the same time we don't know the nature of about half of what builds the universe (still seeking where is the "missing mass" or "missing energy" of the Universe): if we can't see that universe, we can't see them interacting on qubit devices in ways that are measurable. As long as we can't take any measure of the state of a qubit, then we have no additional qubit at all usable in a quantum computer.

So if the search for more qubits is so difficult, it looks simpler to think about doubling the keysizes, and wait about 3 years to get the same performance in traditional computers. If we consider the very slow (and now stalled) growth of the number of qubits, then we can see that the research in quantum computer is a complete failure.

My opinion is that the best performance in computers and cryptography will not come from quantic theories, but theories of chaos, with the explosion of size of the interconnected network (Internet), like in our brains: the more the links we'll have, and the more nodes we'll also connect to it, the more the power of the net, independantly of the simultaneous growth of speed of our individual computers. verdy_p (talk) 18:59, 15 February 2008 (UTC)

5 years later... this article is still inaccessible to the layman. Won't somebody please do a better job of translation? thanks. 04:42, 22 August 2012 (UTC) — Preceding unsigned comment added by 97.126.111.140 (talk)

The first line tells the layperson everything they need to know. What else would you like to see? Skippydo (talk) 17:24, 22 August 2012 (UTC)

In 2020 this article is still meaningless to people who are not specialists in math or quantum computing. The introduction is borderline condescending and reads more like an overcompensating graduate student showing off to their friends. The article is supposed to explain the subject to people who want to learn about it, not to people who already understand it. — Preceding unsigned comment added by 37.235.104.6 (talk) 12:31, 29 August 2020 (UTC)

Some of us would like to understand more than just what's written in the first line. I have to agree with those who say this article is meaningless to all but those who already have a good grasp of the subject. It is so far out of reach of most people that it can, indeed, appear arrogantly condescending. I know for Shor that is not the intent. As someone who frequently has to translate the complexities of computer infrastructures into "human-speak" I also know how hard it is to make a complex subject accessible. The effort to do so, however, is rarely wasted. So can I echo the request of those above and ask that someone at least has crack at adding a section that us idiots have a chance of getting to grips with? 84.92.32.221 (talk) 09:44, 7 July 2022 (UTC)

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. 2A00:23C5:FE18:2701:D405:F957:2002:B538 (talk) 06:25, 15 August 2022 (UTC)

A lot can be done to make the article more accessible to nonexperts, or at least to not make it less accessible.

@Luca Innocenti, you recently replaced "non-quantum algorithms" with "classical algorithms", which is physics jargon that many computer scientist do not accept. It is a shorthand for "algorithms using classical rather than quantum physics" but is confusing because the systematic study of "classical algorithms" is more recent than quantum physics (60 years vs 110 years). Would you be open to restoring "non-quantum algorithms", which is clear to most people? Thanks Qq8 (talk) 21:48, 31 July 2023 (UTC)

@Qq8 I changed it because "classical algorithm" just sounds like a more direct term to me, and it's the standard I've always seen people use. That said, you might be absolutely right that different terminology is used in different fields. Could you point to modern cs references (presumably discussing quantum algorithms) using the "non-quantum algorithm" terminology? Luca (talk) 06:14, 1 August 2023 (UTC)

@Luca Innocenti I am perfectly aware of the term in the field. However, the Wikipedia is mostly for non-scientists, and the text should be accessible to ordinary people. "Classical algorithms" is confusing. "Non-quantum algorithms" seems clear. I can find some papers that use it, but that's kind of irrelevant, TBH. Qq8 (talk) 15:57, 1 August 2023 (UTC)

@Qq8 I see. That's a legitimate concern. If that's the point, we could have it both ways and write it as "classical (that is, non-quantum) algorithms"? Honestly though, pretty much all other wikipedia pages discussing quantum algorithms (or at least all I found) use the "classical X" terminology anyway. I agree this page has problems; I'd say it's quite inaccessible/hard to parse for experts, let alone for non-scientists. But I'm not convinced this particular terminology is what makes it inaccessible to a non-scientist. Luca (talk) 20:22, 1 August 2023 (UTC)

I can agree with pretty much everything you are saying. Of course one word can't make the article clear, but one word can make it more confusing! A good test is whether there is a wiki article for "Classical algorithms" - there isn't, and probably won't be because it's not a separate concept, but rather physics jargon for non-quantum algorithms (which aren't part of physics). Qq8 (talk) 21:11, 1 August 2023 (UTC)

Shor NMR

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using a quantum computer simulator with 7 psuedo-pure state qubits. Current NMR experiments should be considered as simulations of quantum computation rather than true quantum computation, since no entanglement appears in the physical states at any stage of the process.

The citation shows that it is possible to preform quantum computations without entanglement. It also mentions that it is convenient for NMR implementations. Nowhere does it mention experimental realizations of Shor's algorithm.

I believe we should include the following in the article:

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using a quantum computer with 7 qubits.

Skippydo (talk) 18:42, 26 May 2008 (UTC)

Why for you just don't read more articles about NMR, instead showing your don't understanding?

[http://nmr.physics.ox.ac.uk/pdfs/torino2.pdf More recently, it has been suggested that NMR might not be a quantum mechanical technique at all! When assessing this comment, it should be re- membered that "quantum mechanical" is used here with a technical meaning of "provably non-classical".]

[http://qt.tn.tudelft.nl/~lieven/papers/ENC_nmr.pdf Despite the rapid progress in recent years, scaling liquid state NMRQC to tens or hundreds of qubits may be impractical for several reasons, although none of them appear fundamental. In particular, as the number of qubits increases: the strength of the signal selected with current state initialization techniques decreases exponentially.]

Timeline of quantum computing

Since the NMR experiments cannot prepare pure quantum states and exhibit no quantum entanglement during computation, concerns have arisen about their quantum nature. In particular, it has been proved that the presence of entanglement is a necessary condition for quantum computation.

We give a constructive proof that all mixed states of N qubits in a sufficiently small neighborhood of the maximally mixed state are separable (unentangled). The construction provides an explicit representation of any such state as a mixture of product states. We give upper and lower bounds on the size of the neighborhood, which show that its extent decreases exponentially with the number of qubits. The bounds show that no entanglement appears in the physical states at any stage of present NMR experiments. Though this result raises questions about NMR quantum computation, further analysis would be necessary to assess the power of the general unitary transformations, which are indeed implemented in these experiments, in their action on separable states.Weekwhom

I never claimed to understand NMR, nor IBM's implementation of shor's algorithm. The burden of proof is on you to justify these changes you wish to make. My apologies that I do not have the time to read every paper on NMR, as you suggest. I will read what you have listed and get back to you. Skippydo (talk) 16:52, 27 May 2008 (UTC)

Your second link states:

Most recently, a seven-qubit quantum computer has been used to factor the number 15 using Shor’s algorithm.

I'm having trouble finding any reference to IBM's implementation not being real quantum computing. Could you be more specific in your citations or shed a little light on matters yourself? Skippydo (talk) 17:49, 27 May 2008 (UTC)

How much evidence need to you? You grasping each word... All NMR computers (how to call the hell them?) are not real! They just with tradition sometimes called NMR quantum computer, but with quantum computer there no any real relation. You can farther mislead people with your NMR "quantum computers". —Preceding unsigned comment added by Weekwhom (talk • contribs) 18:23, 27 May 2008 (UTC)

You may well be correct. I don't know enough about NMR implementations to say. Ideally, the article should include citations to such a claim. Certainly, you don't expect me or anyone else to simply take your word for it on the matter. I have heard other speak on your concerns, but I do not have the necessary expertise to integrate them into the article. Those changes you have made were not supported with citations. Skippydo (talk) 19:39, 27 May 2008 (UTC)

Show me where in original paper says, that it is 7 qubit quantum computer? [http://arxiv.org/pdf/quant-ph/0112176v1 Finally, our parameter-free decoherence model, a predictive tool for modeling quantum errors in this complex 7 system, provides an avenue for future design simulation of quantum computers.] —Preceding unsigned comment added by Weekwhom (talk • contribs) 04:36, 28 May 2008 (UTC)

"The custom-synthesized molecule used as the quantum computer for this experiment contains five 19F and two 13C spin-1/2 nuclei as qubits (Fig. 2). In a static magnetic field, each spin has two discrete energy eigenstates, |0i (spin-up) and |1i (spin-down), described by the Hamiltonian H0 = −Pi ¯h!iIzi, where !i/2� is the transition frequency between |0i and |1i and Iz is the ˆz component of the spin angular momentum operator. All seven spins in this molecule are remarkably well separated in frequency !i/2�, and interact pairwise via the J-coupling, described by HJ =Pi<j 2�¯hJijIziIzj [17]...." this is from the arxiv paper. --Ancheta Wis (talk) 10:40, 29 May 2008 (UTC)

According to your second link, a seven-qubit quantum computer has been used to factor the number 15 using Shor’s algorithm. In your most recent link The significance of our work lies in the demonstration of experimental and theoretical techniques for precise control and modelling of complex quantum computers. The third line on page 4, We converted ρth into a 7-spin effective pure state [11, 12] ρ1 via temporal averaging [9] (step 0); ρ1 constitutes a suitable initial state for Shor’s factoring algorithmin to a 7-spin effective pure state. However, these are not direct as first quote which I indicated and I'm not qualified to read too much into these statements.

All I want is a quote rising doubt to this. So far, you have not provided one. Skippydo (talk) 15:09, 28 May 2008 (UTC)

Show me quote of this: "In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using a quantum computer with 7 qubits." And it would be better from IBM paper! —Preceding unsigned comment added by Weekwhom (talk • contribs) 16:56, 28 May 2008 (UTC)

I believe we are talking in circles. I do not know how to proceed. I have requested help [5]. Skippydo (talk) 21:24, 28 May 2008 (UTC)

Those quotes don't saying somthing directly, but going round about shor's algorithm, quantum computer, 7 spins, 7 qubits and this words also prety carfuly separated... —Preceding unsigned comment added by Weekwhom (talk • contribs) 13:09, 29 May 2008 (UTC)

Quotes

From the arxiv paper:

Here we report an implementation of the simplest instance of Shor’s algorithm: factorization of N=15

We use seven spin-1/2 nuclei in a molecule as quantum bits

The custom-synthesized molecule used as the quantum computer for this experiment contains five 19F and two 13C spin-1/2 nuclei as qubits

This seems to indicate pretty clearly that they claim implementation of Shor's algorithm on N=15 using an experimentally-realized, 7-qubit quantum computer. Have I misunderstood the paper or this discussion? Let's all remember to keep this WP:CIVIL. Gnixon (talk) 14:41, 29 May 2008 (UTC)

I can use 4 or 8 coins to implement shor algorithm and factorize N=15.

We use seven spin-1/2 nuclei in a molecule as quantum bits

The custom-synthesized molecule used as the quantum computer for this experiment contains five 19F and two 13C spin-1/2 nuclei as qubits

Show me quote in which clearly says, that we build 7 qubit NMR quantum computer! —Preceding unsigned comment added by Weekwhom (talk • contribs) 16:51, 29 May 2008 (UTC)

I can bet, that D-wave also can build even 10000 qubits such quantum computer and implement Shor's algorithm with up to about $N=10^{15}$. But somewhy D-wave computer is fake, but IBM - no.

I'm no expert on quantum computing, so please bear with me a bit. I'm not sure I understand the distinction between "X was used as the quantum computer" and "X is a quantum computer." For example, this webpage from an MIT group seems to claim their NMR setup is a quantum computer: "we set out ... to build a modest two-bit quantum-mechanical computer made from a thimbleful of chloroform"; "we demonstrated that our two-qubit quantum computer could ...". As I read things, these groups are clearly claiming to have built and used quantum computers. Do you disagree with my reading of the sources, or do you dispute their claims? Gnixon (talk) 19:19, 29 May 2008 (UTC)

By the way, it would be helpful to me if you could sign your posts by using the four tildes. Thanks, Gnixon (talk) 19:21, 29 May 2008 (UTC)

I have indicated at least one quote which states that it is a quantum computer. I think we can all agree that the original paper at least implies that it is, if not outright states that it is. I have yet to see a citation which says directly that it isn't. I would be surprised that there are no reputable publication which state that it isn't. Weewhom, can you produce such a citation and summarize it's claims? Skippydo (talk) 21:45, 29 May 2008 (UTC)

I was saying many times, that ALL NMR "quantum" computers don't using entanglement! And Give you many citations of this. But for you seems, that need citation exactly' about IBM NMR computer... Isn't it is not a little bit silly? Where in IBM paper claims, that they NMR 7 spin computer using entanglement??? It is very important part, so no any responsible person, wouldn't say about entanglement if there exist many over NMR "quantum" computer without entanglement?

Current supercomputer in few mounts can factorize somthing $N=2^{700}=10^{210}$ (700 bits number or 210 decimal digits number). And real quantum computer should be able to factorize somthing like $N=2^{1000}=10^{301}$. D-wave computer will work like probabilistic computer and thus should be able to factorize somthing like $N=2^{50}=10^{15}$. IBM NMR quantum computer also working like probabilistic computer (and even worse). Diference between D-wave "quantum computer" and IBM NMR "quantum computer" wouldn't be at all! They both don't using entanglement! But you want to give crown to IBM NMR 7bit qauntum computer simulator and want discrown D-wave quantum computer simulator. Isn't it stupid? —Preceding unsigned comment added by Weekwhom (talk • contribs) 06:14, 30 May 2008 (UTC)

There is your quantum computing! In fact, chemists, who have used NMR for decades to study complicated molecules, have been doing quantum computing all along without realizing it. —Preceding unsigned comment added by Weekwhom (talk • contribs) 06:34, 30 May 2008 (UTC)

"we set out ... to build a modest two-bit quantum-mechanical computer made from a thimbleful of chloroform"

'As an example of this savings, we demonstrated that our two-qubit quantum computer could find a marked item hidden in a list of four possibilities in a single step." But this step is slower/longer than on usual or probabilistic computer. Don't learn from stupid articles! Learn from PDF! And this still don't realated with 7 bits IBM NMR quantum computer simulator. —Preceding unsigned comment added by Weekwhom (talk • contribs) 06:46, 30 May 2008 (UTC) And this step have very bad probability to be right... talk

I'm willing to believe that NMR implementations are not real quantum computers due to the lack of entanglement. Do you have a citation? Skippydo (talk) 15:01, 30 May 2008 (UTC)

Are you stupid? I give 3-4 citations about entanglement in NMR, above. —Preceding unsigned comment added by Weekwhom (talk • contribs) 16:47, 30 May 2008 (UTC)

More quotes

Here's a more of the context from the quote given at the top of this section:

In the paper [4] that gave us Theorem 2, Braunstein, Caves, Jozsa, Linden, Popescu and Schack claimed that “current NMR experiments should be considered as simulations of quantum computation rather than true quantum computation, since no entanglement appears in the physical states at any stage of the process”. Much to the contrary, we showed here that pseudo-entanglement is sufficient to beat all possible classical algorithms, which proves our point since pseudo-entangled states are not entangled!

... We provide a case in which there exists a positive advantage of unentangled quantum computation over classical computation.

It seems like there's some debate within the field over whether the NMR experiments should be considered "true" quantum computation, but I don't quite understand it. Weekwhom, do you have a reference that might clear things up? Gnixon (talk) 16:04, 30 May 2008 (UTC)

I can say shortly. This advantage is fake. It something polinomial advantage in theoretical case, but not exponentional like in real quantum computers. Becouse like saying many quotes entanglement is nessary for REAL QUANTUM COMPUTER! Those pseudoentanglement Maybe exist also in D-wave computer...! And this don't doing it faster! But if you want to know my opinion, those entanglement long cirquit perfomation is slower than on direct probabilistic computer, becouse need more gates. There is key point in understanding say 1.0001 speedup over probabilistic computer. Probabilistic computer using much less gates! —Preceding unsigned comment added by Weekwhom (talk • contribs) 16:52, 30 May 2008 (UTC)

Okay, I think I see your point. Anyway, looking more closely at some of your references, the Lu 2007 paper and references therein (e.g., Linden, Popescu 2001) are pretty definitive: NMR experiments like the ones at IBM don't generate entangled states (although better state-prep techniques might solve that), and entangled states are necessary to get the computational efficiency that quantum computers are all about (Linden, Popescu 2001). This is all very current research---the IBM folks were certainly claiming to have a "quantum computer" (not a simulation), which stirred up quite a bit of activity, resulting in the later understanding that their pseudo-pure states weren't good enough. The happy ending seems to be that Lu et al have (first?) published a realization of Shor's algorithm using photonic qubits, emphasizing the presence of entanglement. Maybe this whole sequence would be a nice story to tell in the article if there's room for it. Gnixon (talk) 18:14, 30 May 2008 (UTC)

the IBM folks were certainly claiming to have a "quantum computer" (not a simulation), which stirred up quite a bit of activity, resulting in the later understanding that their pseudo-pure states weren't good enough. Where you read this? Anyway they certainly with 100% or with 99.99999% was sure, that entanglement is nessary. They just want to look very clever, that they have somthing incredible... I think don't need put photonic qubits, becouse actualy speedup wouldn't be bigger than ~1.2 times with 2 qubits instead 2 times (in theory). And this 2 qubit "bad working" quantum computer using more gates than 2 bits probabilistic computer. So I would say, that no exist quantum computer, which proving many-universe interpretation, or that quantumly possible to do somthing faster. For example 7 qubit photonic quantum computer wouldn't be faster than ~1.01 times, becouse of decoherence (and with much more gates). So actauly quantum computer even small, few qubits don't exist and about it quantumnes possible to do discusion... Quantum computer isn't friendly with Current understanding of nature and this explain, why experiments are so unsucessful. —Preceding unsigned comment added by Weekwhom (talk • contribs) 18:31, 30 May 2008 (UTC)

Ahhh! So you doubt that quantum computing is even possible in principle. I think most physicists would disagree. Gnixon (talk) 18:37, 30 May 2008 (UTC)

But they don't have any bigger probability to be right than I... They and my opinion can be equaly right or wrong. They just believing... This is they job... —Preceding unsigned comment added by Weekwhom (talk • contribs) 19:15, 30 May 2008 (UTC)

But they don't have any bigger probability to be right than I.

Actually, in the context of Wikipedia, they do. The threshold for inclusion in Wikipedia is verifiability, not truth [6]. Get your opinions published and they can be included in the article. Skippydo (talk) 19:43, 30 May 2008 (UTC)

Actualy you don't understand what you talking. If quantum computer don't exist then they opinion is 0.

Article changes

For the article, how about this:

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using a quantum computer with 7 qubits. However, some doubts have been raised as to whether their implementation can be considered an actual quantum computer.

We cite the IBM paper for the first sentence and the we cite the Braunstein et al paper for the second (reference #6 in LBYP07). Is someone willing to read the Braunstein et al paper and summarize it for me? Skippydo (talk) 20:54, 30 May 2008 (UTC)

That sounds pretty good. I would just add the three or four references from footnote 6 of the Lu paper, then add a sentence about the Lu paper. Gnixon (talk) 21:13, 30 May 2008 (UTC)

About D-wave also was rised doubt, but nobody puting D-wave into section of Grover's algorithm. —Preceding unsigned comment added by Weekwhom (talk • contribs) 06:11, 31 May 2008 (UTC)

By the way, if you will ask any quantum computer sciencist, he would say, that NMR (and IBM also) quantum computer working without entanglement. Even NMR implementation can't turn from 0, to 1, etc. Believe me, with NMR there is very bad things and actualy, NMR ("quantum computer") isn't better than simple, natural Nuclear magnetic reasonans, which is used any day with no quantum computation purpose. So probably there then need to mention, that it working without entanglement. But I think until you wouldn't find Quote, that NMR implimentation of Shor algorithm with 7 qubits using entanglement, then you shouldn't post this, becouse in quantum computer article, there clearly says, that entanglement is nessary for quantum computer. —Preceding unsigned comment added by Weekwhom (talk • contribs) 06:18, 31 May 2008 (UTC)

Weekwhom, I believe you are suggesting that we make no mention of the NMR implementation of Shor's algorithm. Please clarify.

Anyway, moving along. Let's see if I can put some of the references together.

BBKM04 [7]

This article shows that an advantage can be obtain using a quantum computer without utilizing entanglement. However, the advantage is asymptotically insignificant.

We conclude that: (a) entanglement is not essential for quantum computing

The quantum advantage that we have found is negligible (exponentially small). A much better advantage might be obtained...

Entanglement is more "conventionaly" nessasary:

"Probably the most often heard answer is that the power of quantum computingcomes from the use of entanglement, and indeed there are very strongarg uments in favour of this belief."

Quantum advantages without entanglement is not proved:

"In this model, we analyse two famous problems due to Deutsch–Jozsa [9] and Simon [21]. We show that, when a single oracle query is performed, the probability to obtain the correct answer is better for the quantum algorithm than for the optimal classical algorithm, and that the information gained by that single query is higher. This is true even when no entanglement is ever present throughout the quantum computation and even when the state of the quantum computer is arbitrarily close to beingtotally mixed. The case of more than one query is left for future research, as well as the case of a fixed average number of queries rather than a fixed maximum number. The quantum “advantage” we found exists for any size n of the problem but is exponentially small with n. The question of the existence of a non-negligible advantage of Quantum Computing Without Entanglement is left as our main open question."

Where here says about Shor's algorithm? There is only advantage for Deutsch-Jozsa algorithm and for Simon's algorithm.

Entanglement is nessasary:

"Several papers dealingwith speed-up and its connection to entanglement have been written, such as [1,14,6,22]. Let us mention two of these that appear at first to contradict our results: Jozsa and Linden [14] showed that for a large class of computational problems, entanglement is required in order to achieve an exponential advantage over classical computation when the quantum state is pure throughout the computation. Ambainis, Schulman and Vazirani [1] showed that quantum computation with a certain mixed state, other than the pseudo-pure state used by us, has no advantage over classical computation. But obviously, there is no real contradiction between our paper and these important results. We provide a case in which there exists a positive advantage of unentangled quantum computation over classical computation."

 —Preceding unsigned comment added by Weekwhom (talk • contribs) 08:05, 1 June 2008 (UTC) 

Jones99 [8]

This article supports the claim that NMR QCs are not real QCs. However, scalability is cited, rather than entanglement. This leaves the entanglement question open.

there has been some debate as to whether NMR QCs are in fact real QCs. Initial criticism focussed on the question of scalability

As NMR states appear to be describable without invoking entanglement, they can therefore be described using classical models (although these classical models may be somewhat contrived). However, while such classical models can be used to describe an individual NMR state, it is not clear that such models can be used to describe the evolution of the state during an NMR experiment[31]. The significance of these conclusions remains contentious and unclear.

There is even worse than just don't apearing entanglement, there don't apearing at all coherence between qubits, they can't prepare pure state (|0>) of each qubit: "The great breakthrough in NMR QC was the realisation by Cory et al. [A] that it is not strictly necessary to form a pure state to implement an NMR QC,". NMR using totaly random entangled or not entangled "gogal mogal" state of superposition, entanglement and this incoherent "bullshit" should lead to 'quantum computing': "Instead it suffices to generate a "pseudo pure" state, that is an ensemble comprising a mixture of the desired pure state and the maximally mixed state." But they says, that signal deacrising exponentionaly with number of qubits: "but tomography is not a practical approach for more general problems, as the number of readout experiments required rises exponentially with the number of nuclei in the system. Furthermore, their implementation uses temporal averaging to produce the initial pseudo pure state, which requires that every experiment be repeated

three times. Thus their results represent the combined analysis of 27 separate experiments (although not all these experiments are strictly necessary)."

"From the beginning there has been a strong current of concern regarding the usefulness of NMR QCs; indeed there has been some debate as to whether NMR QCs are in fact real QCs. Initial criticism focussed on the question of scalability, and it is now widely accepted that current NMR implementations are probably not scalable for a variety of reasons, including the exponential inefficiency in the preparation of pseudo pure states, the limited number of operations which can be carried out before decoherence sets in, and the experimental difficulties involved in implementing logic gates in multispin systems."

"As NMR experiments are conducted at temperatures such that kT is large compared with the splitting between the energy levels, the density matrix describing a nuclear spin system is always close to the maximally mixed state, and it can be shown that such high temperature states can always be decomposed as a mixture of product states (that is, states containing no entanglement between different nuclei). As NMR states appear to be describable without invoking entanglement, they can therefore be described using classical models (although these classical models may be somewhat contrived). However, while such classical models can be used to describe an individual NMR state, it is not clear that such models can be used to describe the evolution of the state during an NMR experiment[31]. The signifficance of these conclusions remains contentious and unclear." - I think they there too much speculative thinking - it's all can be described with classical models! —Preceding unsigned comment added by Weekwhom (talk • contribs) 07:04, 1 June 2008 (UTC)

VYC?? [9]

This article characterises the IBM implementation as a quantum computer. But states that NMR doesn't use entanglement.

Most recently, a seven-qubit quantum computer has been used to factor the number 15 using Shor’s algorithm.

it is not possible to produce genuinely entangled states...

LBYP07 [10]

Reports a implementation of Shor's algorithm using photonic qubits, utilizing entanglement. Also mentions NMR may not be quantum at all.

Were report an experimental demonstration of a complied version of Shor’s algorithm... entanglement is observed which well supports its quantum nature

Since the NMR experiments can not prepare pure quantum states and exhibits no entanglement during computation, concerns have been arisen on its quantum nature.

BCJLPS99 [11]

States that NMR does not produce entanglement. They note that this supports, but does not prove, the assertion that NMR are not quantum.

The bounds show that no entanglement appears in the physical states at any stage of present NMR experiments.

We stress, however, that we have not proved this suggestion, since we would need to analyze the power of general unitary operations.

My latest suggestion for the article: In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether their NMR preform true quantum computations, since no entanglement is observed. In 2007, Lu et al implemented Shor's algorithm using a photonic quantum computer, observing entanglement.

Please feel free to edit. Skippydo (talk) 20:26, 31 May 2008 (UTC)

Yes, at least photonic quantum computer (?) is much more real than NMR. D-wave computer is also much more real than NMR. I don't know how they estimate this exponentionaly small advantage of NMR computer over classical, but according to my understanding NMR computer using up to 100 times more gates than classical or probabilistic computer. So they advantages can be analyzed only from "stupidity" perspective. I don't understand they advantages and I don't think that they possible... I think NMR computer at all can't work somthing more than probabilistic computer, becouse it always exist in equal superposition state (and to separate this state to say |0> and |1> or to manipulate this even one qubit, I think, chance is zero, becouse spin is probabilistic and thus spin based real quantum computer can't exist). In D-wave computer at least for few nanoseconds there can be some coherence and superposition and somthing like in real quantum computer with entanglement, but in NMR about this everything you can forget (but both them decoherence fighting, anyway, and even photonic...). But your suggestion may be better than nothing, but entanglement in photonic computer is very weak and it's hard to say, what it demonstrating, quantum computation or entanglement... —Preceding unsigned comment added by Weekwhom (talk • contribs) 06:29, 1 June 2008 (UTC)

Another quote: Indeed NMR quantum computation does start with initially thermally mixed qubits, although the computation efficiency falls off exponentially with the number of qubits.

I think your suggestion is pretty good, Skippy. The second sentence should have references, of course, and it might be possible to tighten up the first one. Gnixon (talk) 18:00, 1 June 2008 (UTC)

Shor NMR round 2

I thought we had a consensis. Let's try again. Here is the quotation from the article.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether their NMR preform true quantum computations, since no entanglement is observed. In 2007, Lu et al implemented Shor's algorithm using a photonic quantum computer, observing entanglement.

Please state your objections. Skippydo (talk) 15:06, 4 June 2008 (UTC)

Not an objection, but I might replace the last clause with "emphasizing that they observed entanglement." Gnixon (talk) 16:46, 4 June 2008 (UTC)

I do object. There isn't any doubt anymore that a real quantum computation has been performed here (Vandersypen has later co-authored papers with Isaac Chuang of the IBM team on this topic, so I don't think anyone has any doubts). The only issues have to do with scalability, i.e. can one build very large quantum computer using this method. So, we shouldn't write that there is doubt about this being a real quantum computer. It is. Count Iblis (talk) 17:06, 4 June 2008 (UTC)

Count, have you looked through some of the above discussion? There seemed to be legitimate debate in the literature over whether it was fair to call the NMR experiment a "quantum computer" because of the entanglement issue. As I (partially) understood the debate, scalability was an important issue, since the benefits of quantum computing come in their large-N scaling properties. Do you have a source that has considered these issues and concluded that the objections are wrong? Gnixon (talk) 17:39, 4 June 2008 (UTC)

I can briefly summarize. According to BCJLPS99 [12] no entanglement appears in... present NMR experiments. According to BBKM04[13], The quantum advantage that we have found is negligible (exponentially small).

As far as I can tell, it is conjectured that entanglement is required to obtain an exponential advantage. It is also conjectured that NMR will never produced entangled states.

Since the version of Shor's algorithm that was implemented by IBM requires entanglement and entanglement was not observed, this casts doubt on the experiment. Enough so that I feel it deserves a sentence. Skippydo (talk) 17:49, 4 June 2008 (UTC)

Of course, it may still be open to debate whether the NMR stuff should be called a "quantum computer" despite those deficiencies. Gnixon (talk) 18:00, 4 June 2008 (UTC)

NMR experiments with shors algorithms don't have advantages over classical algorithm, becouse for NMR experiment need about $2^{n}=N$ time, where n is number of qubits and N is number to be factorized in bits; for classical computer need about $2^{n^{1/3}}=2^{(\log N)^{1/3}}$ time. So who is faster? For probabilistic computer need also about $2^{n}=N$ time like for NMR computer. So NMR computer can't be faster than classical computer. And advantages was goten only after one querie and only in Deutsch-Jozsa algorithm (but I even with this can discus) and maybe in Simons algorithm, but NO in Shor's algorithm! If you have some sentence about advantage in shor algorithm then give me qoute! And those papers which somthing speculating about NMR advantages they are too old and too stupid, becouse in many those papers about NMR there says, that need more precisly $4^{n}=N^{2}$ time like in probabilistic, but in probabilistic (factorization algorithm) even don't need to do many unneeded steps according to long scheme like in NMR. But even if in shor's algorithm there is exponentionaly small advantage it still would take somthing like $2^{n}-1/N$ time or $2^{n}-1/n$ time, while classical computer need only about $2^{n^{1/3}}$. NMR implimitation with Shor's algorithm don't have and can't have advantages over classical algorithm (computer)! —Preceding unsigned comment added by Weekwhom (talk • contribs) 05:06, 5 June 2008 (UTC)

I believe you are correct on all accounts. Indeed, no advantage has been shown for Shor's algorithm without entanglement. If I understand correctly, you don't want to mention the IBM implementation at all. Correct me, if I'm wrong.

For 5 years, it has been quoted in literature as a implementation of Shor's algorithm. So far, there isn't definitive proof that it isn't. This is why I included the sentence and another sentence summarizing the doubt. This also serves to contrast with the 2007 implementation which observes entanglement. Skippydo (talk) 15:36, 5 June 2008 (UTC)

Photonic computer is somewhy very good performed... Too good. I also read in [[14]] about grover algorithm with claster state quantum computer and this results also too good. So This may don't prove fidelity of entanglement or good implimitation, but becouse of "strenge" models there is such good mach with theory. If you could give me implimetation with photonic qubits grover algorithm and not claster state with such good fidelity then I would be very convinced about entanglement. But there says, that with mroe qubits signal decrease exponentionaly. But results mach with theory and it is most important so photonic quantum computer I think need to accept. But NMR can accept only fanatic! But maybe it is your true, that need debunk it in article, becouse so long it almost everythere flashing like quantum computer. —Preceding unsigned comment added by Weekwhom (talk • contribs) 18:16, 5 June 2008 (UTC)

I don't understand what you are saying, due to a combination of poor English and technical details I don't believe I understand.

Please suggest your amendments to the current version of the offending quotation. Skippydo (talk) 21:03, 5 June 2008 (UTC)

This is not an objection but a potential amendment. In this paper by Lanyon et al., a similar-sounding claim to the Lu et al. paper appears to be made, but it's not the same people. Assuming I understand this correctly, maybe you should replace "Lu et al." by "several groups", and cite both papers. Here's the key quote (and sorry if you've already discussed this paper):

"In the only demonstration to date, a compiled set of gate operations were implemented in a liquid NMR architecture [they cite IBM paper]. However, since the qubits are at all times in a highly mixed state [they cite Braunstein et al.], and the dynamics can be fully modeled classically [they cite some other paper], neither the entanglement nor the coherent control at the core of Shor’s algorithm can be implemented or verified. Here, we implement a compiled version of Shor’s algorithm, using photonic quantum-logic gates to realize the necessary processes, and verify the resulting entanglement via quantum state and process tomography...."

Hope that helps. Keep up the good work :-) --Steve (talk) 23:38, 5 June 2008 (UTC)

If there are no objections, I will add the following to the article.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether their NMR preform true quantum computations, since no entanglement is observed. Since Shor's implementation, several other groups have implemented Shor's algorithm, emphasizing that entanglement was observed.

Skippydo (talk) 16:47, 19 June 2008 (UTC)

Suggest "NMR perform" -> "experiment performed"; "implemented Shor's algorithm" -> "implemented Shor's algorithm using photonic qubits". Gnixon (talk) 16:58, 19 June 2008 (UTC)

I would welcome you to make such edits yourself. Of course, I am happy to do so.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether their IBM's experiment was a true demonstration of quantum computation, since no entanglement was observed. Since IBM's implementation, several other groups have implemented Shor's algorithm using photonic qubits, emphasizing that entanglement was observed.

Skippydo (talk) 17:04, 19 June 2008 (UTC)

References

2009 Nature paper (O'Brien et al) implements Schor's on penny-sized chip

Just sharing this url so those of you who follow more closely than I have in recent years can do a better job of deciding how/whether to add and how to phrase, than I might.

http://news.bbc.co.uk/2/hi/science/nature/8236943.stm

Researchers have devised a penny-sized silicon chip that uses photons to run Shor's algorithm - a well-known quantum approach - to solve a maths problem..The work, reported in Science, is rudimentary but could easily be scaled up to handle more complex computing. ..

.."The way people used to make this kind of circuit consumed square metres of laboratory space and took graduate students many months to align," said Jeremy O'Brien, the University of Bristol researcher who led the work.

"Doubling the complexity of the circuit often times turns it from being a difficult task to a practically impossible one, whereas for us to double the complexity it's really straightforward," he told BBC News.

The Bristol team's approach makes use of waveguides...

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 :-) --Harel (talk) 02:55, 6 September 2009 (UTC)

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

What is the size? Like how many bits it takes to represent the value? Or the value itself? Does "size" have a formal meaning that can be linked to? --184.20.10.253 (talk) 07:07, 22 September 2020 (UTC)

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

Isn't there a missing normalization?

Right after "We define the following eigenvector of U", |psi_j> is defined as a vector of r summands of which all have norm 1. I believe it should be normalized, i.e. multiplied by 1/sqrt(r). It is not just a vector, it is a quantum state.

BTW this is corrected immediately afterwards, in the superposition of all r psi_j's, where the normalization is 1/r, i.e 1/sqrt(r)*1/sqrt(r), where the second multiplicand is the "missing" one from above. Doobiefletzet (talk) 14:10, 22 May 2023 (UTC)

Damn right, all quantum state vectors must have length 1. Jehochman ^Talk 16:07, 22 May 2023 (UTC)