Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum-Assisted Computation for Nash Equilibrium in Bimatrix Games

Duong The Do, Duong Tung Nguyen

Published Feb 27, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.36227/techrxiv.177220387.76420680/v1

Related papers

Calculating Nash equilibrium on quantum annealers

Faisal Shah Khan, Olga Okrut, Keith Cannon +2 more

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.

arXiv:2112.12583•Annals of Operations Research•Jan 19, 2024•3 citations

Quantum algorithms for zero-sum games

Joran van Apeldoorn, András Gilyén

We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods. We are able to achieve speed-ups for both dense and sparse payoff matrices at the cost of a mildly increased dependence on the additive error compared to classical algorithms. In particular we can find $\varepsilon$-approximate Nash equilibrium strategies in complexity $\tilde{O}(\sqrt{n+m}/\varepsilon^3)$ and $\tilde{O}(\sqrt{s}/\varepsilon^{3.5})$ respectively, where $n\times m$ is the size of the matrix describing the game and $s$ is its sparsity. Our algorithms use the LP formulation of the problem and apply techniques developed in recent works on quantum SDP-solvers. We also show how to reduce general LP-solving to zero-sum games, resulting in quantum LP-solvers that have complexities $\tilde{O}(\sqrt{n+m}γ^3)$ and $\tilde{O}(\sqrt{s}γ^{3.5})$ for the dense and sparse access models respectively, where $γ$ is the relevant "scale-invariant" precision parameter

arXiv:1904.03180•Apr 5, 2019•18 citations

Quantum Annealing Combinatorial Optimization (QACO)

Jincheng Zhang

This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.

•Sep 3, 2026•0 citations

A Review of Quantum Supremacy in QUBO-Based Applications

Arim Ryou, Kiwoong Kim, Kyungtaek Jun

We propose a unified approach for reformulating diverse computational challenges into Quadratic Unconstrained Binary Optimization (QUBO) models and solving them via quantum annealing. By applying this framework across multiple domains, we demonstrate its flexibility in handling structurally different problems within a single mathematical formulation. The study highlights QUBO’s capability to exploit quantum parallelism, integrate regularization seamlessly, and address ill-posed inverse problems. These advantages position QUBO-based quantum annealing as a promising tool for large-scale optimization and reconstruction tasks, with strong potential for impact in scientific computing, engineering, and data-driven applications.

IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia)•Oct 27, 2025•0 citations

Finding the optimal Nash equilibrium in a discrete Rosenthal congestion game using the Quantum Alternating Operator Ansatz

Mark J. Hodson, Brendan Ruck, Hugh Ong +2 more

This paper establishes the tractability of finding the optimal Nash equilibrium, as well as the optimal social solution, to a discrete congestion game using a gate-model quantum computer. The game is of the type originally posited by Rosenthal in the 1970's. To find the optimal Nash equilibrium, we formulate an optimization problem encoding based on potential functions and path selection constraints, and solve it using the Quantum Alternating Operator Ansatz. We compare this formulation to its predecessor, the Quantum Approximate Optimization Algorithm. We implement our solution on an idealized simulator of a gate-model quantum computer, and demonstrate tractability on a small two-player game. This work provides the basis for future endeavors to apply quantum approximate optimization to quantum machine learning problems, such as the efficient training of generative adversarial networks using potential functions.

arXiv:2008.09505•Aug 20, 2020•0 citations

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

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.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•7 citations
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.
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.
We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods. We are able to achieve speed-ups for both dense and sparse payoff matrices at the cost of a mildly increased dependence on the additive error compared to classical algorithms. In particular we can find ε\varepsilonε-approximate Nash equilibrium strategies in complexity O~(n+m/ε3)\tilde{O}(\sqrt{n+m}/\varepsilon^3)O~(n+m​/ε3) and O~(s/ε3.5)\tilde{O}(\sqrt{s}/\varepsilon^{3.5})O~(s​/ε3.5) respectively, where n×mn\times mn×m is the size of the matrix describing the game and sss is its sparsity. Our algorithms use the LP formulation of the problem and apply techniques developed in recent works on quantum SDP-solvers. We also show how to reduce general LP-solving to zero-sum games, resulting in quantum LP-solvers that have complexities O~(n+mγ3)\tilde{O}(\sqrt{n+m}γ^3)O~(n+m​γ3) and O~(sγ3.5)\tilde{O}(\sqrt{s}γ^{3.5})O~(s​γ3.5) for the dense and sparse access models respectively, where γγγ is the relevant "scale-invariant" precision parameter
This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.
We propose a unified approach for reformulating diverse computational challenges into Quadratic Unconstrained Binary Optimization (QUBO) models and solving them via quantum annealing. By applying this framework across multiple domains, we demonstrate its flexibility in handling structurally different problems within a single mathematical formulation. The study highlights QUBO’s capability to exploit quantum parallelism, integrate regularization seamlessly, and address ill-posed inverse problems. These advantages position QUBO-based quantum annealing as a promising tool for large-scale optimization and reconstruction tasks, with strong potential for impact in scientific computing, engineering, and data-driven applications.
This paper establishes the tractability of finding the optimal Nash equilibrium, as well as the optimal social solution, to a discrete congestion game using a gate-model quantum computer. The game is of the type originally posited by Rosenthal in the 1970's. To find the optimal Nash equilibrium, we formulate an optimization problem encoding based on potential functions and path selection constraints, and solve it using the Quantum Alternating Operator Ansatz. We compare this formulation to its predecessor, the Quantum Approximate Optimization Algorithm. We implement our solution on an idealized simulator of a gate-model quantum computer, and demonstrate tractability on a small two-player game. This work provides the basis for future endeavors to apply quantum approximate optimization to quantum machine learning problems, such as the efficient training of generative adversarial networks using potential functions.
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.