Abstract We benchmark the 5000+ qubit system coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems calledgarden optimization problemsknown in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system sometimes produce more favourable results if they can solve the problems.
Abstract We benchmark the 5000+ qubit system coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems calledgarden optimization problemsknown in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system sometimes produce more favourable results if they can solve the problems.
We benchmark the 5000+ qubit system Advantage coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems called garden optimization problems known in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the Advantage system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system DW2000Q sometimes produce more favourable results if they can solve the problems.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
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.
The Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.
Abstract We benchmark classical, simulated-quantum, hybrid, and direct quantum-annealing workflows on a structured binary control problem formulated as a quadratic unconstrained binary optimization (QUBO) model. The benchmark is motivated by greenhouse heater scheduling, where the horizon (H) denotes the number of hourly binary control decisions, but the focus is on solver behavior for a physically decoded control-QUBO formulation. For the main one-day instance ((H=24)), all solver outputs are decoded back into heater schedules and evaluated using the same simulator-side objective and feasibility criterion. Classical simulated annealing and path-integral simulated quantum annealing produce feasible near-optimal solutions in all repetitions, with best objectives close to the exact optimum. In contrast, the tested D-Wave Leap Hybrid binary quadratic model workflow is less reliable and does not outperform the classical baselines under 15--60 s requested time limits. Direct D-Wave quantum processing unit execution on reduced instances remains feasible in all runs and recovers the exact optimum for (H=10) and (H=12), but the exact-hit rate decreases with increasing horizon. The results do not indicate quantum advantage, but provide a reproducible benchmark for evaluating annealing-based natural and quantum computing workflows on structured control QUBOs. MSC Classification: 90C27 , 90C59 , 81P68 , 93C55
Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.