論文の概要: Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence

• arxiv url: http://arxiv.org/abs/2504.08159v1
• Date: Thu, 10 Apr 2025 23:00:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 14:18:33.896225
• Title: Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence
• Title（参考訳）: NP問題に対するQUBO生成パラメータの最適化とD波収束への影響
• Authors: Toru Fujii, Koshi Komuro, Kaito Tomari,
• Abstract要約: 本研究では,3つの着色関連問題に対するQUBO式の解析を行った。 我々は,複雑な問題に対する独立パラメータの必要性と,公式特性と最適QUBOパラメータ値の導出関係を同定した。 我々は,独立なイジング係数が最適パラメータ調整に基づいて,正しい状態への収束をいかに促進するかを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: NP problems are closely related to practical optimization challenges but often suffer from exponential increases in computation time as problem sizes grow. Quantum annealing offers a promising approach to solve NP problems faster than classical methods, requiring cost functions and constraints to be expressed in QUBO format. However, setting QUBO coefficients often relies on empirical methods, particularly in scheduling problems where large values and intuition are needed. In this study, we analyzed QUBO formulas for three coloring-related problems: the graph coloring problem, the clique vertex cover problem, and the integer-length job scheduling problem. We identified the need for independent parameters for complex problems and derived relationships between formula characteristics and optimal QUBO parameter values. Using D-Wave quantum annealing, we validated these parameters and visualized the effects of parameter changes on states and eigenvalues in small spin problems. Additionally, we demonstrated how independent Ising coefficients enhance convergence to correct states based on optimal parameter adjustments.
• Abstract（参考訳）: NP問題は実際の最適化問題と密接に関連しているが、問題のサイズが大きくなるにつれて計算時間の指数的な増加に悩まされることが多い。 量子アニーリングは古典的手法よりも高速にNP問題を解くための有望なアプローチであり、QUBOフォーマットで表現するためにコスト関数と制約を必要とする。 しかし、QUBO係数の設定は経験的手法、特に大きな値や直観を必要とするスケジューリング問題に依存することが多い。 本研究では,グラフ着色問題,斜め頂点被覆問題,整数長ジョブスケジューリング問題という3つの着色問題に関するQUBO式を解析した。 我々は,複雑な問題に対する独立パラメータの必要性と,公式特性と最適QUBOパラメータ値の導出関係を同定した。 D-Wave量子アニールを用いてこれらのパラメータを検証し、小さなスピン問題における状態と固有値に対するパラメータ変化の影響を可視化した。 さらに,独立なイジング係数が最適パラメータ調整に基づいて,正しい状態への収束をいかに促進するかを実証した。

関連論文リスト

• One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
  NP完全制約最適化問題を解くための統一量子古典的枠組みを提案する。 QCPのパラメータ化アンサッツクラスは、生成したサブコーン内の最適値を常にキャプチャすることを示す。
  論文  参考訳（メタデータ） (2024-11-01T08:00:30Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Enhancing Hypergradients Estimation: A Study of Preconditioning and Reparameterization [49.73341101297818]
  双レベル最適化は、内部最適化問題の解に依存する外的目的関数を最適化することを目的としている。 外部問題の過次性を計算する従来の方法は、Implicit Function Theorem (IFT) を使うことである。 IFT法の誤差について検討し,この誤差を低減するための2つの手法を解析した。
  論文  参考訳（メタデータ） (2024-02-26T17:09:18Z)
• Solving Forward and Inverse Problems of Contact Mechanics using Physics-Informed Neural Networks [0.0]
  出力変換によって強化された混合変数定式化でPINNをデプロイし、ハード制約とソフト制約を強制する。 PINNは純粋部分方程式(PDE)の解法として、データ強化フォワードモデルとして、そして高速に評価可能なサロゲートモデルとして機能することを示す。
  論文  参考訳（メタデータ） (2023-08-24T11:31:24Z)
• Optimum-Preserving QUBO Parameter Compression [0.9281671380673306]
  本研究では,限定的な精度で2次最適化問題を解くことの意義について検討する。 問題の動的範囲は、歪みに対する問題の堅牢性に決定的な影響を及ぼすことを示す。 本稿では,最小エネルギー値の理論的境界に基づいて,与えられたQUBOインスタンスの動的範囲を削減する手法を提案する。
  論文  参考訳（メタデータ） (2023-07-05T10:42:05Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。 本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
  論文  参考訳（メタデータ） (2022-11-01T07:52:47Z)
• FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels [82.53569355337586]
  この研究は、有限なサポートを持つ一般パラメトリックカーネルを用いた時間点プロセス推論の効率的な解を提供する。 脳磁図(MEG)により記録された脳信号からの刺激誘発パターンの発生をモデル化し,その有効性を評価する。 その結果,提案手法により,最先端技術よりもパターン遅延の推定精度が向上することが示唆された。
  論文  参考訳（メタデータ） (2022-10-10T12:35:02Z)
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm [0.0]
  本稿では,Grover-driven,QAOA-prepared状態下でのハミルトニアンの期待値の計算をシステムサイズとは無関係に行うことができることを示す。 このような計算は、大きな問題の大きさの限界において、QAOAにおける角度のパフォーマンスと予測可能性に関する洞察を与えるのに役立つ。
  論文  参考訳（メタデータ） (2022-08-22T17:18:25Z)
• Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver [0.0]
  本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。 通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。 提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
  論文  参考訳（メタデータ） (2020-07-26T23:36:22Z)

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

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