A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game

This paper presents a versatile QUBO formulation for solving generalized versions of logic puzzles like the LinkedIn Queens, Takuzu, and Tango games, while also introducing new chess-based problems and optimizing the model for execution on quantum hardware via Quantum Annealing or QAOA.

The Gist

Imagine you are a master puzzle designer trying to teach a very specific, super-fast robot how to solve logic games. This paper is essentially a "instruction manual" written in a special code called QUBO (Quadratic Unconstrained Binary Optimization). Think of QUBO as a universal language that quantum computers understand, where every rule of a game is translated into a mathematical "energy cost." The robot's goal is to find the arrangement of pieces that results in the lowest possible energy (zero cost), which corresponds to the perfect solution.

Here is a breakdown of the paper's main ideas using everyday analogies:

1. The Core Concept: The "Energy" Game

The authors are taking popular logic puzzles and rewriting their rules so a quantum computer can solve them.

• The Metaphor: Imagine a hilly landscape where every possible arrangement of a puzzle is a point on the map. A "bad" arrangement (where rules are broken) is a high mountain peak. A "perfect" arrangement is a deep valley. The QUBO formula is a map that tells the quantum computer exactly how steep the hills are. The computer "rolls downhill" until it finds the deepest valley, which is the solution.

2. The Queens Games (LinkedIn & N-Queens)

The classic N-Queens problem asks you to place $N$ queens on a chessboard so none can attack each other.

• The Old Rule: Queens can't share a row, column, or any diagonal line.
• The LinkedIn Twist: The paper looks at a newer version (LinkedIn Queens) where the diagonal rule is "softer." Queens can't attack each other if they are right next to each other diagonally, but they can ignore queens further away. Also, the board is divided into colored regions, and you must place exactly one queen in each region.
• The Paper's Contribution: The authors created a flexible "recipe" (QUBO formulation) that can handle:
  • Standard N-Queens.
  • LinkedIn's softer rules.
  • Irregular board shapes (like a board with missing corners).
  • Boards that wrap around like a donut (Toroidal), where a piece leaving the right edge reappears on the left.
  • The "Tents & Trees" Game: They adapted their recipe for a game where you must place tents next to trees without any tents touching each other, even diagonally.

3. The "Chess Piece" Expansion

The authors realized their recipe wasn't just for Queens. They generalized it for any chess piece.

• The Coloured Chess Piece Problem: Imagine a board where different colored zones must each contain exactly one piece. The pieces can be Rooks, Bishops, or Knights, and they have different ways of moving. The goal is to fit as many as possible without them threatening each other.
• The Max Chess Pieces Problem: Here, the goal is simply to pack the board with as many pieces as possible without them attacking each other. The authors added a "reward" in their math formula: every time you successfully place a piece, the energy goes down a little bit, encouraging the computer to fill the board.

4. The Takuzu and Tango Games

These are grid-filling games (like Sudoku but with 0s and 1s, or Suns and Moons).

• The Rules:
  1. Every row and column must have an equal number of 0s and 1s.
  2. You can't have three of the same symbol in a row (no "000" or "111").
  3. Tango (LinkedIn's version): Adds special symbols between cells. An "=" means the two cells must be the same; an "x" means they must be different.
  4. Classic Takuzu: Adds a hard rule that no two rows can be identical, and no two columns can be identical.
• The Paper's Breakthrough:
  • They created a perfect QUBO recipe for Tango and the local rules of Takuzu.
  • The Hard Part: The "no identical rows" rule in classic Takuzu is tricky for quantum computers. The authors solved this by introducing "Witness Variables."
  • The Analogy: Imagine you have two rows of people and you need to prove they are different. You hire a "witness" for every pair of rows. The witness's job is to point to exactly one column where the two rows differ. If the witness can't find a difference, the penalty (energy) goes up. This allows the quantum computer to enforce the "no identical rows" rule perfectly without needing extra "slack" variables that waste resources.

5. Why This Matters (According to the Paper)

The paper doesn't claim these puzzles will cure diseases or predict the stock market. Instead, it claims to provide a universal toolkit for turning these specific logic puzzles into a format that quantum hardware (like D-Wave machines) or quantum algorithms (like QAOA) can actually run.

• Optimization: They managed to reduce the number of "variables" (the number of switches the computer has to flip) and interactions, making the problems smaller and more likely to fit on current quantum computers.
• Flexibility: Their formulas can handle weird board shapes, different numbers of pieces per row, and even boards that wrap around in circles.

In Summary:
The authors took a bunch of popular logic games (Queens, Tents, Takuzu, Tango) and wrote a single, adaptable "translation guide" that turns their rules into a language quantum computers can speak. They also invented a clever trick using "witnesses" to solve the hardest part of the Takuzu puzzle, ensuring the solution is mathematically perfect.

Technical Summary

1. Problem Definition

The paper addresses the challenge of solving various combinatorial logic puzzles using Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). These algorithms require problems to be formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The authors focus on generalizing and unifying the QUBO formulations for several specific games:

• N-Queens & LinkedIn Queens (LQueens): The classic N-Queens problem (placing $N$ queens on an $N \times N$ board without mutual attacks) and its LinkedIn variant, which relaxes diagonal constraints to only "adjacent" diagonals and adds region-based constraints (one queen per colored region).
• Takuzu (Binairo) & Tango: Logic puzzles involving filling a grid with 0s and 1s (or suns and moons) subject to constraints: equal numbers of 0s and 1s per row/column, no more than two identical consecutive values, and unique rows/columns (for Takuzu). Tango adds specific equality ("=") and inequality ("x") constraints between cells.
• Extensions: The paper also introduces formulations for Tents & Trees, Coloured Chess Piece Problems, and the Max Chess Pieces Problem.

