Talk:Shor's algorithm

From Wikipedia, the free encyclopedia

	Portal This article is within the scope of WikiProject Physics, which collaborates on articles related to physics.
???	This article has not yet received a rating on the assessment scale. [FAQ]
???	This article has not yet received an importance rating within physics.
Help with this template Please rate this article, and then leave comments to explain the ratings and/or to identify its strengths and weaknesses.

[edit] 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.

[edit] 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)

[edit] 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)

[edit] 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

264

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

== Definition of f() in the 'classical part' Shouldn't it be: : $f(r) = a^r\ \mbox{mod}\ N$ ? Evan Ettinger.

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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 [2] 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 [3] it explains that a clever choice of

a

in the modular exponentiation

f (x) = a x M o d (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)

[edit] 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. [4].

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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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.

[edit] 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)

[edit] 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 $| ψ 1 >$ |0000001> (Fig. 1). However, experimentally we start from thermal equilibrium. The density matrix is then given by $\rho_{th}=e^{H_0/k_BT}/2^7,$ with $k_BT >>\hbar\omega_i$ at room temperature so each spin is in a statistical mixture of |0> and |1> (Fig. 3a). We converted $ρ t h$ into a 7-spin effective pure state $ρ 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)

[edit] 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. ^[1] However, some doubts have been raised as to whether their NMR preform true quantum computations, since no entanglement is observed. ^[2] In 2007, Lu et al implemented Shor's algorithm using a photonic quantum computer, observing entanglement. ^[3]

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)