論文の概要: Superadditivity of classical communication over quantum channels via random and deterministic permutations
- arxiv url: http://arxiv.org/abs/2608.25961v1
- Date: Wed, 26 Aug 2026 16:21:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-27 14:15:15.899364
- Title: Superadditivity of classical communication over quantum channels via random and deterministic permutations
- Title（参考訳）: ランダムおよび決定論的置換による量子チャネル上の古典的通信の超付加性
- Abstract要約: ハールランダム性は、非加法性に責任を負う極限幾何学を変更することなく、ランダムな置換に置き換えることができる。
単純な閉形式や実際計算可能な反例を見つけることは、依然として開である。
N le 5.422times 10116216] の集合に作用する57,836,025の置換の有限次元が存在し、関連するチャネルは非付加性を示す。
- 参考スコア（独自算出の注目度）: 2.1485350418225244
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Since Hastings' proof of superadditivity of classical communication over quantum channels, considerable effort has been devoted to finding a structural explanation of this phenomenon that was originally established by concentration of measure for Haar random unitaries. The main observation of this work is that Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity. This replacement turns a continuous problem over unitary matrices into a discrete combinatorial problem over zero--one permutation matrices, and thereby opens a path toward derandomization. The theorem of Bordenave and Collins shows that random permutations have the required limiting behavior and the algorithm of O'Donnell and Wu then provides a deterministic asymptotic construction, running in polynomial time in the size when the channel parameters and accuracy are fixed. Thus the random construction can be derandomized in an asymptotic algorithmic sense, although finding a simple closed-form or practically computable counterexample remains open. Finally, a quantitative random permutation estimate by Chen, Garza-Vargas, Tropp and van Handel gives a fully numerical estimate: there exists a tuple of 57,836,025 permutations acting on a set of size \[ N \le 5.422\times 10^{116216}\] such that the associated finite dimensional channel exhibits nonadditivity. This enormous value remains an obstacle to a practical construction.
- Abstract（参考訳）: ハスティングスの量子チャネル上の古典的通信の超付加性証明以来、この現象の構造的説明の発見に多大な努力が注がれてきた。
この研究の主な観察は、ハールランダム性は非加法的に責任を負う極限幾何学を変更することなく、ランダムな置換によって置き換えることができることである。
この置換は、ユニタリ行列上の連続問題をゼロ1置換行列上の離散組合せ問題に変換し、デランドマイズへの道を開く。
Bordenave と Collins の定理は、ランダムな置換が所要の制限挙動を持ち、O'Donnell と Wu のアルゴリズムが決定論的漸近的構造を提供し、チャネルパラメータと精度が固定されたときに多項式時間で実行されることを示している。
このように、ランダムな構成は漸近的アルゴリズムの意味でデランドマイズすることができるが、単純な閉形式や実際計算可能な反例を見つけることは未解決である。
最後に、Chen, Garza-Vargas, Tropp and van Handel による定量的なランダムな置換の推定は、完全に数値的な見積もりを与える: 57,836,025 個のタプルが存在し、大きさの集合 \[ N \le 5.422\times 10^{116216}\] に作用し、関連する有限次元チャネルが非随意性を示す。
この膨大な価値は、実際的な建設の障害として残っています。
関連論文リスト
- Variational Approach for Uniform Quantum Permutation Generators [2.4283267413173877]
接続制約下での均一な置換生成のための変分量子回路フレームワークを開発した。
直近近傍の位相上の2次回路サイズと線形深さ(O(n))とを正確に均一化できる明示的な制御SWAPに基づくユニタリ構成を提案する。
論文 参考訳（メタデータ） (2026-06-08T22:41:09Z) - Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure [52.51019642214249]
我々は,カットのエントロピーを量子時間で推定できない2次元局所定数深さ量子回路の族を構築する。
定深量子回路は特定の多くの量子サンプルから学習できるので、結果として得られる擬似絡み状態は暗黙的に公鍵であり、擬似ランダムではない。
論文 参考訳（メタデータ） (2026-05-29T15:43:00Z) - Composition Law of Conjugate Observables in Random Permutation Sorting Systems [0.0]
乱数置換ソーティングシステム(RPSS)における共役可観測物質を規定する基本構成則の発見について述べる。
この法則は、離散置換数Npと連続経過時間Tとを、時間の特徴関数と置換数の確率生成関数とを連結する関数関係を介して連結する。
この枠組みはエントロピーの浄化を可能にし、幾何学的収束を通して微構造的タイミング変動を均一なランダム性に変換する。
論文 参考訳（メタデータ） (2025-10-09T09:50:21Z) - Compressed Permutation Oracles [0.6768558752130311]
我々は、圧縮された置換オラクルの音質を発達させ、証明する。
我々は、基本的にすべての既知の量子クエリの低い境界をランダムな置換モデルで再証明する。
論文 参考訳（メタデータ） (2025-09-23T03:13:48Z) - Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
量子乱数置換と理想的な暗号モデルにおけるセキュリティを確立するための最初の持ち上げ定理を導出する。
これらの定理は、任意の量子逆数の成功確率と、少数の古典的クエリのみを作る古典的アルゴリズムの成功確率を関連付ける。
論文 参考訳（メタデータ） (2025-04-25T09:07:55Z) - Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。
我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文 参考訳（メタデータ） (2024-04-25T17:08:34Z) - Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
実数値ユニタリは完全に擬似ランダムとは言えなくても、実数値ユニタリを諦めることなく、いくつかの擬似ランダム特性を得ることができることを示す。
我々の分析は、ランダムな(バイナリ)フェーズとランダムな計算ベイシスの置換を適用すると、さらに単純な構成になることを示している。
論文 参考訳（メタデータ） (2024-03-25T12:37:50Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
おもちゃの光ファイバーをベースとしたセットアップを用いてバイナリシリーズを生成し、そのランダム度をVilleの原理に従って評価する。
標準統計指標の電池、ハースト、コルモゴロフ複雑性、最小エントロピー、埋め込みのTakensarity次元、および拡張ディッキー・フラーとクワイアトコフスキー・フィリップス・シュミット・シン(英語版)でテストされ、ステーション指数をチェックする。
Toeplitz 抽出器を不規則級数に適用することにより得られる系列のランダム性のレベルは、非還元原料のレベルと区別できない。
論文 参考訳（メタデータ） (2022-08-31T17:39:29Z) - Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。
オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。
乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
論文 参考訳（メタデータ） (2021-03-16T11:05:48Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。