論文の概要: On the hardness of quadratic unconstrained binary optimization problems
- arxiv url: http://arxiv.org/abs/2206.11689v1
- Date: Thu, 23 Jun 2022 13:29:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-08 07:14:49.126413
- Title: On the hardness of quadratic unconstrained binary optimization problems
- Title(参考訳): 二次非制約二元最適化問題の硬さについて
- Authors: Vrinda Mehta, Fengping Jin, Kristel Michielsen, Hans De Raedt
- Abstract要約: 厳密な列挙法を用いて、21変数未満の2次非制約二元最適化問題の解を特徴づける。
また、D-Wave Advantage 5.1量子アニールを用いて実験を行い、最大170変量2次最適化問題を解く。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We use exact enumeration to characterize the solutions of quadratic
unconstrained binary optimization problems of less than 21 variables in terms
of their distributions of Hamming distances to close-by solutions. We also
perform experiments with the D-Wave Advantage 5.1 quantum annealer, solving
many instances of up to 170-variable, quadratic unconstrained binary
optimization problems. Our results demonstrate that the exponents
characterizing the success probability of a D-Wave annealer to solve a QUBO
correlate very well with the predictions based on the Hamming distance
distributions computed for small problem instances.
- Abstract(参考訳): 厳密な列挙法を用いて、21変数未満の2次非制約二項最適化問題の解を、ハミング距離の分布からクローズバイ解へと特徴づける。
また,d波アドバンテージ5.1量子アニーラを用いた実験を行い,最大170変数の非拘束二元最適化問題を解く。
その結果,d-wave annealer が qubo を解く確率を特徴とする指数は,小さな問題に対して計算されたハミング距離分布に基づく予測と非常によく相関することがわかった。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳(メタデータ) (2023-11-16T09:19:01Z) - Advancing stable set problem solutions through quantum annealers [0.0]
グラフにおける安定セット問題の解法としてD波量子解法の性能を評価する。
ハイブリットソルバは良い結果が得られるのに対し、Quantum Processing Unitソルバは全体的には控えめなパフォーマンスを示している。
論文 参考訳(メタデータ) (2023-08-23T07:18:52Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - Convex Non-negative Matrix Factorization Through Quantum Annealing [0.6423239719448167]
我々は、D波量子アニールを用いて、凸非負行列分解アルゴリズム(凸-NMF)の量子バージョンを提供する。
D-wave 2000Qにおいて,本手法で使用する実データの最大数について検討した。
論文 参考訳(メタデータ) (2022-03-28T09:56:47Z) - Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing [0.5156484100374059]
量子異方体は, 実用的な最適化問題の解法として利用できることを示す。
量子異方体の性能を、最も洗練された数学的最適化解法の一つと比較する。
結果: 20チームで問題が発生した場合、QAは0.05秒で正確なソリューションを決定できた。
論文 参考訳(メタデータ) (2021-10-14T09:08:09Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳(メタデータ) (2021-05-05T03:36:00Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳(メタデータ) (2021-01-19T17:51:02Z) - Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
線形制約は、量子アニールで表現できる問題のサイズを減らす。
オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。
D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
論文 参考訳(メタデータ) (2020-12-18T09:48:28Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。