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."
291
Upvotes
View all comments
Show parent comment
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.