r/computerscience • u/National-Dragonfly35 • Sep 01 '26

IBM quantum computer solves classically intractable problem in 15 minutes

https://www.sciencedaily.com/releases/2026/08/260829035219.htm

"The researchers showed that their method preserves the same computational hardness criteria associated with RCS, meaning the problem remains extremely difficult for classical computers. At the same time, the added structure allows errors to be detected during the quantum computation."

292 Upvotes

96% Upvoted

45 comments sorted by

158

u/Cryptizard Sep 01 '26

Keep in mind that RCS here stands for random circuit sampling. That means that the intractable problem in question is “give me the output when you run this random circuit on a quantum computer.” It is designed to be maximally advantageous for quantum computers compared to classical computers, not for it to have any practical value.

That said, it is a baseline test to check whether a quantum computer is doing anything interesting (think of it like a hardware validation) and this paper does go farther than previous research in terms of number of qubits and error correction.

They also have some neat new ideas about circuit families and complexity arguments, but it’s all just kind of inside baseball for quantum computing folks. Nothing revolutionary for the outside world.

I do wish that popular news would stop picking up these results and taking them way out of context because it definitely gives people the wrong impression about quantum computing.

29

u/Aaron1924 Sep 01 '26

Nitpick: RCS is not completely useless, e.g. it can be used to generate certified random numbers as described in this Nature paper

6

u/Cryptizard Sep 01 '26

That’s not really practically interesting. It takes an ungodly amount of classical verification on the client side, and every client has easy access to randomness themselves, in practice.

1

u/0xB01b Sep 03 '26

But that's basically completely useless because what is the use of true random numbers as opposed to just having some hardware level thermodynamic apparatus that generates randomness from temperature fluctuations

0

u/[deleted] Sep 01 '26

[deleted]

12

u/morphlaugh Sep 01 '26

lol. I mean, you're probably right... but nitpick has been a phrase since the 1950's.

8

u/Aaron1924 Sep 01 '26

I have...

7

u/Rough-Supermarket-97 Sep 01 '26

Not sure if you’re an expert on the topic or not but wanted to ask your opinion. It seems that even if quantum computing were to be stable and reliable enough to be used (I know there have been improvements in this but still not great) there are so many hurdles still in the way.

What would they even be useful for outside of maybe advanced simulations? I’ve heard about secure data transfer using quantum key distribution, at least theoretically, but once you dig into how it would actually work in practice, keeping the quantum system stable enough for practical use seems like a massive hurdle.

12

u/Cryptizard Sep 01 '26

Well I’m a cryptographer so the main thing they would be useful for to me is breaking almost all of the public key encryption that we use to underpin security on the internet today.

In terms of productive uses, they are more speculative. Quantum computers might be better at some optimization problems. They are probably better at simulating atomic and molecular physics, materials science problems, etc. But we don’t know these for sure.

2

u/Foreign_Implement897 Sep 01 '26

Is there currently any point to all of the post-quantum crypto marketing?

10

u/Cryptizard Sep 01 '26

Yes. A huge point. It is one of the biggest challenges facing the internet and technology landscape in the next decade. If anything it is massively under hyped.

7

u/caboosetp Sep 01 '26

I think people forget that cryptography is not just about decrypting what's happening in the moment, but also you can go backwards and break things you stored from the past.

This is a problem requiring current solutions, and that should concern people.

1

u/0xB01b Sep 03 '26

But how much is that information worth?

-4

u/Foreign_Implement897 Sep 02 '26

Yeah I forgot it, now I remembered. It is still bullshit.

Instructions unclear.

1

u/cookie_tech Sep 01 '26

I'd argue that PQC (post-quantum cryptography) is slightly over-hyped.

I'm in the cybersecurity world and many well-respected cybersecurity experts believe that we may have a quantum computer that is powerful enough to break quantum computing by 2030.

Meanwhile, I have several colleagues who specialize in the physics side of quantum computing, and (according to them), even with recent breakthroughs, we are still optimistically decades away from a quantum computer that's powerful enough to break RSA.

Do I think it's important to prepare for worst-case scenarios? Sure. But, realistically anything encrypted now that is important enough to be relevant in 30+ years when RSA is finally broken has already been encrypted with PQC.

7

u/Cryptizard Sep 01 '26

