11
votes
$\begingroup$

[Note that this was originally asked on April 1, 2024, also known as April Fool's day in many Western nations]

I'm hearing some rumors that a combination of neutral atoms (Lukin's group?), in conjunction with some of the key players in superconducting (Google, IBM, maybe others?) and ions (IonQ, Quantinuum? Others?) and maybe photonics and even NV-centers and Intel? have been teaming together to optimize their processors with the stated goals of being able to factor RSA-2048. When they originally formed their consortium a year ago, they thought they could use naive Shor to factor RSA-2048 within five or so years; but with Regev's recent breakthrough they rushed to get it done, parallelizing the computation across multiple processing cores.

Late last night, at around 1:00am Eastern (or so I heard) they were able to crack it - putting all the pieces of the puzzle together. Now, they are being understandably very cautious about announcing precisely the factors, as they know that such a release will send shockwaves through the entire world economy (in conjunction with the obvious tranche of Nobel prizes for all).

So, they are working carefully with the NSA, the CIA, and other three-letter acronyms within the US (and abroad?) to time the announcement and let the market adjust before the shock. Researchers have been referring to the coming Q-day for a while now.

It's really impressive that this consortium managed to work in secret for as long as they did. It's also great that the consortium apparently included pretty much every player involved - I'm hearing no one qubit worked better than others, and it really was a team effort.

But even still, does anyone have any more information that they can share? Of course the proof is in the pudding, and we can wait for the factors to be posted (maybe anonymously, maybe on the blockchain...) but any details as to the processors and how they operated would be much appreciated.


What's really I guess just a quirk of history is that this comes thirty years to the day when the first quantum-parallel computer capable of such factoring was announced on Usenet, although we know now that the team that was driving that research never was able to replicate their results.

$\endgroup$
9
  • 1
    $\begingroup$ I'm not an algorithm's expert but can you really efficiently parallelize this computation? Having two $N$ qubits quantum computers ($2N$ qubits in total) is not as powerful as a single $2N$ qubit computer. So apart if there are algorithm breakthroughs, or they have much more logical qubits that I'm aware of, I'm quite skeptical about this. $\endgroup$ Apr 1 at 17:42
  • 2
    $\begingroup$ Thanks @MarcoFellous-Asiani. Maybe you're right. My sources haven't had a good track record; just this time last year they also had some foolishness that they were passing on. $\endgroup$ Apr 1 at 17:51
  • 1
    $\begingroup$ 👀 these are some very juicy rumours you have heard! $\endgroup$
    – FDGod
    Apr 1 at 18:33
  • 3
    $\begingroup$ @MartinVesely whaaaat? Huh? Me, be a victim of an April Fools Day Joke? And, to turn around and post it here on the austere and serious QCSE? $\endgroup$ Apr 1 at 18:59
  • 5
    $\begingroup$ No comment.::::: $\endgroup$ Apr 1 at 21:30

1 Answer 1

8
votes
$\begingroup$

It is likely an April fools joke

Factoring RSA-2048 will require billions of qubits, or thousands of very "clean" qubits in a quantum computer that operates so well that it doesn't need error correction.

Let's go through the claims one by one

"I'm hearing some rumors that a combination of neutral atoms (Lukin's group?), in conjunction with some of the key players in superconducting (Google, IBM, maybe others?) and ions (IonQ, Quantinuum? Others?) and maybe optical? have been teaming together to optimize their processors with the stated goals of being able to factor RSA-2048."

Lukin's group is one of the best in the world, but neutral atoms quantum computers are unlikely even to be able to factor the number 21 (which would be the equivalent of RSA-5, rather than RSA-2048), otherwise there would be a good paper about that accomplishment somewhere. In this answer you can see that factoring the number 21 with Shor's algorithm has remained elusive for long enough that accomplishing that would be worthy of a good paper (the one paper that I mentioned in that answer, "cheated" when "factoring" 21 and this is explained in the paper called "Pretending to factor numbers on quantum computers"). Whatever I said about neutral atoms, also applies to ions and optical quantum computers, so IonQ and Quantinuum and optical quantum computers are unlikely to have accomplished much in this area either.

Google and IBM have accomplished more with superconducting qubits than anyone has with neutral atoms, but none of them have the thousands of qubits in an "idealized" quantum computer, which would be required to factor RSA-2048, let alone the billions of qubits in a more "realistic" quantum computer, which would be required to factor RSA-2048. Again, what's the largest number that has been factored by an IBM or Google quantum computer? It is nowhere near RSA-2048. If they could factor a RSA-100 (which was factored by Lenstra in the early 1990s), they would have bragged even more than they did when they tried to make everyone think that they accomplished "quantum supremacy". I would be impressed if they could even factor 56153 without cheating.

"Late last night, at around 1:00am Eastern (or so I heard) they were able to crack it - putting all the pieces of the puzzle together. Now, they are being understandably very cautious about announcing precisely the factors, as they know that such a release will send shockwaves through the entire world economy (in conjunction with the obvious tranche of Nobel prizes for all)."

1am on April fools day?

The beautiful thing about factoring numbers, is that there's no "pieces of the puzzle to put together". If they really factored the number, then multiplying the factors of RSA-2048 together to verify that they are the correct factors, will take seconds on a classical CPU, and it is not rocket science: it is integer multiplication. If they still don't have the factors because they are "putting the pieces together" then they haven't factored anything, and they are in no position to make any claims of having done anything, no matter how famous they are (Lukin, Google, IBM, etc.). Either they have done it completely or they have a long way to go.

"So, they are working carefully with the NSA, the CIA, and other three-letter acronyms within the US (and abroad?) to time the announcement and let the market adjust before the shock."

When RSA factorization records are broken, there's no need to delay telling people the factors. When every other RSA number has been factored, it was announced on places like the CADO NFS discussion group, like here for example. The NSA, CIA, FBI, and every other "3-letter" institution in the USA had nothing to do with these announcements.

$\endgroup$
5
  • 1
    $\begingroup$ I thought the reference to the 30-years to the day Usenet posting would be the giveaway! $\endgroup$ Apr 1 at 22:51
  • 3
    $\begingroup$ Addition: by going RSA2048, the claim looses any credibility. Factoring RSA896 (resp. RS1024) by any mean would be news (resp. big news). Factoring a 300+ bit RSA number with any king of actual help from a quantum computer would be revolutionary. $\endgroup$
    – fgrieu
    Apr 2 at 8:21
  • $\begingroup$ @fgrieu interesting... $\endgroup$ Apr 2 at 15:02
  • 1
    $\begingroup$ @user1271772 a small comment, I'll let you decide, but is there another way to phrase "If they could factor a RSA-100 (which was factored by Lenstra in the early 1990s), they would have bragged even more than they did when they tried to make everyone think that they accomplished 'quantum supremacy'" that has a little less snark? Maybe "... they would most likely certainly want to loudly highlight this - likely much more so than even they did a number of years ago with respect to their then-claims about quantum supremacy"? $\endgroup$ Apr 3 at 14:18
  • $\begingroup$ @MarkSpinelli I see why you're considering that, but they did brag and exaggerate their accomplishments. In my opinion "quantum supremacy" must be in inverted commas, and there's a boatload of information about the controversy around that term. When I search "snark" on Google, I find that it refers to "indirect or sarcastic" remarks, but was I being indirect or sarcastic? When I search "brag", it says "say something in a boastful manner", which I think is an excellent characterization of what happened. I'll continue to think about this okay? There might be a better way to say what I said. $\endgroup$ Apr 3 at 14:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.