論文の概要: Do quantum linear solvers offer advantage for networks-based system of linear equations?

• arxiv url: http://arxiv.org/abs/2509.00913v1
• Date: Sun, 31 Aug 2025 15:55:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:03.458102
• Title: Do quantum linear solvers offer advantage for networks-based system of linear equations?
• Title（参考訳）: 量子線形解法は線形方程式のネットワークベースのシステムに有利か?
• Authors: Disha Shetty, Supriyo Dutta, Palak Chawla, Akshaya Jayashankar, Jordi Riu, Jan Nogue, K. Sugisaki, V. S. Prasannaa,
• Abstract要約: ネットワークベースの線形システム問題では、まずグラフから始まり、線形方程式の系に到達する。 指数関数的優位性(ベストグラフファミリ)を提供するグラフファミリと、サブ指数的ではあるが少なくとも優位性(グラフファミリ)を提供するグラフファミリを推奨する。 分析の範囲内では、検討対象のグラフファミリーのうち指数関数的な優位性を示すのはわずか4%である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this exploratory numerical study, we assess the suitability of Quantum Linear Solvers (QLSs) toward providing a quantum advantage for Networks-based Linear System Problems (NLSPs). NLSPs are of importance as they are naturally connected to real-world applications. In an NLSP, one starts with a graph and arrives at a system of linear equations. The advantage that one may obtain with a QLS for an NLSP is determined by the interplay between three variables: the scaling of condition number and sparsity functions of matrices associated with the graphs considered, as well as the function describing the system size growth. We recommend graph families that can offer potential for an exponential advantage (best graph families) and those that offer sub-exponential but at least polynomial advantage (better graph families), with the HHL algorithm considered relative to the conjugate gradient (CG) method. Within the scope of our analyses, we observe that only 4 percent of the 50 considered graph families offer prospects for an exponential advantage, whereas about 20 percent of the considered graph families show a polynomial advantage. Furthermore, we observe and report some interesting cases where some graph families not only fare better with improved algorithms such as the Childs-Kothari-Somma algorithm but also graduate from offering no advantage to promising a polynomial advantage, graph families that exhibit futile exponential advantage, etc. Given the limited number of graph families that one can survey through numerical studies, we discuss an interesting case where we unify several graph families into one superfamily, and show the existence of infinite best and better graphs in it. Lastly, we very briefly touch upon some practical issues that one may face even if the aforementioned graph theoretic requirements are satisfied, including quantum hardware challenges.
• Abstract（参考訳）: 本稿では,NLSP(Networks-based Linear System Problems)の量子優位性を実現するために,QLS(Quantum Linear Solvers)の適合性を評価する。 NLSPは、現実世界のアプリケーションと自然に結びついているため、重要である。 NLSP では、まずグラフから始まり、線形方程式の系に到達する。 NLSP に対する QLS で得られる利点は、3つの変数間の相互作用によって決定される。 本稿では,指数関数的優位性(ベストグラフファミリー)を付与できるグラフ群と,部分指数的だが少なくとも多項式的優位性(ベターグラフファミリー)を提供するグラフ群を,共役勾配(CG)法に対してHHLアルゴリズムを用いて推奨する。 分析の範囲内では,50のグラフファミリーのうち指数関数的優位性を示すのはわずか4%であり,約20%のグラフファミリーが多項式的優位性を示す。 さらに,数あるグラフファミリが,例えばChilds-Kothari-Sommaアルゴリズムのような改良アルゴリズムをうまく活用するだけでなく,多項式の利点を期待できないグラフファミリや,不活性指数的な優位性を示すグラフファミリなどのメリットを享受し,報告する。 数値的な研究を通じて探索できるグラフファミリの数が限られていることを考えると、いくつかのグラフファミリを1つのスーパーファミリに統一し、その中に無限の最良のグラフとより良いグラフが存在することを示す興味深いケースについて議論する。 最後に、上述したグラフ理論の要件が満たされたとしても、量子ハードウェアの課題を含む、実際に直面するいくつかの問題について簡単に触れる。

関連論文リスト

• What makes a good feedforward computational graph? [0.8370225749625163]
  フィードフォワード計算グラフの望ましい性質について検討し、忠実度と混合時間という2つの重要な相補的尺度を探索する。 我々の研究は、様々なグラフに対するメトリクスの振る舞いに関する理論的分析と、これらのメトリクスをトレーニングされたニューラルネットワークモデルの性能に関連付けることの両方から裏付けられている。
  論文  参考訳（メタデータ） (2025-02-10T18:26:40Z)
• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  共有インタラクション(SI)は、複数のノード間のノードのコントリビューションとインタラクションを定量化する。 GNNアーキテクチャを利用して、ノード埋め込みにおける相互作用の構造がグラフ予測のために保存されていることを示す。 任意の順序SIを正確に計算するための効率的なアプローチであるGraphSHAP-IQを導入する。
  論文  参考訳（メタデータ） (2025-01-28T13:37:44Z)
• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  大規模言語モデル(LLM)は、期待される推論能力と推論能力のために、AIコミュニティで再編成されている。 我々は、グラフのこのようなパラメトリック表現、グラフ法則は、LLMがグラフデータを入力として理解させるソリューションであると信じている。
  論文  参考訳（メタデータ） (2024-10-16T00:01:31Z)
• Cayley Graph Propagation [0.0]
  グラフニューラルネットワーク(GNN)は、オーバースカッシングに弱いと悪名高い。 本研究は, トランケーションが対流膨張特性に有害であることを示す。 完全ケイリーグラフ構造上の情報伝達手法であるCGPを提案する。
  論文  参考訳（メタデータ） (2024-10-04T13:32:34Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。 アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。 数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2024-05-26T08:17:13Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。 我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
  論文  参考訳（メタデータ） (2020-10-28T17:59:59Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  本稿では,グラフクラスタメンバシップを潜在因子とするDGVAE(Dirichlet Graph Variational Autoencoder)を提案する。 バランスグラフカットにおける低パス特性により、入力グラフをクラスタメンバシップにエンコードする、Heattsと呼ばれるGNNの新しい変種を提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:35:26Z)

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

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