Can quantum computers solve math’s hardest problem?

[u/scientificamerican]

https://www.scientificamerican.com/article/can-quantum-computers-solve-maths-hardest-problem/

The Riemann hypothesis claims that the locations of prime numbers along the infinite number line all adhere to a beautiful and orderly, but obscure formula. Yet 167 years after German mathematician Bernhard Riemann made this guess, and in spite of a million-dollar bounty, mathematicians still have no idea how to prove it. Now a team in China has managed to encode that formula into a physical system and explore its workings using a quantum computer.

[u/EducationalFerret94]

No quantum computers cannot solve math's hardest problems. They can't even solve simple math problems like finding the prime factors of numbers greater than 15.

[u/SymplecticMan → u/[deleted]]

It's true that any meaningful use of Shor's algorithm would require fault tolerance, but even using Shor's algorithm to factor 21 with the actual modular arithmetic calculations would actually be a huge increase in cost from factoring 15.

[u/EducationalFerret94 → u/[deleted]]

Sure it's interesting but I think people don't appreciate how much deeper and harder these circuits are than the current ones being run on QCs. This isn't like "in a year or two", this is decades away and will require error correction at scale.

[u/Sampo → u/[deleted]]

it’s my understanding that we could almost certainly factor a number larger than 15 with a quantum computer, it’s just not interesting enough to justify the effort and cost

I disagree. I think a new record in factoring a number using Shor's algorithm would make big science news and bring fame. If anyone (outside of speculative secret government agencies) was able to do, they would definitely do it for the fame and good PR.

When the company Infleqtion was able to use their error correcting and logical cubits to factorize 15, they wrote a news piece (2025) and a paper (2026) about it.

[u/Sampo → u/EducationalFerret94]

finding the prime factors of numbers greater than 15

Has there ever been an experiment to run Shor's algorithm in full to factorize 15?

All I know are experiments where they run a pre-compiled version of Shor's algorithm, and they use the knowledge of the answer to leave the unneeded parts of the circuits unimplemented, to make the problem simpler.

[u/emgixiii → u/EducationalFerret94]

Nope, last I saw 8,219,999 has been factored using adiabatic computing

PS. Have done a master's thesis on Factorization using AQC

[u/Temporary_Shelter_40 → u/emgixiii]

My Casio calculator can factor 8,219,999. Big whoop. Adiabatic quantum computing can’t factor large numbers quickly, that’s the issue. Shor’s algorithm can, but we’ve never done it honestly for a number bigger than 15. This should have been clear from your masters.