論文の概要: Learning with errors may remain hard against quantum holographic attacks

• arxiv url: http://arxiv.org/abs/2509.22833v1
• Date: Fri, 26 Sep 2025 18:38:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:18.899599
• Title: Learning with errors may remain hard against quantum holographic attacks
• Title（参考訳）: 量子ホログラフィー攻撃に対する誤りによる学習の困難さ
• Authors: Yunfei Wang, Xin Jin, Junyu Liu,
• Abstract要約: 近年の研究では、絡み合いのエントロピーはLearning with Errors (LWE)と同じくらい難しく、量子重力とAdS/CFTとの緊張を生み出すことが示されている。 これは、ホログラフィック双対を構築し、極端の表面を測定することで、LWEを解くためのパラドックス的な経路を示唆している。 ホログラフィックエントロピーは、難解なホログラフィック辞書を必要とせず、量子計算の限界と一致していることを示す。
• 参考スコア（独自算出の注目度）: 20.779821328622454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Learning with Errors (LWE) problem underlies modern lattice-based cryptography and is assumed to be quantum hard. Recent results show that estimating entanglement entropy is as hard as LWE, creating tension with quantum gravity and AdS/CFT, where entropies are computed by extremal surface areas. This suggests a paradoxical route to solving LWE by building holographic duals and measuring extremal surfaces, seemingly an easy task. Three possible resolutions arise: that AdS/CFT duality is intractable, that the quantum-extended Church-Turing thesis (QECTT) fails, or that LWE is easier than believed. We develop and analyze a fourth resolution: that estimating surface areas with the precision required for entropy is itself computationally hard. We construct two holographic quantum algorithms to formalize this. For entropy differences of order N, we show that measuring Ryu-Takayanagi geodesic lengths via heavy-field two-point functions needs exponentially many measurements in N, even when the boundary state is efficiently preparable. For order one corrections, we show that reconstructing the bulk covariance matrix and extracting entropy requires exponential time in N. Although these tasks are computationally intractable, we compare their efficiency with the Block Korkine-Zolotarev lattice reduction algorithm for LWE. Our results reconcile the tension with QECTT, showing that holographic entropy remains consistent with quantum computational limits without requiring an intractable holographic dictionary, and provide new insights into the quantum cryptanalysis of lattice-based cryptography.
• Abstract（参考訳）: ラーニング・ウィズ・エラー(Learning with Errors)問題(LWE)は、現代の格子ベースの暗号を基礎にしており、量子ハードであると仮定されている。 近年の研究では、エントロピーの推定はLWEと同等に難しく、量子重力とAdS/CFTとの緊張が生じ、エントロピーは極端表面積によって計算されることが示された。 これは、ホログラフィック双対を構築し、極端の表面を測定することで、LWEを解くためのパラドックス的な経路を示唆している。 AdS/CFT双対性は難解であること、量子拡張チャーチ・チューリング論(QECTT)が失敗すること、LWEが信じているよりも容易であること、の3つの可能な解決法が生じる。 エントロピーに必要な精度で表面積を推定することは、それ自体が計算的に困難である。 我々はこれを定式化する2つのホログラフィック量子アルゴリズムを構築した。 次数 N のエントロピー差について、高柳-高柳測地線長を重場2点関数で測定するには、境界状態が効率的に準備可能であっても、N において指数関数的に多くの測定が必要であることを示す。 次数1の補正のために、バルク共分散行列の再構成とエントロピーの抽出には指数時間が必要であり、これらのタスクは計算に難航するが、それらの効率をLWEのブロックコルキン・ゾロタレフ格子削減アルゴリズムと比較する。 その結果, ホログラフィックエントロピーは, 難解なホログラフィック辞書を必要とせず, 量子計算限界と整合性を維持し, 格子暗号の量子暗号解析に関する新たな知見を提供することができた。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• One-Shot Min-Entropy Calculation Of Classical-Quantum States And Its Application To Quantum Cryptography [21.823963925581868]
  古典量子状態のミニエントロピーに対するワンショット下界計算手法を開発した。 BB84量子鍵分布スキームに対して、より厳密な有限データ解析を提供する。 これは、デバイス独立量子鍵分配プロトコルの変種について、現在知られている最高の有限鍵境界を与える。
  論文  参考訳（メタデータ） (2024-06-21T15:11:26Z)
• Stable computation of entanglement entropy for 2D interacting fermion systems [1.3165428727965363]
  エンタングルメントエントロピー(EE)は、2次元相互作用するフェルミオン系の組織原理を推測するために用いられる。 EEは、ユニバーサルスケーリングシステムにアクセス可能な信頼性のあるデータで成功していません。 インクリメンタルアルゴリズムで概念的および計算的障壁を克服する方法を示す。
  論文  参考訳（メタデータ） (2023-03-25T01:56:09Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• The refined quantum extremal surface prescription from the asymptotic equipartition property [0.0]
  ワンショット情報理論のエントロピーは、量子情報の観点からより基本的なエントロピー測度である。 私たちは、量子情報と量子重力の両方の技術的手法を組み合わせて、このアイデアをしっかりとした根拠に置きます。 固定領域状態に対する改良された量子極端表面処方法を、新しいAEPレプリカトリックにより導出する。
  論文  参考訳（メタデータ） (2021-05-12T18:26:30Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)

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

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