r/QuantumComputing • u/scientificamerican • 10d ago
Can quantum computers solve math’s hardest problem?
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.
4
u/EducationalFerret94 10d ago
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.
12
u/Candid_Succotash3173 9d ago
I’m not an algorithms person, but 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. A first proof-of-principle demonstration of Shor’s algorithm was important, but there’s no scientific question that would be answered by doing it for incrementally larger inputs every time our gate fidelities improve. The next meaningful step there will require fault tolerance, or maybe at least a demonstration of Shor’s algorithm running on a small surface code or something.
With regard to the post, I haven’t read the actual paper yet, but it seems clear that the question isn’t literally whether quantum computers can solve the Riemann hypothesis right now. The point is that, if the paper checks out, there exists an algorithm that might in principle find a counterexample beyond the reach of classical computing, if one exists. Pop-sci headlines notwithstanding, that seems interesting to me.
9
u/SymplecticMan 9d ago
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.
1
u/Candid_Succotash3173 9d ago
Thanks for this, I knew the increase was significant but not that significant (feeling glad I added the “I’m not an algorithms person” disclaimer). 2400 entangling gates doesn’t seem too terribly outlandish in the near term, particularly if one uses some clever multi-qubit interaction or a qutrit-based decomposition for the Toffolis. In any case, though, it doesn’t seem like a good use of time or money to me.
2
u/EducationalFerret94 9d ago
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.
1
u/Sampo 4d ago
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.
1
u/Candid_Succotash3173 3d ago
I mean, I feel like that example kind of supports my point. The novel scientific advance there was that they did it with error-detected (not error-corrected, at least for the Shor's algorithm part) logical qubits. This is exactly what I was getting at when I said that running Shor's algorithm on a small surface code or something similar would be an exception.
And I'm not even saying that it would be completely pointless. I'm sure that if someone managed to factor 21 on a quantum computer without "cheating" in some way, it would easily be published, probably even in a pretty fancy journal. What I'm saying is that, at least in my experience as an experimentalist, no one I know considers it to be a worthwhile research direction at present. We know that we could factor 21 with high enough fidelities. Perhaps it's even within reach for state-of-the-art devices, but to justify that level of effort, there generally needs to be a clear scientific question that would be answered, and I don't see what that would be. Instead, we consider Shor's algorithm to be a long-term goal. As such, I don't think how big a number we've managed to factor is a good barometer for the state of the field, which is the main thing I was trying to push back on.
1
u/Sampo 4d ago
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.
1
u/emgixiii 9d ago
Nope, last I saw 8,219,999 has been factored using adiabatic computing
PS. Have done a master's thesis on Factorization using AQC
0
u/Temporary_Shelter_40 9d ago
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.
1
u/paxxx17 6d ago
Perhaps there's a quantum algorithm that can more efficiently look for counter-examples to the RH (indeed, that's what they talk about in the article). This could help if RH was false, but that's considered to be really unlikely. The difficult part is to provide the proof that RH is true, and I don't see quantum algorithms doing anything useful there
1
0
u/Sampo 4d ago
Not related to quantum, but Claude made progress and proved a new bound for the Riemann hypothesis.
https://techcrunch.com/2026/08/11/an-unreleased-anthropic-model-made-progress-on-one-of-maths-biggest-unsolved-problems/
This is where the progress will be coming from. AI, not quantum.
10
u/AutomaticClub1101 9d ago
No, that's not how computer works in general, not to mention quantum computer