SudoQ -- a quantum variant of the popular game

• URL: http://arxiv.org/abs/2005.10862v1
• Date: Thu, 21 May 2020 19:19:51 GMT
• Title: SudoQ -- a quantum variant of the popular game
• Authors: Ion Nechita and Jordi Pillet
• Abstract summary: We introduce SudoQ, a quantum version of the classical game Sudoku. The solution set of SudoQ puzzles can be much larger than in the classical (commutative) setting.
• Score: 1.5229257192293197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce SudoQ, a quantum version of the classical game Sudoku. Allowing the entries of the grid to be (non-commutative) projections instead of integers, the solution set of SudoQ puzzles can be much larger than in the classical (commutative) setting. We introduce and analyze a randomized algorithm for computing solutions of SudoQ puzzles. Finally, we state two important conjectures relating the quantum and the classical solutions of SudoQ puzzles, corroborated by analytical and numerical evidence.

Related papers

• Quantum permutation puzzles with indistinguishable particles [0.0]
  We introduce quantum versions of permutation puzzles where the pieces of the puzzles are replaced with indistinguishable quantum particles. The moves in the puzzle are achieved by swapping or permuting the particles. We show that simply permuting the particles can be mapped to a classical permutation puzzle, even though the identical particles are entangled.
  arXiv  Detail & Related papers  (2024-10-29T17:39:13Z)
• A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game [49.1574468325115]
  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.
  arXiv  Detail & Related papers  (2024-10-08T23:54:54Z)
• A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
  We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity.
  arXiv  Detail & Related papers  (2024-10-07T12:29:27Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• A Simple QUBO Formulation of Sudoku [0.0]
  This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO) A QUBO instance with 729 variables is constructed, encoding a Sudoku grid with all constraints in place, which is then partially assigned to account for clues. The resulting instance can be solved with a Quantum Annealer, or any other strategy, to obtain the fully filled-out Sudoku grid.
  arXiv  Detail & Related papers  (2024-03-07T09:54:06Z)
• 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)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Desig [69.02688684221265]
  This paper presents an evolutionary algorithm, empowered by expert-knowledge informeds, for solving logical puzzles in video games efficiently. We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles.
  arXiv  Detail & Related papers  (2023-02-17T18:15:33Z)
• 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)
• 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)

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.