論文の概要: A Quantum Algorithm for $st$-Transport on Flat Connection Graphs

• arxiv url: http://arxiv.org/abs/2609.40231v1
• Date: Wed, 30 Sep 2026 17:30:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.183789
• Title: A Quantum Algorithm for $st$-Transport on Flat Connection Graphs
• Title（参考訳）: フラット接続グラフにおける$st$-transportの量子アルゴリズム
• Abstract要約: 我々は、エッジが量子演算を持つグラフへの無方向性の$st$-connectivityの一般化について研究する。 時間内に動作する$st$-transportに対して、境界付きエラー量子アルゴリズムを提供する。 また、$s$と$t$が接続されることを約束しても保持できる$(n)$の量子クエリローバウンドを証明します。
• 参考スコア（独自算出の注目度）: 0.07646713951724009
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a generalization of undirected $st$-connectivity to graphs whose edges carry quantum operations. Let $G=(V,E)$ be an undirected graph on $n$ vertices in which each edge $\{u,v\}$ is labeled by a unitary $U_{uv}\in\mathbb{C}^{k\times k}$, with $U_{vu}=U_{uv}^\dagger$. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices $u$ and $v$ is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever $s$ and $t$ are connected, transporting a state from $s$ to $t$ defines a unique unitary $U_s(t)$. Given states $|ψ_s\rangle,|ψ_t\rangle\in\mathbb{C}^k$ and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{$st$-transport problem} is to decide whether $s$ and $t$ are connected and, if so, to estimate the squared overlap between $U_s(t)|ψ_s\rangle$ and $|ψ_t\rangle$ to additive error $\varepsilon$. When $k=1$ and all labels are trivial, this is exactly undirected $st$-connectivity. We give a bounded-error quantum algorithm for $st$-transport that runs in time $\widetilde{O}(n/\varepsilon)$ and uses $O(\log n+\log k+\log(1/\varepsilon))$ space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an $Ω(n)$ quantum query lower bound that holds even when $s$ and $t$ are promised to be connected, so for constant $\varepsilon$ our algorithm is optimal up to polylogarithmic factors.
• Abstract（参考訳）: 我々は、エッジが量子演算を持つグラフへの無方向性の$st$-connectivityの一般化について研究する。 G=(V,E)$ を$n$頂点上の無向グラフとし、各辺 $\{u,v\}$ は、$U_{uv}\in\mathbb{C}^{k\times k}$ でラベル付けられ、$U_{vu}=U_{uv}^\dagger$ となる。 ラベルの順序付けられた積は、一対の頂点の$u$と$v$の間の任意の経路に沿って、その経路とは独立である。 等価に、接続は純粋ゲージ、すなわち自明な接続と同値である;そのようなグラフはまさにスペクトルグラフ理論の一貫性のある接続グラフであり、群同期のノイズレスインスタンスである。 その結果、$s$と$t$が接続されるたびに、$s$から$t$への状態転送は、ユニークなユニタリな$U_s(t)$を定義する。 対応するエッジユニタリをコヒーレントに適用しながら頂点の近傍を返却するオラクルが与えられたとき、 \emph{$st$-transport problem} は $s$ と $t$ が接続されているかどうかを判断し、もしそうであれば、$U_s(t)|\_s\rangle$ と $|\_t\rangle$ の2乗重なりを加法誤差 $\varepsilon$ と推定する。 k=1$ですべてのラベルが自明な場合、これは正確には$st$-connectivityではない。 我々は、$st$-transportに対して有界エラー量子アルゴリズムを与え、$\widetilde{O}(n/\varepsilon)$で実行し、$O(\log n+\log k+\log(1/\varepsilon))$ spaceを使用する。 我々は、トランスデューサを設計し、入力グラフにメトロポリス・ハスティングの重み付けを適用することでこれを行う。 また、$s$ と $t$ が連結されることが約束されたとしても保持される$Ω(n)$ の量子クエリローバウンドも証明するので、定数 $\varepsilon$ に対して、我々のアルゴリズムは多変数因子に最適である。

関連論文リスト

• Schur States, Average Mixing, and Counting Trees on Line Graphs' CTQW [0.0]
  有限単純グラフ上の複素数値エッジ重みの族を、ライングラフ上の連続時間量子ウォークから生じる$G$で紹介する。 構造的機構 -- $ellG$ の 2$ 固有空間 -- を同定し、通常の場合を超える一様可換状態を与える。
  論文  参考訳（メタデータ） (2026-05-03T16:31:26Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。 制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
  論文  参考訳（メタデータ） (2024-10-30T17:01:00Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。 我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
  論文  参考訳（メタデータ） (2021-12-15T03:45:39Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-10-29T07:35:46Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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