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.<n>We adapt this formulation for several particular cases of the problem, as Tents & Trees.<n>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: http://creativecommons.org/licenses/by/4.0/
• 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)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  We apply variational quantum algorithm QAOA to a variant of satisfiability problem (SAT): Not-All-Equal SAT. We show that while the runtime of both solvers scales exponentially with the problem size, the scaling for QAOA is smaller for large enough circuit depths.
  arXiv  Detail & Related papers  (2024-01-05T15:11:24Z)
• 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)
• Quantum Computing for a Profusion of Postman Problem Variants [0.0]
  We study the viability of solving the Chinese Postman Problem, a graph routing optimization problem. We put emphasis on the explanation of how to convert such problems into quadratic unconstrained binary optimization problems. We also expand upon a previously discovered algorithm for solving the Chinese Postman Problem on a closed undirected graph.
  arXiv  Detail & Related papers  (2022-08-17T16:42:23Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• BILP-Q: Quantum Coalition Structure Generation [0.0]
  We propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP) We run BILP-Q on medium-size problems using a real quantum annealer (D-Wave)
  arXiv  Detail & Related papers  (2022-04-28T22:19:50Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)
• 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.