Fugu-MT 論文翻訳(概要): A Simple QUBO Formulation of Sudoku

論文の概要: A Simple QUBO Formulation of Sudoku

arxiv url: http://arxiv.org/abs/2403.04816v1
Date: Thu, 7 Mar 2024 09:54:06 GMT
ステータス: 処理完了
システム内更新日: 2024-03-11 21:52:52.266598
Title: A Simple QUBO Formulation of Sudoku
Title（参考訳）: すどくの簡単なQUBO式
Authors: Sascha M\"ucke
Abstract要約: 本稿では,擬似非制約二項最適化(QUBO)を用いた数独パズルの解法について述べる。 729変数を持つQUBOインスタンスが構築され、すべての制約のあるSudokuグリッドを符号化する。結果として得られるインスタンスは、量子アニールまたは他の戦略で解決でき、完全に満たされたスドク格子を得ることができる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO). To this end, 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. Moreover, as all valid solutions have the same energy, the QUBO instance can be used to sample uniformly from the space of valid Sudoku grids. We demonstrate the described method using both a heuristic solver and a Quantum Annealer.
Abstract（参考訳）: 本稿では,二分最適化(qubo)を用いた数独パズルの解法について述べる。この目的のために、729の変数を持つQUBOインスタンスが構築され、すべての制約のあるSudokuグリッドをコードし、手掛かりを部分的に考慮するように割り当てられる。結果として得られたインスタンスは量子アニーラや他の戦略で解くことができ、完全に満たしたsudokuグリッドを得ることができる。さらに、すべての有効な解が同じエネルギーを持つため、quboインスタンスは有効なsudokuグリッドの空間から一様にサンプリングすることができる。本稿では,ヒューリスティックな解法と量子アニールを用いて記述法を示す。

関連論文リスト

A QUBO Formulation for the Generalized LinkedIn Queens Game [49.1574468325115]
本稿では、LinkedIn Queens ゲームの一連の一般化を解決するために設計された QUBO の定式化について述べる。この定式化は、変数の数と相互作用を最適化しようと試みることで、問題の特定のケースに適応する。また,カラーチェスピース問題 (Coloured Chess Piece Problem) とマックスチェスピース問題 (Max Chess Pieces Problem) という2種類の新しい問題を,対応するQUBOの定式化とともに提示する。
論文参考訳（メタデータ） (2024-10-08T23:54:54Z)
An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
そこで本研究では,NP-Complete問題から準拘束的二項最適化問題への抽象化問題を符号化する手法を開発した。 QUBOの定式化により、QuantumやDigital Annealersといった新しいコンピューティングアーキテクチャを活用することができる。論証や議論の実施における古典的問題の正しさと適用性を証明するために,実験を行った。
論文参考訳（メタデータ） (2024-09-09T11:29:46Z)
Quantum Backtracking in Qrisp Applied to Sudoku Problems [0.52197339162908]
任意のバックトラックインスタンスに対して量子ステップ演算子を実装するための詳細な命令を提供する。深さnのバイナリバックトラックツリーの単一の制御ディフューザに対して、我々の実装では、たった6n+14$ CXゲートしか必要としない。これは、この一般化のコンパイル可能な実装の最初の例であり、量子ソフトウェア工学における重要な、そしてエキサイティングな進歩を示している。
論文参考訳（メタデータ） (2024-02-15T16:29:44Z)
Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
論文参考訳（メタデータ） (2023-03-26T18:53:51Z)
Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文参考訳（メタデータ） (2023-03-22T03:28:12Z)
One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文参考訳（メタデータ） (2023-01-05T11:05:22Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文参考訳（メタデータ） (2021-07-08T17:59:55Z)
Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文参考訳（メタデータ） (2021-05-06T17:59:38Z)
TBA Equations and Quantization Conditions [0.0]
我々は,TBA方程式の壁交差挙動を研究するために,トレドによるグラフィカルな手法を開発した。多くの例において、全順序のWKB周期に対する量子補正を計算する。特に,この手法を用いて電位共鳴を決定できることを示す。
論文参考訳（メタデータ） (2020-08-31T15:42:01Z)
SudoQ -- a quantum variant of the popular game [1.5229257192293197]
古典ゲームSudookuの量子バージョンであるSudoQを紹介する。 SudoQパズルの解集合は古典的な(可換な)設定よりもはるかに大きい。
論文参考訳（メタデータ） (2020-05-21T19:19:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。