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

European Journal of Applied Mathematics

Battleship, tomography and quantum annealing

W. Riley Casper, Taylor Grimes

Published Jan 16, 2023• 0 citations
Publisher

Abstract

Abstract The classic game of Battleship involves two players taking turns attempting to guess the positions of a fleet of vertically or horizontally positioned enemy ships hidden on a $10\times 10$ grid. One variant of this game, also referred to as Battleship Solitaire, Bimaru or Yubotu, considers the game with the inclusion of X-ray data, represented by knowledge of how many spots are occupied in each row and column in the enemy board. This paper considers the Battleship puzzle problem: the problem of reconstructing an enemy fleet from its X-ray data. We generate non-unique solutions to Battleship puzzles via certain reflection transformations akin to Ryser interchanges. Furthermore, we demonstrate that solutions of Battleship puzzles may be reliably obtained by searching for solutions of the associated classical binary discrete tomography problem which minimise the discrete Laplacian. We reformulate this optimisation problem as a quadratic unconstrained binary optimisation problem and approximate solutions via a simulated annealer, emphasising the future practical applicability of quantum annealers to solving discrete tomography problems with predefined structure.

DOI
10.1017/s0956792522000377

Related papers

Reformulating Battleship Solitaire for Quantum Annealers

Vishmi Fernando, Anuradha Mahasinghe

\n\nWe investigate the possibility of reformulating the puzzle of Battleship Solitaire as a quadratic unconstrained binary optimization problem, in order for the problem to be acceptable to a quantum annealer. Starting from a linear integer programming formulation, we develop two binary quadratic programs and compare them.

•Jan 1, 2022•0 citations

Utilizing Quantum Annealing in Computed Tomography Image Reconstruction

Kilian Dremel, Dimitri Prjamkov, Markus Firsching +6 more

One of the primary difficulties in computed tomography (CT) is reconstructing cross-sectional images from measured projections of a physical object. There exist several classical methods for this task of generating a digital representation of the object, including filtered backprojection or simultaneous algebraic reconstruction technique. Our research aims to explore the potential of quantum computing in the field of industrial X-ray transmission tomography. Specifically, this work focuses on the application of a method similar to that proposed by Nau et al. (2023) on real CT data to demonstrate the feasibility of quadratic-unconstrained-binary-optimization-based tomographic reconstruction. Starting with simulated phantoms, results with simulated annealing as well as real annealing hardware are shown, leading to the application on measured cone-beam CT data. The results demonstrate that tomographic reconstruction using quantum annealing is feasible for both simulated and real-world applications. Yet, current limitations—involving the maximum processable size and bit depth of voxel values of the images, both correlated with the number of densely connected qubits within the annealing hardware—imply the need of future research to further improve the results. This approach, despite its early stage, has the potential to enable more sophisticated reconstructions, providing an alternative to traditional classical methods.

IEEE Transactions on Quantum Engineering•Jan 1, 2025•4 citations

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

Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing

Sota Hirama, Masayuki Ohzeki

We propose an efficient algorithm that combines column generation and quantum annealing to solve binary quadratic problems. Binary quadratic problems are difficult to solve because they are NP-hard. An attempt to solve binary quadratic problems efficiently by column generation has been studied, but it demands successively solving quadratic unconstrained binary optimization problems. We solve the bottleneck by using quantum annealing or simulated annealing. Our results demonstrate a good approximate solution obtained in 2.7 to 1000 times shorter computational time to use column generation and quantum annealing to solve binary quadratic problems than the existing fast solver.

arXiv:2307.05966•Journal of the Physical Society of Japan•Oct 19, 2023•16 citations

Quantum-Assisted Computation for Nash Equilibrium in Bimatrix Games

Duong The Do, Duong Tung Nguyen

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.

•Feb 27, 2026•0 citations

Optimization with Quantum Annealing Machines

Samuel Deleplanque

