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

← Back to Stories (view on slashdot.org)

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

Posted by timothy on Sunday August 26, 2012 @03:41AM from the please-show-your-work dept.

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

262 comments

Min score:

Reason:

Sort:

That's no moon... by Anonymous Coward · 2012-08-26 03:45 · Score: 0, Funny

...It's a space station!
1. Re:That's no moon... by Anonymous Coward · 2012-08-26 03:48 · Score: 5, Funny
  
  To be fair, it could have been either until we looked.
  (And you could have posted either here or at the correct story.)
2. Re:That's no moon... by shentino · 2012-08-26 04:09 · Score: 1, Insightful
  
  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.
3. Re:That's no moon... by Dexter+Herbivore · 2012-08-26 06:52 · Score: 1
  
  Without having studied this particular issue, I'm guessing that that is why the answer is correct only 50% of time under ideal circumstances. It can be 5x3=15 or 3x5=15 (so it could've been either). Perhaps someone more involved with quantum algorithms can correct me on this?
4. Re:That's no moon... by Anonymous Coward · 2012-08-26 08:55 · Score: 3, Informative
  
  Schrödinger wrote about the cat idea in order to demonstrate how ridiculous that particular model of quantum physics is; he'd be rolling in his grave if he knew that people were taking it as truth...
5. Re:That's no moon... by Anonymous Coward · 2012-08-26 11:07 · Score: 1
  
  I'm no expert. But Shor's algorithm has you choose a value A and find the period of f(x) = a**x mod n.. If r ends up being odd or a**r/2 = -1 mod n, you have to start over.. (If I understand it correctly, if r/2 = -1, you just showed 15x1 = 15 which isn't useful..
  Perhaps some more knowledgeable could comment on this?
6. Re:That's no moon... by Pseudonym · 2012-08-26 14:09 · Score: 3, Informative
  
  That case happens rarely. The case you're actually looking for is values of a where the function has even period.
  The reasoning behind it is this:
  Suppose that N has at least two distinct prime factors. (If it isn't, then N is either prime or a perfect power of a prime. There are efficient algorithms for detecting the latter case.) Further suppose that the function f(x) = a^x mod N has minimum period 2r for some r. (That is, f(x+2r) = f(x), but f(x+q) f(x) for any q < 2r.)
  In this case, a^(2r) is congruent to 1 modulo N, but a^r is NOT congruent to 1 modulo N. That is, a^r is a square root of unity modulo N, but it isn't congruent to 1. If it also isn't congruent to -1 (which is the case that you mentioned), then it's a nontrivial square root of unity.
  Now consider the number d = gcd(a^r-1, N). If d=N, then N is a factor of a^r-1, that is, a^r is congruent to 1 modulo N. This is a contradiction (since we eliminated this case above), so it can't happen. Similarly, if d=1, then a^r is congruent to -1 modulo N, which is the other case that we eliminated above. (Exercise: prove this!)
  So d is a divisor of N (because it's the gcd of N with some other number), but it isn't 1 or N. Therefore, it's a nontrivial factor of N.
  Of course, it's not obvious that there should be an a for which f has even period, but that's where the hardcore analysis comes in.
  
  --
  sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
7. Re:That's no moon... by billstewart · 2012-08-27 06:58 · Score: 1
  
  But you can't tell which way he's rolling without opening his coffin.
  
  --
  
  Bill Stewart
  New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Maths by Anonymous Coward · 2012-08-26 03:45 · Score: 3, Funny

Sometimes 2+2=5, give the thing a break!
1. Re:Maths by Anonymous Coward · 2012-08-26 03:51 · Score: 4, Funny
  
  Of course 2 + 2 = 5. Take two strings. Tie 2 knots in each. Then tie them together and count the knots.
2. Re:Maths by Anonymous Coward · 2012-08-26 04:23 · Score: 2, Funny
  
  For very large values of 2
3. Re:Maths by Anonymous Coward · 2012-08-26 05:06 · Score: 0
  
  If you define the operator + as +: x +_ y +_ 1 for all x,y in some magma, where +_ denotes the common addition +, then yes.
4. Re:Maths by user32.ExitWindowsEx · 2012-08-26 06:52 · Score: 1
  
  If you define the operator + as +: x +_ y +_ 1 for all x,y in some magma, where +_ denotes the common addition +, then yes.
  magma? volcanoes can do math now?
  
  --
  "Evil will always triumph because good is dumb." -- Dark Helmet
5. Re:Maths by Anonymous Coward · 2012-08-26 07:19 · Score: 0
  
  If you redefine everything at will, then every nonsense you say suddenly becomes correct.
  No, you can't just redefine + to mean something fitting your agenda.
  It's called the “no true Scotsman" fallacy.
6. Re:Maths by K.+S.+Kyosuke · 2012-08-26 07:54 · Score: 2
  
  Two is a large value already, it's larger than the average number of ears per capita in the general population.
  
  --
  Ezekiel 23:20
7. Re:Maths by Anonymous Coward · 2012-08-26 08:24 · Score: 0
  
  Clearly you don't understand the "no true Scotsman" fallacy nor mathematics nor logic nor the original claim that "Sometimes 2+2=5".
8. Re:Maths by Anonymous Coward · 2012-08-26 08:37 · Score: 0
  
  ... 6?
  wait, tie one or both ends of each string together?
9. Re:Maths by lordmetroid · 2012-08-26 08:56 · Score: 1, Interesting
  
  Why is this anonymous coward moderated funny. The anonymous should be moderated insightful cause it is correct that for very large number of two. 2+2=5. Let me demonstrate:
  
  By writing 2+2=5, we merely have one significant digit of precision. It is very possible that the 2s are for example 2.4 or 2.1 or whatever number which would be rounded down to 2 when written with a one significant digit.
  
  Imagine that the twos are actually 2.4999... which when added together would be 4.999... As we are only have a single digit of precision we are forces to round that to 5. Hence we have proved that 2+2=5 for very large numbers of 2.
10. Re:Maths by Anonymous Coward · 2012-08-26 09:26 · Score: 1
  
  You will never make an accountant.
  The correct response to 'what is 2+2?' is 'what do you want it to be?'
11. Re:Maths by Smallpond · 2012-08-26 09:27 · Score: 1
  
  If you define the operator + as +: x +_ y +_ 1 for all x,y in some magma, where +_ denotes the common addition +, then yes.
  magma? volcanoes can do math now?
  Yes. And they're really bad at it.
12. Re:Maths by Anonymous Coward · 2012-08-26 10:23 · Score: 0
  
  This is dumb. You are adding whole numbers then. If you decided to write 2.4999 as 2 then your answer is 4. I mean, it is what it is and if you were intending to add 2.4999 & 2.4999 and not 2 & 2 then you should write 2.4999 + 2.4999.
13. Re:Maths by Ossifer · 2012-08-26 10:51 · Score: 2
  
  Oh come on! They're right almost 48% of the time!
14. Re:Maths by Anonymous Coward · 2012-08-26 11:18 · Score: 0
  
  And if you define the number 2 as 2.5, then yes as well.
  Of course, my solution is ridiculous, yours is "accepted in some circles."
15. Re:Maths by hajile · 2012-08-26 11:48 · Score: 2
  
  You're thinking of ++2 + 2 = 5;
16. Re:Maths by starakurva · 2012-08-26 13:21 · Score: 1
  
  "2 ought to be enough for anybody." --Bill Gates 1066
  
  --
  All you need is lurv.
17. Re:Maths by VortexCortex · 2012-08-26 14:42 · Score: 1
  
  Of course 2 + 2 = 5. Take two strings. Tie 2 knots in each. Then tie them together and count the knots.
  A similar proof can be (de)constructed using division instead of addition:
  Take a string, and divide it into multiple strings by first cutting it in two places. Select any part of the string and cut it in two places.
  Count the pieces of string: 5
  Eg, a string with two cuts, then two cuts again: __ __ --- --- ---
  Five pieces.
18. Re:Maths by tzot · 2012-08-26 18:47 · Score: 1
  
  > "2 ought to be enough for anybody." --Bill Gates 1066
  That's another Bill Gates: the chairman of the witch burning society.
  
  --
  I speak England very best
19. Re:Maths by Anonymous Coward · 2012-08-26 21:39 · Score: 1
  
  In what world can 2+2=5 ever be true? Where are these 2.4999 coming from?
  The statement was "two plus two equals five", not "two point four nine recurring plus two point four nine recurring equals a number close enough to five we might as well call it five".
  You can't just add arbitrary fractions of a number to an equation that you pulled out of nowhere, to make the answer something it's not.
  What you're thinking of is that limitations in computers can make 2+2=5 appear true in very specific circumstances, like outputting the values of the twos as integers, so that it looks like they're twos, when in fact the computer is calculating the answer using 2.49999 or whatever.
  2+2=5 is still not true as a concept since that is not the actual calculation being performed, just what your debugger is showing.
  In that case, 2+2=5 is no more true than 2+2="hello, world", just because you managed to write a program that shows that in stdout.
  
  As we are only have a single digit of precision we are forces to round that to 5. Hence we have proved that 2+2=5 for very large numbers of 2.
  No, what you've proved is that 2+2 can be rounded to 5, assuming there are fractional parts of one or both twos that add up to 0.5 or more that weren't stipulated in the equation, and we're arbitrarily imposing that because the twos were rounded, so too must the result.
  Fractions for which there is no reason to believe exist any more than to pretend 2-3=9, because there was actually a 1 in front of the 2 (making it 12) that wasn't displayed because we're arbitrarily imposing that the display of the numbers is limited to the one right-most digit.
20. Re:Maths by Zembar · 2012-08-26 22:56 · Score: 1
  
  actually, 2.499999.... is exactly equal to 2.5, so it would be 3 if rounded to one digit.
21. Re:Maths by thomasw_lrd · 2012-08-27 01:56 · Score: 1
  
  For large enough values of 2, it actually approximates to 6.
  
  --
  21st Century Renaissance Man
First post - from a quantum computer by Anonymous Coward · 2012-08-26 03:46 · Score: 1

50% of the time.
1. Re:First post - from a quantum computer by StillAnonymous · 2012-08-26 05:43 · Score: 4, Funny
  
  They've done studies, you know. 48% of the time, it works every time.
2. Re:First post - from a quantum computer by Anonymous Coward · 2012-08-26 20:37 · Score: 0
  
  It's only when the professor is around that it doesn't seem to work so well...
3. Re:First post - from a quantum computer by Anonymous Coward · 2012-08-27 04:22 · Score: 0
  
  48% is still better than most freshman college students.
Can someone explain... by Crudely_Indecent · 2012-08-26 03:55 · Score: 4, Insightful

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?

--

"Lame" - Galaxar
1. Re:Can someone explain... by Anonymous Coward · 2012-08-26 03:58 · Score: 5, Informative
  
  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.
2. Re:Can someone explain... by Anonymous Coward · 2012-08-26 03:58 · Score: 1
  
  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).
3. Re:Can someone explain... by gmueckl · 2012-08-26 03:59 · Score: 4, Informative
  
  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.
  
  --
  http://www.moonlight3d.eu/
4. Re:Can someone explain... by Anonymous Coward · 2012-08-26 04:00 · Score: 0
  
  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.
5. Re:Can someone explain... by Anonymous Coward · 2012-08-26 04:03 · Score: 5, Funny
  
  How is it useful to have the correct answer 50% of the time?
  Cat life-support devices.
6. Re:Can someone explain... by Grumbleduke · 2012-08-26 04:03 · Score: 1
  
  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).
7. Re:Can someone explain... by Anonymous Coward · 2012-08-26 04:04 · Score: 2, Insightful
  
  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.
8. Re:Can someone explain... by Anonymous Coward · 2012-08-26 04:12 · Score: 5, Funny
  
  If you can factor really large prime numbers,
  I can factor really large prime numbers in my head.
9. Re:Can someone explain... by thue · 2012-08-26 04:12 · Score: 4, Insightful
  
  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 )
  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.
