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