Quantum annealing is a method based on simulated annealing where temperature variations are replaced by quantum fluctuations that cause qubit state transitions. ISING problems and Quadratic Unconstrained Binary Optimization problems (QUBO) can be tackled by quantum annealing-based machines. We can link the interconnected qubits of the machine and the binaries of our model: qubits are binary variables and each pair of them linked by a coupler has a strong impact on the equality or the non-equality of the two binaries of the associated pair. Quantum annealing is based on the fact that any system tends to seek its minimum energy state. Starting from qubits in a state of superposition where all the solutions to the problem are fairly represented, the machine will apply a magnetic field by targeting the qubits and couplers in such a way as to make their value energetically favorable in the direction of optimization (minimization). For the coupled qubits, it is the quadratic products of the binary variables that are considered here and the physical system will make it energetically favorable for them to take (or not) the same values. To work on these machines based on quantum annealing in order to solve optimization problems with constraints, the latter must be relaxed while penalizing the Objective function. After presenting the case of the Max-Cut problem, we will look at such constrained problems.

•Jul 3, 2022•0 citations
Abstract The classic game of Battleship involves two players taking turns attempting to guess the positions of a fleet of vertically or horizontally positioned enemy ships hidden on a 10×1010\times 1010×10 grid. One variant of this game, also referred to as Battleship Solitaire, Bimaru or Yubotu, considers the game with the inclusion of X-ray data, represented by knowledge of how many spots are occupied in each row and column in the enemy board. This paper considers the Battleship puzzle problem: the problem of reconstructing an enemy fleet from its X-ray data. We generate non-unique solutions to Battleship puzzles via certain reflection transformations akin to Ryser interchanges. Furthermore, we demonstrate that solutions of Battleship puzzles may be reliably obtained by searching for solutions of the associated classical binary discrete tomography problem which minimise the discrete Laplacian. We reformulate this optimisation problem as a quadratic unconstrained binary optimisation problem and approximate solutions via a simulated annealer, emphasising the future practical applicability of quantum annealers to solving discrete tomography problems with predefined structure.
One of the primary difficulties in computed tomography (CT) is reconstructing cross-sectional images from measured projections of a physical object. There exist several classical methods for this task of generating a digital representation of the object, including filtered backprojection or simultaneous algebraic reconstruction technique. Our research aims to explore the potential of quantum computing in the field of industrial X-ray transmission tomography. Specifically, this work focuses on the application of a method similar to that proposed by Nau et al. (2023) on real CT data to demonstrate the feasibility of quadratic-unconstrained-binary-optimization-based tomographic reconstruction. Starting with simulated phantoms, results with simulated annealing as well as real annealing hardware are shown, leading to the application on measured cone-beam CT data. The results demonstrate that tomographic reconstruction using quantum annealing is feasible for both simulated and real-world applications. Yet, current limitations—involving the maximum processable size and bit depth of voxel values of the images, both correlated with the number of densely connected qubits within the annealing hardware—imply the need of future research to further improve the results. This approach, despite its early stage, has the potential to enable more sophisticated reconstructions, providing an alternative to traditional classical methods.
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 propose an efficient algorithm that combines column generation and quantum annealing to solve binary quadratic problems. Binary quadratic problems are difficult to solve because they are NP-hard. An attempt to solve binary quadratic problems efficiently by column generation has been studied, but it demands successively solving quadratic unconstrained binary optimization problems. We solve the bottleneck by using quantum annealing or simulated annealing. Our results demonstrate a good approximate solution obtained in 2.7 to 1000 times shorter computational time to use column generation and quantum annealing to solve binary quadratic problems than the existing fast solver.
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 is a method based on simulated annealing where temperature variations are replaced by quantum fluctuations that cause qubit state transitions. ISING problems and Quadratic Unconstrained Binary Optimization problems (QUBO) can be tackled by quantum annealing-based machines. We can link the interconnected qubits of the machine and the binaries of our model: qubits are binary variables and each pair of them linked by a coupler has a strong impact on the equality or the non-equality of the two binaries of the associated pair. Quantum annealing is based on the fact that any system tends to seek its minimum energy state. Starting from qubits in a state of superposition where all the solutions to the problem are fairly represented, the machine will apply a magnetic field by targeting the qubits and couplers in such a way as to make their value energetically favorable in the direction of optimization (minimization). For the coupled qubits, it is the quadratic products of the binary variables that are considered here and the physical system will make it energetically favorable for them to take (or not) the same values. To work on these machines based on quantum annealing in order to solve optimization problems with constraints, the latter must be relaxed while penalizing the Objective function. After presenting the case of the Max-Cut problem, we will look at such constrained problems.