10. Re:Can someone explain... by Anonymous Coward · 2012-08-26 04:13 · Score: 1
  
  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.
11. Re:Can someone explain... by Sancho · 2012-08-26 04:19 · Score: 4, Informative
  
  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.
12. Re:Can someone explain... by Sancho · 2012-08-26 04:21 · Score: 1
  
  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.
13. Re:Can someone explain... by ShanghaiBill · 2012-08-26 04:23 · Score: 4, Informative
  
  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 fall into this category.
14. Re:Can someone explain... by Forty+Two+Tenfold · 2012-08-26 04:26 · Score: 1
  
  number n, which is the product of two secret primes p and q
  
  --
  Upward mobility is a slippery slope - the higher you climb the more you show your ass.
15. Re:Can someone explain... by Sancho · 2012-08-26 04:27 · Score: 2
  
  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.
16. Re:Can someone explain... by cowboy76Spain · 2012-08-26 04:37 · Score: 2
  
  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?
  
  --
  Why can't /. have a rich-text editor? Editing your own HTML is so XXth century.
17. Re:Can someone explain... by JustOK · 2012-08-26 04:43 · Score: 1
  
  Sometimes it's good enough, sometimes it's not.
  
  --
  rewriting history since 2109
18. Re:Can someone explain... by __aaltlg1547 · 2012-08-26 04:43 · Score: 5, Interesting
  
  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.
19. Re:Can someone explain... by Russ1642 · 2012-08-26 04:50 · Score: 1
  
  There is no Nobel prize in math.
20. Re:Can someone explain... by cryptizard · 2012-08-26 04:50 · Score: 4, Informative
  
  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.
21. Re:Can someone explain... by Anonymous Coward · 2012-08-26 04:53 · Score: 0
  
  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.
22. Re:Can someone explain... by neokushan · 2012-08-26 04:54 · Score: 4, Insightful
  
  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.
  
  --
  +1 IDisagreeSoHeMustBeATrollOrAnAstroturferOrAShill
23. Re:Can someone explain... by Opyros · 2012-08-26 04:57 · Score: 0
  
  What's more, there is no Nobel prize in math.
24. Re:Can someone explain... by crabel · 2012-08-26 04:58 · Score: 1
  
  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 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...
25. Re:Can someone explain... by goffster · 2012-08-26 05:00 · Score: 4, Insightful
  
  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.
26. Re:Can someone explain... by V!NCENT · 2012-08-26 05:01 · Score: 1
  
  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.
  
  --
  Here be signatures
27. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:01 · Score: 0
  
  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.
28. Re:Can someone explain... by V!NCENT · 2012-08-26 05:06 · Score: 1
  
  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...
  
  --
  Here be signatures
29. Re:Can someone explain... by sjames · 2012-08-26 05:13 · Score: 1
  
  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.
30. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:16 · Score: 0
  
  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)
31. Re:Can someone explain... by kaws · 2012-08-26 05:23 · Score: 1
  
  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.
32. Re:Can someone explain... by circletimessquare · 2012-08-26 05:27 · Score: 2, Insightful
  
  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?
  
  --
  intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
33. Re:Can someone explain... by __aaltlg1547 · 2012-08-26 05:31 · Score: 1, Insightful
  
  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.
34. Re:Can someone explain... by sjames · 2012-08-26 05:31 · Score: 3, Informative
  
  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).
35. Re:Can someone explain... by jjh37997 · 2012-08-26 05:32 · Score: 1
  
  Just run the program multiple times and take the mode.
36. Re:Can someone explain... by ld+a,b · 2012-08-26 05:36 · Score: 3, Insightful
  
  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.
  
  --
  10 little-endian boys went out to dine, a big-endian carp ate one, and then there were -246.
37. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:36 · Score: 0
  
  They aren't primes... they are relatively prime... big big difference :)
38. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:36 · Score: 0
  
  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.
39. Re:Can someone explain... by Wraithlyn · 2012-08-26 05:40 · Score: 5, Insightful
  
  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.
  
  --
  "Mind, as manifested by the capacity to make choices, is to some extent present in every electron." -Freeman Dyson
40. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:44 · Score: 0
  
  The hit rate for the next likely incorrect answer is probably a percentage far lower than 48%. So you can be reasonably assured of the answer even at 48% hit rate.
41. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:49 · Score: 0
  
  This actually doesn't help with primes at all. The quantum factoring algorithm will returns some false positives rather than no positives at all. And just because you verify all false positives from quantum computing as false, that doesn't prove that factorization is impossible. It just proves that the identified ones are wrong.
  To use this for primes someone would have to first prove that if the true positive exists, it will be always included in the output of the quantum factorization, but nothing like that has been proven.
  Nevertheless, the GP is correct that if you need to factor a number where the factors are really large it may take a long time to compute the factorization in a normal way, but if we identify the factors quickly using quantum computing, then we can isolate the actual solution very quickly with classical computing.
  However the main issue is scaling - the numbers that would be of interest are 512 bits, 1024 bits, 2048 bits, or more, and scale geometrically. So far quantum computing doesn't and every bit added multiplies the quantum system complexity by a factor of 2, so regardless of how this is done we'll probably never get there with any of the current approaches.
42. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:57 · Score: 3, Informative
  
  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.
  
  Actually, the math and abstract procedure of how to do this is pretty well understood. The question of how to get definite answers from such quantum states is solved, in the sense the algorithm's results are very quickly and easily shown to have worked or not (and not just by multiplying the two factors, the result of the quantum portion of calculation has to be converted into actual factors via classical computation, and is obvious when this fails). The jump from probabilistic states to definite answers is already quite clear.
  The hard part is improving the signal to noise ratio essentially. It is not the managing of the quantum states, but managing of the apparatus to keep it doing what you want it to do. And that is one of the big results of this paper. It is not about the 48% being good enough to be practical, it is that the 48% result is almost the ideal 50% case. This means that outside noise and device failure due to improperly carrying out the steps was quite small, which suggest that the number of qubits could be scaled up, and still have the algorithm followed. It is pretty well understood what the limitations of the algorithm is, and known that it could still be very, very useful, but that won't go anywhere if the algorithm can't be implemented.
43. Re:Can someone explain... by Anonymous Coward · 2012-08-26 05:57 · Score: 0
  
  Computers can't factor, they just check every possibility.
  This thing can factor.
  small steps.
44. Re:Can someone explain... by Anonymous Coward · 2012-08-26 06:01 · Score: 0
  
  Yeah, that kind of begs the question in more ways than one... and also raises the question: can this post be proved with more or less drugs?
45. Re:Can someone explain... by poizan42 · 2012-08-26 06:11 · Score: 1
  
  You can easily check if a factorization is correct using a conventional computer. Of course factorizing 15 is pretty useless in itself, but you have to start somewhere. To put things into perspective, assume you have a number with 1000 digits, and you want to factorize that. The best known conventional algorithm for doing that is the General Number Field Sieve with which the factorization would take in the order of 1.4 * 10^43 operations. Assuming you had a computer capable of executing a trillion operations per second it would still take about 4.6 * 10^23 years, which is 33 trillion times the age of the universe!
  Now assume you had a quantum computer with enough qubits - we would need at least 3322 qubits. Let us say that it is otherwise a pretty crappy quantum computer as it only gets the factorization right 0.1% of the time. Now we try to use our quantum computer. It gives us an answer in the order of just a few billion operations. Even if it is quite slow and only capable of 1 million operations per second, it would still give an answer in less than an hour. This answer is probably wrong, however we can easily check that using our conventional computer. Checking if a number divides another is FAST. It can actually be done in slightly more than just the size of the input - the existence of a factor in a 1000 digit number would take the order of maybe 100,000 operations to check - in much less than a second.
  So the time it takes to validate the answer is negligible here. We just keep on asking the quantum computer to try again until we get it right. So how long would it take? After 10000 tries we would have gotten the correct result with a probability of 99.995%. So if every try takes 1 hour, we would be pretty sure to have succeeded in less than a year (10000 hours = 1 year 1 month 21 days 6 hours). So even with this big but crappy quantum computer we would be able to factorize the integer in less than a year instead of 33 trillion times the age of the universe.
