The future of quantum computing is often described in physical terms: more qubits, lower error rates, longer computations, and eventually machines capable of correcting their own errors. These milestones matter enormously. Without capable hardware, even the most elegant quantum algorithm remains a mathematical proposal.
But the relationship also runs in the other direction. The usefulness of a quantum computer depends on what we ask it to do, how economically we express that task, and how efficiently we turn an abstract algorithm into operations a physical device can execute.
A better quantum algorithm can change the machine we need.
That possibility deserves attention alongside the hardware roadmap.
The lesson from classical optimization
A study of mathematical programming solvers from 2001 to 2020 found roughly a thousandfold combined performance improvement for mixed-integer linear programming on its benchmark comparisons. Of that improvement, the researchers attributed about 20 times to hardware and approximately 50 times to better algorithms and solver implementations.
The numbers describe a particular classical field over a particular period. They are not a forecast for quantum computing. Yet they reveal an important principle: software progress can dramatically expand what hardware makes possible.
Quantum computing has its own opportunities for the same kind of ingenuity. Circuit synthesis can express a computation with fewer operations. Placement and routing can adapt those operations to the connections between physical qubits. Better algorithms can reduce the number of repetitions or the resources needed to reach a useful answer. Error correction and fault-tolerant compilation influence how many physical qubits are required to protect a logical computation.
Each improvement changes the equation between a scientific idea and an executable program.
When an algorithm changes the hardware requirement
One particularly vivid example comes from quantum resource estimation, the discipline of working out what it would take to run a proposed algorithm on a sufficiently capable machine.
In 2019, Craig Gidney and Martin Ekerå estimated that factoring a 2,048-bit RSA integer could require around 20 million noisy physical qubits under a specified set of assumptions. In 2025, Gidney published a substantially revised approach estimating fewer than one million under broadly comparable physical assumptions.
Both are estimates for future fault-tolerant hardware under broadly comparable physical assumptions. The newer approach trades a longer runtime for far fewer qubits.
The newer estimate involved major algorithmic and error-correction advances. It also traded qubits against runtime: the earlier estimate envisaged about eight hours, whereas the newer one allowed less than a week. Neither paper reported an experiment on a machine of that size. Both were resource estimates for future hardware.
The striking point is that the mathematical and software approach changed the scale of the proposed machine before the machine existed.
This was a result about factoring, not industrial optimization. Its relevance here is the broader possibility: resource requirements are not fixed simply because a quantum algorithm has been written down. Better constructions, implementations and compilers can change them.
A hardware roadmap is also an algorithm roadmap, because better software changes what the hardware must deliver.
The computation between an idea and a qubit
A quantum algorithm is not yet a circuit ready to run. A practical implementation must accommodate the device's available gates, qubit connections, noise characteristics and execution limits.
For example, two qubits that interact in a logical circuit may not be adjacent on a physical processor. The compiler may need to reorganize the computation, choose different qubit placements or introduce additional operations. Different choices can produce significantly different circuit sizes and depths.
A shorter circuit is often attractive because it uses fewer operations and may expose the quantum state to less noise. But gate counts alone do not tell the whole story. Which gates are used, how reliably they execute, how long the circuit runs and what result must be measured all matter.
This turns quantum compilation into a serious optimization problem in its own right. Better search over equivalent circuit implementations can make existing hardware more useful and reveal which physical improvements would have the greatest effect.
At the algorithm level, a similar search continues. Researchers compare different circuit constructions, initialization strategies, classical optimizers and methods for combining partial results. Some ideas offer advantages only under particular assumptions. Others may require larger, fault-tolerant machines before their potential can be realized.
Two frontiers, moving together
It would be misleading to expect quantum software to follow the same numerical improvement curve as classical optimization. Quantum algorithms face different mathematical limits; a better classical solver may also move the goalposts for any claimed quantum advantage. And advances in quantum error correction, control or physical architecture can change which software approaches are worthwhile.
What is reasonable to expect is sustained progress on both sides. Hardware research makes new computations possible. Algorithm research makes some computations cheaper, more reliable or more useful. Each changes the priorities of the other.
For organizations exploring quantum applications, this suggests a more productive way to think about the future. Rather than asking only when a machine will reach a particular qubit count, ask which algorithms are promising for the actual problem, what resources they need, how strong the classical alternatives are, and which technical milestones could make the comparison change.
The result is a more meaningful picture of quantum opportunity over time.
Quantum advantage, when it arrives for a useful optimization workload, will be measured against the best classical methods available at that time, including the algorithmic improvements that are still to come.
That is why progress in quantum hardware and quantum software must be studied together. One expands the machine. The other expands what we know how to do with it.
Further reading
- Koch and colleagues, Progress in mathematical programming solvers from 2001 to 2020 (2022)
- Gidney and Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019)
- Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (2025)
- Challenges and opportunities in quantum optimization, Nature Reviews Physics (2024)