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

• URL: http://arxiv.org/abs/2410.06429v2
• Date: Sat, 14 Dec 2024 23:16:22 GMT
• Title: A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game
• Authors: Alejandro Mata Ali, Edgar Mencia,
• Abstract summary: We present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game. We adapt this formulation for several particular cases of the problem, as Tents & Trees. We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.
• Score: 49.1574468325115
• License:
• Abstract: In this paper, we present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game, a version of the N-queens problem, for the Takuzu game (or Binairo), for the most recent LinkedIn game, Tango, and for its generalizations. We adapt this formulation for several particular cases of the problem, as Tents & Trees, by trying to optimise the number of variables and interactions, improving the possibility of applying it on quantum hardware by means of Quantum Annealing or the Quantum Approximated Optimization Algorithm (QAOA). We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.

Related papers

• Imperfect-Information Games on Quantum Computers: A Case Study in Skat [0.8437187555622164]
  We show how Quantum Computers can play a significant role in solving non-perfect information games. We show how Quantum Computers can play a significant role in solving these kind of games, using an example of the most popular German card game Skat.
  arXiv  Detail & Related papers  (2024-11-22T18:19:33Z)
• A QUBO Formulation for the Generalized Takuzu/LinkedIn Tango Game [49.1574468325115]
  We present a QUBO formulation for the Takuzu game ( Binaor Binairo), for the most recent LinkedIn game, Tango, and for its generalizations. We optimize the number of variables needed to solve the problem, making it suitable to be solved by quantum devices with fewer resources.
  arXiv  Detail & Related papers  (2024-10-13T13:49:56Z)
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems [0.0]
  Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
  arXiv  Detail & Related papers  (2023-11-16T09:19:01Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• QUBOs for Sorting Lists and Building Trees [3.0745536448480326]
  We show that the fundamental tasks of sorting lists and building search trees or heaps can be modeled as quadratic unconstrained binary optimization problems (QUBOs) We discuss how to construct such QUBOs and how to solve them using Hopfield nets or adiabatic) quantum computing.
  arXiv  Detail & Related papers  (2022-03-15T11:58:17Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Solving diner's dilemma game, circuit implementation, and verification on IBMQ simulator [0.0]
  We find the quantum strategy that gives maximum payoff for each diner without affecting the payoff and strategy of others. We present the circuit implementation for the game, design it on the IBM quantum simulator and verify the strategies in the quantum model.
  arXiv  Detail & Related papers  (2020-10-24T08:49:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.