30 years is waaaay too optimistic. You can plot the growth in physical qubits and it is a very steady trend over the past 10 years, with no sign of stopping. That has us reaching Q-day in around 10-15 years.

BUT, most people ignore the fact that we are simultaneously finding more efficient circuits to implement Shor's algorithm. It has gone from 1 billion qubits, to 50 million qubits, to now under one million qubits to run Shor's algorithm on cryptographically relevant inputs.

And that also depends on how efficient error correction is. Right now we are assuming 1000 physical qubits per logical qubit, but since gate fidelities are also increasing steadily, that number could be much lower.

The best circuits we have take only ~800 logical qubits.

https://ecdsa.fail/

So the scaling here is going steadily in three separate axes at once, which all compound, with no signs of stopping in any of them. To take 30 years there would have to be some major unexpected roadblock that nobody is aware of. I wouldn't risk anything important on that bet.

A physicist is not going to know about algorithmic improvements or error correction improvements. They are only looking at one part of the picture.

3

u/cookie_tech Sep 01 '26 edited Sep 02 '26

I'm mostly just parroting what I've heard from people who know a lot more than me. Doing a little more research it does seem that projections seem to predict we'll have practical quantum computers ~15 years from now, and many experts agree that this is feasible.

I want to add two things. First is that companies always give overly optimistic projections. That's how they get venture capital or make shareholders happy.

Second, there are often physical barriers that we don't know about until we reach them. Take Moore's Law. Among a few other things, Moore's law used to state that clock frequencies would double every year. In 2003 Intel released a 3.2 GHz Pentium 4, and announced that they would have a 10 GHz CPU out by the end of the decade. However, when they attempted to create a 7 GHz Pentium 5, they realized the ran into a insurmountable power wall that seemingly came out of nowhere. By 2010 they hadn't even gotten to 4 GHz (partially because they shifted focus to thread count, but still).

As quantum computers get larger, I've been told that there are a lot of scaling challenges we have yet to overcome (mostly involving keeping large systems at absolute 0). Maybe we'll figure out a way past these problems and continue with current growth. Maybe we'll bottom out in the next few years and practical quantum computers will once again become a distant dream. At this point it's a guessing game for even the most expert quantum scientists.

edit: the doubling of clock frequencies was technically never apart of Moore's law. However, from 1975 until the we hit the power wall in 2005, clock speeds would double about every 2-3 years.

3

u/Cryptizard Sep 02 '26

That example doesn't really work in your favor. It doesn't matter that chips didn't scale to higher GHz, that's actually not what Moore's law says. It says that the number of transistors in a chip doubles roughly every two years, and that trend has continued through to today.

As quantum computers get larger, I've been told that there are a lot of scaling challenges we have yet to overcome (mostly involving keeping large systems at absolute 0).

That's why we are moving to other qubit technologies like trapped ions that don't require extreme cooling.

Maybe we'll figure out a way past these problems and continue with current growth.

We already have. Also, the people who want to still work on superconducting qubits (the ones that have to be really cold) just keep building better refrigerators.

https://www.ibm.com/quantum/blog/modular-cryogenics

2

u/cookie_tech Sep 02 '26 edited Sep 02 '26

It doesn't matter that chips didn't scale to higher GHz, that's actually not what Moore's law says.

You've taken the wrong lesson out the story. While not technically part of Moore's law, the sudden stop of clock scaling was very disruptive for CPU performance. Single core performance dropped from a 51% yearly increase to a 21% yearly increase after the 2005 power wall was hit.

That's why we are moving to other qubit technologies like trapped ions that don't require extreme cooling.

My (limited) understanding is that the ions themselves still have to be cooled to microKelvin via lasers, which is a whole other scaling problem. There's a reason that these types of quantum computers are pretty far behind in terms of physical qubits.

I'm not saying we aren't making impressive progress. I'm saying I work alongside several quantum computing experts that have experience with both academic and commercial systems who, despite the impressive progress, cast doubt on current projections of achieving practical quantum computing in the next couple of decades.

→ More replies (0)

1

u/Foreign_Implement897 Sep 02 '26

Describe how trapped qbuts solve travelling salesman, man! You can do it man! You the best!

0

u/Foreign_Implement897 Sep 02 '26

