論文の概要: Optimum-Preserving QUBO Parameter Compression

• arxiv url: http://arxiv.org/abs/2307.02195v1
• Date: Wed, 5 Jul 2023 10:42:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-06 14:02:59.097897
• Title: Optimum-Preserving QUBO Parameter Compression
• Title（参考訳）: 最適保存QUBOパラメータ圧縮
• Authors: Sascha M\"ucke and Thore Gerlach and Nico Piatkowski
• Abstract要約: 本研究では,限定的な精度で2次最適化問題を解くことの意義について検討する。 問題の動的範囲は、歪みに対する問題の堅牢性に決定的な影響を及ぼすことを示す。 本稿では,最小エネルギー値の理論的境界に基づいて,与えられたQUBOインスタンスの動的範囲を削減する手法を提案する。
• 参考スコア（独自算出の注目度）: 0.9281671380673306
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic unconstrained binary optimization (QUBO) problems are well-studied, not least because they can be approached using contemporary quantum annealing or classical hardware acceleration. However, due to limited precision and hardware noise, the effective set of feasible parameter values is severely restricted. As a result, otherwise solvable problems become harder or even intractable. In this work, we study the implications of solving QUBO problems under limited precision. Specifically, it is shown that the problem's dynamic range has a crucial impact on the problem's robustness against distortions. We show this by formalizing the notion of preserving optima between QUBO instances and explore to which extend parameters can be modified without changing the set of minimizing solutions. Based on these insights, we introduce techniques to reduce the dynamic range of a given QUBO instance based on theoretical bounds of the minimal energy value. An experimental evaluation on random QUBO instances as well as QUBO-encoded Binary Clustering and Subset Sum problems show that our theoretical findings manifest in practice. Results on quantum annealing hardware show that the performance can be improved drastically when following our methodology.
• Abstract（参考訳）: quabo(quadratic unconstrained binary optimization)問題は、現代の量子アニーリングや古典的なハードウェアアクセラレーションを使ってアプローチできるため、よく研究されている。 しかし、精度の制限とハードウェアノイズのため、有効なパラメータ値のセットは厳しく制限されている。 その結果、解決可能な問題は難しくなり、あるいは難解になる。 本研究では,QUBO問題を限定的精度で解くことの意味について検討する。 具体的には、問題のダイナミックレンジが歪みに対する問題のロバスト性に重大な影響を与えていることが示されている。 本稿では、QUBOインスタンス間の最適保存の概念を定式化し、最小化ソリューションのセットを変更することなく拡張パラメータを変更できる方法を提案する。 これらの知見に基づいて、最小エネルギー値の理論的境界に基づいて、与えられたQUBOインスタンスの動的範囲を削減する手法を導入する。 ランダムなQUBOインスタンスと、QUBOに符号化されたバイナリクラスタリングおよびサブセットサム問題に関する実験的評価は、我々の理論的発見が実際に現れることを示している。 量子アニールハードウェアの結果から,本手法に従えば大幅な性能向上が期待できることがわかった。

関連論文リスト

• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。 本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。 本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
  論文  参考訳（メタデータ） (2024-07-29T17:13:01Z)
• Enhancing Hypergradients Estimation: A Study of Preconditioning and Reparameterization [49.73341101297818]
  双レベル最適化は、内部最適化問題の解に依存する外的目的関数を最適化することを目的としている。 外部問題の過次性を計算する従来の方法は、Implicit Function Theorem (IFT) を使うことである。 IFT法の誤差について検討し,この誤差を低減するための2つの手法を解析した。
  論文  参考訳（メタデータ） (2024-02-26T17:09:18Z)
• Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems [0.0]
  クローズストストリング問題(Closest String problem)は、生物情報学や符号化理論でよく見られるNP完全問題である。 2つのQUBOの定式化が提案されており、1つはもう1つに対してわずかに修正されている。 DWaveアナライザは、特定のプラットフォーム固有の関心事に対する最適なガイドラインを提供しながら使われてきた。
  論文  参考訳（メタデータ） (2023-10-19T16:03:25Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。 これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
  論文  参考訳（メタデータ） (2023-05-14T03:49:10Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) は、制約近似を避けるための概念的に単純で決定論的アプローチである。 CUQBは制約のある場合と制約のない場合の両方において従来のベイズ最適化よりも著しく優れることを示す。
  論文  参考訳（メタデータ） (2023-05-05T19:57:36Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  量子ゼノダイナミクスを用いて、不等式を含む複数の任意の制約で最適化問題を解く手法を提案する。 量子最適化のダイナミクスは、フォールトトレラントな量子コンピュータ上の制約内部分空間に効率的に制限できることを示す。
  論文  参考訳（メタデータ） (2022-09-29T18:00:40Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• The Variational Method of Moments [65.91730154730905]
  条件モーメント問題は、観測可能量の観点から構造因果パラメータを記述するための強力な定式化である。 OWGMMの変動最小値再構成により、条件モーメント問題に対する非常に一般的な推定器のクラスを定義する。 同じ種類の変分変換に基づく統計的推測のためのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-12-17T07:21:06Z)

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

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