論文の概要: 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グリッドの空間から一様にサンプリングすることができる。
本稿では,ヒューリスティックな解法と量子アニールを用いて記述法を示す。
関連論文リスト
- Quantum Backtracking in Qrisp Applied to Sudoku Problems [0.54445489321361]
任意のバックトラックインスタンスに対して量子ステップ演算子を実装するための詳細な命令を提供する。
深さ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) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳(メタデータ) (2021-04-19T17:21:54Z) - A new perspective of paramodulation complexity by solving massive 8
puzzles [0.4514386953429769]
スライディングパズルは、プレイヤーがボード上の特定のルートに沿ってスライドして特定のエンド構成に達するコンビネーションパズルです。
パラモジュレーションで得られる節数をカウントすることで、各パズルの難易度を評価できることが分かりました。
論文 参考訳(メタデータ) (2020-12-15T11:47:47Z) - TBA Equations and Quantization Conditions [0.0]
我々は,TBA方程式の壁交差挙動を研究するために,トレドによるグラフィカルな手法を開発した。
多くの例において、全順序のWKB周期に対する量子補正を計算する。
特に,この手法を用いて電位共鳴を決定できることを示す。
論文 参考訳(メタデータ) (2020-08-31T15:42:01Z) - Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem [0.0]
D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem。
断熱的量子最適化では、knapsackの最適充填に対応する解が得られない。
論文 参考訳(メタデータ) (2020-08-17T16:29:34Z) - SudoQ -- a quantum variant of the popular game [1.5229257192293197]
古典ゲームSudookuの量子バージョンであるSudoQを紹介する。
SudoQパズルの解集合は古典的な(可換な)設定よりもはるかに大きい。
論文 参考訳(メタデータ) (2020-05-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。