論文の概要: Convex Non-negative Matrix Factorization Through Quantum Annealing
- arxiv url: http://arxiv.org/abs/2203.15634v1
- Date: Mon, 28 Mar 2022 09:56:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-30 12:54:13.170225
- Title: Convex Non-negative Matrix Factorization Through Quantum Annealing
- Title(参考訳): 量子アニーリングによる凸非負行列分解
- Authors: Ahmed Zaiou, Basarab Matei, Youn\`es Bennani and Mohamed Hibti
- Abstract要約: 我々は、D波量子アニールを用いて、凸非負行列分解アルゴリズム(凸-NMF)の量子バージョンを提供する。
D-wave 2000Qにおいて,本手法で使用する実データの最大数について検討した。
- 参考スコア(独自算出の注目度): 0.6423239719448167
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we provide the quantum version of the Convex Non-negative
Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum
annealer. More precisely, we use D-wave 2000Q to find the low rank
approximation of a fixed real-valued matrix X by the product of two
non-negative matrices factors W and G such that the Frobenius norm of the
difference X-XWG is minimized. In order to solve this optimization problem we
proceed in two steps. In the first step we transform the global real
optimization problem depending on W,G into two quadratic unconstrained binary
optimization problems (QUBO) depending on W and G respectively. In the second
step we use an alternative strategy between the two QUBO problems corresponding
to W and G to find the global solution. The running of these two QUBO problems
on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q,
this embedding is limited by the number of qubits of D-wave 2000Q. We perform a
study on the maximum number of real data to be used by our approach on D-wave
2000Q. The proposed study is based on the number of qubits used to represent
each real variable. We also tested our approach on D-Wave 2000Q with several
randomly generated data sets to prove that our approach is faster than the
classical approach and also to prove that it gets the best results.
- Abstract(参考訳): 本稿では,D波量子アニールを用いたConvex非負行列分解アルゴリズム(Convex-NMF)の量子バージョンを提案する。
より正確には、D-wave 2000Q を用いて、X-XWG 差のフロベニウスノルムが最小となるような2つの非負行列係数 W と G の積による固定実数値行列 X の低階近似を求める。
この最適化問題を解決するために、我々は2つのステップで進める。
最初のステップでは、W,G に依存する大域的な実最適化問題を、それぞれ W と G に依存する2つの2次非制約バイナリ最適化問題 (QUBO) に変換する。
第2のステップでは、wとgに対応する2つのqubo問題の代替戦略を使用して、グローバルソリューションを見つけます。
D-wave 2000Q上のこれらの2つのQUBO問題の実行には、D-wave 2000Qのキメラグラフへの埋め込みが必要となるが、この埋め込みはD-wave 2000Qのキュービット数によって制限される。
本研究では,d-wave 2000qにおける実データ利用の最大数について検討する。
提案手法は,各実変数を表すために使用される量子ビットの数に基づく。
また、d-wave 2000qのアプローチをランダムに生成されたいくつかのデータセットでテストして、私たちのアプローチが従来のアプローチよりも高速であること、最高の結果が得られることを証明しました。
関連論文リスト
- Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。
この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。
D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
論文 参考訳(メタデータ) (2024-07-09T11:44:58Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-06-11T04:40:05Z) - Global optimization of MPS in quantum-inspired numerical analysis [0.0]
この研究は、ハミルトン方程式の最も低い固有状態の探索に焦点を当てている。
5つのアルゴリズムが導入された: 想像時間進化、最も急勾配降下、改良された降下、暗黙的に再起動されたアルノルニ法、密度行列再正規化群 (DMRG) 最適化。
論文 参考訳(メタデータ) (2023-03-16T16:03:51Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳(メタデータ) (2023-02-13T19:57:17Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳(メタデータ) (2022-11-01T07:52:47Z) - On the hardness of quadratic unconstrained binary optimization problems [0.0]
厳密な列挙法を用いて、21変数未満の2次非制約二元最適化問題の解を特徴づける。
また、D-Wave Advantage 5.1量子アニールを用いて実験を行い、最大170変量2次最適化問題を解く。
論文 参考訳(メタデータ) (2022-06-23T13:29:59Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Using machine learning for quantum annealing accuracy prediction [0.0]
我々は、ネットワーク分析、バイオインフォマティクス、計算化学において重要な応用を持つ古典的なNPハード問題であるMaximum Clique問題に焦点をあてる。
基本問題特性に基づいて機械学習分類モデルを訓練することにより、解硬度への寄与順に特定の特徴をランク付けすることができる。
そこで本研究では,D-Wave 2000Qアニールを用いて最適解法が解けるかどうかを予測できる簡易決定木を提案する。
論文 参考訳(メタデータ) (2021-05-31T19:14:37Z) - 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) - Solving Inequality-Constrained Binary Optimization Problems on Quantum
Annealer [0.966840768820136]
量子アニールを用いた不等式制約下でのバイナリ最適化問題の解法を提案する。
本研究では,乗算器の交互方向法を用いる。
本手法の計算時間は,高密度グラフ上で定義された様々なQKPに取り組み,精度の高い解法よりも高速であることがわかった。
論文 参考訳(メタデータ) (2020-12-11T04:30:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。