Fugu-MT 論文翻訳(概要): Boosting Sparsity in Graph Decompositions with QAOA Sampling

論文の概要: Boosting Sparsity in Graph Decompositions with QAOA Sampling

arxiv url: http://arxiv.org/abs/2509.10657v1
Date: Fri, 12 Sep 2025 19:36:03 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-16 17:26:22.719359
Title: Boosting Sparsity in Graph Decompositions with QAOA Sampling
Title（参考訳）: QAOAサンプリングによるグラフ分解のスパシティ向上
Authors: George Pennington, Naeimeh Mohseni, Oscar Wallis, Francesca Schiavello, Stefano Mensa, Corey O'Meara, Giorgio Cortiana, Víctor Valls,
Abstract要約: 本稿では,フリーコレクティブ・フランク・ウルフ (FCFW) アルゴリズムに基づくハイブリッド量子古典最適化アルゴリズム E-FCFW を提案する。このようなサブルーチンをQAOAを用いて設計する方法を示す。以上の結果から,QAOAを用いたE-FCFWは,他の方法よりもスペーサー分解(平均および中央値)が一貫して発生することがわかった。
参考スコア（独自算出の注目度）: 0.44407890087827867
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the problem of decomposing a graph into a weighted sum of a small number of graph matchings. This problem arises in network resource allocation problems such as peer-to-peer energy exchange, and it is challenging to solve with current classical algorithms even for small instances. To address this problem, we propose a hybrid quantum-classical algorithm, E-FCFW, based on the Fully-Corrective Frank-Wolfe (FCFW) algorithm. In particular, E-FCFW extends FCFW by incorporating a matching-sampling subroutine that can be carried out classically or with a quantum approach. We show how to design such a subroutine using QAOA, which aims at solving a constrained discrete optimisation problem approximately to obtain solution-variety. We benchmark our approach on complete, bipartite, and heavy-hex graphs, conducting experiments using the Qiskit Aer state-vector simulator (9-25 qubits), the Qiskit Aer MPS simulator (52-76 qubits) and on IBM Kingston (52-111 qubits), demonstrating performance at a utility-scale quantum hardware level. Our results show that E-FCFW with QAOA consistently yields sparser decompositions (mean and median) than the other methods (random sampling and simulated annealing) for small complete and bipartite graphs. For large heavy-hex graphs with 50 and 70 nodes, E-FCFW with QAOA also outperforms the other methods in terms of approximation error. Our findings highlight a promising role for quantum subroutines in classical algorithms.
Abstract（参考訳）: グラフを少数のグラフマッチングの重み付け和に分解する問題を考察する。この問題は、ピアツーピアエネルギー交換のようなネットワークリソース割り当ての問題で発生し、小さなインスタンスでも現在の古典的アルゴリズムでは解決が難しい。この問題に対処するため,フリーコレクティブ・フランク・ウルフ (FCFW) アルゴリズムに基づくハイブリッド量子古典アルゴリズム E-FCFW を提案する。特に、E-FCFWは、古典的または量子的アプローチで実行できるマッチングサンプリングサブルーチンを組み込むことでFCFWを拡張している。このようなサブルーチンをQAOAを用いて設計する方法を示す。我々は,完全,二部グラフ,ヘビーヘックスグラフをベンチマークし,Qiskit Aer状態ベクトルシミュレータ(9-25キュービット),Qiskit Aer MPSシミュレータ(52-76キュービット),IBM Kingston(52-111キュービット)を用いて,実用規模の量子ハードウェアレベルでの性能を示す実験を行った。以上の結果から,QAOA を用いた E-FCFW はスペーサー分解(平均および中央値)を小完全および二部グラフの他の手法(ランダムサンプリングおよび模擬焼鈍)よりも一貫して得ることが示された。 50と70のノードを持つ大きなヘックスグラフの場合、QAOAを持つE-FCFWは近似誤差の点で他の手法よりも優れている。この結果から,古典的アルゴリズムにおける量子サブルーチンの役割が示唆された。

関連論文リスト

Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
論文参考訳（メタデータ） (2025-04-21T18:19:19Z)
Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。 The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
論文参考訳（メタデータ） (2024-06-25T09:02:31Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Phase-Binarized Spintronic Oscillators for Combinatorial Optimization, and Comparison with Alternative Classical and Quantum Methods [0.04660328753262073]
アイシングコンピューティングではPBOが提案されており、様々なデバイス技術を用いてPBOを実験的に実装している。このようなPBOを実装し, 4ノード重み付きグラフ上でのNP-Hard問題MaxCutを解くために, 4つの双極子結合型一様モードスピンホールナノ発振器(SHNO)のアレイを使用できることを示す。
論文参考訳（メタデータ） (2023-06-26T09:04:03Z)
An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。 QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文参考訳（メタデータ） (2023-02-09T07:47:06Z)
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)
Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文参考訳（メタデータ） (2022-03-23T18:00:03Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
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)

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

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