A new playbook for quantum optimization benchmarking

Demonstrating quantum advantage for real-world problems requires more than advances in quantum hardware. It also requires new algorithms, careful benchmarking, and a clear understanding of where quantum methods can outperform classical counterparts. A new paper from the Quantum Optimization Working Group, published today in Nature Computational Science, highlights the Quantum Optimization Benchmarking Library (QOBLIB), a community-driven effort to establish rigorous, shared benchmarks for computational optimization.

Stefan Woerner, Principal Research Scientist and Manager of Applied Quantum Science at IBM Research in Zurich, is an active member of the Quantum Optimization Working Group and a co-author of the new paper. His work includes research in quantum optimization algorithms, applications, and benchmarking aimed at identifying where quantum computers may offer a practical advantage—even before the advent of large-scale, fault-tolerant quantum computing. Recent advances, including new methods for implementing optimization circuits and progress in multi-objective optimization, are helping clarify the path forward.

In a recent conversation, Woerner discussed how researchers are rethinking optimization for the quantum era, where early signs of advantage may emerge, and what it will take to turn those insights into real-world impact.

How do you define quantum optimization today and why is it a central focus for IBM's research?

Quantum optimization explores how quantum computers, in combination with classical computers, may help solve important optimization problems better than classical methods alone. This is highly relevant for IBM and its clients because optimization is everywhere. It appears across industries, from finance and logistics to medicine and the life sciences. Even problems like protein folding can be viewed through the lens of optimization. These problems can be extremely difficult to solve today. In addition, in many real-world settings, even small gains in solution quality can have an outsized impact. That's what makes quantum optimization so important for IBM, its clients, and industry and science more broadly.

What are the fundamental limits of classical methods for solving optimization problems?

That's a very good and difficult question, because the way an optimization problem is formulated strongly influences how difficult it is to solve. Classical optimization researchers and practitioners usually formulate problems so they remain tractable for the available tools. Typically, this involves simplifications, which can widen the gap between the real-world problem we care about and the model we actually solve.

In many cases, we need to take a step back and ask: What do we really want to achieve? Where does that gap come from? And could quantum computing help reduce it while keeping the problem tractable? This is an important direction for research: looking at the original real-world problems, identifying features that are hard to handle classically—the features simplified in classical approaches—and understanding whether quantum methods can create value by addressing them more directly.

Can you give an example of an optimization problem where quantum methods might offer an advantage?

A good example is multi-objective optimization, which we explored in a paper published in Nature Computational Science last October.

Many real-world business problems are multi-objective. You usually have several goals and need to find the best trade-offs between conflicting objectives. In finance, for example, that might be risk vs. return. In supply chains, it might be service level vs. inventory cost. Improving one objective usually comes at the expense of another. Often, there are also more than just two objectives.

These problems can be very difficult to solve classically, especially if you’re trying to recover the full set of optimal trade-offs, known as the Pareto front. It is a good example of how taking a step back and revisiting the core problem helped us identify opportunities where quantum methods might offer an advantage.

How should readers think about the timeline to usefulness for these quantum methods? Do they require fault tolerance?

Our goal is to demonstrate quantum advantage in optimization before large-scale fault tolerance. That is an ambitious goal, but I think there are reasons to be optimistic. For one thing, we’re already seeing some credible research organizations begin to challenge classical optimization solvers with quantum methods, but the community still has a lot of work to do.

Ultimately, it is difficult to put a precise timeline on this. Continued progress depends on algorithmic advances, which are hard to predict, and on continued hardware improvements as outlined on our roadmap. At the same time, we have already come a long way. Today’s quantum devices are no longer just scientific prototypes, they are tools that researchers use to explore algorithms, test ideas, and understand where quantum approaches may create value.

What kind of algorithmic advances could help us get there? Can you give an example?

Just recently, we published a paper where we took a completely different perspective on how we implement quantum optimization algorithms on our hardware. Instead of directly compiling a complex target unitary—the mathematical operation that describes what the circuit does—into a quantum circuit, we first decompose it into a weighted sum of simpler-to-implement unitaries. The tradeoff is that we need to take more samples, meaning more hardware runs, but that’s something we can often afford because our hardware can generate samples very quickly.

We’re effectively trading one resource for another: reducing circuit complexity at the cost of additional sampling. This shift in perspective can change what we consider feasible for today’s devices. It can help us run circuits that would otherwise be too demanding, for instance because of connectivity or circuit depth constraints. That’s the kind of algorithmic insight that could help move us closer to demonstrating advantage with near-term devices.

Why is benchmarking so critical for optimization, and how do efforts like QOBLIB help?

In optimization, many of the algorithms we use in practice are heuristics. That means they often don’t come with general guarantees about how well they will perform on a given problem instance. They are usually based on years of experience, testing, and intuition, and while they can work very well, we can’t always know in advance how well they will do. That makes it very difficult to claim any quantum advantage, because many quantum algorithms will also be heuristic. We can’t rely on theoretical scaling arguments alone—we need to compare performance in practice.

To demonstrate an advantage, you need to show that you outperform the best available classical heuristics, and there are many of them. That’s why community-driven benchmarking is so important. QOBLIB is a collection of diverse, practically relevant problem classes, with the goal of creating a common set of benchmarks against which both classical and quantum methods can be tested and compared. By working with the community to submit and evaluate solutions, we can better understand what works, track progress over time, and establish the robust classical baselines needed to make credible claims of quantum advantage.

How do you envision a real-world workflow for these methods that you're developing today? What will that actually look like for users?

A major challenge in optimization is translating a real-world decision problem into a mathematical model that an algorithm can solve. This requires expert knowledge, careful modeling choices, and often significant effort to adapt the model when the problem or environment changes. With advances in AI, this workflow can become much more dynamic. Users may be able to describe a problem in natural language, and the system can help turn that description into suitable optimization models. While it still requires careful validation, it can substantially accelerate the process, allowing optimization to be used even more broadly.

From there, an orchestration layer decides how to solve the problem. Because optimization methods are often heuristic, the system can try, compare, and combine different approaches—sometimes purely classical, sometimes involving quantum methods. This will mostly run in the cloud, or, when needed, in on-premises installations. For the user, the interface becomes much simpler: they interact with a system that manages the complexity under the hood and delivers better solutions, faster, without requiring them to choose or tune each method themselves.

What does success look like for quantum optimization now and over the next few years? What breakthroughs do you hope to see?

What I would like to see in the next few years is a clear and credible demonstration of quantum advantage in optimization. One that is accepted not only by the quantum community, but also by experts in classical optimization. It would also help connect the quantum and classical optimization communities more closely, which is essential for accelerating progress.

Ideally, this would be on a practically relevant problem. But even if the first demonstration is more academic, it should involve a meaningful problem class: one that is not entirely artificial, that researchers agree is important to study, and that has a plausible path towards real-world use cases. The key is that the result should be robust. It should stand up to comparison with the best available classical methods and establish that, for this particular problem, a quantum approach is the right tool.

That kind of broadly accepted result would be a major milestone for the field, and that’s what I really want to see in the next few years.