46. Re:Can someone explain... by Volguus+Zildrohar · 2012-08-26 06:18 · Score: 1
  
  Well, when I'm brute-forcing the bits of a 128-bit encryption key, I get the right answer 50% of the time too. The problem is that I need 128 answers ;)
  
  --
  When confronted with one problem, some think "I'll use recursion". Now they are confronted with one problem.
47. Re:Can someone explain... by Anonymous Coward · 2012-08-26 06:34 · Score: 0
  
  your code is missing a paren, and it is really bothering me.
  This code will always return the first answer, or 0 or NaN.
  (But most likely fail to compile.)
  (assuming it is written in D)
48. Re:Can someone explain... by Atzanteol · 2012-08-26 06:35 · Score: 0
  
  Whaaah! The automobile is slower than my horse! And it doesn't go as faaaar! Whaaaah!
  
  --
  "Ignorance more frequently begets confidence than does knowledge"
  
  - Charles Darwin
49. Re:Can someone explain... by Dexter+Herbivore · 2012-08-26 06:55 · Score: 2
  
  Ever heard of 'proof of concept'?
50. Re:Can someone explain... by Matchstick · 2012-08-26 06:55 · Score: 2
  
  I have a device that gives you the winning lottery numbers ahead of time, but it has only a 10% chance of being correct. Is it useful?
51. Re:Can someone explain... by Anonymous Coward · 2012-08-26 06:56 · Score: 0
  
  An algorithm that could factor a 4096 bit number even 10%
  of the time in a reasonable amount of run-time would be enough
  to consider 4096 key as completely unsafe
  there, ftfy. we already have algorithms that can factor any number 100%
  of the time. i think what you want is the product of success rate and runtime.
  if runtime is on the order of even an hr, then a success rate of even 1% would
  render many uses unsafe. eg, for short-lived ssl connections, this would matter,
  but longer-lived ssl connections might need to consider their key rotation schedule.
52. Re:Can someone explain... by Anonymous Coward · 2012-08-26 06:57 · Score: 2, Funny
  
  Well, at least the poster was half right...
53. Re:Can someone explain... by Anonymous Coward · 2012-08-26 06:58 · Score: 0
  
  What's more, there is no Nobel prize in math.
  "On the bright side, if we can make this happen they're going to have to invent a new kind of Nobel Prize to give us, so hang in there."- Cave Johnson
54. Re:Can someone explain... by Rich0 · 2012-08-26 07:00 · Score: 2
  
  That may be so, but computing the prime factorization of 15 is not in that class.
  Actually, it is. There is a reason that kids are taught multiplication long before factoring. It just happens that for numbers this small you can do both in your home.
  If I handed you a pencil and paper and asked you to factor 1474 to primes it would take you a LOT longer than if I gave you the factors and asked you to multiply them.
  Verifying the factorization of even a 2048 bit number by hand on paper is probably doable, though likely pretty tedious. Calculating those factors if they are just two primes would be astronomically difficult without Shor's algorithm or some other breakthrough even with every supercomputer likely to be made in the next 100 years. So, if I told you that some particular answer was 48% likely to be right, and any of 1 million other answers were each about 0.00001% likely to be right, then it seems like verification would be pretty easy to do.
55. Re:Can someone explain... by V!NCENT · 2012-08-26 07:15 · Score: 1
  
  OK, I'm sorry; (48+52)/2 equals 50 (%). I even forgot what I was calculating... Damnit. I realy need to stop taking these cianide pills.
  How stupid of me to see the Universe as a corral, with all possible branches (time is change, right?), counting in relativity (in time), multiverse Quantum Physic behavior (48% versus 52%, damn how retarded) and the fact that we are observing multiverse behavior in just 'side' of the universe, while testing a mathmetical theory without checking all infinite numbers. Holy shit, I so stupid.
  Thanks man, I'm off to rehad straight away 3
  
  --
  Here be signatures
56. Re:Can someone explain... by chgros · 2012-08-26 07:15 · Score: 1
  
  Most NPC problems fall into this category.
  Actually, by definition, *all* NP-complete problems fall into this category (unless P = NP)
57. Re:Can someone explain... by mcswell · 2012-08-26 07:43 · Score: 1
  
  As has been pointed out in postings above, if you have a device that returns the correct factorization half the time, then by running it multiple times, you can easily determine the factors of a composite number--because it's easy and fast to _check_ the answers with a classical computer.
  Or if you don't know whether the number is composite or prime, then by running it N times and checking the answer each time, you can reduce the uncertainty that a number which happens to be prime is prime to 1/2**N.
  In both cases, you can arrive at negligible error rates in reasonable time.
  (BTW, I believe factoring has been shown *not* to be NP hard, but it has some similarities: hard to come up with answers, easy to verify them.)
58. Re:Can someone explain... by Anonymous Coward · 2012-08-26 07:46 · Score: 0
  
  You would be more convincing if you actually sounded like you knew any math or physics. Either learn what some of those terms and theories refer to, or stop trying to re-purpose them to mean something from your own ideas. In the latter case, people will use their normal meanings, which makes what you say nonsensical. Doesn't matter how good of an idea you have in your head if you can't communicate it.
59. Re:Can someone explain... by __aaltlg1547 · 2012-08-26 07:48 · Score: 1
  
  I guess somewhat close to halfway there. If they had also computed the factorization of 14 with about 48% correct results, I'd be 100% more confident that they were onto something. What they've shown is that they made a quantum device that can produce results of 3 and 5 about half the time. Wouldn't you be happier if you knew that it didn't produce 3 and 5 half the time regardless how they program it?
  The original abstract (http://www.nature.com/nphys/journal/vaop/ncurrent/full/nphys2385.html) mentions that their device is a 9-qubit device. If it can factor numbers bigger than 15, why didn't they do that? Or did they try that and get null results? If they haven't tried any other number yet, I'd say their publication is premature. If they have, they should be presenting more results.
  Regarding the scalability, a lot more experiements are needed to find out if their hardware is at all scalable. Four qubits working is almost nothing. If that gives you a 48% correct result, that's 96% of the 50% expected. If the scaling of errors is 1% additional probability of error per bit, then the probabilty of a correct result would be 1/2 (the Schor 50%) x 99%^N. At 128 bits, that's about 14% correct, which would make cracking 128 bit encryption trivial. You'd only need on average 7 trials to verify a correct factoring, which would be awesome, and at 1024 bits you'd only need about 59,000 trials. So all present day encryption would be pretty much useless.
  But that's ONLY if the error scales linearly with number of bits like that. If the errors creep in inside the computation somehow, it could be a lot worse than Pb^N. If they have a 9-bit machine they ought to try factoring the biggest numbers it can handle. That would give us a clue to how the errors scale.
60. Re:Can someone explain... by amorsen · 2012-08-26 07:50 · Score: 1
  
  If you can factor really large prime numbers, you are a long way to breaking private/public-key encryption.
  "The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers." From Bill Gates: "The Road Ahead".
  
  --
  Finally! A year of moderation! Ready for 2019?
61. Re:Can someone explain... by __aaltlg1547 · 2012-08-26 07:57 · Score: 1
  
  As has been pointed out in postings above, if you have a device that returns the correct factorization half the time, then by running it multiple times, you can easily determine the factors of a composite number--because it's easy and fast to _check_ the answers with a classical computer.
  Or if you don't know whether the number is composite or prime, then by running it N times and checking the answer each time, you can reduce the uncertainty that a number which happens to be prime is prime to 1/2**N.
  In both cases, you can arrive at negligible error rates in reasonable time.
  (BTW, I believe factoring has been shown *not* to be NP hard, but it has some similarities: hard to come up with answers, easy to verify them.)
  With only four-bit computations, it's useless. It needs to be scaled up by several bits just to show that their hardware approach has the potential to solve problems that aren't trivial.
62. Re:Can someone explain... by mcswell · 2012-08-26 08:08 · Score: 1
  
  Yes, but that's a different point from the posting I was replying to, namely the putative need for "negligible error rates."
63. Re:Can someone explain... by Anonymous Coward · 2012-08-26 08:30 · Score: 0
  
  Hell...calling a coin flip is right 50% of the time.
64. Re:Can someone explain... by vandy1 · 2012-08-26 08:47 · Score: 1
  
  They aren't primes... they are relatively prime... big big difference :)
  I'm sorry, that's just wrong in the case of RSA: RSA on wikipedia.
  Step 1: Choose 2 distinct primes.
  etc...
65. Re:Can someone explain... by Anonymous Coward · 2012-08-26 08:54 · Score: 0
  
  And don't forget that you contribute shitting all over the accomplishments of others. That's super important too.
66. Re:Can someone explain... by ShanghaiBill · 2012-08-26 09:47 · Score: 2
  
  Well, when I'm brute-forcing the bits of a 128-bit encryption key, I get the right answer 50% of the time too. The problem is that I need 128 answers ;)
  No, your problem is that you have no way of verifying individual bits.
  I remember the scene from Terminator 2, where the teenage John Conner is stealing money from an ATM. He is cracking the encryption, and each digit takes the same amount of time. But that is nonsense. Once you find the first digit, you are 90% done, and all the others combined would take only 10% more time. The other problem is in the final scene, where they are fighting the T-1000 in the smelting plant, and Arnold destroys him by shooting him at point blank range with an M79. Grenade launchers don't work that way! They are rotationally armed, and need to turn a certain number of times after firing or they will not detonate. You can't fire them at point blank range!
  The worst part about these technical discrepancies is that people don't even appreciate you pointing them out, "Would you just shut up and let us enjoy the movie."
67. Re:Can someone explain... by V!NCENT · 2012-08-26 09:49 · Score: 1
  
  If I want to be on the convincing bandwagon, I'd get into politics.
  Instead I'd like to see you prove me wrong.
  Proof in front of every reader here why I'm wrong, and even I will be convinced that I am stupid.
  Some would call this "put up or shut up". There; I made a punchline. Like me now?
  
  --
  Here be signatures
68. Re:Can someone explain... by Ambvai · 2012-08-26 10:17 · Score: 1
  
  Not if the lottery only has ten possible results. More or less than that? Yep!
69. Re:Can someone explain... by Anonymous Coward · 2012-08-26 10:31 · Score: 0
  
  You would have to make an actual point before there is anything to attempt to prove/disproved. The simple math error was already dealt with in response to the other AC. Someone could ask what you define as "pure logic" and why math doesn't overlap with that, but I don't except that to be fruitful. Otherwise, how does one disprove a list of random jargon word salad?
70. Re:Can someone explain... by Anonymous Coward · 2012-08-26 10:33 · Score: 0
  
  This may be the true essence of science, in fact. Thanks for the example!
71. Re:Can someone explain... by russotto · 2012-08-26 11:20 · Score: 2
  
  2% difference is significant and whatever the cause of that is, it's almost certain to not scale well:
  That's a lot of extrapolation from a single data point.
72. Re:Can someone explain... by Lord_Naikon · 2012-08-26 11:27 · Score: 1
  
  On the subject of splitting hairs...
  1) Every ATM locks you out after a couple of tries.
  2) You don't find the first digit. You find all of them at once with 1/(10000-n) probability (where n is the number of known bad codes).
  3) Terminator 2 is awesome.
