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.
It's medium.com pagefiller from a serial medium.com filler page spammer.
What's a qubit?
(Too soon?)
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.)
The problem can be solved classically using O(Choose(N,n)) bignum operations, where N is the number of bits in the larger of the two factors. In their case n=2 so we get O(N^2) bignum operations, which is polynomial, not exponential.
You're right that when more than half of the bits are different, it can become easier as the Choose function's maximum is attained at n = N/2.
n=p*q where n is the semiprime, p and q are the prime factors
floor(sqrt(n))=p --- finds the first prime factor,p
then just n/p=q to find the second. (or alternatively, p+2 )
works for the domain of all n such that |p-q|=2
There, and I didn't even need a magical computer made from a huge pile of dead cats that cost billions.
LFMAO
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
Those aren't the same question. Factoring numbers is not a magic task that Turing machines cannot do.
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.
They tried factoring 143, and ended up factoring 56153 by accident?
IQC ('Quantum Valley'), at the University of Waterloo, and the Perimenter Institute in Waterloo, Canada, have 12 qubit computers...
phys.org/pdf66322040.pdf
Mathematicians hate it!
Nowhere I can find that they mention the Chinese mathematicians' names, like they are not worth mentioning.
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 !
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."
Great comment! I'm one of the authors of the paper. While trying to factor 56153 using our Table 2, you end up with Eqs. 16-18. Solving these equations is equivalent to factoring 56153. These equations are the same equations that the Chinese group solved on a quantum computer in 2012. Hope that helps :)
Yes you're correct that any quantum algorithm can be emulated on a classical computer, just not efficiently.
Emulating a 4 qubit quantum computer on a classical computer is very easy, because the hamiltonian is a 16x16 matrix.
For a quantum computer to outperform a classical computer, you need more qubits. A classical computer cannot emulate a 512 qubit quantum computer because the hamiltonian is a (2^512 x 2^512) matrix.
Dear oldmacdonald. I admired your paper on oversimplifying quantum factoring very much, and I actually cited it in the abstract of my paper (which is the subject of this thread). Without your paper, I wouldn't have even known that all implementations of Shor's algorithm to date used prior knowledge of the factors to determine an "easy" base a.
However, your Nature paper and arXiv paper do not explain why the results in my paper are silly. 143 and 56153 were both factored with 4 proton spin qubits, without any prior knowledge of the factors. It's not clear whether or not this approach will outperform Shor's algorithm, or the GNFS for RSA-220. But it's worth a try!
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
Factoring numbers whose factors are known to differ only in two bits is efficient on a classical computer. Therefore, both the experiment and the realization that it can be used to factor a larger number are useless.
There's no speedup in using a quantum computer over a classical computer for that problem. Unrestricted factoring, on the other hand, would show such an improvement.
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.
It is a general factoring method. Equations like our Eq. 1-6 can be made for any integer factorization, in 1 second. The solution of these equations can be formulated as a minimization problem, and therefore encoded in the ground state of a hamiltonian. References [9,10] of my paper do it this way. What we do different is that we simplify the equations by using rules such as p+q = 1+2*z implies z=0. Now that we know the value of z, we can find p & q with only 2 qubits instead of 3.
You are right that whether or not we can simplify to a very small number of qubits seems to depend on the factors having some structure, or in some sense, luck. We did everything by ignoring knowledge of the factors, and we randomly found some cases that factor with very few qubits. Other factors will need more qubits, but can still use our very same method. I hope this clears it up a bit!
In 1985 I could factorize a much larger number (product of 2 primes) on an 8086/8087 Compaq PC in about 10 ms using a simple recursive use of the Sieve of Aristostenes. My biggest limitation was the size of data supported by the hardware (80 bits).
Dont worry - I dont smoke - and dont worry about this either - you could really live more safe in Berlin - than me - and dont worry either about my nick - I am really NO radical (or somehow suspicious "dschihadist" ?! ) - in case you believe in movies of TV - you may know that most of the reels in the news are repitions of the 80ies and of the 90ies ... sleep tight and well ! - by the way, I doubt that you are breast-feeded like most parliament members in UK are probably not breast-feeded ?!