2. Methodology

The core methodology involves translating the logical constraints of these games into quadratic penalty functions. The authors utilize standard binary variable identities ($x^2 = x$) to ensure all terms remain quadratic.

Key Technical Components:

• Constraint Penalties: The authors define standard penalty terms for:
  • Exact Counts: $(s - k)^2$ to enforce exactly $k$ active variables.
  • At-most-one: $\sum x_i x_j$ to prevent simultaneous activation.
  • Consecutive Values: Penalties for patterns like 000 or 111 using $(s-1)(s-2)$.
  • Equality/Inequality: $(x-y)^2$ and $(x+y-1)^2$.
• Conflict Graphs: Instead of treating diagonal constraints as complex regions, the authors model them as conflict graphs where edges represent forbidden simultaneous activations. This approach is shown to be more rigorous and efficient for N-Queens variations.
• Preprocessing & Variable Reduction:
  • Fixed Variables: Pre-placed pieces (clues) are fixed to 0 or 1, and their conflicting neighbors are fixed to 0, reducing the number of optimization variables.
  • Parity Reduction (Takuzu/Tango): For "=" and "x" constraints, the authors propose a Union-Find structure with parity. This reduces the number of free variables by expressing dependent cells as $x_v = y_C \oplus \pi_v$, where $y_C$ is a representative variable for a connected component.
• Handling Global Uniqueness (Takuzu): Classical Takuzu requires that no two rows or columns are identical. Standard local penalties cannot enforce this. The authors introduce Witness Variables ($u_{rsj}$) to certify that for every pair of rows $r, s$, there exists at least one column $j$ where they differ. This creates an exact QUBO formulation without slack variables, though it increases the variable count to $O(N^3)$.

3. Key Contributions

A. Generalized N-Queens Framework

The authors propose a unified QUBO formulation for N-Queens that supports:

• Variable numbers of queens per row/column.
• "Soft" regions (allowing 0 or 1 queen) and overlapping regions.
• Toroidal boards (where edges wrap around).
• Crucial Insight: They demonstrate that diagonal constraints are best modeled as pairwise conflict graphs rather than region-based "at-most-one" constraints, preserving the exactness of the solution space.

B. Exact Takuzu/Tango Formulation

• Local vs. Global: They distinguish between the "local" TTP (Takuzu/Tango Problem), which handles row balance and repetition constraints, and the "global" uniqueness constraint.
• Witness Variable Construction: They present a novel method to enforce row/column uniqueness in Takuzu using auxiliary witness variables. This allows for an exact QUBO formulation for classical Takuzu, which was previously difficult to achieve without relaxation or slack variables.
• Generalizations: They extend Takuzu to include unbalanced regularity (different counts of 0s/1s), diagonal repetition constraints, and long-distance equality/inequality symbols.

C. New Problem Definitions

• Coloured Chess Piece Problem: A generalization where different piece types (with different move sets) must be placed such that no piece threatens another, with one piece per colored region.
• Max Chess Pieces Problem: An optimization problem to place the maximum number of non-conflicting pieces on a board, formulated with a reward term ($-\sum w_{ij}x_{ij}$) and a conflict penalty.
• Exact Tents & Trees: They provide an exact QUBO for Tents & Trees using assignment variables ($y_{t,c}$) to link trees to tents, avoiding the inaccuracies of simplified relaxation methods.

4. Results and Theoretical Analysis

• Exactness: The paper proves that the proposed formulations are exact.
  • For LinkedIn Queens, preprocessing ensures the reduced QUBO matches the original problem's solution space.
  • For Takuzu, the witness variable method guarantees that any zero-energy state corresponds to a valid solution with unique rows and columns.
  • For Max Chess Pieces, the authors prove that if the penalty coefficient $\lambda$ for conflicts is greater than the maximum reward weight, no global minimizer will contain conflicting pieces.
• Complexity:
  • The standard local Takuzu formulation scales with the board size ($O(N^2)$ variables).
  • The exact Takuzu formulation with witness variables scales as $O(N^3)$ due to the $2N^2(N-1)$ auxiliary variables required to enforce uniqueness.
• Optimization: The use of "fractional" penalty terms (e.g., $(s - (q+0.5))^2$) is highlighted as a technique to reduce the number of variables (avoiding slack variables) while only introducing a constant energy offset that does not affect the minimizers.

5. Significance

• Quantum Hardware Readiness: By providing rigorous, exact QUBO formulations, the paper bridges the gap between abstract logic puzzles and practical implementation on quantum annealers (like D-Wave) and gate-based quantum computers (via QAOA).
• Unified Framework: The work demonstrates that diverse puzzle types (Queens, Takuzu, Tents) can be modeled under a single mathematical framework using conflict graphs and region constraints, facilitating the development of general-purpose quantum solvers for combinatorial problems.
• Benchmarking: These formulations serve as robust benchmarks for testing quantum algorithms, particularly for handling constraints, variable reduction, and the trade-off between solution exactness and qubit overhead (e.g., the cost of witness variables).
• Future Directions: The paper outlines paths for future research, including implementing these formulations on real quantum hardware, reducing the auxiliary variable overhead for global constraints, and exploring higher-order formulations (HOBO/QUDO).

In summary, this paper provides a comprehensive toolkit for translating complex, constraint-heavy logic games into QUBO format, with a specific emphasis on achieving exactness through advanced techniques like conflict graphs and witness variables, making these problems viable candidates for near-term quantum computing applications.