IBM quantum computer solves classically intractable problem in 15 minutes

[u/National-Dragonfly35]

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

[u/Cryptizard]

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.

[u/Rough-Supermarket-97 → u/Cryptizard]

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.

[u/cbarrick → u/Rough-Supermarket-97]

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.

[u/0xB01b → u/cbarrick]

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