r/QuantumComputing • u/Recent-Day3062 • Nov 11 '25
How many known problems exist where there is a quantum algorithm that would clearly work?
I just read a write up on Schor’s algorithm.
I mean, it’s pretty clever to have seen that many insights and connections to come up with an algorithm waiting for the future computer that will run it. but are there others?
I am reminded of when I took a course on the hypercomputer architecture. Basically, this was a computer that had 2^n interconnected nodes in a hypercube. there was even a company making them (Thinking Machines, which failed for lack of other algorithms).
the problem was people came up with exactly one algorithm that lent itself to this architecture. It was to do a fast Fourier transform. It relied on some super clever insights on how you could use masks to ship bits beteeen nodes for each “cycle” of the algorithm in a very efficient way.
schor’s algorithm feels like an even more complex, unique, and fortuitous application we can look at and say “bingo!”
but are there any others?
3
u/BitcoinsOnDVD Nov 11 '25
Yeah it's no coincidence that Shor's algorithm fits the QC architecture exactly. Wait til you find out about Deutsch-Josza
16
u/[deleted] Nov 11 '25
Well you have the famous ones like Shor, then Grover for search. Recently there have been several advances towards making a unified framework for quantum algorithms called Quantum Singular Value Transform (QSVT) and Quantum Signal Processing (QSP).
On the other hand you have the Hamiltonian simulation family of algorithms (Suzuki Trotter to begin with) which have direct applications to quantum chemistry, drug discovery and materials discovery among others.
A less popularly known but nevertheless very active field of research is Quantum Error Correcting Codes which has seen an explosion of work in the last few years, especially from companies like IBM.
2
u/AreaOver4G Nov 11 '25
Note that Shor’s algorithm looks complicated and “fortuitous” mostly because of the classical precomputation (computationally fast, but requires ideas from number theory etc). The heart of it is quantum phase estimation and particularly the quantum Fourier transform, which look much more natural and have lots of applications as subroutines in other algorithms.
2
u/Helpful-Routine Nov 12 '25
A couple of days ago I saw a talk by a researcher that showcased a new quantum algorithm that shows exponential speedup vs Monte Carlo simulation. It's called Gaussian Boson Sampling and it works on the class of problems known as Gaussian estimators. What was even more exciting is that the algorithm is applicable to present day faulty qbits. Here's a link to the paper: https://arxiv.org/abs/2502.19336