73. Re:Can someone explain... by Chris+Burke · 2012-08-26 11:31 · Score: 2
  
  10% accuracy is useful if their are less than 10 results? Like, in case you want to make this 8-number lottery more exciting by reducing your chances? Actually, that's brilliant. The 8-number lottery wouldn't pay out well, but it'd be so cheap everyone would enter just for the fleeting feeling of winning something... They might even go so far as to reduce their own chances to make it more of a rush when they win. We'll be rich.
  
  --
  
  The enemies of Democracy are
74. Re:Can someone explain... by Anonymous Coward · 2012-08-26 11:51 · Score: 0
  
  Yes, but he did it with "style" using a "computer that could fit in a backpack" back when a laptop weighed as much as my desktop at work. His methods were also incorrect as you have to have a proper account number to send to the host, and have the proper pin, you only get a couple of tries with the units from that era. (I used to work in the ATM trade).
  The grenade launcher portion was fun to watch, I know that grenades don't work that way and that they have a minimum arming range. My take is that the sheer impact of the grenade is what launched the T1000 over the edge. I also love how long it took for the T1000 to reform after being shot in that scene, other times he instantly reformed but this time it took a while.
  I also get slapped senseless when watching movies and calling bullshit on the screw ups I see. I guess we can't let facts get in the way of a good story. Gotta love Aspergers :)
75. Re:Can someone explain... by Anonymous Coward · 2012-08-26 12:03 · Score: 0
  
  What if you could solve a problem that would normally take say 2 million years with classic computers in 10 years with 50% probability of being a correct solution?
76. Re:Can someone explain... by Anonymous Coward · 2012-08-26 13:15 · Score: 0
  
  Well, you probably have a point, but unless you know a lot more than is in the article, you're making an awful lot of unjustified leaps. And it's somewhat of a moot point whether the error scales exponentially with the number of bits, linearly, or not at all, because we don't actually know how to add more bits right now at all...
77. Re:Can someone explain... by cryptizard · 2012-08-26 13:43 · Score: 1
  
  I'm not sure how your comment is relevant to what I said. Quantum algorithms are not interesting for finding primes as we already have very fast classical algorithms for this. I was merely illustrating how our probabilistic classical algorithms are similar to Shor's because they both have one-sided error that we can efficiently limit by repeating the experiment. We even have a polynomial algorithm for primality testing which gives correct answers every time. Also, why do you say that the numbers we are interested in scale geometrically?
78. Re:Can someone explain... by Anonymous Coward · 2012-08-26 14:30 · Score: 0
  
  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?
  If it could quickly factor large numbers it would be useful (and practical) even if it only got the answer right 1 in a thousand times.
79. Re:Can someone explain... by Anonymous Coward · 2012-08-26 14:32 · Score: 0
  
  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?
  For crypto stuff, this is not really a problem.
80. Re:Can someone explain... by Anonymous Coward · 2012-08-26 14:41 · Score: 0
  
  > Also, why do you say that the numbers we are interested in scale geometrically?
  That's simply because if you can currently efficiently factor a 1024-bit number, and you want something for cryptographic purposes, you have to go twice the size or four times the size - to 2048 bits or 4096 bits - any classic algorithm/machine that can efficiently factor a 1024-bit number will do about the same to factor a 1025-bit number. You really want to put some gap between what can be factored and what is used for various specific purposes. So, in turn, quantum computing would have to scale better than that to actually make any sense at all. Otherwise all it does is shift the needed numbers to "the next size up", if it can do anything at all. And so far it isn't even good enough to do that. Factoring complexity is based on the size in bits of the number that is being factored.
81. Re:Can someone explain... by jedwidz · 2012-08-26 14:56 · Score: 1
  
  I remember the scene from Terminator 2, where the teenage John Conner is stealing money from an ATM. He is cracking the encryption, and each digit takes the same amount of time. But that is nonsense.
  This could've been a timing or side-channel attack, which really can reveal digits one at a time.
  Sometimes Hollywood does get it right.
82. Re:Can someone explain... by Anonymous Coward · 2012-08-26 15:01 · Score: 0
  
  You may find this interesting http://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/
83. Re:Can someone explain... by KingMotley · 2012-08-26 15:43 · Score: 1
  
  Nah, it's exact. Exactly 2% with a confidence level of +-98%.
84. Re:Can someone explain... by Anonymous Coward · 2012-08-26 15:50 · Score: 0
  
  Slashdot 1878: Thomas Edison successfully discovers 9,999 ways to not make a lightbulb.
85. Re:Can someone explain... by Anonymous Coward · 2012-08-26 17:56 · Score: 0
  
  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.
  
  I think your great-grandfather sat on the porch and his neighbor came by to say: "Hey, I have news. They invented a machine that can punch holes on a sheet of paper." and your great-grandfather said "Come again when they invent something to do math for me."
  My point is: don't be ignorant. CS and everything related to that is the fastest-developing domain the human kind ever got to know.
  
  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.
  
  Quantum computing may just as well be 30 years behind traditional computing methods in general, 15 behind automated mechanical methods and 5 behind electronic computers, but can you tell me how many years part the potential? (HINT: quantum computing is ahead)
86. Re:Can someone explain... by Anonymous Coward · 2012-08-26 20:35 · Score: 0
  
  He is cracking the encryption, and each digit takes the same amount of time. But that is nonsense.
  He's just a kid there, perhaps he didn't have a most optimal implementation yet. Or even more likely, the ATM cracking scene doesn't take that long, maybe he was satisfied with the current speed and didn't bother to optimize the algorithm any further...
87. Re:Can someone explain... by Anonymous Coward · 2012-08-26 21:29 · Score: 0
  
  Prime factorization is in that class; don't be a dumbass. 50% success rate means you only have to do two verifications, on average, to get the correct result. GP gave a perfectly good response to GGP.
  And no, a middle school dropout cannot factorize 15 in his head. He knows that 3x5 = 15 and uses associative memory to get the result. Not the same thing at all.
88. Re:Can someone explain... by cryptizard · 2012-08-26 22:34 · Score: 1
  
  Yes but the difficulty is not linear, that is the whole point. If you can factor a 1024-bit number in x time, it should take 2*x to factor a 1025-bit number. That means that regardless of your current insecure bit length, if it has just now become insecure (i.e. we have just reached the technological level to factor keys of that length) you should be able to make it secure by adding a fixed number to the bit length (say 1024 bits, that seems to be the way we are going now). People didn't just jump from 2048 to 4096, there was a 3072 in between. There is no reason to continuously double your bit length except that you are being particularly paranoid. Now, this is all predicated on the assumption that a polynomial time factoring algorithm has not been found. If that is the case then it all goes out the window.
  
  Another slightly problemwith encryption based on factoring it is more complicated than say AES because the keyspace is more nuanced. For AES the above holds wonderfully because for any key length n there are exactly 2^n possible keys and each of them is just as good as any other. For RSA, we only allow keys that are a product of two prime numbers. There are not so many of these in a given number range so with the same bit length n there will not be 2^n possible keys, but actually far fewer. Luckily, what is important is that the number of keys is exponential in n and we believe currently that primes are distributed something like 2^n/n in an n bit keyspace. This means that we lose a bit of security (this is the reason RSA keys are so much longer than comparably secure AES keys) but asymptotically we get the properties that we want.
89. Re:Can someone explain... by V!NCENT · 2012-08-26 22:36 · Score: 1
  
  Pure logic is form, expressing their rules in symbols. Math is written in these symbols, but implements its own. Math is explaining the patterns we find in the way everything behaves. How it behaves is written, therefore, in math, and we call it physics.
  Then again, I was not making a point, yet I was explaining how it could be that the expected 50%, wasn't 50%. but then again 50% was expected from a mathematical algorithm. Since math, like I proved, has an infinite amount of variables, the 50% of the time, time which is possibilities thus variables, criteria was not met, because it wasn't tested long enough for the result to become 50%. So what happens in between, is that in a multiverse; 48% of the time it was correct in this universe, and thus 52% of the time it was correct in the other universe. That is true, because it still upholds the quantum principles, because the balance is proven by the averages in the percentage, hence my calculation.
  
  --
  Here be signatures
90. Re:Can someone explain... by Sqr(twg) · 2012-08-26 23:43 · Score: 1
  
  Oh, are we playing pick-a-nit? Then I'd like to point out that the word "sum" does not always refer to addition. It also has several other meanings, including "essence", "union", and "summary".
  I cryptography (which is the subject of the grandparent post), the word "sum" is frequently taken to mean "cheksum" or "combination of information". For example, the MD5 hash is often reffered to as the "MD5 sum". In that sense, it would be correct to say that "n is the sum of p and q".
91. Re:Can someone explain... by Rxke · 2012-08-26 23:51 · Score: 1
  
  Simple.
  run it, say, 100 times, you'll get a bunch of different answers, the right one is the one cropping up around 48 times :)
92. Re:Can someone explain... by Anonymous Coward · 2012-08-27 00:45 · Score: 0
  
  You're not making enough sense to be proven wrong. I think you're slipping in a bunch of "many worlds hypothesis" into your conversation. But you're jumping between definitions of linear time, as far as I can tell. Or maybe that's just what fell out of the grammar flaws in your posts ("time is not linear" sounds like timecube rantings).
