論文の概要: Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization
- arxiv url: http://arxiv.org/abs/2203.12633v1
- Date: Wed, 23 Mar 2022 18:00:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-25 13:23:32.404164
- Title: Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization
- Title(参考訳): Q-FW: 二次二項最適化のためのハイブリッド古典量子フランクウルフ
- Authors: Alp Yurtsever and Tolga Birdal and Vladislav Golyanik
- Abstract要約: 本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
- 参考スコア(独自算出の注目度): 44.96576908957141
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a hybrid classical-quantum framework based on the Frank-Wolfe
algorithm, Q-FW, for solving quadratic, linearly-constrained, binary
optimization problems on quantum annealers (QA). The computational premise of
quantum computers has cultivated the re-design of various existing vision
problems into quantum-friendly forms. Experimental QA realizations can solve a
particular non-convex problem known as the quadratic unconstrained binary
optimization (QUBO). Yet a naive-QUBO cannot take into account the restrictions
on the parameters. To introduce additional structure in the parameter space,
researchers have crafted ad-hoc solutions incorporating (linear) constraints in
the form of regularizers. However, this comes at the expense of a
hyper-parameter, balancing the impact of regularization. To date, a true
constrained solver of quadratic binary optimization (QBO) problems has lacked.
Q-FW first reformulates constrained-QBO as a copositive program (CP), then
employs Frank-Wolfe iterations to solve CP while satisfying linear (in)equality
constraints. This procedure unrolls the original constrained-QBO into a set of
unconstrained QUBOs all of which are solved, in a sequel, on a QA. We use
D-Wave Advantage QA to conduct synthetic and real experiments on two important
computer vision problems, graph matching and permutation synchronization, which
demonstrate that our approach is effective in alleviating the need for an
explicit regularization coefficient.
- Abstract(参考訳): 本稿では,量子アニール(QA)上の二次的,線形に制約された2値最適化問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
量子コンピュータの計算前提は、様々な既存の視覚問題を量子フレンドリーな形式に再設計した。
実験的QA実現は、二次非制約バイナリ最適化(QUBO)として知られる特定の非凸問題を解くことができる。
しかし、naive-quboはパラメータの制限を考慮に入れることができない。
パラメータ空間にさらなる構造を導入するために、研究者たちは正規化子の形で(線形)制約を組み込んだアドホックな解法を開発した。
しかし、これは超パラメーターを犠牲にして、正規化の影響のバランスをとる。
現在までに、二次二元最適化(QBO)問題の真の制約付き解法は欠落している。
Q-FW は最初、制約付き QBO をコ陽性プログラム (CP) として再定義し、その後、線形(不等式)の制約を満足しながら CP を解くためにフランク=ウルフ反復を用いる。
この手順は、元の制約付きQBOを一連の制約なしQUBOにアンロールし、これらすべてを後続のQAで解決する。
我々はD-Wave Advantage QAを用いて、グラフマッチングと置換同期という2つの重要なコンピュータビジョン問題に対する合成および実実験を行い、この手法が明示的な正規化係数の必要性を軽減するのに有効であることを示す。
関連論文リスト
- Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE [0.0]
変分量子アプローチは、計算的に困難なタスクに対する準最適解を見つけることに大きな期待を示している。
この研究は、VQECと呼ばれるハイブリッド量子古典的アルゴリズムパラダイムを提案し、制約による最適化を扱う。
論文 参考訳(メタデータ) (2023-11-14T19:49:09Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
分解法の性能を古典的・量子的メタヒューリスティックスで評価する。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
論文 参考訳(メタデータ) (2023-10-04T12:14:56Z) - A hybrid algorithm for quadratically constrained quadratic optimization
problems [8.90266532129563]
一般QCQPに対する変分量子アルゴリズムを提案する。
量子状態の振幅に変数を符号化することにより、量子ビット数の要求は変数の次元と対数的にスケールする。
Max-Cutや最適電力フロー問題を含む典型的なQCQP問題に関する数値実験は、従来のアルゴリズムよりも優れた性能を示す。
論文 参考訳(メタデータ) (2023-09-19T12:19:12Z) - Quantum-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
最適なエッジサーバ配置とワークロード割り当てのための混合整数線形プログラミング(MILP)モデルを提案する。
既存の量子解法は制約のないバイナリプログラミング問題の解法に限られる。
数値実験により,エッジコンピューティングの複雑な最適化問題を解くために量子超越性を活用できることが実証された。
論文 参考訳(メタデータ) (2023-06-01T21:33:08Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳(メタデータ) (2021-05-06T17:59:38Z) - Machine Learning Framework for Quantum Sampling of Highly-Constrained,
Continuous Optimization Problems [101.18253437732933]
本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。
本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
論文 参考訳(メタデータ) (2021-05-06T02:22:23Z) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。
量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
論文 参考訳(メタデータ) (2021-03-12T20:58:41Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳(メタデータ) (2021-01-19T17:51:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。