Fugu-MT 論文翻訳(概要): On the hardness of quadratic unconstrained binary optimization problems

論文の概要: 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 を解く確率を特徴とする指数は,小さな問題に対して計算されたハミング距離分布に基づく予測と非常によく相関することがわかった。

関連論文リスト

Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
論文参考訳（メタデータ） (2024-07-29T13:54:28Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
ゲートモデル量子コンピュータにおける二項最適化問題に対する包括的量子解法を提案する。最大127キュービットの問題の正しい解を一貫して提供する。我々は、古典的に非自明な2進最適化問題に対して、IBM量子コンピュータ上でこの解法をベンチマークする。
論文参考訳（メタデータ） (2024-06-03T19:08:01Z)
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)
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)

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