September 05, 2025 -- Since the 1990s, evidence has been growing that quantum computers should be able to solve a range of particularly complex computational problems, with applications in everything from supply chain management to medicine and beyond. A new study out this week provides a novel blueprint for achieving this, detailing a deep new understanding of how a problem's intrinsic difficulty dictates the quantum computer's ultimate speed – and how we might learn to push that speed to its limit.

“Some mathematical problems are easy. Some mathematical problems are hard, but what makes a problem easy or hard?” asks Achim Kempf, Dieter Schwarz Chair in the Physics of Information and AI at the University of Waterloo and Associate Member at Perimeter Institute. “It turns out, when you put a problem on a quantum computer, the problem’s complexity translates into a need for quantum entanglement. The harder the question, the more complex the entanglement needs to be.

That means the computational problem becomes a physical reality, where particles or qubits within a quantum computer have to behave differently based on the complexity. What used to be mathematics has become physics, with entanglement acting as the key process.

The new study, co-authored by Kempf and Einar Gabbassov, a PhD student at the University of Waterloo’s Institute for Quantum Computing and Perimeter Institute, delineates this relationship in detail for the first time.

Defining the hardness of a mathematical problem

Mathematicians and computer scientists have developed a sophisticated classification system that groups problems by their complexity, revealing which problems are computationally hard and which are not. The hardest class of these problems are known as NP-hard problems, and while there is no evidence that quantum computers can solve them all quickly, researchers have high hopes that they will be able to provide significant speed-ups for some of the most difficult and practical applications, like optimizing complex systems.

To write quantum algorithms that can provide such speedups, it is incredibly useful to be able to categorize and describe a problem’s complexity in physical terms. One of the longstanding visualizations that experts use to do this is to describe a problem’s complexity in terms of the ruggedness of a landscape.

“Imagine you are parachuted down onto a landscape with hills and valleys and cliffs, and you want to find the lowest possible point, where you’ve been told you’ll find a treasure chest. When we are dealing with an easy problem, the corresponding landscape is gently sloping or consists of a single valley. But for a hard problem, the corresponding landscape is rugged, and you might easily find yourself at the bottom of a valley with no treasure in sight, because the actual lowest point is in a deeper chasm 20 kilometres away. It then becomes a very hard problem to solve,” says Kempf.

The power of quantum computers is that they allow you to search all valleys at once, namely by using entanglement, instead of checking each one in sequence. And for that, the entanglement needs to be literally as complex as the geography of the problem’s landscape.

Mapping entanglement onto mathematical terrain

Entanglement was famously described by Albert Einstein as “spooky action at a distance,” by which he meant that one particle appears to influence another instantly, regardless of how far apart they are. Entangled particles can become connected in such a way that when you measure the state of one of them, you immediately know the state of the other.

“You can have two separate objects, two particles or two qubits, and once they get entangled, they kind of become one entity. It is not possible to view them separately: they become one thing in the same state,” explains Gabbassov.

Kempf likens it to throwing a dozen spare charging cables into a drawer, which inevitably come out knotted and clumped together.

The unique properties of entanglement are what give quantum computing its advantage over classical computers.

Gabbassov and Kempf show that the ‘rugged terrain’ analogy for computational complexity is more than just a metaphor. It provides a direct specification for the entanglement a quantum computer must create to solve the problem. A rugged, complex landscape requires an equally complex and sophisticated web of entanglement between the quantum bits.

“We find that hard mathematical problems are hard because they require quantum computers to manipulate, create, and redistribute highly complex entanglement inside the system. As the system evolves, the qubits start building a complex web. The relationships can shift and change, with particles becoming disentangled and entangled again to something else – in sync with hills and valleys of a landscape flowing into each other. Hard problems require a lot of entanglement manipulation with constant change, and this determines how fast the computation can be.” says Gabbassov.

With this study, the team has created a brand-new way to measure the speed by which a problem can be solved on a quantum computer, based on the amount of entanglement required.

That ‘speed limit’ will be able to inform the design of quantum algorithms in future, allowing them to “smooth” the computational path, anticipate bottlenecks, and achieve the fastest possible solutions.

The future of quantum computers

These results were obtained for a particular type of quantum computer, known as an adiabatic (or quantum analog) quantum computer, but it is known that any adiabatic quantum computation can also be performed on circuit-based (or quantum digital) quantum computers and vice versa. That means the new insight can be applied across the entire quantum computing industry.

Many leaders in the quantum computing industry, including D-Wave, Quantinuum, IonQ, QuEra Computing, Pasqal, Atom Computing, Microsoft, Google, and IBM are developing quantum hardware, and some hardware can even run both adiabatic and circuit-based quantum computations.

Gabbassov and Kempf believe this research is a fertile ground for subsequent work, and hope that this research will inspire other scientists to apply these insights to their own fields, where further discoveries may emerge.

“I think this research will speed up the economic viability of quantum computing. We now better understand how to turn a mathematical problem into a physical problem,” says Kempf. “We’ve basically provided a new bridge between mathematics and physics, and we think that a lot of traffic can be put on that bridge. This result will be helpful in running quantum computers, improving their design, and creating software for them.