Slashdot Mirror
Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
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.
But was it discovered by a suburban housewife and the authorities don't want you to know it?
Time to offend someone
Mathematicians will hate you for it!
You won't BELIEVE what factors next!
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.
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.
systemd is Roko's Basilisk.
So where is the two bit difference?
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!!!
"Transparent" is a shit show that trades on every stereotype going. A man in drag is NOT a transsexual.
If I understand correctly, the classical version of this factoring scales with 2^n where n is the number of bits different in the two binary factors. Wouldn't there be some kind of trick to handle situations where more than half the bits are different though? IIRC this still wouldn't be the best known classical algorithm, but this seems worth some thought.
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 general insights.
This is just a two bit story.
I apologize - kinda.
They found a pair of primes that differ by two bits. If you find two billion-digit primes that differ by two bits, you'll get the same system of equations. And once you find those, you can claim that a quantum computer has factored their product. Ooooh, maaaaagic. Quaaaaaantum maaaaaagic. It sounds even more magical if you say that you're solving infinitely many biprime factorizations, but I suspect that proving such a claim is at least as hard as the prime gap conjecture.
The authors then go on to say that the D-Wave machine has 512 qubits. This is true. But those qubits are nothing like fully connected, so their insinuation that arbitrary systems of 512 variables are solvable is totally ludicrous. Assuming Moore's law works out for D-Wave for a while, we might see that... but it'll be years.
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.)
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.
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?
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
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.
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...
http://arxiv.org/abs/1301.7007
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...
The probability that you get something outside the range 450-550 is almost zero so any method based on the idea that some factorizations will have a lot or few identical pairs is unusable in practice.
What's a qubit?
(Too soon?)
Mod parent funny for the Cosby connection.
They can take my LifeAlert pendant when they pry it from my cold dead fingers.
If you have to explain the joke, it's not funny.
I don't what you are smoking but you should try to stop for a while!
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.
Oh, I'm sorry sir, I thought you were referring to me, Mr. Wensleydale.
I wish I could understand your refutation of the article that I also didn't understand.
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 continual huge investment in STEM China gonna reap lots and lots of amazing pay off in coming years
That said, why is the US of A cutting off the funding for math, science and technology?
Muchas Gracias, Señor Edward Snowden !
Hilarious. Reminds me of a usenet discussion we had back in 2003, but I never thought about playing this game to claim factorization of absurdly large numbers.
OS Reviews: Free and Open Source Software
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.
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 I mean "to run Shor's algorithm on") if only you know you are in the class.
What really stimulated us to write the paper was the observation that 21 had been factored on only a qutrit. The numbers being factored were growing, but the size of the quantum computer was shrinking. Surely something fishy was going on.