Abstract Adiabatic quantum computing is implemented on specialized hardware using the heuristics of the quantum annealing algorithm. To solve a problem using quantum annealing,the problem requires the formatting as a discrete quadratic function without constraints. The problem of finding Nash equilibrium in two-player, non-cooperativegames is a two-fold quadratic optimization problem with constraints. This problem was formatted as a single, constrained quadratic optimization in 1964 by Mangasarianand Stone. Here, we show that adding penalty terms to the quadratic function formulation of Nash equilibrium gives a quadratic unconstrained binary optimization(QUBO) formulation of this problem that can be executed on quantum annealers. Three examples are discussed to highlight the success of the formulation, and an overall,time-to-solution (hardware + software processing) speed up by seven to ten times is reported on quantum annealers developed by D-Wave System.
Abstract Adiabatic quantum computing is implemented on specialized hardware using the heuristics of the quantum annealing algorithm. To solve a problem using quantum annealing,the problem requires the formatting as a discrete quadratic function without constraints. The problem of finding Nash equilibrium in two-player, non-cooperativegames is a two-fold quadratic optimization problem with constraints. This problem was formatted as a single, constrained quadratic optimization in 1964 by Mangasarianand Stone. Here, we show that adding penalty terms to the quadratic function formulation of Nash equilibrium gives a quadratic unconstrained binary optimization(QUBO) formulation of this problem that can be executed on quantum annealers. Three examples are discussed to highlight the success of the formulation, and an overall,time-to-solution (hardware + software processing) speed up by seven to ten times is reported on quantum annealers developed by D-Wave System.
Nash equilibrium (NE) computation is a fundamental problem in game theory, with numerous applications in economics, control theory, computer science, and engineering. However, finding an NE remains computationally challenging, even in two-player normal-form games. In this work, we leverage quantum computing (QC) to develop an efficient quantum annealing-based algorithm for computing NEs in two-player non-cooperative games. Our approach exploits quantum parallelism to enhance computational efficiency. We first formulate the NE computation as a non-convex quadratic problem, which is then transformed into a quadratic unconstrained binary optimization (QUBO) problem through the use of penalization techniques. This reformulation is amenable to quantum annealing solvers. However, due to the probabilistic nature of quantum annealing, the solver typically returns a distribution of candidate solutions, which may not directly correspond to valid NEs. To address this, we propose a novel QA-assisted algorithm that incorporates a post-quantum processing step to refine, verify, and select approximate NEs from the sampled solutions. The effectiveness of the proposed algorithm is demonstrated through experimental validation, highlighting the potential of QC in solving complex equilibrium computation problems.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.
Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.
Quantum Annealing is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.