論文の概要: Computational Bounds for $f$-Routing

• arxiv url: http://arxiv.org/abs/2609.40278v1
• Date: Wed, 30 Sep 2026 17:46:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.226353
• Title: Computational Bounds for $f$-Routing
• Title（参考訳）: $f$-Routingの計算バウンド
• Abstract要約: 我々は、一様攻撃者に対する無条件リソースの低い境界を証明した。 入力長 $n$ と十分小さい定数 $>0$ に対して、$q$ qubits を用いた一様生成戦略は、以下の計算境界を$f$ で表している。 これらの境界は、内積関数 $f=mathrmIP$ に対して、Bluhm, Christandl, Speelman (2022) の$qlelog n$ を超える。
• 参考スコア（独自算出の注目度）: 1.2604738912025477
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers; our new techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and sufficiently small constant $ε>0$, a uniformly generated strategy using $q$ qubits and having description length $\mathrm{poly}(q)$, with success probability at least $1-ε$ on every input, implies the following computational bounds on $f$: 1. If the strategies are arbitrary quantum channels, then $f\in\mathrm{QSZK}(\mathrm{poly}(nq))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero knowledge proofs in which the verifier runs in time $T$ (and the simulator in time $\mathrm{poly}(T)$). 2. If the strategies are explicit Pauli-sparse unitaries on $q$ qubits that have at most $s$ nonzero Pauli coefficients, then $f\in\mathrm{DTIME}(\mathrm{poly}(nqs))$. 3. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in\mathrm{DTIME}(\mathrm{poly}(nq2^t))$. Time and space hierarchies then yield explicit functions secure against polynomial and even quasipolynomial qubits $q$ under our computational restrictions. These bounds exceed the $q\le\log n$ bound of Bluhm, Christandl, and Speelman (2022) for inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
• Abstract（参考訳）: f$routingプロトコルは量子位置検証(Kent, Munro, and Spiller, 2011)の主要な候補であるが、明示的な関数に対するセキュリティ保証は限定的である。 我々は、一様攻撃者に対する非条件リソースの低い境界を証明し、我々の新しい手法は、入力長において本質的に最も線形である以前の作業の中心となる通信-複雑境界をバイパスする。 入力長 $n$ と十分小さい定数 $ε>0$ に対して、$q$ qubits と記述長 $\mathrm{poly}(q)$ を均一に生成し、成功確率が少なくとも 1-ε$ を全ての入力で持つと、$f$: 1. の計算バウンダリは、任意の量子チャネルであるならば、$f\in\mathrm{QSZK}(\mathrm{poly}(nq)$, ここで$\mathrm{QSZK}(T)$ は、検証者が時間$T$(および時間$\mathrm{poly}(T)$で実行する量子ゼロ知識の証明を持つ言語のクラスである。 2. 戦略が、少なくとも$s$非ゼロのパウリ係数を持つ$q$ qubits上の明示的なパウリスパースユニタリであれば、$f\in\mathrm{DTIME}(\mathrm{poly}(nqs))$である。 3. 戦略が少なくとも$t$マジックゲートを使用するクリフォード+T回路であれば、$f\in\mathrm{DTIME}(\mathrm{poly}(nq2^t))$である。 時間と空間の階層は、我々の計算制限の下で多項式や準多項式のqubits$q$に対してセキュアな明示関数を生成する。 これらの境界は、内積関数 $f=\mathrm{IP}$ に対する Bluhm, Christandl, Speelman (2022) の$q\le\log n$ バウンドを超える。

関連論文リスト

• Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
  非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
  論文  参考訳（メタデータ） (2026-09-28T16:43:48Z)
• Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
  例えば、$Lotimes k$に属するステートメントのセット$k$-tuplesは、複雑さを伴うあいまいなインタラクティブな証明を持つ。 $ellcdotmathsfpolylog(k)$、$acdot ellcdotmathsfpolylog(k)$、ラウンドごとの通信である。
  論文  参考訳（メタデータ） (2025-10-21T21:04:10Z)
• $\mathsf{P} \neq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weak Quantale $w_Q=K_mathrmpoly(cdotmidcdot)$. ランダムな3ドルCNFをマスキングした効率よくサンプリング可能なアンサンブル$D_m$に対して、スイッチング・バイ・ウェイクネスの正規形式を証明する。
  論文  参考訳（メタデータ） (2025-10-09T21:01:17Z)
• Magic and communication complexity [0.6533091401094101]
  量子回路におけるマジックと通信複雑性の間の新しい接続を確立する。 低魔法で計算可能な関数は通信コストが低いことを示す。
  論文  参考訳（メタデータ） (2025-10-08T17:14:25Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [6.8680041558282054]
  並列量子計算は,従来よりも計算能力が高いことを示す。 我々は、新しい量子コンピュータに計算上の優位性を持たせて、より高次元の非局所ゲーム理論を橋渡しする。
  論文  参考訳（メタデータ） (2024-08-29T09:40:55Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• 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)

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

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