93. Re:Can someone explain... by Your.Master · 2012-08-27 00:48 · Score: 1
  
  If it has less than 10 possible results, it could still be useful if the incorrect results were guaranteed to be achieved > 10% of the time. Then you find the answer it gives least, and that's your answer.
94. Re:Can someone explain... by steveb3210 · 2012-08-27 00:54 · Score: 1
  
  How in the world this was moderated insightful is beyond me - mod parent down, its wrong.
95. Re:Can someone explain... by Maximum+Prophet · 2012-08-27 01:01 · Score: 1
  
  Grenade launchers don't work that way! They are rotationally armed, and need to turn a certain number of times after firing or they will not detonate. You can't fire them at point blank range!..
  He's from the future. When you weren't looking, he disassembled the rounds, adjusted the arming device, and replaced the explosive with 5 common household chemicals that make it 10x more explosive.
  
  --
  All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
96. Re:Can someone explain... by Anonymous Coward · 2012-08-27 01:27 · Score: 0
  
  No, Mr. Sock Puppet, your other account got it wrong and now you're getting angry and defensive. Suck it up, buttercup.
97. Re:Can someone explain... by Anonymous Coward · 2012-08-27 01:43 · Score: 0
  
  Not instantly, polynomial time. That means that if the hardware is scaled up, if will be faster than the equivalent classical methods. However, the number of repetitions required to get a statistically meaningful answer will take some serious R&D before it is faster than a linear brute division algorythm.
  So, yes this is progress, but don't worry about your encryption scheme being broken by quantum computers yet.
98. Re:Can someone explain... by MozeeToby · 2012-08-27 01:51 · Score: 1
  
  I'd say the accuracy is more likely to be related to the number of qubits involved in the calculation. 4 qubits in this case gave an error of 4% (Shor's algorithm produces the correct result only 50% of the time so 1/25 times that the algorithm should run it is failing). That could imply that each qubit has an issue in ~1% of the runs, which would mean that 256 bit encryption can be solved 3.5% of the time, but it would arrive at the possible answer instantly. If you could do 10 runs a second, you'd have your answer in less than 5 seconds (remember, verifying a result is trivial). 2048 bit encryption would only produce the right answer .00000006% of the time. That's terrible right? Except again, 10 runs per second would give you the answer in matter of days.
99. Re:Can someone explain... by thomasw_lrd · 2012-08-27 02:19 · Score: 1
  
  /Puts on tinfoil hat
  The NSA has been using quantum computers for years. /Takes off tinfoil hat
  
  --
  21st Century Renaissance Man
100. Re:Can someone explain... by superzerg · 2012-08-27 02:32 · Score: 1
  
  I guess iff the reponse is right 50% of the time u just need to make the calcution several time : u will get 50 % of right reponse and lots af small % of different wrong reponses.
101. Re:Can someone explain... by IAmR007 · 2012-08-27 02:34 · Score: 1
  
  No. That's not how it works. That is totally incorrect.
  
  "Shor's algorithm will produce a nontrivial factor of n with probability >= 1-(1/2)^(k-1) where k is the number of distinct odd prime factors of n."
  Number Theory for Computing By Song Y. Yan
  
  Public key cryptography that is susceptible to Shor's algorithm specifically choose to use two prime numbers, so the probability of success is always theoretically 50%. Verifying the result is trivial. All that's needed is to feed the result into an oracle (easiest to do classically) to see if the result is valid, and loop until the oracle says "true". The loop can stop any time a correct answer is found; which one is correct is not based on statistics but an easy P complexity check. There are many quantum algorithms that only work a certain percentage of the time, and it isn't a problem.
102. Re:Can someone explain... by thue · 2012-08-27 02:48 · Score: 1
  
  Typo - I meant to write product :(.
103. Re:Can someone explain... by Anonymous Coward · 2012-08-27 04:17 · Score: 0
  
  The reason the result was 48% and not 50% was because of noise and loss of the quantum signal they were working with. It doesn't involve multiverse explanations (which is only one interpretation of quantum mechanics, that doesn't have any impact on the actual predictions or results of quantum theory) or requiring them to test longer, it is simply the device getting the wrong signal. It would be no different than say a packet collision on a network, or a radio signal loosing a bit due to some noise spike form a near by source. They would get closer to 50% by building a new device with less noise.
  Even if assuming an over-simplified multiverse interpretation, 48% correct in this universe doesn't mean 52% correct in the other universe, it could mean 48% correct in the other universe because both have lose 2% of the correct calculations, or it could be different if there is a bias in the noise for correct vs. incorrect calculations. A more accurate application of the multiverse interpretation would be much messier, as they are performing several quantum operations in the course of the algorithm.
  Also, by that definition, mathematics is pure logic, as rules are expressed by various symbols. Pure/Abstract math fields do not seek to explain patterns in the way things in the world behave, they seek to explain what results can be deduced from various combinations of rules and axioms. Other fields seek to apply these deduced patterns and rules to the physical world, e.g. physics, or applied math fields.
104. Re:Can someone explain... by kaws · 2012-08-27 05:06 · Score: 1
  
  My example is not as bad as your answer. I agree that it wasn't the best example but I wasn't really going for a perfect example. A tree type of search would find the name in less than 16 loops. This still wouldn't be faster than being able to find the answer right away. A proper way to critique my post would have been giving a better example than the one that I provided, than you wouldn't have shown up looking like a troll/jerk.
105. Re:Can someone explain... by onemorechip · 2012-08-27 05:09 · Score: 1
  
  Actually probably not. If you are told the number is prime, then the answer is already given and not by you. If you are not told, then you have to factor it, which amounts to proving that it is prime. If you can do that with a "really large" number, you are quite the machine.
  
  --
  But, I wanted socialized health insurance!
106. Re:Can someone explain... by Rotag_FU · 2012-08-27 07:18 · Score: 1
  
  Since it is now Monday, I doubt anyone will actually see this, but here goes. Disclaimer: I did not RTFA, I've been a Slashdot reader long enough to know there be dragons.
  Anyway, if the single correct answer is given 48% of the time and the set of all other incorrect answers is given at a rate of 52% of the time, it is possible that any individual incorrect answer does not appear nearly as many times as the correct answer. For example, lets say the correct answer is presented 48% of the time, but Wa is presented 24% of the time and Wb is presented 28% of the time. Where Wa is wrong answer a and Wb is wrong answer b where Wa is not equal to Wb. As long as the statistical presentation of an incorrect answer is significantly smaller than the presentation of a correct answer then the result could still be valuable since it should be easy to detect the likely correct answer "quickly". This is only the case if you can run the calculation enough times to determine a statistically significant variation between the correct answer and the various wrong answers in less time than it would take a non quantum computer to calculate it correctly the first time. As the problem space scales up, there should be a divergence point where this would occur.
  Alternatively, for one way functions you could do as numerous others have suggested in this thread: get a factored answer and run it forward to see if the answer is correct. If it is, stop, if not, refactor. This could also be faster than a single run with a non quantum computer and may be faster than what I've proposed above.
107. Re:Can someone explain... by Crudely_Indecent · 2012-08-27 07:46 · Score: 1
  
  I saw it.
  
  --
  
  "Lame" - Galaxar
108. Re:Can someone explain... by Anonymous Coward · 2012-08-27 08:22 · Score: 0
  
  Appropriate qotd on Slashdot today:
  
  Mathematics deals exclusively with the relations of concepts to each other without consideration of their relation to experience. -- Albert Einstein
109. Re:Can someone explain... by V!NCENT · 2012-08-27 09:41 · Score: 1
  
  Now this, I like :)
  
  --
  Here be signatures
110. Re:Can someone explain... by Anonymous Coward · 2012-08-27 10:28 · Score: 0
  
  A regular computer can do it in log2(N) operations or less. Most people do it in less.
  Doubtful. You're applying a different standard to the computer for what constitutes an "operation".
  Consider that for the human, every page which they see the name in the corner counts as one "operation". If you flip through a few dozen pages, watching the first letter of the names, you've burned a whole lot of "operations". If you know you're close so you start leafing through the pages, you burn a lot more. And then when you've arrived on the correct page, every name you look at counts as an "operation" - and again, the typical behavior is going to be a binary tree search to get close, but scanning down once you're close - you've used several dozen operations when a computer could have done it with far fewer because it searches much more efficiently.
111. Re:Can someone explain... by Anonymous Coward · 2012-08-27 15:32 · Score: 0
  
  (it is no worthy computer game if the other player is invincible and scores perfectly always; but you would not use this technology for !GAMES!...)
112. Re:Can someone explain... by Wraithlyn · 2012-08-29 11:13 · Score: 1
  
  Are you seriously claiming you have better insight into how this specific approach will scale, compared to the actual scientists working on it?
  
  --
  "Mind, as manifested by the capacity to make choices, is to some extent present in every electron." -Freeman Dyson
113. Re:Can someone explain... by __aaltlg1547 · 2012-08-29 15:35 · Score: 1
  
  No, and they wrote about it in the summary article, "Improvements in the superconducting qubit coherence times and more complex circuits should provide the resources necessary to factor larger composite numbers and run more intricate quantum algorithms." In other words, they don't believe their hardware works well enough to do anything much more complex than factoring small composite numbers, a conclusion that I concur with based on their not being much closer to 50% predicted by the Shor algorithm.
  There's a tendency in science writing to make inflated claims about how important results are. This is important in that it shows that they have a quantum processor with elements that fundamentally work and carry out the intended process. But it's also very limited in that they only factored one number without giving a rationale for why they didn't extend this to more interesting problem sets. This might be due to a limitation of the hardware that makes it hard to reprogram it to carry out a different operation, or it may be that they just decided to publish the first time they had any confidence at all that they had a result that wasn't random. The full article doesn't state why they only factored 15 nor does it state anything about limitations on the scalability.
114. Re:Can someone explain... by jacobb · 2012-08-29 23:21 · Score: 1
  
  If you know you get the right answer exactly 10% of the time, and you had fewer than 10 possible outcomes, you'd bet on every (or any) outcome except the one predicted.
