論文の概要: Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard

• arxiv url: http://arxiv.org/abs/2412.14932v1
• Date: Thu, 19 Dec 2024 15:10:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 13:30:46.592634
• Title: Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard
• Title（参考訳）: スパースグラフにおける平衡成分と二部成分の存在の検証はQMA1-hardである
• Authors: Massimiliano Incudini, Casper Gyurik, Riccardo Molteni, Vedran Dunjko,
• Abstract要約: 符号付きグラフにおけるバランス成分の存在と符号なしグラフにおけるバイパートイト成分の存在をテストするなど、重要なスペクトル特性はQMA1-hardであることを示す。 両部テストの硬さは量子ハミルトニアン複雑性に関係しており、確率ハミルトニアンの固有空間に関連する別の性質のテストの例は、グラフのスパース入力モデルにおいて量子的に困難である。
• 参考スコア（独自算出の注目度）: 2.643652100761612
• License:
• Abstract: Determining whether an abstract simplicial complex, a discrete object often approximating a manifold, contains multi-dimensional holes is a task deeply connected to quantum mechanics and proven to be QMA1-hard by Crichigno and Kohler. This task can be expressed in linear algebraic terms, equivalent to testing the non-triviality of the kernel of an operator known as the Combinatorial Laplacian. In this work, we explore the similarities between abstract simplicial complexes and signed or unsigned graphs, using them to map the spectral properties of the Combinatorial Laplacian to those of signed and unsigned graph Laplacians. We prove that our transformations preserve efficient sparse access to these Laplacian operators. Consequently, we show that key spectral properties, such as testing the presence of balanced components in signed graphs and the bipartite components in unsigned graphs, are QMA1-hard. These properties play a paramount role in network science. The hardness of the bipartite test is relevant in quantum Hamiltonian complexity, as another example of testing properties related to the eigenspace of a stoquastic Hamiltonians are quantumly hard in the sparse input model for the graph.
• Abstract（参考訳）: 抽象的な単体複体、しばしば多様体を近似する離散対象が多次元の穴を含むかどうかを決定することは、量子力学と深く結びついており、クリニニョとコーラーによってQMA1-ハードであることが証明されたタスクである。 このタスクは線型代数的項で表すことができ、コンビニアル・ラプラシアン ( Combinatorial Laplacian) として知られる作用素の核の非自明性をテストするのと同値である。 本研究では,抽象単体錯体と符号付きグラフ,符号付グラフ,符号付グラフ,符号付グラフ,符号付グラフ,および符号付グラフのスペクトル特性の類似性について検討する。 我々の変換がこれらのラプラシア作用素への効率的なスパースアクセスを維持することを証明している。 その結果、符号付きグラフにおける平衡成分の存在や符号なしグラフにおける二部構造成分の存在をテストするなど、重要なスペクトル特性がQMA1-hardであることを示す。 これらの性質はネットワーク科学において重要な役割を担っている。 両部テストの硬さは量子ハミルトニアン複雑性に関係しており、確率ハミルトニアンの固有空間に関連する別の性質のテストの例は、グラフのスパース入力モデルにおいて量子的に困難である。

関連論文リスト

• Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs [0.0]
  バイパルタイト相互作用グラフを持つハイゼンベルク反強磁性体(AFM)は、計算量子モンテカルロ研究の一般的なターゲットである。 直列展開QMC法の基底状態変種を導入し、相互作用グラフ上のAFMの特別なクラスに$O(1)$-bipartite成分(スターライクな)を導入する。 我々は、Jerrumとシンクレアの正準経路法を用いて、関連するQMCマルコフ鎖(キュービット数の多項式時間)の高速混合を証明した。
  論文  参考訳（メタデータ） (2024-11-03T06:19:42Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。 具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。 我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Geometric quantum machine learning of BQP$^A$ protocols and latent graph classifiers [17.857341127079305]
  幾何学量子機械学習(GQML)は、効率的な解法プロトコルを学習するための問題対称性を埋め込むことを目的としている。 このレターでは、ブール関数の学習特性に関するサイモンの問題を考察し、これは教師なし回路分類問題と関係があることを示す。
  論文  参考訳（メタデータ） (2024-02-06T10:32:39Z)
• Graphical Symplectic Algebra [0.0]
  任意の体上のアフィンラグランジアンおよび共等方的関係のダガーコンパクトプロップに対して完全なプレゼンテーションを行う。 これは、親和性に制約された古典力学系と奇数素次元安定化器量子回路の両方に対して統一的なグラフィカル言語群を提供する。
  論文  参考訳（メタデータ） (2024-01-15T19:07:33Z)
• On the Equivalence of Graph Convolution and Mixup [70.0121263465133]
  本稿では,グラフ畳み込みと混合手法の関係について検討する。 2つの穏やかな条件の下では、グラフの畳み込みはMixupの特別な形式と見なすことができる。 グラフ畳み込みネットワーク(GCN)と単純化グラフ畳み込み(SGC)をミックスアップの形で表現できることを証明し、数学的にこの等価性を確立する。
  論文  参考訳（メタデータ） (2023-09-29T23:09:54Z)
• Probing multipartite entanglement through persistent homology [6.107978190324034]
  永続的ホモロジーによる多部交絡の研究を提案する。 永続ホモロジーは トポロジカルデータ分析で 使われるツールです 永続バーコードはそのトポロジ的要約よりもきめ細かな情報を提供することを示す。
  論文  参考訳（メタデータ） (2023-07-14T17:24:33Z)
• Clique Homology is QMA1-hard [0.0]
  simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
  論文  参考訳（メタデータ） (2022-09-23T18:14:16Z)
• Spectral embedding and the latent geometry of multipartite networks [67.56499794542228]
  多くのネットワークはマルチパーティションであり、ノードはパーティションに分割され、同じパーティションのノードは接続されない。 本稿では,高次元空間の分割特異的な低次元部分空間近傍のスペクトル埋め込みにより得られるノード表現について述べる。 スペクトル埋め込み後の追従ステップとして,周辺次元ではなく固有次元のノード表現を復元する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-08T15:52:03Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。 提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。 我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
  論文  参考訳（メタデータ） (2020-03-02T16:40:36Z)

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

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