論文の概要: New lower bounds for CDS and $f$-routing

• arxiv url: http://arxiv.org/abs/2609.24291v1
• Date: Mon, 21 Sep 2026 08:50:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:01.22507
• Title: New lower bounds for CDS and $f$-routing
• Title（参考訳）: CDSと$f$-routingの新しい下位境界
• Abstract要約: 中心となる特別なケースは$f$-routingであり、部分的には量子位置検証によって動機付けられる。 本研究では、秘密の厳密な条件開示の共有ランダム化コストについて検討する。 1つの入力クラスでプロトコルが正確であり、もう1つのクラスではエラーが一定である、一方の完全$f$-routingを考える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and related areas. A central special case is $f$-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and $f$-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect $f$-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix arising in the method of Asadi, Culf, and May (ITCS 2025), we derive a general lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.
• Abstract（参考訳）: 非局所量子計算(NLQC)の絡み合いコストを理解することは、複雑性理論、暗号、量子重力、および関連する領域に関係している。 中心となる特別なケースは$f$-routingであり、部分的には量子位置検証によって動機付けられる。 完全にロバストな設定における絡み合いコストの低い境界を証明することは、NLQCで大きな問題となっている。 この問題によって、我々は2つの関連する下界を確立する。 まず, 秘密条件開示(CDS)の共有ランダム化コストについて検討した。 Allerstorfer et al (Quantum 2024) によって確立された CDS と$f$-routing の接続は、ロバストCDS のランダム性複雑性を、完全にロバストなルーティング問題に対する下位境界への自然なステップとして理解させる。 本研究では,CDSの共有ランダム化コストが,通信やプライベートランダム化が制限されない場合であっても,決定論的SMP通信複雑性の対数によって低く抑えられることを示す。 我々の下界は等式関数に対してきつい。 第二に、プロトコルが1つの入力クラス上で正確であり、他方では一定のエラーを持つ一方の完全$f$-routingを考える。 Asadi, Culf, May (ITCS 2025) 法で生じる低ランク行列の正当性を利用して, エンタングルメントコストを符号ランクの観点から一般の低い値に導出する。 特に、これは、既知の上界に一致する一方的な完全設定の両方において、内積関数のルーティングの絡み合いコストの線形下界が得られる。

関連論文リスト

• Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
  我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。 構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。 クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
  論文  参考訳（メタデータ） (2026-09-14T20:17:04Z)
• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。 本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。 このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
  論文  参考訳（メタデータ） (2026-02-12T17:49:07Z)
• Lower bounds on non-local computation from controllable correlation [0.0]
  我々は、任意のユニタリに対して評価できる2つの新しい下界技術を与える。 ハールランダムな2量子ユニタリの場合、我々の手法は典型的に非自明な下界につながる。 我々は、CNOT、DCNOT、$sqrttextSWAP$、XX相互作用を含む、よく研究されている2つの量子ゲートのほとんどの下界を得る。
  論文  参考訳（メタデータ） (2026-01-30T19:19:12Z)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。 最適率を達成するための情報重み付け回帰手法を提案する。 特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
  論文  参考訳（メタデータ） (2025-02-18T18:35:24Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Rank lower bounds on non-local quantum computation [0.0]
  非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。 NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
  論文  参考訳（メタデータ） (2024-02-28T19:00:09Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)

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

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