If I calculate 135257x15643 in my head by G3ckoG33k · 2012-08-26 03:57 · Score: 1

If I calculate 135257x15643 in my head, the correct answer is found pretty close to zero in five attempts. Is that good?
Size, not reliability by TheRaven64 · 2012-08-26 03:57 · Score: 4, Interesting

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.

--
I am TheRaven on Soylent News
1. Re:Size, not reliability by taktoa · 2012-08-26 03:59 · Score: 1
  
  Beat me to it.
2. Re:Size, not reliability by Yarhj · 2012-08-26 04:06 · Score: 1
  
  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.
3. Re:Size, not reliability by Anonymous Coward · 2012-08-26 05:01 · Score: 0
  
  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? by taktoa · 2012-08-26 03:57 · Score: 0

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? by Anonymous Coward · 2012-08-26 03:59 · Score: 0

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.
1. Re:Not of practical use? by TheRaven64 · 2012-08-26 04:32 · Score: 1
  
  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.
  
  --
  I am TheRaven on Soylent News
2. Re:Not of practical use? by petermgreen · 2012-08-26 04:36 · Score: 1
  
  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.
  
  --
  note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
3. Re:Not of practical use? by fuzzyfuzzyfungus · 2012-08-26 04:38 · Score: 2
  
  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.
4. Re:Not of practical use? by Anonymous Coward · 2012-08-26 04:41 · Score: 0
  
  The main use surely is breaking today's assymetric cryptosystems.
5. Re:Not of practical use? by smellotron · 2012-08-26 04:44 · Score: 1
  
  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.
6. Re:Not of practical use? by CastrTroy · 2012-08-26 05:40 · Score: 1
  
  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"
  
  --
  
  Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
7. Re:Not of practical use? by smellotron · 2012-08-26 06:25 · Score: 2
  
  We make compromises for accuracy all the time in computation. The use of floating point numbers is one such case.
  
  I agree. The AC's comment which is blatantly wrong is more specific:
  
  part of optimization is refactoring math equations in the code for shortest execution period.
  
  High-performance numerical algorithms are written with the expectation of a well-behaved compiler which will not attempt to refactor mathematical expressions on the basis that it may change the numerical error. The mathematicians who write these algorithms understand how the error accumulates, so their order-of-operations will be tailored accordingly.
Not of practical use? by roboticon · 2012-08-26 04:00 · Score: 0

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.
One word: by drainbramage · 2012-08-26 04:02 · Score: 4, Funny

Close enough for government work.

--
No brain, no pain.
1. Re:One word: by Crudely_Indecent · 2012-08-26 04:05 · Score: 1
  
  I'm satisfied with that answer.
  Not really, but I did get a good chuckle...
  
  --
  
  "Lame" - Galaxar
2. Re:One word: by fuzzyfuzzyfungus · 2012-08-26 04:25 · Score: 3, Insightful
  
  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...
3. Re:One word: by fustakrakich · 2012-08-26 04:39 · Score: 1
  
  One word
  Close enough for government work.
  That's not even half right... 20% at best
  
  --
  “He’s not deformed, he’s just drunk!”
4. Re:One word: by Anonymous Coward · 2012-08-26 04:42 · Score: 0
  
  I havent thought of my old ti calc in a long time. Those were good times.
5. Re:One word: by __aaltlg1547 · 2012-08-26 05:40 · Score: 4, Funny
  
  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.
6. Re:One word: by ArsonSmith · 2012-08-27 01:46 · Score: 1
  
  but tepid accuracy isn't a big deal if ...
  or looking for terrorists.
  
  --
  Paying taxes to buy civilization is like paying a hooker to buy love.
Why isn't 48% good enough? by wonkey_monkey · 2012-08-26 04:03 · Score: 1

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

--
systemd is Roko's Basilisk.
1. Re:Why isn't 48% good enough? by LateArthurDent · 2012-08-26 04:09 · Score: 2
  
  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.
2. Re:Why isn't 48% good enough? by Sancho · 2012-08-26 04:29 · Score: 2
  
  Then the summary was worded terribly.
3. Re:Why isn't 48% good enough? by paleo2002 · 2012-08-26 04:59 · Score: 2
  
  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.
4. Re:Why isn't 48% good enough? by LateArthurDent · 2012-08-26 05:06 · Score: 1
  
  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.
5. Re:Why isn't 48% good enough? by Anonymous Coward · 2012-08-26 05:09 · Score: 0
  
  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.
6. Re:Why isn't 48% good enough? by CastrTroy · 2012-08-26 05:35 · Score: 1
  
  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.
  
  --
  
  Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
