Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Solid State Quantum Computer Finds 15=3x5 — 48% of the Time

timothy posted about 2 years ago | from the please-show-your-work dept.

Math 262

mikejuk writes "The Shor quantum factoring algorithm has been run for the first time on a solid state device and it successfully factored a composite number. A team from UCSB has managed to build and operate a quantum circuit composed of four superconducting phase qubits. The design creates entangled bits faster than before and the team verified that entanglement was happening using quantum tomography. The final part of the experiment implemented the Shor factoring algorithm using 15 as the value to be factored. In 150,000 runs of the calculation, the chip gave the correct result 48% of the time. As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result but not of practical use."

cancel ×

262 comments

Sorry! There are no comments related to the filter you selected.

That's no moon... (0, Funny)

Anonymous Coward | about 2 years ago | (#41129503)

...It's a space station!

Re:That's no moon... (5, Funny)

Anonymous Coward | about 2 years ago | (#41129533)

To be fair, it could have been either until we looked.

(And you could have posted either here or at the correct story.)

Re:That's no moon... (1, Insightful)

shentino (1139071) | about 2 years ago | (#41129713)

It was both a moon and a space station at the same time.

To the jerk who modded the parent down:

Read up on schroedinger's cat you doofus.

Then you can have your geek card back.

Re:That's no moon... (-1)

Anonymous Coward | about 2 years ago | (#41129807)

It was both a moon and a space station at the same time.

Depends on which interpretation you prefer.

PS: Don't be too harsh on the poor mods. I did use a bit of a cliche.

Maths (3, Funny)

Anonymous Coward | about 2 years ago | (#41129509)

Sometimes 2+2=5, give the thing a break!

Re:Maths (4, Funny)

Anonymous Coward | about 2 years ago | (#41129551)

Of course 2 + 2 = 5. Take two strings. Tie 2 knots in each. Then tie them together and count the knots.

Re:Maths (-1)

Anonymous Coward | about 2 years ago | (#41129945)

Of course 2 + 2 = 5. Take two strings. Tie 2 knots in each. Then tie them together and count the knots.

2+2=5 is somehow equivalent to 2+2+1=5 now?

Re:Maths (0)

Anonymous Coward | about 2 years ago | (#41130089)

If you define the operator + as +: x +_ y +_ 1 for all x,y in some magma, where +_ denotes the common addition +, then yes.

Re:Maths (2, Funny)

Anonymous Coward | about 2 years ago | (#41129777)

For very large values of 2

First post - from a quantum computer (1)

Anonymous Coward | about 2 years ago | (#41129515)

50% of the time.

Can someone explain... (4, Insightful)

Crudely_Indecent (739699) | about 2 years ago | (#41129585)

From TFA:

As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result.

How is it useful to have the correct answer 50% of the time? When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?

Re:Can someone explain... (5, Informative)

Anonymous Coward | about 2 years ago | (#41129615)

Consider problems which take a lot longer to compute than to verify. It may be much faster to compute the answer with a quantum computer, then check it with a regular computer, than to simply compute it with a regular computer.

Re:Can someone explain... (2)

cowboy76Spain (815442) | about 2 years ago | (#41129871)

The main problem is the "there is no solution" answer. What if we use the algorithm for a number N for several iterations and found that there are no valid decompositions. Can we ensure that the number is prime?

Re:Can someone explain... (4, Informative)

cryptizard (2629853) | about 2 years ago | (#41129949)

Thats how we find primes right now. All the practical algorithms are probabilistic. If a number is prime, running the algorithm always returns "prime". If it is composite, running the algorithm will result in "prime" about half the time and "composite" about half the time. This is fine, however, because we can run the algorithm n times and our confidence is .5^n, which grows very small very fast.

Re:Can someone explain... (0)

Anonymous Coward | about 2 years ago | (#41130165)

Thats how we find primes right now. All the practical algorithms are probabilistic. If a number is prime, running the algorithm always returns "prime". If it is composite, running the algorithm will result in "prime" about half the time and "composite" about half the time. This is fine, however, because we can run the algorithm n times and our confidence is .5^n, which grows very small very fast.

Actually it's 1-.5^n

If you did .5^n you would get: 0.5, 0.25, 0.125 (decreasing)

Re:Can someone explain... (0)

Anonymous Coward | about 2 years ago | (#41130277)

One of the step's in Shor's algorithm, before you get to the quantum computation, is to use a classical computer to run a primality test on the number. This will tell you if it is prime or not (but not give the factors), and can be done in polynomial time. You would only proceed with the quantum part when you know it is a composite number.

Re:Can someone explain... (5, Interesting)

Shavano (2541114) | about 2 years ago | (#41129905)

That may be so, but computing the prime factorization of 15 is not in that class.

I don't think you should even get to call something a middle-school dropout can figure in his head faster than he can say "Fries with that?" computation. So-called quantum computers still barely qualify as expensive but useless toys.

Post again when a quantum computer can solve a real mathematical puzzle at a speed comparable to what a traditional computer can do. That would be news.

Scientists have been touting the supposedly vast potential of quantum computing for decades now. D-E-C-A-D-E-S. But thanks to fundamental limitations of the nature of what they are, it's really hard to get them to barely work at all. It appears we could forever be stuck at the point where the qubits can be minimally processed but quantum decoherence can't be held off long enough to get a useful result. Meanwhile traditional methods of computing continue to forge ahead, although the rate of increase is slowing. Just keep in mind: quantum computing is 2500 years behind traditional computing methods in general, 175 years behind automated mechanical methods and more than 70 years behind electronic computers.

Electronic computing methods overtook all other methods extremely quickly, but they faced only technical challenges not challenges posed by the fundamental nature of what they were trying to do. You can regard them in some ways as fancy abacuses: they literally count chunks of charge the way an abacus uses the position of beads to represent numbers (or in principle anything else). With qubits, you are attempting to get definite results by exploiting the indefinite character of things like the spin states of electrons. That's not just hard. It may be intractably hard. But if somebody can get it to work it might be very valuable to the NSA and anybody else interested in cracking the security of computing systems.

Re:Can someone explain... (4, Insightful)

neokushan (932374) | about 2 years ago | (#41129977)

Yeah, scientists were theorising about the Higgs-boson for deacdes as well. Sometimes it takes that long to get somewhere.

It's very early days for quantum computing. The fact that they've taken something from pure theory and made it actually do something is a fantastic indicator that they're onto something. So what if it takes another 5 decades to get there, the implications would still be incredible by that point.

Re:Can someone explain... (1)

crabel (1862874) | about 2 years ago | (#41129997)

That may be so, but computing the prime factorization of 15 is not in that class.

Well, it's O(n^2 log n), which is pretty high. http://numbers.computation.free.fr/Constants/Algorithms/splitting.html [computation.free.fr] If you have a machine, that can do it with large numbers in an instant, but only with 50%, it would be awesome. But I agree on the rest of the argument, still way to go...

Re:Can someone explain... (1)

sjames (1099) | about 2 years ago | (#41130141)

And there were people who could outrun the first adding machines by doing it in their head. Nobody said that the this was in itself useful. It IS one more step along the way. It may be that at some point the next step will prove impossible or it may be that step by step we'll get there, but either way, we'll likely learn a few things that do prove useful.

All the same, I'm not going to hold my breath.

Re:Can someone explain... (1)

kaws (2589929) | about 2 years ago | (#41130199)

The reason behind the interest behind quantum computers is they have the potential to be exponentially faster. Here's an example that I've read. You have to find a name in a phone book. A regular computer has to search through in a more linear maner. Like you are going from the first page and so on. A quantum computer's manner of getting the answer is based upon probability, what's the likelihood that you'll open the phone book to the right page. In other words, you skip the intermediate steps of searching.

Re:Can someone explain... (2, Insightful)

circletimessquare (444983) | about 2 years ago | (#41130223)

yeah. the wright brothers built some stupid linen and balsa wood thing that fluttered above the ground for a few seconds. useless. they've been talking about flight for centuries

morse can send little tappity taps on a wire? big deal. i can't figure out what it means, and does anyone actually believe we're going to string wires all over the country? impossible!

and i heard of this television device. what a crazy unweildy delicate gizmo. shows a fluttering image you have to squint to maybe make out what they are trying to show. ma and pa middle america is going to set up this gizmo in their living rooms instead of a trusty radio? you're out of your minds. they have radio shows and the picture show at the local theatre, this television thing is going nowhere

in other words: thank god we have people with actual imagination in this world. what do dull minds like yours contribute exactly?

Re:Can someone explain... (5, Insightful)

Wraithlyn (133796) | about 2 years ago | (#41130299)

There should be a "-1 Bitching That This Doesn't Meet My Personal Criteria For News" mod. Every. Damn. Article. Somebody has to come write an essay on how completely not interesting or impressive this is to them.

Yes, factoring 15 isn't particularly impressive. Thank you, Captain Fucking Obvious.

Now if you'd bothered to RTFA, you'd have noted it already directly discusses this:

Of course, factoring 15 isn't something that is going to threaten the PKI and cryptography in general, but factoring larger numbers is just a matter of increasing the number of qubits and this approach does seem to be a scalable solid state approach.

So they can instantly factor numbers (well, with ~50% success), with an approach that *seems scalable*. That's news to me.

Maybe in a few months, there will be another story about how they failed to scale this approach up. That will be an additional piece of news. Failure can be news.

Some of us are interested in the journey, not just the destination.

Re:Can someone explain... (1)

Anonymous Coward | about 2 years ago | (#41129621)

I don't think so. It's hard to factor numbers, but once you have a potential factorization then it is easy to multiply them together and see if you get the correct result. The tricky bit is coming up with possible factorizations that might be correct (with reasonable probability).

Re:Can someone explain... (4, Informative)

gmueckl (950314) | about 2 years ago | (#41129623)

That depends. Sometimes you have a hard time finding a possible result, but verifying it is simple. Factorization is just such a problem. So you repeat the algorithm and test the result until the test succeeds. If this is on average faster than a completely deterministic approach, you have won.

Re:Can someone explain... (4, Insightful)

thue (121682) | about 2 years ago | (#41129733)

For a concrete example, the RSA public key includes a number n, which is the sum of two secret primes p and q. The encryption is broken if an attacker can derive p and q from n by factorization. ( http://en.wikipedia.org/wiki/RSA_(algorithm)#Operation [wikipedia.org] )

if you could factorize an RSA public key 48% of the time then it would be a pretty big deal, since it would render RSA completely obsolete.

Re:Can someone explain... (4, Informative)

Sancho (17056) | about 2 years ago | (#41129761)

RSA public key includes a number n, which is the sum of two secret primes p and q

Just FYI, it's the product of two secret primes. Product is for multiplication, while sum is for addition.

Re:Can someone explain... (1)

Forty Two Tenfold (1134125) | about 2 years ago | (#41129795)

number n, which is the product of two secret primes p and q

Re:Can someone explain... (0)

Anonymous Coward | about 2 years ago | (#41130275)

They aren't primes... they are relatively prime... big big difference :)

Re:Can someone explain... (1, Insightful)

Shavano (2541114) | about 2 years ago | (#41130243)

But we are a very long way from that. Right now it takes enormously more effort to do the job with a quantum computer and it can only be done at all with very small numbers like 15. And the results show that hardware is not scalable. It's supposed to get the answer right 50% of the time and it only gets 48% in 150,000 runs. The 2% difference is significant and whatever the cause of that is, it's almost certain to not scale well:

If a 4 bit number gives you a 48% correct rate, that means that it gets the wrong answer 2% more often than it theoretically should. So the hardware is failing to work correctly conservatively 4% of the time. (Since only half the time can you tell that the hardware didn't perform as expected.). The machine has to be massively scaled up to get into the class that might be able to solve lengthy computing problems, and the hardware-dependent error rate is going to scale up at least exponentially with the number of bits. (Looks like it might be 99%^N.) If it's only that bad, the hardware CAN be scaled up to useful problems, like breaking 128-bit encryption with fewer trials than traditional methods.

Re:Can someone explain... (0)

Anonymous Coward | about 2 years ago | (#41129635)

Yes, ideally, but since it's easy to check the answer, keep running it until you get the right answer. If it's faster than conventional methods, then it's useful.
If you can factor really large prime numbers, you are a long way to breaking private/public-key encryption.

Re:Can someone explain... (5, Funny)

Anonymous Coward | about 2 years ago | (#41129729)

If you can factor really large prime numbers,

I can factor really large prime numbers in my head.

Re:Can someone explain... (-1)

Anonymous Coward | about 2 years ago | (#41130063)

I can factor really large prime numbers in my head.

I guess this was modded down to -1 by the mod brigade who never took gradeschool mathematics?
 

Re:Can someone explain... (1)

Anonymous Coward | about 2 years ago | (#41129739)

Yes, ideally, but since it's easy to check the answer, keep running it until you get the right answer. If it's faster than conventional methods, then it's useful.
If you can factor really large prime numbers, you are a long way to breaking private/public-key encryption.

If you can factor really large prime numbers, you'll hopefully get a Nobel prize in math.

Re:Can someone explain... (1)

Sancho (17056) | about 2 years ago | (#41129771)

Actually, grade-school children can factor really large prime numbers in their heads. The trick is factoring the product of two really large prime numbers in your head without knowing either of the primes. You can get two of the factors (one and the product) but neither of those is particularly useful to the problem at hand.

Re:Can someone explain... (0)

Opyros (1153335) | about 2 years ago | (#41129991)

What's more, there is no Nobel prize in math.

Re:Can someone explain... (1)

Russ1642 (1087959) | about 2 years ago | (#41129943)

There is no Nobel prize in math.

One word: (4, Funny)

drainbramage (588291) | about 2 years ago | (#41129657)

Close enough for government work.

Re:One word: (1)

Crudely_Indecent (739699) | about 2 years ago | (#41129683)

I'm satisfied with that answer.

Not really, but I did get a good chuckle...

Re:One word: (3, Insightful)

fuzzyfuzzyfungus (1223518) | about 2 years ago | (#41129789)

In this case, I suspect that the NSA would readily agree... This quantum computer is far too small for any practical purposes that couldn't be brute-forced with a TI-83 much more easily; but tepid accuracy isn't a big deal if checking your work is computationally inexpensive...

Re:One word: (0)

Anonymous Coward | about 2 years ago | (#41129901)

I havent thought of my old ti calc in a long time. Those were good times.

Re:One word: (1)

fustakrakich (1673220) | about 2 years ago | (#41129883)

One word
Close enough for government work.

That's not even half right... 20% at best

Re:One word: (4, Funny)

Shavano (2541114) | about 2 years ago | (#41130297)

Close enough for government work.

Did you count that with a quantum computer, because by traditional methods I get 5 words 100% of the time.

Re:Can someone explain... (5, Funny)

Anonymous Coward | about 2 years ago | (#41129661)

How is it useful to have the correct answer 50% of the time?

Cat life-support devices.

Re:Can someone explain... (1)

Grumbleduke (789126) | about 2 years ago | (#41129671)

I assume that you are supposed to run the algorithm a few times and see which answer comes up most often (about 50% of the time) and assume it is true. The point being that running this algorithm a few times is significantly faster than running the equivalent algorithm on a non-quantum(?) computer (particularly when dealing with huge near-prime numbers), so what you lose in accuracy you make up for in time.

This is the basis for most "quantum" things (such as qubits); you can theoretically encode an infinite amount of stuff in them, but because they work probabilistically rather than Newtonianly (i.e. pre-determined), you have to take an infinite number of measurements to get all the information out. So you're not getting something for nothing, but if you can live with a small level of uncertainty or inaccuracy, then you might be better off taking the "quantum" route.

But I'm not a CS person (although I did do some quantum mechanics stuff a while back, which included looking into the maths behind some quantum computing things).

Re:Can someone explain... (2)

Sancho (17056) | about 2 years ago | (#41129813)

Nah, as others have pointed out, what you do is run the Shor's algorithm, then verify it. If it's wrong, run Shor's again. If it's right, you know you have the factorization. In this way, you can be 100% sure that you've correctly solved the problem, even if Shor's only provides the correct answer some percentage of the time.

What I don't fully understand is why 48% makes this impractical. Having not read TFA, the only way I can imagine that would be the case is if somehow not having exactly a 50% chance of getting the correct answer means that the algorithm doesn't scale correctly. Even only being correct 10% of the time would mean that you could break RSA much faster than you can without quantum computers. I suspect that was some bad editorializing.

What wouldn't be practical under these conditions is factoring larger numbers. You need more qubits for that. Nevertheless, this is a nice stepping stone towards high-qubit computing.

Re:Can someone explain... (3, Informative)

sjames (1099) | about 2 years ago | (#41130245)

I believe it's just confusing wording. They're saying 48% is good because at best it could only have been 50%. It's impractical because it is only 4 qbits and so conventional computing can easily do the job faster and cheaper for numbers that small (for that matter, it' small enough that a lookup table is an attractive solution).

Re:Can someone explain... (3, Insightful)

ld a,b (1207022) | about 2 years ago | (#41130273)

Let me remind you of the zeroth law of thermodynamics - You can't have nice things.
By that law I predict Shor's algorithm works in practice as follows:
6=2x3 96%
15=3x5 48%
35=5x7 24%
77=7x11 12%
143=11x13 6%
Good luck breaking RSA.

Re:Can someone explain... (2, Insightful)

Anonymous Coward | about 2 years ago | (#41129675)

It's useful because checking that the answer is correct or not is trivial, and having to run the algorithm twice (long term average) is still exponentially faster than relying on classical methods.

Raw speed (0)

Anonymous Coward | about 2 years ago | (#41129691)

Getting the correct answer with 100% propability might be very slow and with a fast way to confirm the result the 50% algorithm can be used to avoid the slow algorithm half the time.

even 1% of the time is great (1)

Anonymous Coward | about 2 years ago | (#41129765)

Because once you get the (maybe wrong) answer, you can easily check whether it's right, and try again if it's wrong.

Try to factor 15, and machine tells you something like 15=8*4. Multiply 8 times 4 and see whether you get 15. Yes => done. No => run 15 through machine again. 50% accurate means you only have to try twice on the average. 1% right means you have to try 100 times. Each try might take a few seconds, or a few minutes, or a few hours, say, for a 500 digit number. Even if you have to try 1000 times (on multiple machines in parallel, perhaps), that's nothing compared to the millions of years it would take to factor a 500 digit number conventionally.

Re:Can someone explain... (4, Informative)

ShanghaiBill (739463) | about 2 years ago | (#41129779)

How is it useful to have the correct answer 50% of the time?

In many cases, it is very useful. If you need to crack a code by factoring a 200 digit number, getting the right answer 50% of the time would be fantastic. You just try repeatedly until you get the right answer.

When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?

Of course. That is why the "quantum" computer would be just part of the solution. Overall, your algorithm would look like this:

correct_answer() {
    for (;;)
        answer = quantum_result();
        if (verify_answer(answer)) {
              return answer;
        }
    }
}

 

This solution would be good enough for any problem where verifying an answer is much faster than finding an answer. Most NPC problems [wikipedia.org] fall into this category.

Re:Can someone explain... (1)

JustOK (667959) | about 2 years ago | (#41129903)

Sometimes it's good enough, sometimes it's not.

Re:Can someone explain... (0)

Anonymous Coward | about 2 years ago | (#41129963)

It depends on the distribution that the answers form. Most science is based on statistics and that works out all right. Our brains operate on fuzzy logic, but it is still valuable.

Re:Can someone explain... (4, Insightful)

goffster (1104287) | about 2 years ago | (#41130007)

An algorithm that could factor a 4096 bit number even 10%
of the time would be enough to consider 4096 key as completely unsafe
for cryptography.

It is easy enough to verify the result.

Re:Can someone explain... (1)

V!NCENT (1105021) | about 2 years ago | (#41130019)

Well, since time isn't linear in this case, and so each step/change (time is advancement through possibilities) is not fixed, you can bump into 48%, when measured in linear time.

Re:Can someone explain... (1)

V!NCENT (1105021) | about 2 years ago | (#41130073)

Just like converting between units:
(1/3)+(2/3)=1;
0,333333333~+0,666666666~=0,99999999~;
1=0,99999999~.

So in this case, the conversion hit 48% linear time here (and 52% elsewhere, hehe), so (48+52)/2=0.

But math isn't pure logic, and so there can never be proof/disprove of what I have typed in this post...

Re:Can someone explain... (0)

Anonymous Coward | about 2 years ago | (#41130031)

Not really. Yourun the algorithm 3 times, try all 3 passwords, and one of them is almost garanteed to be the right one... so you can crack the encryption. And since this is quantum computer, these 3 results will be returned very quickly... so, it is very useful.

Re:Can someone explain... (1)

jjh37997 (456473) | about 2 years ago | (#41130251)

Just run the program multiple times and take the mode.

If I calculate 135257x15643 in my head (1)

G3ckoG33k (647276) | about 2 years ago | (#41129599)

If I calculate 135257x15643 in my head, the correct answer is found pretty close to zero in five attempts. Is that good?

Re:If I calculate 135257x15643 in my head (-1)

Anonymous Coward | about 2 years ago | (#41129641)

LOL!

Go Samsung, go jugular!

Size, not reliability (4, Interesting)

TheRaven64 (641858) | about 2 years ago | (#41129601)

Validating the result is cheap on a classical computer. Even for very large values, multiplying two 4096-bit values together and checking the result is incredibly cheap. A quantum computer that could give the right set of divisors for a 4096-bit prime 1% of the time would still let you very quickly find which of the answers that it gave was correct. The limitation is the size, not the reliability.

Re:Size, not reliability (1)

taktoa (1995544) | about 2 years ago | (#41129627)

Beat me to it.

Re:Size, not reliability (1)

Yarhj (1305397) | about 2 years ago | (#41129697)

And even if classical verification was hard, depending on how quickly the quantum algorithm runs and how random the other 50% of solutions are, you should have a pretty good idea which answer is correct before checking classically. E.g. we want to calculate 2x2, and get the following results: 4, 4, -123, 2, 90, 12, 4, 70. Gee, let's check 4 first.

Re:Size, not reliability (0)

Anonymous Coward | about 2 years ago | (#41130023)

A quantum computer that could give the right set of divisors for a 4096-bit prime 1% of the time would still let you very quickly find which of the answers that it gave was correct.

Yes, you have a 50% chance of getting the right number on your first try, but you also have a 50% chance of not getting the answer on your first try. You have a 25% chance of not getting the right number on your first two tries. There is a small but possible chance that you won't get the answer after a million tries. The average time for this is great and would still be good at 1% correctness. The worst case time is horrible for either.

How is this not practical? (0)

taktoa (1995544) | about 2 years ago | (#41129605)

Couldn't you just multiply out the factorization to see if it's correct? IIRC that's way faster than normal factorization, and since you're starting from a pool of possible factors that is smaller than the space of all prime integers, you're getting a faster result than pure brute force.

Not of practical use? (0)

Anonymous Coward | about 2 years ago | (#41129631)

I don't understand how this isn't of practical use. Any acceptable compiler by todays standards must be capable of optimization, and part of optimization is refactoring math equations in the code for shortest execution period. Prime factorization is particularly useful to that end. That's just one example where factorization is important, there are many others, a few of which you rely upon without even noticing it during your everyday computer activities.

Re:Not of practical use? (2)

fuzzyfuzzyfungus (1223518) | about 2 years ago | (#41129873)

I don't understand how this isn't of practical use.

Size. In order to attack larger problems, you need more entangled qubits. For some mixture of engineering and physics reasons that I am deeply unqualified to discuss, building systems capable of keeping qubits in their proper state seems to get increasingly hairy as the number of qubits you need grows.

That's why '15' is a popular number to factorize in quantum computing experiments. It's really small. Since classical computers are far more mature, and a great deal cheaper, the problems that very small quantum computers are capable of attacking are also solvable in minimal time by ordinary means. Only if you can build a fairly large quantum computer do you get to the point where the extreme efficiency(for certain purposes) of the quantum computations can be applied to problems sufficiently large that you can't just steamroller them with cheap silicon.

Re:Not of practical use? (0)

Anonymous Coward | about 2 years ago | (#41129895)

The main use surely is breaking today's assymetric cryptosystems.

Re:Not of practical use? (1)

smellotron (1039250) | about 2 years ago | (#41129909)

Any acceptable compiler by todays standards must be capable of optimization, and part of optimization is refactoring math equations in the code for shortest execution period.

No acceptable compiler refactors math equations in a way that breaks numerical accuracy, unless the user explicitly requests it (gcc's -funsafe-math-optimizations comes to mind). Optimizing compilers are useless if they give the wrong answers for the most compute-intensive problems.

Re:Not of practical use? (1)

CastrTroy (595695) | about 2 years ago | (#41130301)

We make compromises for accuracy all the time in computation. The use of floating point numbers is one such case. Simple numbers such as 0.1 can't even be accurately represented in binary floating point but we use binary floating point over decimal floating point for many tasks simply because it runs faster, and the answers it gives us is "close enough"

Not of practical use? (0)

roboticon (2715841) | about 2 years ago | (#41129633)

Of course this is practically useful. Even if you have to run it multiple times before arriving at the right answer, you're virtually guaranteed to get there in orders of magnitude less time. Just verify the result (multiply the factors, try to decrypt whatever you're guessing the key for, etc.) until it's correct.

Re:Not of practical use? (1)

TheRaven64 (641858) | about 2 years ago | (#41129841)

As I said two posts above yours, it's not practically useful because factorising 4-bit numbers on a classical computer is already easy. Factoring larger numbers is hard, but requires more entangled qubits.

Re:Not of practical use? (1)

petermgreen (876956) | about 2 years ago | (#41129865)

As others have said the real issue isn't the success rate they have. The real question is can they make it scale to bit counts where it is actually useful while maintaining a tolerable success rate? That means increasing the number of bits dramatically.

Why isn't 48% good enough? (1)

wonkey_monkey (2592601) | about 2 years ago | (#41129659)

Why isn't getting the correct answer 48% of the time impractical?

Re:Why isn't 48% good enough? (2)

LateArthurDent (1403947) | about 2 years ago | (#41129709)

Why isn't getting the correct answer 48% of the time impractical?

It's not the 48% that is not good enough, it's factoring a number such as 15, which is easy enough to do already without going through all the trouble of using a quantum computer. Basically, this is a very significant stepping stone, but we're not living in a world of quantum computing yet.

Re:Why isn't 48% good enough? (2)

Sancho (17056) | about 2 years ago | (#41129825)

Then the summary was worded terribly.

Re:Why isn't 48% good enough? (2)

paleo2002 (1079697) | about 2 years ago | (#41130003)

Don't know much about higher mathematics, but based on the post and the explanation of Shor's Algorithm from wikipedia, its not an issue of how easy it is to factor a small number or how practical. Its more of a benchmark for quantum computing. If the ideal success rate is 50%, then 48% is an indicator of how well the system is operating.

And besides, the quantum computer got a higher score on that math problem than the average American student. That's got to count for something.

Re:Why isn't 48% good enough? (1)

LateArthurDent (1403947) | about 2 years ago | (#41130081)

Don't know much about higher mathematics, but based on the post and the explanation of Shor's Algorithm from wikipedia, its not an issue of how easy it is to factor a small number or how practical. Its more of a benchmark for quantum computing. If the ideal success rate is 50%, then 48% is an indicator of how well the system is operating.

And besides, the quantum computer got a higher score on that math problem than the average American student. That's got to count for something.

Not really. 48% is plenty good enough, if you have a solid state quantum computing device that can use Shor's algorithm on larger numbers.

As mentioned above by other people, the way you'd use Shor's algorithm is use it to get the factors, then multiply them together using a conventional computer and see if you get the original number back. Multiplication is a pretty fast operation, compared to factorization, so the verification isn't really very costly. With a 50% success rate for Shor's algorithm, on average you'd expect to have to run it twice for every number you want to factor. With 48%, that average doesn't change much.

Re:Why isn't 48% good enough? (1)

CastrTroy (595695) | about 2 years ago | (#41130267)

Also, it's 48% for all the trials they did. The probability of getting heads when flipping a coin is 50% as well, but if you flip it 100 times, that doesn't mean that you'll end up with exactly 50 heads and 50 tails. All it means is that as you approach infinite trials the probabilty of getting heads tends towards 50%. So, depending on the number of trials they did, 48% is actually close enough to 50 that you can be assured that the algorithm is working just fine.

Re:Why isn't 48% good enough? (0)

Anonymous Coward | about 2 years ago | (#41130113)

Compare this achievement to the first transistor, the Wright Flyer or a pre 1900 automobile. Look at what a century of development has done with solid state electronics, airplanes and automobiles. It's an interesting proof of concept but it remains to be seen if it can be scaled.

Well heck, Intel might buy it. (5, Funny)

Anonymous Coward | about 2 years ago | (#41129677)

Historically, they're a bit more tolerant about that math thing.

Better results than our political class (0)

dietdew7 (1171613) | about 2 years ago | (#41129703)

I would welcome a quantum computer overlord that was guaranteed to make the correct decision close to 50% of the time.

Re:Better results than our political class (0)

Anonymous Coward | about 2 years ago | (#41129913)

Better results than our political class (Score:0)

Seems that someone modded you up using a quantum computer...

NSA likely already built one (5, Interesting)

IamTheRealMike (537420) | about 2 years ago | (#41129719)

It seems that quantum computing has consistently been viewed as harder than it really is, judging by the ever-decreasing timescales between breakthroughs. Judging from the history of cryptography, and the military value of being able to break RSA, it's not unreasonable to expect that the NSA may have been trying to build such a chip for some time and could potentially have succeeded.

Some months ago James Bamford, who is the premier chronicler of the NSA and has a history of being given accurate leaks, claimed the NSA had made a "huge breakthrough" in its ability to break codes [wired.com] - and that the datacenter they're currently building is a part of the solution. The NSA denied everything of course. But if academics are now able to build a working implementation of Shors algorithm for small numbers, that strongly implies that a focussed team with practically infinite budgets could have already succeeded in building one that can handle crypto-sized numbers.

Re:NSA likely already built one (4, Insightful)

Sancho (17056) | about 2 years ago | (#41129849)

And before anyone freaks out and thinks that the NSA is reading their e-mail, keep in mind that they have to be very selective about how and when they use results from their quantum computer. This is similar to breaking ENIGMA--you want the enemy to think that their codes are secure, so you don't suddenly counter all of their plans perfectly. You certainly don't turn this on e.g. classical organized crime, as that could give away your capabilities on a considerably less valuable target.

Re:NSA likely already built one (1)

fustakrakich (1673220) | about 2 years ago | (#41129867)

Absolutely. It is naive and foolish to believe that there is any publicly available encryption that actually works. Some things are born secret and will stay that way until it's no longer useful

Re:NSA likely already built one (1)

Kynde (324134) | about 2 years ago | (#41130169)

Absolutely. It is naive and foolish to believe that there is any publicly available encryption that actually works. Some things are born secret and will stay that way until it's no longer useful

Don't be silly. There are symmetric ciphers that have been proven to be "unbreakable" in a sense that to open them would take time comparable to brute forcing.

Factoring large prime composites and RSA is another matter, but to entangle 4000 qubits right now? I seriously doubt it.

And I think you're also wrong on the availability aspect. It's naive to think that anything but public encryption methods actually work.

Re:NSA likely already built one (1)

fustakrakich (1673220) | about 2 years ago | (#41130235)

No, not public encryption (as in escrow). I'm talking about the tools available to the general public. Actually "unbreakable" encryption is not available to you and me. There is very strong interest to have you believe otherwise. Especially under all this post 9/11 hysteria. We, the public, simply don't have the resources to "prove" something unbreakable.. The government, on the other hand... And don't expect them to reveal what they know.

Re:NSA likely already built one (1)

sco08y (615665) | about 2 years ago | (#41129987)

It seems that quantum computing has consistently been viewed as harder than it really is, judging by the ever-decreasing timescales between breakthroughs. Judging from the history of cryptography, and the military value of being able to break RSA, it's not unreasonable to expect that the NSA may have been trying to build such a chip for some time and could potentially have succeeded.

Well, of course, they got it from the aliens at area 51 decades ago. They've just been spoonfeeding us the tech, bit by bit.

Re:NSA likely already built one (1)

gl4ss (559668) | about 2 years ago | (#41130067)

or perhaps someone managed to sell them the idea that by using billion bucks they would then have that?

50% of the truth (1, Interesting)

OzPeter (195038) | about 2 years ago | (#41129797)

Could it be that the reason the algorithm is only supposed to get the rich answer 50% of the time is that there is a parallel universe out there where 5 x 3 is not 15???!?!?

Re:50% of the truth (1)

Anonymous Coward | about 2 years ago | (#41130189)

No.

Re:50% of the truth (0)

Anonymous Coward | about 2 years ago | (#41130249)

Could it be that the reason the algorithm is only supposed to get the rich answer 50% of the time is that there is a parallel universe out there where 5 x 3 is not 15???!?!?

Yes there is. It's called creationism.

Huh? (1)

StripedCow (776465) | about 2 years ago | (#41129835)

I get the correct answer 99% of the time. Too bad I hit that remaining 1% during my entire period of elementary school :/

Re:Huh? (1)

cowboy76Spain (815442) | about 2 years ago | (#41129881)

A little offtopic, but your post reminds me of something I read not so long ago

"If religions say that life is eternal, why are they so worried about what you do in your first century?"

but not of practical use (1)

fustakrakich (1673220) | about 2 years ago | (#41129837)

Why not? It could be used to count ballots. Couldn't be any sloppier than what we have now. Considering who's running, it may as well be a coin toss anyway

The most important part is knowing the question. (1)

The Living Fractal (162153) | about 2 years ago | (#41130149)

It may sound cheesy, but if you are going to get the answer correct 50% of the time then the most important piece becomes knowing which question to ask, and being able to test whether your 50% answer is right. If not, rinse and repeat. Eventually you're going to get something interesting.

MUST BE A MADE IN USA VERSION !! (0)

Anonymous Coward | about 2 years ago | (#41130153)

Cuz like dude, that's not half bad !!

Oh, wait, it is !!

Better accuracy than a Pentium (1)

turkeyfeathers (843622) | about 2 years ago | (#41130289)

IIRC, the Pentium gave correct answers 0% of the time.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>