論文の概要: Exponential lower bounds for low-degree strategies in position-based quantum cryptography

• arxiv url: http://arxiv.org/abs/2609.35592v1
• Date: Mon, 28 Sep 2026 16:43:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 20:32:46.239135
• Title: Exponential lower bounds for low-degree strategies in position-based quantum cryptography
• Title（参考訳）: 位置ベース量子暗号における低次戦略の指数的下界
• Abstract要約: 非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
• 参考スコア（独自算出の注目度）: 0.764671395172401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary $U_{AB}$ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary $U_{AB}$ whose implementation in NLQC requires extra quantum systems with dimensions ${\rm exp}(n^{Ω(1)})$, where $n$ is the dimension of systems $A$ and $B$. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in $n$. In this paper we consider the family of diagonal ${\pm 1}$ valued unitaries $U_{\varepsilon}$, indexed by an element of the Boolean hypercube $\varepsilon \in \{\pm 1\}^{n^2}$, i.e. $U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$. We show that if $U_{\varepsilon}$ can be implemented in NLQC with constant accuracy for all $\varepsilon$, and the dependency on $\varepsilon$ in the first round of the associated strategy is a polynomial of degree $O(n^{\frac{1}{4}-δ})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)$. The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
• Abstract（参考訳）: 非局所量子計算 (NLQC) は、単一の中間ラウンドの通信を同時に行う2ラウンドのプロトコルを用いて、2つの遠隔プレイヤーが連携する2部単位の$U_{AB}$の実装に基づいて構成される。 NLQC に実装するためには、次元が ${\rm exp}(n^{Ω(1)})$ の余剰量子系が必要であり、$n$ はシステム $A$ と $B$ の次元である。 このタイプの指数的下界は、NLQCによって敵の能力が正確に記述されるため、位置ベースの量子暗号のセキュリティに不可欠である。 また、普遍量子シミュレータの最適性やホログラフィック量子重力の期待される性質など、他の多くの問題とも関係している。 現在、最良の下限は$n$のサブリニアのみである。 本稿では、対角的な${\pm 1}$値のユニタリ $U_{\varepsilon}$、ブールハイパーキューブ $\varepsilon \in \{\pm 1\}^{n^2}$、すなわち、$U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$の要素によってインデックス付けされる対角的な${\pm 1}$の族を考える。 U_{\varepsilon}$ が NLQC においてすべての$\varepsilon$ に対して一定の精度で実装可能であり、関連する戦略の第1ラウンドにおける $\varepsilon$ への依存が次数$O(n^{\frac{1}{4}-δ})$ の多項式であるなら、NLQC における少なくとも 1 つの $U_{\varepsilon}$ の実装は $\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)$ のリソーススケーリングを必要とする。 この証明は、特定のバナッハ空間の幾何学的性質、すなわちそれらの型定数、およびそれらの上で値付けられたブール関数のランダムな推定に基づいている。

関連論文リスト

• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
  上界と下界の両方で$operatornametr(rhoq)$を推定することで、サンプルの複雑さを大幅に改善する。 我々の上界は、弱いシュアサンプリングに基づく(プラグインでない)量子推定器によって得られる。
  論文  参考訳（メタデータ） (2025-05-14T17:06:33Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• 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)

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

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