論文の概要: Clustering-Based Sub-QUBO Extraction for Hybrid QUBO Solvers

• arxiv url: http://arxiv.org/abs/2502.16212v1
• Date: Sat, 22 Feb 2025 12:29:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:53:45.835428
• Title: Clustering-Based Sub-QUBO Extraction for Hybrid QUBO Solvers
• Title（参考訳）: クラスタリングに基づくハイブリッドQUBO解のサブQUBO抽出
• Authors: Wending Zhao, Gaoxiang Tang,
• Abstract要約: 量子近似最適化アルゴリズム(QAOA)は2次非制約バイナリ最適化(QUBO)問題を解決するために用いられる。 ノイズの多い中間量子(NISQ)デバイスを活用して大規模なQUBO問題を解決するには、完全な問題を複数のサブプロブレムに分解する1つの方法がある。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) can be used to solve quadratic unconstrained binary optimization (QUBO) problems. However, the size of the solvable problem is limited by the number of qubits. To leverage noisy intermediate-scale quantum (NISQ) devices to solve large-scale QUBO problems, one possible way is to decompose the full problem into multiple sub-problems, which we refer to as the Sub-QUBO Formalism. In this work, we enhance this formalism by proposing a sub-QUBO extraction protocol. To do so, we define a measure to quantify correlations between variables and use it to build a correlation matrix. This matrix serves as the input for clustering algorithms to group variables. Variables belonging to the same group form sub-QUBOs and are subsequently solved using QAOA. Our numerical analysis on several classes of randomly generated QUBO problems demonstrates that this grouping method outperforms previous approaches in terms of objective function values, while maintaining a comparable number of quantum subroutine calls. This method offers wide applicability for solving QUBO problems on NISQ devices.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は2次非制約バイナリ最適化(QUBO)問題を解決するために用いられる。 しかし、解ける問題のサイズは、キュービットの数によって制限される。 ノイズの多い中間量子(NISQ)デバイスを利用して大規模なQUBO問題を解くには、完全な問題を複数のサブプロブレムに分解し、これをサブQUBO形式主義と呼ぶ。 本研究では,サブQUBO抽出プロトコルを提案することにより,この形式性を高める。 そのため、変数間の相関を定量化し、それを用いて相関行列を構築する尺度を定義する。 この行列は、グループ変数に対するクラスタリングアルゴリズムの入力として機能する。 同じグループに属する変数はサブQUBOを形成し、その後QAOAを用いて解決される。 ランダムに生成したQUBO問題のいくつかのクラスに関する数値解析により、このグループ化法は、同じ数の量子サブルーチン呼び出しを維持しながら、目的関数値の点で従来の手法よりも優れていることを示した。 NISQデバイス上でのQUBO問題に対する広範な適用性を提供する。

関連論文リスト

• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。 提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
  論文  参考訳（メタデータ） (2024-12-18T12:05:18Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor [0.0]
  本稿では、MILP(Mixed Linear Programming)を解くためのハイブリッド古典量子法を提案する。 我々は、MILPをマスター問題(MP)とサブプロブレム(SP)に分割するためにベンダー分解(BD)を適用する。 我々のMILPからQUBOへの変換は、関連する連続変数の上限を狭め、必要量子ビット数とアルゴリズムの収束に肯定的に影響を及ぼす。
  論文  参考訳（メタデータ） (2024-02-08T15:33:09Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Variational Amplitude Amplification for Solving QUBO Problems [0.0]
  本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。 我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
  論文  参考訳（メタデータ） (2023-01-31T14:33:40Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Hybrid Quantum-Classical Unit Commitment [0.0]
  本稿では、単位コミットメント(UC)と呼ばれる基本電力系統問題を解決するためのハイブリッド量子古典アルゴリズムを提案する。 シミュレーション環境としてIBM Qシステム上でのQiskitを用いて,提案アルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2022-01-07T01:48:58Z)
• 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)
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates [14.905085636501438]
  問題のインスタンスの集合に関するソルバデータから学習することで,quboソルバのサロゲートモデルを構築する。 このようにして、インスタンスの共通構造とそれらの解決者との相互作用を捉えることができ、ペナルティパラメータを適切に選択することができる。 qrossは分散型データセットや様々な種類のquboソルバによく一般化されている。
  論文  参考訳（メタデータ） (2021-03-19T09:06:12Z)

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

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