Comparing Quantum Annealer and Metaheuristic Methods to Solve the Steiner Tree Problem

This chapter delves into the comparison of quantum annealing and metaheuristic methods to solve the Steiner tree problem, a challenging combinatorial optimization task. The study explores the performance of a quantum annealer (QA), specifically D-WAVE’s Advantage QA, against classical methods such as simulated annealing, genetic algorithms, and hill climbing. The chapter introduces a novel QUBO (Quadratic Unconstrained Binary Optimization) formulation for the Steiner tree problem, derived using the AutoQUBO method, which simplifies the conversion of complex optimization problems into QUBO format. The results indicate that while the QA can return feasible solutions, its performance is currently outperformed by hybrid and classical simulated annealing solvers in terms of solution quality and runtime. The study highlights key issues such as qubit errors and the computational cost of minor embedding, which affect the QA's efficiency. Despite these challenges, the QA shows promise for future advancements in quantum computing. The chapter also discusses the potential of hybrid annealers, which prove to be as effective as classical methods and faster, offering a practical solution while quantum methods mature. The analysis provides a detailed comparison of solver runtimes, solution feasibility, and quality, offering valuable insights for professionals in the field of optimization and quantum computing.