論文の概要: Investigating the Relation Between Problem Hardness and QUBO Properties

• arxiv url: http://arxiv.org/abs/2404.02751v1
• Date: Wed, 3 Apr 2024 13:53:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 17:11:28.114455
• Title: Investigating the Relation Between Problem Hardness and QUBO Properties
• Title（参考訳）: 問題硬度とQUBO特性の関係の検討
• Authors: Thore Gerlach, Sascha Mücke,
• Abstract要約: この研究は、問題のプロパティ間の関係にいくつかの光を当てることを目的としている。 機械学習、すなわちクラスタリングとサポートベクトルマシン(SVM)のトレーニングからよく知られた2つの問題を解析する。 経験的評価は興味深い洞察を与え、クラスタリングQUBOインスタンスのスペクトルギャップがデータ分離可能性と正の相関を示す一方で、SVM QUBOでは逆が真であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems, integral to various scientific and industrial applications, often vary significantly in their complexity and computational difficulty. Transforming such problems into Quadratic Unconstrained Binary Optimization (QUBO) has regained considerable research attention in recent decades due to the central role of QUBO in Quantum Annealing. This work aims to shed some light on the relationship between the problems' properties. In particular, we examine how the spectral gap of the QUBO formulation correlates with the original problem, since it has an impact on how efficiently it can be solved on quantum computers. We analyze two well-known problems from Machine Learning, namely Clustering and Support Vector Machine (SVM) training, regarding the spectral gaps of their respective QUBO counterparts. An empirical evaluation provides interesting insights, showing that the spectral gap of Clustering QUBO instances positively correlates with data separability, while for SVM QUBO the opposite is true.
• Abstract（参考訳）: 様々な科学的・工業的応用に不可欠な組合せ最適化問題は、その複雑さと計算の難しさにおいて大きく異なる。 量子アニーリングにおけるQUBOの中心的役割により、これらの問題を準拘束的二項最適化(QUBO)に変換することは近年、かなりの研究の注目を集めている。 この研究は、問題のプロパティ間の関係にいくつかの光を当てることを目的としている。 特に,QUBO定式化のスペクトルギャップが,量子コンピュータ上でどのように効率的に解けるかに影響を及ぼすため,元の問題とどのように相関するかを検討する。 機械学習からよく知られた2つの問題、すなわちクラスタリングとサポートベクトルマシン(SVM)のトレーニングから、それぞれのQUBOのスペクトルギャップについて分析する。 経験的評価は興味深い洞察を与え、クラスタリングQUBOインスタンスのスペクトルギャップがデータ分離可能性と正の相関を示す一方で、SVM QUBOでは逆が真であることを示す。

関連論文リスト

• Solving the Turbine Balancing Problem using Quantum Annealing [0.0]
  本稿では, 量子コンピューティングを用いて, タービンバランス問題の解法について述べる。 小さいが関連するインスタンスは業界で発生し、初期の量子コンピューティングベンチマークではこの問題が興味深い。
  論文  参考訳（メタデータ） (2024-05-10T11:52:40Z)
• Trade-off between Bagging and Boosting for quantum separability-entanglement classification [0.0]
  量子分離性問題に対するランダムアンダーサンプリングブースターCHA(RUSBCHA)の長所と短所を比較した。 結果は、RUSBCHAがBCHAアプローチに代わるものであることを示唆している。
  論文  参考訳（メタデータ） (2024-01-22T15:29:35Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• Quantum Vision Clustering [10.360126989185261]
  本稿では,Adiabatic quantum computing を用いた解法に適した最初のクラスタリング定式化を提案する。 提案手法は,最先端の最適化手法と比較して高い競合性を示す。 この研究は、現在世代の実量子コンピュータにおけるクラスタリング問題の解決可能性を示す。
  論文  参考訳（メタデータ） (2023-09-18T16:15:16Z)
• Biclustering Algorithms Based on Metaheuristics: A Review [0.0]
  Biclusteringは、データマトリックス内の行と列を同時にクラスタする、教師なしの機械学習技術である。 重要な双クラスターを見つけることは最適化問題として定式化できるNPハード問題である。 複雑な最適化問題を妥当な時間で解く探索能力のために、様々なメタヒューリスティックが双クラスタリング問題に適用されている。
  論文  参考訳（メタデータ） (2022-03-30T12:16:32Z)
• Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees [115.08148491584997]
  本稿では,MASHA1 と MASHA2 の圧縮通信による変分不等式とサドル点問題の解法について理論的に検討した。 新しいアルゴリズムは双方向圧縮をサポートし、バッチの設定や、クライアントの部分的な参加を伴うフェデレーション学習のために修正することもできる。
  論文  参考訳（メタデータ） (2021-10-07T10:04:32Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。 本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
  論文  参考訳（メタデータ） (2021-09-06T14:35:15Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。 本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
  論文  参考訳（メタデータ） (2021-05-06T02:22:23Z)
• Bottleneck Problems: Information and Estimation-Theoretic View [2.7793394375935088]
  情報ボトルネック(IB)とプライバシファンネル(PF)は、密接に関連する2つの最適化問題である。 特定の関数の下位エンベロープや上部エンベロープを等価に表現することで、閉形式のボトルネック問題を評価する方法を示す。
  論文  参考訳（メタデータ） (2020-11-12T05:16:44Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  我々は、CQED実験にインスパイアされたオープン量子力学を、2つの非可換リンドブラッド作用素を用いて解析する。 Fock状態は、決定的な結合をデコヒーレンスにデコヒーレンスする最も堅牢な状態のままであることを示す。
  論文  参考訳（メタデータ） (2020-01-29T14:15:19Z)

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

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