7. Re:Why isn't 48% good enough? by Anonymous Coward · 2012-08-26 05:46 · Score: 0
  
  The parent has an important point though. The scientists already knew that at best they could only get 50% success rate, and knew that it was still practical there, or at much smaller rates (assuming rates don't shrink too fast with increased number of qubits). One of the really meaningful results of the 48% is that it is near ideal, that losing coherence and other sources of noise only lowered the success rate by another 2%. If the chip failed to even perform the quantum computation most of the time, resulting in much lower success rate, it would be much more difficult to be optimistic that the computation could be done on a larger system with more qubits, each with similar sources of noise issues.
8. Re:Why isn't 48% good enough? by wonkey_monkey · 2012-08-26 06:44 · Score: 1
  
  Ah. I should've taken that as read, really.
  
  --
  systemd is Roko's Basilisk.
Well heck, Intel might buy it. by Anonymous Coward · 2012-08-26 04:04 · Score: 5, Funny

Historically, they're a bit more tolerant about that math thing.
1. Re:Well heck, Intel might buy it. by Noughmad · 2012-08-26 08:17 · Score: 1
  
  Historically, they're a bit more tolerant about that math thing.
  Yes, they do show at least a qubit of interest in this.
  
  --
  PlusFive Slashdot reader for Android. Can post comments.
Raw speed by Anonymous Coward · 2012-08-26 04:06 · Score: 0

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.
Better results than our political class by dietdew7 · 2012-08-26 04:07 · Score: 0

I would welcome a quantum computer overlord that was guaranteed to make the correct decision close to 50% of the time.
1. Re:Better results than our political class by Anonymous Coward · 2012-08-26 04:46 · Score: 0
  
  Better results than our political class (Score:0)
  Seems that someone modded you up using a quantum computer...
NSA likely already built one by IamTheRealMike · 2012-08-26 04:10 · Score: 5, Interesting

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 - 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.
1. Re:NSA likely already built one by Sancho · 2012-08-26 04:34 · Score: 4, Insightful
  
  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.
2. Re:NSA likely already built one by fustakrakich · 2012-08-26 04:36 · Score: 1
  
  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
  
  --
  “He’s not deformed, he’s just drunk!”
3. Re:NSA likely already built one by sco08y · 2012-08-26 04:56 · Score: 1
  
  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.
4. Re:NSA likely already built one by gl4ss · 2012-08-26 05:05 · Score: 1
  
  or perhaps someone managed to sell them the idea that by using billion bucks they would then have that?
  
  --
  world was created 5 seconds before this post as it is.
5. Re:NSA likely already built one by Kynde · 2012-08-26 05:17 · Score: 1
  
  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.
  
  --
  1 Earth is warming, 2 It's us, 3 it's royally bad, 4 we need to take action NOW
6. Re:NSA likely already built one by fustakrakich · 2012-08-26 05:30 · Score: 1
  
  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.
  
  --
  “He’s not deformed, he’s just drunk!”
7. Re:NSA likely already built one by Nimey · 2012-08-26 05:59 · Score: 2
  
  Nah, they just have to act "correctly" on the intel without it being statistically obvious.
  
  --
  Hail Eris, full of mischief...
  
  E pluribus sanguinem
8. Re:NSA likely already built one by equex · 2012-08-26 06:14 · Score: 1
  
  Also called 'don't worry, just a routine check'.
  
  --
  Can I light a sig ?
9. Re:NSA likely already built one by IamTheRealMike · 2012-08-26 06:57 · Score: 1
  
  Email mostly transits the backbone unencrypted, so no crypto breakthroughs are necessary to do that. All the evidence points towards huge data collection and mining operations by the NSA that are only getting bigger, so I'm pretty sure that yes, the NSA does "read" my mail (in the sense that it is probably run against a large list of regular expressions or something).
10. Re:NSA likely already built one by Anonymous Coward · 2012-08-26 09:14 · Score: 0
  
  i love conspiracy wackos. while you're here, answer me a quick question; why is it that you people don't shower?
11. Re:NSA likely already built one by ffflala · 2012-08-26 11:23 · Score: 2
  
  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.
  That's not much comfort, because there's a subtle distinction you blur. After cracking ENIGMA, they were aware of much more than they acted upon, in order to keep the breakable communication flowing. It doesn't mean they decided not to crack as much enemy communication as possible. Similarly, it doesn't mean they won't actually monitor "classical organized crime," but rather that they might not act upon the information they glean from monitoring it.
  
  The only thing that will limit their reach is capacity. They will not avoid monitoring groups for the sole reason that said group is not an action priority, nor would they avoid gleaning info for the reason that they would avoid action on such info to keep secure the depths of their capacity for comms penetration. IOW, just because they will be selective about which info they act upon doesn't mean they won't gather as much info as possible.
12. Re:NSA likely already built one by Anonymous Coward · 2012-08-26 15:22 · Score: 0
  
  All the smart people agree with this, of course. But as soon as someone that works for law enforcement gets ahold of it, they'll practically trip over themselves to decode some stoner's secret communications and bust them for a dime bag.
13. Re:NSA likely already built one by moderators_are_w*nke · 2012-08-26 23:09 · Score: 1
  
  A one time pad is provably unbreakable if used correctly
  
  --
  "XML is like violence. If it doesn't solve your problem, use more." - Anonymous Coward
14. Re:NSA likely already built one by Maximum+Prophet · 2012-08-27 01:13 · Score: 1
  Yes, and the Germans, Soviets, and Americans have all been caught re-using their pads.
  
  Some famous last words in the crypto business: "Everyone knows OTP is unbreakable, so no-one would ever try." "It's been over a year since I last used this pad, they couldn't possibly have kept the data that long."
  
  It's time for some new entrepreneur to work out the details of this business model:
  
  Generated tons of random data.
  
  Distribute DVDs of data to people.
  
  On request, some of your data will be transmitted securely to designated financial organizations.
  
  For the next year or so, all your important communication with those banks will be secure.
  
  Problem is, all the communication channels can be made absolutely secure, but the endpoints are the weak link. If the customer's PC is infected, all the encryption in the world won't help.
  --
  All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
15. Re:NSA likely already built one by TheSync · 2012-08-27 04:29 · Score: 1
  
  It seems that quantum computing has consistently been viewed as harder than it really is
  Quantum computing with a few qubits is easy. Quantum computing with enough qubits for actual useful problems (i.e. thousands of qubits) and maintaining coherence is really unclear. The scaling issue is the problem.
  That said, the UCSB group seems to be on to something!
16. Re:NSA likely already built one by robsku · 2012-08-29 18:03 · Score: 1
  
  Some famous last words in the crypto business: "Everyone knows OTP is unbreakable, so no-one would ever try." "It's been over a year since I last used this pad, they couldn't possibly have kept the data that long."
  Why would anyone keep a used one time pad for over a year!?
  Anyway, my bank uses OTP - I'm always baffled when I hear about American banks where you have just login+password - and the only thing the used pad is good for is fixing hash+weed/tobacco on it.
  
  --
  In capitalist USA corporations control the government.
17. Re:NSA likely already built one by Maximum+Prophet · 2012-08-30 07:26 · Score: 1
  
  I presume that your bank uses a "One Time Password", which is good, but not proveably unbreakable.
  
  I was refering to "One Time Pad", where the key length == text length. Getting the new pads to agents in the field is difficult. Back in the day, they really did use pads of paper covered with random letters + some sort of synchronization protocol. You were suppose to destroy each sheet of paper after using it, but sometimes that wasn't done.
  
  But you're right, just using login+password is almost as bad as using a Social Security Number to identify someone.
  
  --
  All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
even 1% of the time is great by Anonymous Coward · 2012-08-26 04:19 · Score: 1

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.
50% of the truth by OzPeter · 2012-08-26 04:26 · Score: 1, Interesting

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???!?!?

--
I am Slashdot. Are you Slashdot as well?
1. Re:50% of the truth by Anonymous Coward · 2012-08-26 05:21 · Score: 1
  
  No.
2. Re:50% of the truth by Anonymous Coward · 2012-08-26 05:32 · Score: 0
  
  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? by StripedCow · 2012-08-26 04:31 · Score: 1

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

--
If Pandora's box is destined to be opened, *I* want to be the one to open it.
1. Re:Huh? by cowboy76Spain · 2012-08-26 04:39 · Score: 1
  
  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?"
  
  --
  Why can't /. have a rich-text editor? Editing your own HTML is so XXth century.
2. Re:Huh? by StripedCow · 2012-08-26 12:16 · Score: 1
  
  If religions say that life is eternal, why are they so worried about what you do in your first century?
  Because if they don't, meta-God will call them bad religions and send them to religion-hell?
  Or, from an evolutionary perspective, if they don't, then these religions are not intimidating enough to keep their followers, and the religions will just fade away by natural selection?
  Since relgion and evolution don't mix well, I'd say it is the first option.
  
  --
  If Pandora's box is destined to be opened, *I* want to be the one to open it.
but not of practical use by fustakrakich · 2012-08-26 04:31 · Score: 1

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

--
“He’s not deformed, he’s just drunk!”
The most important part is knowing the question. by The+Living+Fractal · 2012-08-26 05:14 · Score: 1

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.

--
I do not respond to cowards. Especially anonymous ones.
MUST BE A MADE IN USA VERSION !! by Anonymous Coward · 2012-08-26 05:15 · Score: 0

Cuz like dude, that's not half bad !!
Oh, wait, it is !!
Better accuracy than a Pentium by turkeyfeathers · 2012-08-26 05:39 · Score: 1

IIRC, the Pentium gave correct answers 0% of the time.
what a waste of time... by Anonymous Coward · 2012-08-26 05:42 · Score: 0

the answer was 42, not 15 !
Like a broken clock... by Anonymous Coward · 2012-08-26 05:43 · Score: 0

It's wrong more often than it's right. I have an algorithm to factor 15, also. It goes like this.
0. Is the number to be factored, n, a positive base-10 integer? If yes, proceed. If not, stop, this algorithm cannot be used.
1. What is the least perfect square that is LARGER than n? What is the square root of that number?
Only prime numbers need to be tested, and only the primes, p, from 2 to the largest prime number less than or equal to the square root found in step 1.
2. Using the integer "INT" function, (however it's usually defined,) in this case it's a function that returns only the integer portion of a positive decimal number, or 0 if the number is between 1 and 0, and division (/, a function that for any three real A, B, and C (such that C is not 0,) returns the ratio of A/C=B, provided A=B*C) functions, determine iteratively if the integer of the number to be factored divided by each successive prime number is equal to the number to be factored divided by each successive prime number. In pseudo-computer speak, does INT (n/p) = n/p? If yes, then the number n can be divided by p.
4. Note each prime, p, that the number n can be divided by evenly, (each p for which INT (n/p) = n/p). If n is the product exclusively of some one or more iterations of p, then those primes are the factors of n. If n divided by some primes result in a duplicate prime, (as 4 does, for instance) or some other factor that is not prime, then call that non-prime n2, etc., and treat it the same way, until no non-primes remain. Then the collection of all the primes for n, n2, n3, n4, etc. are the factorization of n, which takes care of numbers such as 64, for instance, which will end up being 2*32, while 32=2*16, and 16=2*8, 8=2*4, and finally 4=2*2. So the factorization of 64 using this process is revealed to be 2(2(2(2(2(2))))) = 2^6. Another example, 100, would yield 2(50) = 2(5)(10) = 2*2*5*5.
This works 100% of the time, provided the numbers are as specified. If you feed 1 into this algorithm as a number, the next larger perfect square is 4, the square root of it is 2. INT (1/2) is NOT equal to (1/2) as 0 != 0.5, and running out of primes, the result is that the number (1) is not factorable. Some might argue that it's factorization is 1*1, but that's useless and meaningless, since you could argue that there are more factors, such as -1 and -1, -2 and -0.5, etc., but we won't worry about that. For numbers 2 and larger, you get RESULTS. 2 gives back a factorization of "2". 3 gives back 3, 4 gives back 2*2, 5 gives back 5... in fact, any valid input that is just spat back out as output, can be interpreted as an indication that that number is itself a prime. 6, on the contrary, gives back 2 and 3.
I just looked up Shor's algorithm, and General number field sieve... and realized that with regard to what I just wrote... nevermind. I decided to post it anyway, in the hopes that it's complete non-applicability to what the article is talking about, will make SOMEBODY laugh... yeah, when they start talking about N log log n or whatever, my eyes start to glaze over. I know what a log is, and even know arbitrary-base log conversion (or I used to) but it still seems like some form of low-voltage magic to me...
I liken it to how most people completely fail to understand how an airplane flies... 97+% of the population still believes the popular misconception that it's speed of air differing over and under the wing causing PRESSURE differences that result in lift... whereas it's more accurate to discuss the effect of the differing airspeeds resulting in the formation of a vortex behind the trailing surface of the wing... but I digress.
The algorithm is apparently not as simple as this, it's more on the level of the mechanics of performing these mathematical functions. I was focusing on the program, they're talking about the machine that would run such a program. It'd be like someone saying "you know how hard it is to program a computer from nothing to how to draw windows on the screen?" and me replying "sure, you just draw a box..." ignoring the whole - having to interface with the video hardware... thing.
48% right = 52% wrong = *worse* than random chance by Anonymous Coward · 2012-08-26 05:54 · Score: 0

I'll prefer to use this noise source here to predict if 15 = 3*5, thank you very much. ;)
After all they have proven it to be more likely to be right than what they did.
This has to be a huge trolling. All I can do, is facepalm. And facepalm even more at /. being full of retards who don't realize it, or think it can't possibly be, these days.
Accountants Rejoice! by Joviex · 2012-08-26 06:08 · Score: 1

Great, now some financier is going to get the brilliant idea to start using this to calculate my paycheck each week.
I'm sorry, that's a crappy example. by way2trivial · 2012-08-26 06:11 · Score: 2

because-- we haven't 'gotten there' with the higgs yet-- still may NEVER..

--
every day http://en.wikipedia.org/wiki/Special:Random
1. Re:I'm sorry, that's a crappy example. by neokushan · 2012-08-26 06:17 · Score: 2
  
  Er yes we have? Where have you been for the last month?
  
  --
  +1 IDisagreeSoHeMustBeATrollOrAnAstroturferOrAShill
2. Re:I'm sorry, that's a crappy example. by killkillkill · 2012-08-26 06:41 · Score: 1
  
  Probably the same place as me, as I have only seen reports of a discovery of a new boson that is likely to be the Higgs but not fully confirmed yet.
  (Okay... I have seen reports that it has been definitively discovered, but those reports also said we would soon have replicators, transporters and time machines because of the discovery)
3. Re:I'm sorry, that's a crappy example. by mcswell · 2012-08-26 07:35 · Score: 2
  
  Yes, I'm reporting back from next year: we have time machines. (No replicators or transporters yet.)
4. Re:I'm sorry, that's a crappy example. by Noughmad · 2012-08-26 08:05 · Score: 1
  
  (No replicators or transporters yet.)
  Do you mean ST or SG replicators?
  
  --
  PlusFive Slashdot reader for Android. Can post comments.
5. Re:I'm sorry, that's a crappy example. by mcswell · 2012-08-26 08:11 · Score: 1
  
  Ba'al hasn't told us yet.
What comes after? by Mr_Blank · 2012-08-26 06:25 · Score: 1

If quantum computing is the end of encryption as we know it, then soon the internet as we know it will end too.
How will electronic communication be secured after quantum computing?
Someone call Al Gore: We need a new internet.
1. Re:What comes after? by ark1 · 2012-08-26 06:43 · Score: 1
  
  Quantum computing threatens only public key crypto, secret key crypto is not affected. So how do you solve the key distribution problem if traditional algorithms are insecure? Either you use quantum key distribution or you base your public key crypto on a mathematical problem not affected by quantum computing.
  
  In any case fundamentals of cryptography should be the least of your concerns as vulnerabilities are usually found in the implementation and usage.
solid state quantum computer, since when? by fritsd · 2012-08-26 06:26 · Score: 1

I found it interesting that the summary mentioned a solid-state quantum computer, since I (apparently incorrectly) believed that it consisted of teasing a cloud of Rubidium atoms to standstill in a near-vacuum and then shining lasers at them.
Solid-state sounds a lot cheaper.

--
To be, or not to be: isn't that quite logical, Slashdot Beta?
Oh no! That's my public and private keys! by marciot · 2012-08-26 06:28 · Score: 1

Crap! I knew it was only a matter of time before these new fanged quantum computers cracked my 4 bit RSA encryption key!
Bourbon by ichthus · 2012-08-26 06:45 · Score: 2

"48% of the time, *finger snap* it works 100% of the time."

--
sig: sauer
What about the other 52% of the time? by Anonymous Coward · 2012-08-26 07:45 · Score: 1

Am I the only one interested in what the quantum computation returned the OTHER 52% of the time?
1. Re:What about the other 52% of the time? by Anonymous Coward · 2012-08-26 22:26 · Score: 0
  
  Am I the only one interested in what the quantum computation returned the OTHER 52% of the time?
  6 * 9, but when it multiplies them it doesn't get 15, it gets 42. So no use for anything.
New Math by PPH · 2012-08-26 07:55 · Score: 1

Its sufficient to understand what you are doing. Never mind getting the right answer.

--
Have gnu, will travel.
ROFLMAO! by Anonymous Coward · 2012-08-26 07:59 · Score: 0

And just how often is 2+2 = 4... :rolleyes:
not perfect but by Anonymous Coward · 2012-08-26 08:07 · Score: 1

still better than most humans
"Headline" is 100% wrong! by Anonymous Coward · 2012-08-26 08:43 · Score: 0

TFH says: "Solid State Quantum Computer Finds 15=3x5 ..."
That is 100% Wrong! Read TFA or your own effing summary, FFS!
TFH should say something like: "Quantum Computer Finds 15!=3x5 ..."
What kind of a dimwit wrote that so-called headline? There's an ever-so-slight difference between "15!=" and "15=".
Great! Congrats! by drolli · 2012-08-26 08:58 · Score: 4, Interesting

Disclaimer: I am a former researcher in the field, left to some other job.
What you can see at UCSB is what happens when a team of scientists which ae skilled in engineering, working as a team, and collaborating with everybody happens to have the right guy as the leader (with the right policy about co-authors on publications).
Everybody whom i met from this team was open, honest, and friendly; they have worked hard and long on it and they accumulated some of the best people.
They deserve the success they have now! I think there may be a small break now in their publications, since i have the ffeling they now may work on overcoming the next big roadblocks (but now they they have all the backing they could need for it).
I also have to state it will be a long long way to the first QC. While i believe that every step like this will be more than just replicated at the NSA, i believ that they wont be more than 10 years ahead, and i estimate 20y-30y until qc works better than classical qc (although I also hope and believe that breaktroughs are possible).
Would you like to win the lottery 50% of the time? by Anonymous Coward · 2012-08-26 10:21 · Score: 0

How about 1% of the time?
Or 0.1% of the time?
Or 0.0001% of the time? Thats $100,000 for a reasonable certainty that you win.
If I could sell a machine that predicted the lottery correctly 0.0001% of the time I would borrow a few hundred thousand dollars and never work again.
This is massive massive positive news if it scales.
Quantom computers are this century's big thing if they work.
Ob C vs C++ reference by DrYak · 2012-08-26 12:16 · Score: 1

That explains why some programmer's hate C++'s operator overloading.

--
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
1. Re:Ob C vs C++ reference by The+Evil+Atheist · 2012-08-26 21:03 · Score: 1
  
  Good thing you can't overload the apostrophe in C++
  
  --
  Those who do not learn from commit history are doomed to regress it.
Checking by DrYak · 2012-08-26 12:30 · Score: 2

Consider the "use quantum computing to get an answer, use regular computing to verify answer" post higher in this thread.
While it's computationally intensive to factor number, it's absolutely trival to check factors' prdocut against target number.
Yes, it's possible that the quantum computer will give a false positive half of the time like "13 = 3 x 5"
On the other hand, it's quite trivial to see that 3 x 5 make 15 and not 13 and thus this was a false positive.
It can be a viable pre-filtering technique. Currently, factoring large numbers is awfully resource intensive. You basically have to recursively build a table of prime numbers up to sqrt(n)
Now with a quantum computer, you might only need to do multiplications to check the things that the quantum unit is spitting, and keep doing this until you have a big enough confidence of the result.
Depending on the implementation (specially the hardware implementation of the quantum unit), you might get a sufficient enough answer in a much shorter time frame than with a classic computer (where the time frame might be more like "universe heat death")
As you said the problem currently is successfully making a quantum computing units that can work on anything bigger than a trivially small number of qubit.

--
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
small is better than zero by DrYak · 2012-08-26 12:56 · Score: 1

Good luck breaking RSA.
Yup.
for a 4096 bit key, it would give the correct numbers only a very tiny fraction of the time. But that's still better than zero.
consider that to mutliply the factors to verify the answer is trivial.
if the speed of the quantum unit is high enough and it spits answers at a sufficient rate, even if it only spits the correct answer at a very low rate, by veryfying constantly the result of the quantum unit, after a while you may end up with the correct result with a sufficiently high confidence.
if the answer-spitting-rate is high enough compared to the correct-answer-rate this "after a while" might be better than the time necessary to brute-force-factorise the numbers with current technology.
Yes you can't have nice things (for free).
But quantum is the kind of weird technology which can give lots of *shitty* things (for free).
Okay, these things are *shitty* and not *nice*, but you still get them for free.
And you can still try putting them in a big pile, light them on fire and use the heat to cook a nice dinner. And a dinner is *nice*.
maybe the production rate is forced to scale badly compared to the true-positive rate and they cancel each other exactly the same way a perpetual motion machine always ends up having an output energy of zero or worse.
but that not a reason to not even try proving *that*. we need to at least understand quantum computing well enough to be able to see if this 50% vs 48% difference will become an obstacle in the long term or not. we have to test and prove your predictions.
maybe cooking dinner over quantum virtual shit is not worth it, but at least we have to prove it.

--
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
That's not so bad by Anonymous Coward · 2012-08-26 13:04 · Score: 0

It gets 5x3 right 48% of the time, that's at least twice as often as my daughter in 3rd grade.
48% of the time is better than by Anonymous Coward · 2012-08-26 13:29 · Score: 0

the government in solving problems correctly.
PvsNP by watershape · 2012-08-26 14:36 · Score: 1

Does this have something to do with PvsNP problem? Its solution provides a perfect algorithm for facturing numbers i guess
1. Re:PvsNP by Maximum+Prophet · 2012-08-27 01:18 · Score: 1
  
  Sort of, but not really. You still can't prove P != NP or otherwise.
  
  For problems like travelling salesman, you know you can figure out the best route by trying them all (perfect induction). What a quantum computer allows you to do, is try every combination in constant time. You still have to try every combination.
  
  --
  All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
Copenhagen interpretation by detritus. · 2012-08-26 16:10 · Score: 1

The computer really didn't want to give an answer after being asked so many times, but was forced to take a side.
Computers with natural attitudes.
Just remember by Anonymous Coward · 2012-08-26 16:37 · Score: 0

48% of the time, it works every time.
Yeah, Yeah... by Anonymous Coward · 2012-08-27 04:28 · Score: 0

This is a nice achievement, but I'm still wondering....WHEN WILL IT RUN DOOM???
Re:Would you like to win the lottery 50% of the ti by petteyg359 · 2012-08-27 04:32 · Score: 1

There are only 379,501,200 (54!5) combinations in Texas. With a few hundred thousand dollars spent on unique combinations, your probability of winning is rather higher than 0.0001%. Your problem there is going to be finding the people and time to get all those dots filled in.
You can try Quantum Computing by TheSync · 2012-08-27 04:45 · Score: 1

If you want to try playing with a simulation of Quantum Computing, you can check out my tutorial that shows you how to do Gover's Algorithm using QCF on Octace.
Getting better, but PKI seems safe for a while yet by Anonymous Coward · 2012-08-27 07:12 · Score: 0

Following the Wiki links for Shor and reversible logic,
It looks like the academic definition for reversible logic is not what I would have expected.
They cite an XOR gate as non-reversible because if you know the output, you don't know the inputs.
This seems the wrong answer because in this example, the XOR doesn't loose information, so reversible feels more useful.
Perhaps a better def for reversible logic would be if you are told the value for all but one of the nodes then you know the value at the last node.
In other words, one shouldn't care/know/ if the nodes are inputs or outputs.
I think the idea of reversible logic ought to be that there are no inputs or outputs, just connections and logic boxes.
Much much faster, when it's right by billstewart · 2012-08-27 07:43 · Score: 1

Getting the right answer quickly 50% of the time (and being able to quickly verify that it's correct) is much faster than getting the right answer 100% of the time if the calculations take longer than you're willing to wait (e.g. crypto problems where you can pick a key size for which cracking requires a computer the size of the planet to run for billions of years.)
And knowing that somebody else can guess the right answer 50% of the time, instead of having to wait arbitrarily long times, affects your choice of algorithms. This is why cryptographers are really concerned about quantum computers - they're the only significant threat to modern cryptography (except for special cases like differential power analysis when the attacker has physical access to your computer, or sloppiness like bad random number generators or protocols that leak information.) So while factoring "15" is obviously not a hard problem, if the methods used to do it can be extended to crack longer keys, and don't hit some kind of Heisenberg limit (Planck's constant is about 150 bits), then it's interesting.

--

Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Idiocracy by Anonymous Coward · 2012-08-27 07:46 · Score: 0

You know... people stupidity is being limited by computer's accurate answers. This situation can no longer continue. Free the human stupidity!!!