論文の概要: A Max-Flow Min-Cut Theorem for Quantum Graphs
- arxiv url: http://arxiv.org/abs/2611.15508v1
- Date: Wed, 11 Nov 2026 14:04:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.162341
- Title: A Max-Flow Min-Cut Theorem for Quantum Graphs
- Title(参考訳): 量子グラフのための最大流動ミニカット理論
- Abstract要約: 我々は、この定義が最大フローのミンカット定理を満たすことを示す。
また、フローを通常のカットではなく一般化されたカットの双対として考えることがいかに自然であるかを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We propose natural definitions of cuts and flows for quantum graphs. For cuts we consider two notions: ordinary cuts, which partition the vertex set into two parts; and generalised cuts, defined as a continuous relaxation of the binary partition function. We show that our definitions satisfy a max-flow min-cut theorem: For any disjoint terminal sets $S$ and $T$, the maximum value of an $S$-$T$-flow of a quantum graph equals the minimum value of a generalised $S$-$T$ cut, while the minimum value of an ordinary $S$-$T$ cut can be larger. While for classical graphs the values of the minimum generalised cut and the minimum ordinary cut coincide---recovering the classical max-flow min-cut theorem---we also show how it is more natural to think of flows as duals of generalised cuts instead of ordinary cuts.
- Abstract(参考訳): 量子グラフに対するカットとフローの自然な定義を提案する。
カットに対しては、頂点集合を2つの部分に分割する通常のカットと、二項分割関数の連続緩和として定義される一般化カットという2つの概念を考える。
任意の非連結端末集合$S$と$T$に対して、量子グラフの$S$-$T$-フローの最大値は一般化された$S$-$T$カットの最小値と等しいが、通常の$S$-$T$カットの最小値が大きい。
古典グラフでは、最小の一般化されたカットの値と最小の通常のカットの値が一致する---古典的なマックスフローのミンカットの定理を復元する-----通常のカットの代わりに一般化されたカットの双対としてフローを考えることがいかに自然であるかも示している。
関連論文リスト
- Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。
コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
論文 参考訳(メタデータ) (2026-09-23T22:25:52Z) - Multi-entropy in random tensor networks [2.7233225545211375]
我々はRandom Network (RTN) 状態における Rényi multi-entropies $S(q)_n$ の評価について検討した。
Rényi index $n=2$ および任意のパーティ数$q$ の場合、マルチエントロピーはネットワークを通しての最小のマルチウェイカットによって決定されることを示す。
論文 参考訳(メタデータ) (2026-06-03T05:30:41Z) - Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
$dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか?
この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
論文 参考訳(メタデータ) (2026-05-06T17:53:20Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳(メタデータ) (2026-03-19T15:53:41Z) - A Lovász theta lower bound on Quantum Max Cut [2.0305676256390934]
我々は、グラフの量子マックスカットへの下界を、その補体のロヴシュ・テータ函数の観点から証明する。
境界は量子マックスカットに適用されたときの古典的境界よりも優れる。
論文 参考訳(メタデータ) (2025-12-23T12:53:40Z) - Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
統計物理学からの予測では、ブロックモデル(SBM)におけるコミュニティの回復は、上述の時間で可能であり、上述のケステンスティグム(KS)しきい値のみである。
Chinら(2025)は、最近、スパース体制では、非バックトラック経路を数えることにより、KS閾値以下でコミュニティの回復が可能であることを証明した。
論文 参考訳(メタデータ) (2025-09-19T09:53:56Z) - Finite-Time Information-Theoretic Bounds in Queueing Control [54.11376591632282]
本稿では, 待ち行列の待ち行列を, 待ち行列と待ち行列の双方で処理するネットワーク上のスケジューリング問題において, 待ち行列の総長を求める新しいポリシーを導出する。
これらの結果は「ドリフトオンリー」な手法の基本的な制限を明らかにし、待ち行列制御における原則的、非漸近的最適性への道を示す。
論文 参考訳(メタデータ) (2025-06-23T04:14:40Z) - Reflected entropy in random tensor networks III: triway cuts [0.0]
整数 R'enyi の反射エントロピーは、ネットワークを通しての最小三路切断によって決定されることを示す。
三角カット問題によって示唆される整数 R'enyi パラメータからの自然な外挿は、ホログラフィック予想 $S_R=2EW$ を意味する。
このことは、ホログラフィック状態における三部体の絡み合いの存在と、ビットスレッドによって動機付けられた二部体の絡み合い構造とのギャップに光を当てる。
論文 参考訳(メタデータ) (2024-09-25T18:00:00Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Quantum Max-Flow Min-Cut theorem [11.98034899127065]
量子最大流の新しい定義に対する量子最大流分法定理を確立する。
この結果は、量子最大フローと量子ミンカットの比が、次元$n$が無限大になる傾向にあるため、$$に収束することを示している。
論文 参考訳(メタデータ) (2021-10-03T02:11:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。