論文の概要: Robust logarithmic lower bound on shared-resource cost for $f$-routing

• arxiv url: http://arxiv.org/abs/2608.05775v1
• Date: Thu, 06 Aug 2026 09:09:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-07 15:25:20.861289
• Title: Robust logarithmic lower bound on shared-resource cost for $f$-routing
• Title（参考訳）: 共有リソースコストによる$f$-routingのロバスト対数下限
• Abstract要約: 1ラウンド$f$-routingでは、Aliceは$n$-bit文字列と未知のqubitを受け取り、Bobは$n$-bit文字列を受け取る。 彼らは1つの同時メッセージを交換し、$f$の値は、どのパーティがクォービットを回復しなければならないかを決定する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In one-round $f$-routing, Alice receives an $n$-bit string and an unknown qubit, while Bob receives another $n$-bit string. They exchange one simultaneous message each, and the value of $f$ determines which party must recover the qubit. Message lengths, local systems, and local operations are unrestricted. We charge only $E_{\dim}(ρ_{LR})=\log_2\min\{\operatorname{rank}ρ_L,\operatorname{rank}ρ_R\}$, the logarithm of the smaller marginal support dimension of the shared state prepared before the inputs arrive. The state may be arbitrary and mixed. For the inner product modulo $2$, we prove that every protocol with worst-case error at most $0.09$ in both routing cases, measured in the full, unhalved diamond norm, satisfies $d\log_2(2d)=Ω(n)$ for $d=\min\{\operatorname{rank}ρ_L,\operatorname{rank}ρ_R\}$. Thus $d=Ω(n/\log n)$ and $E_{\dim}(ρ_{LR})\ge\log_2 n-\log_2\log_2 n-O(1)$. The closest earlier growing Schmidt-rank lower bound for an explicit routing function assumes zero error in one routing case. Our proof converts correctness into a matrix whose entries have a constant gap between the two routing cases. It approximates this matrix by one whose rank depends on $d$, but not on the dimensions of messages or local systems. A sign-rank lower bound for the matrix of the inner product modulo $2$ completes the argument. A lower bound polynomial in $n$ on $E_{\dim}$ remains open.
• Abstract（参考訳）: 1ラウンド$f$-routingでは、Aliceは$n$-bit文字列と未知のqubitを受け取り、Bobは$n$-bit文字列を受け取る。 彼らは1つの同時メッセージを交換し、$f$の値は、どのパーティがクォービットを回復しなければならないかを決定する。 メッセージの長さ、ローカルシステム、ローカル操作は制限されない。 E_{\dim}(ρ_{LR})=\log_2\min\{\operatorname{rank}ρ_L,\operatorname{rank}ρ_R\}$, 状態は任意で混ざり合っていることもある。 内部積 modulo $2$ に対して、両方のルーティングケースで最低ケースエラーが少なくとも0.09$で、完全なダイヤモンドノルムで測定された全てのプロトコルが $d\log_2(2d)=Ω(n)$ for $d=\min\{\operatorname{rank}ρ_L,\operatorname{rank}ρ_R\}$ を満たすことを証明している。 したがって、$d=Ω(n/\log n)$ と $E_{\dim}(ρ_{LR})\ge\log_2n-\log_2\log_2n-O(1)$ である。 明示的なルーティング関数に対するシュミットランクの低いバウンダリは、1つのルーティングケースでゼロエラーを仮定する。 我々の証明は、正しさを2つのルーティングケースの間に一定の間隔を持つ行列に変換する。 この行列は、ランクが$d$に依存するが、メッセージやローカルシステムの寸法に依存しないものによって近似される。 内積モジュラーの行列に対する符号ランク下界は、議論を完遂する。 A lower bound polynomial in $n$ on $E_{\dim}$ は依然として開である。

関連論文リスト

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。 加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
  論文  参考訳（メタデータ） (2026-09-04T18:28:01Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
  $$n$-qubit $s$-sparse状態は、$widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gatesを使ってエラーを発生させることができる。 0le$と2le sle 2n/2$に対して、スパース状態の準備には$(mins,sqrtns)$$Tが必要である。
  論文  参考訳（メタデータ） (2026-08-01T03:33:19Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。 我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
  論文  参考訳（メタデータ） (2026-05-22T12:22:20Z)
• Shallow ReLU$^s$ Networks in $L^p$-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization [12.871748162999062]
  特に、$_d$が均一測度で$1le p2$のとき、近似率は$O!left(m-fracp(2s+2d+1)-2d2dpright)$ for $1le p*$と$O!left(m-fracp(4s+3d-1)-2d+24dpright)$ for $p*p2$である。 non (複数形 nons)
  論文  参考訳（メタデータ） (2026-05-18T14:27:49Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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