論文の概要: A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem

• arxiv url: http://arxiv.org/abs/2510.19835v1
• Date: Fri, 10 Oct 2025 14:24:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-26 16:57:26.513086
• Title: A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem
• Title（参考訳）: 量子インスピレーションによるスドクノズルの解法とMaxCut問題
• Authors: Max B. Zhao, Fei Li,
• Abstract要約: 擬似非制約二項最適化問題の解法として量子インスパイアされたアルゴリズムを提案し,評価する。 このアルゴリズムは、イジング・スピングラス・ハミルトンの基底状態の発見と数学的に等価である。 本研究では,公開資料から得られた中間レベルSudokuパズルに対して,その有効性を示す。
• 参考スコア（独自算出の注目度）: 4.421992085973174
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose and evaluate a quantum-inspired algorithm for solving Quadratic Unconstrained Binary Optimization (QUBO) problems, which are mathematically equivalent to finding ground states of Ising spin-glass Hamiltonians. The algorithm employs Matrix Product States (MPS) to compactly represent large superpositions of spin configurations and utilizes a discrete driving schedule to guide the MPS toward the ground state. At each step, a driver Hamiltonian -- incorporating a transverse magnetic field -- is combined with the problem Hamiltonian to enable spin flips and facilitate quantum tunneling. The MPS is updated using the standard Density Matrix Renormalization Group (DMRG) method, which iteratively minimizes the system's energy via multiple sweeps across the spin chain. Despite its heuristic nature, the algorithm reliably identifies global minima, not merely near-optimal solutions, across diverse QUBO instances. We first demonstrate its effectiveness on intermediate-level Sudoku puzzles from publicly available sources, involving over $200$ Ising spins with long-range couplings dictated by constraint satisfaction. We then apply the algorithm to MaxCut problems from the Biq Mac library, successfully solving instances with up to $251$ nodes and $3,265$ edges. We discuss the advantages of this quantum-inspired approach, including its scalability, generalizability, and suitability for industrial-scale QUBO applications.
• Abstract（参考訳）: 本研究では,等角スピングラスハミルトニアンの基底状態を求めるために数学的に等価な量子非拘束バイナリ最適化(QUBO)問題を解くための量子インスピレーション付きアルゴリズムを提案し,評価する。 このアルゴリズムはマトリックス生成状態(MPS)を用いてスピン構成の大きな重ね合わせをコンパクトに表現し、離散駆動スケジュールを利用してMPSを基底状態に導く。 それぞれのステップで、横磁場を組み込んだドライバーハミルトンは、スピンフリップを可能にし、量子トンネルを容易にするためにハミルトニアンの問題と組み合わせられる。 MPSは標準密度行列再正規化グループ (DMRG) 法を用いて更新され、スピンチェーンを横断する複数のスイープによってシステムのエネルギーを反復的に最小化する。 そのヒューリスティックな性質にもかかわらず、アルゴリズムは多種多様なQUBOインスタンスにまたがる、単なる最適解ではなく、グローバルなミニマを確実に特定する。 我々はまず,制約満足度によって予測される長距離結合を持つ200ドル以上のIsingスピンを含む,公開ソースからの中間レベルSudokuパズルの有効性を実証した。 次に、アルゴリズムをBik MacライブラリからMaxCut問題に適用し、最大251ドルのノードと3265ドルのエッジを持つインスタンスの解決に成功した。 産業用大規模QUBOアプリケーションに対するスケーラビリティ,一般化性,適合性など,この量子に着想を得たアプローチの利点について論じる。

関連論文リスト

• Max-Cut graph-driven quantum circuit design for planar spin glasses [0.0]
  スピングラスの基底状態を求めるためのグラフベースの手法を提案する。 我々は、最大カット法に基づいて、キュービットを異なるグループに整理するクラスタリング戦略を採用する。 本結果は,複雑な最適化問題に対処するハイブリッド量子古典法の可能性を明らかにするものである。
  論文  参考訳（メタデータ） (2025-04-16T14:00:32Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks [41.94295877935867]
  本稿では,三対角四角形非制約二元最適化問題の解法として量子インスピレーション付きテンソルネットワークアルゴリズムを提案する。 また、直列鎖内の一方の隣り合う相互作用を伴うより一般的な2次非制約離散最適化問題を解く。
  論文  参考訳（メタデータ） (2023-09-19T10:45:15Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。 我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。 この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
  論文  参考訳（メタデータ） (2023-06-10T23:28:13Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。 私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。 実際の量子コンピュータを用いて得られた結果について述べる。
  論文  参考訳（メタデータ） (2022-01-25T05:59:24Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Iterative Quantum Assisted Eigensolver [0.0]
  我々は、ハミルトニアン基底状態を近似するハイブリッド量子古典アルゴリズムを提供する。 我々のアルゴリズムは、現在の量子コンピュータに適した方法で、強力なKrylov部分空間法に基づいている。
  論文  参考訳（メタデータ） (2020-10-12T12:25:16Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。