Mathematical Trick Helps Smash Record For the Largest Quantum Factorization 62
KentuckyFC writes: One of the big applications for quantum computers is finding the prime factors of large numbers, a technique that can help break most modern cryptographic codes. Back in 2012, a team of Chinese physicists used a nuclear magnetic resonance quantum computer with 4 qubits to factor the number 143 (11 x 13), the largest quantum factorization ever performed. Now a pair of mathematicians say the technique used by the Chinese team is more powerful than originally thought. Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. So instead of just factoring 143, the Chinese team actually quantum factored the number 56153 (233 x 241, which differ by two bits when written in binary). That's the largest quantum factorization by some margin. The mathematicians point out that their discovery will not help code breakers since they'd need to know in advance that the factors differ by 2 bits, which seems unlikely. What's more, the technique relies on only 4 qubits and so can be easily reproduced on a classical computer.
Mathematical trick (Score:5, Funny)
Re: Mathematical trick (Score:1)
Hey try out this weird new trick that no one wants you to know about to lose weight! Cocaine!
Re: (Score:3)
Hey try out this weird new trick that no one wants you to know about to lose weight! Cocaine!
Rob Ford (former mayor of Toronto) already proved it doesn't work. He kept getting the munchies and being videoed drunk in Burger King eating and swearing at everyone.
Re: (Score:2)
No he just has enough money to afford both drugs and food. While many stimulant do have an effect on appetite, its never really been a panacea for those looking to lose weight. Much of the stereotype of emaciated drug users is a direct result of the ravages of the policy of increasing the price of drugs based on some misguided notion that if you can do anything you want in the name of helping someone who doesn't want your help, even if its not the least bit effective.
Use this weird mathematical trick! (Score:1, Funny)
Mathematicians will hate you for it!
What investment in STEM will get ya! (Score:1)
China is not well known for high tech (or high knowledge) innovations --- at least not since the invention of paper, compass and explosive, thousands of years ago --- and the fact that a bunch of Chinese researchers could come up with the idea of using a nuclear magnetic resonance quantum compute in aiding the discovery of large factorized prime numbers shows that China's huge investment in STEM is starting to pay off
And I presume (I certainly have no idea what else will come up next) that with their conti
This one weird math trick! (Score:4, Funny)
You won't BELIEVE what factors next!
Enough (Score:3, Insightful)
Re: (Score:3, Insightful)
The clickbait joke reply wasn't funny the first time it was posted. It didn't suddenly become funny after the third time, or any time thereafter.
Look at the timestamps on the posts. They were all posted close enough in time that Slashdot's new "slow to show a comment" feature hid them from the posters.
And what's worse? Making an obvious joke, or bitching about that obvious joke?
PS - take the corncob out of your ass.
Is it me (probably) or is the article a bit dumb? (Score:5, Insightful)
The work that Dattani and Bryans have done is to show that exactly the same calculation works for much bigger numbers as well.
I don't quite get how "the same algorithm works for some larger numbers of this kind" leads to "therefore the Chinese also did this calculation without realising it."
Think of that trick where you add the digits of a number, then keep adding the answer's digits until you're left with one digit. If that digit is a 9, then the original number was a 9. Neat trick, and you can use it to work out that 12393 is a multiple of 9. But that doesn't mean that you've also just calculated that 9578394 is also a multiple of 9.
And in any case, because this trick works using only 4 qubits, it can easily be reproduced on any classical computer. So it’s not so useful after all.
That's not why it's not useful - I thought any quantum algorithm could be emulated on a classical computer, just not very efficiently.
Re: (Score:2)
The authors then go on to s
Re: (Score:2)
I wish I could understand your refutation of the article that I also didn't understand.
Examples given look like 1 bit different (Score:1)
So where is the two bit difference?
Re: (Score:2)
13 in binary is "1101"
Two bits were flipped.
Likewise with 233 and 241:
233 in binary is "11101001"
241 in binary is "11110001"
Again, two bits were flipped.
That said, I am not a mathematician and haven't read the article so I don't understand how these two pairs are related.
Prior art? (Score:2)
Again, two bits were flipped.
So, cosmic rays bit-flipping are prior art of how natural processes can do the same thing. The universe really is one big computer and we're stuck in it!!!
Douglas? (Score:2)
A computer of such infinite and subtle complexity that organic life itself will form part of its operational matrix. And it shall be called... the Universe.
Re:Examples given look like 1 bit different (Score:5, Interesting)
I rather hope that it requires that the bits which flip are next to each other, because otherwise they've overlooked 16843009 = 257 * 65537, the product of the two largest known Fermat primes.
Re: (Score:1)
It's easy to come up with bigger examples, even with the flipping bits next to each other. For example
1000000021 = 0b111011100110101100101000010101
1001048597 = 0b111011101010101100101000010101
Re: (Score:2)
233 = 11101001
241 = 11110001
So worst case still classically exponential, but.. (Score:2)
Also nice to see the whys and wherefores of quantum algorithms being better understood, but can't really say I know enough so see if this gives any more
Re: (Score:1)
Is my understanding correct, that quantum computing is fast, but isn't the magic oracle to factor numbers? It neither exceeds a Turing machine while remaining finite, nor is infinite in that context?
Re: (Score:1)
In a regular factorization all bits except the 1st and the last are basically unpreditable (in the sense that they have no generic and well defined properties that could help predict their value) so the probability of the number of identical (or different) N pairs follows the same rules than flipping N coins. In practice the number will be around N/2 with a very strong probability.
For N=1000, see for instance the graph for 'output 1000d2-1000' in http://anydice.com/program/4d4... [anydice.com]
The probability that you ge
I'm surprized no one has said it. (Score:3)
I apologize - kinda.
Re: (Score:2)
What's a qubit?
(Too soon?)
Mod parent funny for the Cosby connection.
Re: (Score:2)
If you have to explain the joke, it's not funny.
Factors differ by a power of 2 in the examples (Score:1)
If we assume c can be factored as a (a+2^k) then the resulting quadratic gives a = -2^{k-1} + sqrt(2^{2k-2}+c). Thus for such numbers that allow factoring in this form, one can search for the factors in time linear in the number of bits in c. (One just needs to check for 2^{2k-2} + c being a perfect square, for the various values of k.)
... break most modern cryptographic codes? (Score:2)
This statement always shows up when discussing quantum computers. The only important 'modern cryptographic codes' dependant on factoring large primes are RSA and Diffie-Hellman.RSA has replacements waiting in the wings (notably Elliptic Curves); Diffie-Hellman might be a bit trickier to live without.But I'm not aware of any claims that the symmectric cyphers (AES, Blowfish, 3DES, etc) or the advanced hashes (SHA3? or whatever) would be vulnerable.
Re: (Score:2)
Re: (Score:2)
I think GPP was talking about the generic comments made on quantum computing rather than the particular analysis which is the main topic. Shor's algorithm does discrete log as well as factorisation.
Related paper: Oversimplifying quantum factoring (Score:2)
Here are links to my paper in Nature and to the arXiv version which explains why all such results are very silly.
http://www.nature.com/nature/j... [nature.com]
http://arxiv.org/abs/1301.7007 [arxiv.org]
Re: (Score:2)
Dear AC,
I'm glad you liked our paper and it stimulated your research. I had not actually read your paper when I posted the link to mine and I'm still thinking it over. I think you would agree that your approach is not a general factoring method, but rather depends on the factors having some structure, even if you don't need to know the factors entirely.
Re: (Score:2)
Hilarious. Reminds me of a usenet discussion [google.com] we had back in 2003, but I never thought about playing this game to claim factorization of absurdly large numbers.
Re: (Score:2)
Very interesting to see this idea has some history to it. I'm not surprised that other people thought of it too!
Like you, I had noticed that the number of qubits used (7) was smaller than the number needed to implement Shor's algorithm. I actually asked Shor about this and he said, "15 is special, because it is 4 to an integer power minus 1." I asked him what that meant and it said "it means it's divisible by 3."! This told me that there are special classes of numbers that are easy to "factor" (by which
Re: (Score:2)
IQC ('Quantum Valley'), at the University of Waterloo, and the Perimenter Institute in Waterloo, Canada, have 12 qubit computers... phys.org/pdf66322040.pdf
...or at least 12 is the peak of the p.d.f.
Re: (Score:1)
I don't what you are smoking but you should try to stop for a while!