Thorsten Koch, David E. Bernal Neira, Ying Chen, G. Cortiana, Daniel J. Egger, Raoul Heese, Narendra N. Hegade, Alejandro Gomez Cadavid, R. Stephanie Huang, Toshinari Itoko, Thomas Kleinert, Pedro Maciel Xavier, Naeimeh Mohseni, J. A. Montañez-Barrera, Koji Nakano, Giacomo Nannicini, Corey O’Meara, Justin Pauckert, Manuel Proissl, Anurag Ramesh, Maximilian Schicker, Noriaki Shimada, Mitsuharu Takeori, Víctor Valls, David Van Bulck, Stefan Woerner, Christa Zoufal
Recent progress has brought benchmarking of (heuristic) quantum algorithms at scale within reach. Particularly in combinatorial optimization, it is key to empirically analyze and track progress towards quantum advantage. This work introduces a systematic, fair and comparable benchmarking framework for quantum optimization methods by presenting ten model-independent problem classes that are challenging for classical methods. Track records of specific instances and solutions are given in an accompanying open-source repository. While the individual properties of the problem classes vary, they all become challenging from less than 100 to, at most, an order of 100,000 decision variables. We reference results from state-of-the-art solvers for instances across all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems, which illustrate standardized benchmark reporting. The presented problem instances may be approached with classical or quantum algorithms executed on varying hardware platforms to drive the field towards quantum advantage.
Recent progress has brought benchmarking of (heuristic) quantum algorithms at scale within reach. Particularly in combinatorial optimization, it is key to empirically analyze and track progress towards quantum advantage. This work introduces a systematic, fair and comparable benchmarking framework for quantum optimization methods by presenting ten model-independent problem classes that are challenging for classical methods. Track records of specific instances and solutions are given in an accompanying open-source repository. While the individual properties of the problem classes vary, they all become challenging from less than 100 to, at most, an order of 100,000 decision variables. We reference results from state-of-the-art solvers for instances across all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems, which illustrate standardized benchmark reporting. The presented problem instances may be approached with classical or quantum algorithms executed on varying hardware platforms to drive the field towards quantum advantage.
Benchmarking the performance of quantum optimization algorithms is crucial for identifying utility for industry-relevant use cases. However, Benchmarking processes most often vary between optimization applications and depend on user-specified goals. The heuristic nature of quantum algorithms additionally poses a challenge, especially in the comparison to classical algorithms. A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches. This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks. We discuss (1) application-specific algorithm choice, ensuring every solver is provided with the most fitting mathematical formulation of a problem; (2) the selection of benchmark data, including hard instances and real-world samples; (3) the choice of a suitable holistic figure of merit, like time-to-solution or solution quality within time constraints; and (4) equitable hyperparameter training to eliminate bias towards a particular method. Finally, the proposed guidelines are tested across three benchmarking scenarios, utilizing the Max-Cut (MC) and Travelling Salesperson Problem (TSP). The benchmarks employ classical mathematical algorithms, such as Branch-and-Cut (BNC) solvers, classical heuristics, Quantum Annealing (QA), and the Quantum Approximate Optimization Algorithm (QAOA).
Recently, several researchers proposed portfolio optimization as a potential use case for quantum optimization. However, the literature is lacking an extensive benchmark quantifying the potential of quantum computers for portfolio optimization. In this work, we contribute to closing this gap. We provide a computational study, comparing quantum approaches against state-of-the-art classical methods on a meaningful, real-world instance set. In particular, we compare quantum annealing and the quantum approximate optimization algorithm against classical mixed-integer programming, simulated annealing, steepest descent local search, tabu search and a problem-tailored heuristic. We consider a variance-minimizing variant of portfolio optimization which we show to be more difficult to solve for classical optimizers than return-maximizing or multi-objective formulations. Our benchmark data set comprises 270 instances with up to 1,000 assets from actual stock data. Due to hardware limitation, quantum methods could only be tested for instances with at most 30 assets. The results show that all instances can be solved to proven optimality by mixed-integer programming in the order of seconds. Moreover, the problem-tailored heuristic consistently outperforms quantum approaches in terms of solution quality for fixed runtime. Thus, we conclude that there is only very limited room for a potential quantum advantage for the considered variant of portfolio optimization.
Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this thesis, we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible. We first give a general overview of the quantum (sub)routines that serve as building blocks for more advanced algorithms, as well as of the three hybrid benchmarking techniques used throughout this thesis. Then, we elaborate on each method: we start with the algorithmic descriptions, proceed to the methodology, and conclude with their hybrid evaluation on practically relevant datasets. Within the hybrid benchmarking method 1 (gate count analysis), we analytically derive the minimum number of gates that a quantum version of the classical simplex algorithm would require to solve realistic instances. By executing classical counterparts of the quantum subroutines, we infer the execution speed required per gate for the quantum simplex to outperform its classical counterpart. Within the hybrid benchmarking method 2 (query count analysis), we benchmark functional quantum linear solvers by analytically deriving a precise number of query calls made to the same oracles as a function of problem parameters. This provides insight into which algorithm might be more suitable in a given parameter regime. It allows for a direct comparison only between different quantum algorithms and is independent of classical runtime measurements. Within the hybrid benchmarking method 3 (cycle count analysis), we develop a runtime estimation framework tailored to the quantum tree generator–based search for solving 0-1-knapsack problems. We evaluate its performance on large scale instances beyond the reach of general simulation. We compare it with state-of-the-art classical linear programming solvers in terms of processor cycle counts. Hybrid benchmarking provides a fair, systematic benchmarking methodology, ensuring reproducible and relevant comparisons not only between classical and quantum approaches, but also among different quantum algorithms.
Quantum computing has emerged as a promising paradigm for addressing computational challenges in physics that remain intractable for classical methods. This study presents a quantitative benchmarking analysis of prominent quantum algorithms applied to representative physics problem classes, with the objective of evaluating their computational performance relative to state-of-the-art classical algorithms. Using standardized performance metrics—including execution time, algorithmic complexity, resource utilization, accuracy, scalability, and quantum advantage ratios—the study systematically compares quantum and classical approaches across multiple experimental configurations. The results demonstrate that quantum algorithms exhibit measurable performance gains for specific problem types, particularly in terms of runtime efficiency and scaling behavior, while also highlighting practical constraints related to qubit requirements and circuit depth. Visual and tabulated analyses further reveal that quantum advantage is highly problem-dependent and influenced by algorithmic structure and system size. Overall, the findings provide empirical evidence that quantum algorithms can offer substantial computational benefits for selected physics applications, while underscoring the importance of quantitative benchmarking in distinguishing theoretical promise from practical performance. This work contributes to ongoing efforts to objectively assess quantum advantage and informs future research directions in quantum algorithm development and physics-based applications.
Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.