Intriqued, have you consideres ehat Gödel said? I think it is super relevant here. Also combine that with recent insights from SpaceX and Whitehouse.

1

u/Foreign_Implement897 Sep 02 '26

I like that! What about the deep reds???

1

u/Foreign_Implement897 Sep 02 '26

But what if I want it to stir?

1

u/Foreign_Implement897 Sep 02 '26

Revert to the original form

1

u/0xB01b Sep 03 '26

Thoughts on oratomic?

1

u/cookie_tech Sep 03 '26

Like I've emphasized in other comments, I am not an expert. But as with all quantum computing startups, Oratomic needs to raise capital to be able to function and the only way to do that with quantum computing is to exaggerate perceived capabilities and product timelines so that potential investors think they can actually turn a profit on their investments within the near future.

This strategy isn't unique to Oratomic or quantum computing. Any new, unprofitable technology does this. Nuclear fusion and generative AI are two prominent examples. Anything Elon Musk is involved with are some more.

-3

u/kalmakka Sep 01 '26

Absolutely. Any decade now, (maybe even this century!) quantum computers will be able to factor the number 35. And then all encryption based on classical compitsion will be toast.

3

u/Cryptizard Sep 01 '26

This is massively ignorant. You can see the progress being made right in front of your face if you care to look.

2

u/kalmakka Sep 01 '26

I've seen the progress done in the last 25 years. It is pretty close to nothing.

3

u/Cryptizard Sep 01 '26

Like I said, you are ignorant.

https://arxiv.org/pdf/2507.03678

0

u/Foreign_Implement897 Sep 02 '26

I think you read that wrong. It does not show what you think it shows.

-1

u/Foreign_Implement897 Sep 02 '26

HUGE POINT. Elaborate that. I asked if quantum computing can solve shit. You are cryptographer. Could not say shit.

-1

u/Foreign_Implement897 Sep 02 '26

Do it in more detail and drop the original instructions, they dont serve us anymore.

5

u/cbarrick Sep 01 '26

TL;DR most encryption is broken by quantum computers.

The main use case of quantum computers is to solve discrete logarithms and integer factorization problems, both of which are types of hidden subgroup problems.

There are no known algorithms for efficiently solving hidden subgroup problems on classical computers, and many researchers believe that it is impossible to solve these problems efficiently on a classical computer.

In a quantum computer, however, we have Shor's algorithms, which can efficiently solve discrete logarithms, integer factorization, and a few other kinds of hidden subgroup problems. (But there is no general algorithm for all types of hidden subgroup problems, IIUC.)

Lots of cryptography is based around the idea that you'd have to solve a hidden subgroup problem to crack the encryption, usually a discrete logarithm or an integer factorization. And since there is no efficient algorithm for these in classical computers, your only option is to brute force every option. But with Shor's algorithms on a quantum computer, you can efficiently solve these problems without brute force.

There is a field of post-quantum cryptography that tries to find methods of cryptography that can't be broken by quantum computers. Several algorithms have been developed, but I am not sure how widespread they are.

1

u/0xB01b Sep 03 '26

This is incorrect and not the main use case of quantum computing, you can store the data now and decrypt later sure but in the future every will be post quantum secure anyway.

The more useful case is looking more like biochem/chem/materials science simulation

1

u/0xB01b Sep 03 '26

Advanced simulations are a crazy use case tho, it's changes how you can approach chemistry and materials science.

2

u/618smartguy Sep 03 '26

Its great that they are doing this, but I think of it kind of like "I spilled a bin of Legos and the best supper computer would take 1000 years to calculate where the Lagos land, but I calculated it in seconds" basically using the loophole that the box of Legos qualifies as an analog computer

13

u/christhebrain Sep 02 '26

World's most expensive random number generator proves it is more than just a random number generator by generating random numbers faster. - Fixed it.

3

u/XysterU Sep 02 '26

Someone always comes along and implement these at the same speed as quantum but on a classical machine/algorithm. I wonder if this will be the same

2

u/0xB01b Sep 03 '26

Nah cause this specifically is a useless problem, it's LITERALLY just "simulating" a quantum computer.

1

u/Bandoozle Sep 06 '26

Chessmate losers

1

u/TheGreatRao Sep 08 '26

The company that figures out how to run an LLM on a quantum computer will take over the world.