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

Reformulating Battleship Solitaire for Quantum Annealers

Vishmi Fernando, Anuradha Mahasinghe

Published Jan 1, 2022• 0 citations
Publisher

Abstract

\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.
DOI
10.0608/jisst.2022160443

Related papers

Battleship, tomography and quantum annealing

W. Riley Casper, Taylor Grimes

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.

European Journal of Applied Mathematics•Jan 16, 2023•0 citations

Binary Integer Reformulations for Adiabatic Quantum Annealing Hardware

Richard S. Barr, Toby Huskinson

Abstract It has been demonstrated that Binary Integer Programming (BIP) formulations can be reformulated to a corresponding quadratic unconstrained binary optimization (QUBO) problem. The reformulation allows for BIPs to run as QUBOs on adiabatic quantum annealing hardware. Current BIP to QUBO reformulation techniques propagate dense QUBO structures that are not ideal for current hardware where quantum bits, and the connections between them, are scarce. We propose a methodology for BIP to QUBO reformulation that results in a sparse QUBO that, when used to embed set-partitioning problems onto a D-Wave Pegasus topology, requires 80% fewer qubits and is embedded is 41 times faster. The same methodology for set-covering problems requires 77% fewer qubits and is embedded 26 times faster. We discuss the limitations of the technique and avenues for future extensions.

•Oct 23, 2023•0 citations

Conversion of Boolean and Integer FlatZinc Builtins to Quadratic or Linear Integer Problems

Wolf, Armin

Constraint satisfaction or optimisation models -- even if they are formulated in high-level modelling languages -- need to be reduced into an equivalent format before they can be solved by the use of Quantum Computing. In this paper we show how Boolean and integer FlatZinc builtins over finite-domain integer variables can be equivalently reformulated as linear equations, linear inequalities or binary products of those variables, i.e. as finite-domain quadratic integer programs. Those quadratic integer programs can be further transformed into equivalent Quadratic Unconstrained Binary Optimisation problem models, i.e. a general format for optimisation problems to be solved on Quantum Computers especially on Quantum Annealers.

arXiv:2404.12797•Apr 19, 2024•0 citations

Constraint Embedding for Solving Optimization Problems on Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2019•2 citations

Embedding Equality Constraints of Optimization Problems into a Quantum Annealer

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.

Algorithms•Apr 17, 2019•22 citations

A Survey of Quadratization Methods Used in QUBO Formulations and their Usage in Quantum and Digital Annealing

Geethika Prabhath, Anuradha Mahasinghe, Nalin Ranasinghe +1 more

Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.

Journal of Computer Science•Jan 1, 2026•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.
Abstract It has been demonstrated that Binary Integer Programming (BIP) formulations can be reformulated to a corresponding quadratic unconstrained binary optimization (QUBO) problem. The reformulation allows for BIPs to run as QUBOs on adiabatic quantum annealing hardware. Current BIP to QUBO reformulation techniques propagate dense QUBO structures that are not ideal for current hardware where quantum bits, and the connections between them, are scarce. We propose a methodology for BIP to QUBO reformulation that results in a sparse QUBO that, when used to embed set-partitioning problems onto a D-Wave Pegasus topology, requires 80% fewer qubits and is embedded is 41 times faster. The same methodology for set-covering problems requires 77% fewer qubits and is embedded 26 times faster. We discuss the limitations of the technique and avenues for future extensions.
Constraint satisfaction or optimisation models -- even if they are formulated in high-level modelling languages -- need to be reduced into an equivalent format before they can be solved by the use of Quantum Computing. In this paper we show how Boolean and integer FlatZinc builtins over finite-domain integer variables can be equivalently reformulated as linear equations, linear inequalities or binary products of those variables, i.e. as finite-domain quadratic integer programs. Those quadratic integer programs can be further transformed into equivalent Quadratic Unconstrained Binary Optimisation problem models, i.e. a general format for optimisation problems to be solved on Quantum Computers especially on Quantum Annealers.
Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.
Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.
Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.