論文の概要: On the Spectral theory of Isogeny Graphs and Quantum Sampling of Hard Supersingular Elliptic curves

• arxiv url: http://arxiv.org/abs/2602.02263v1
• Date: Mon, 02 Feb 2026 16:04:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.277944
• Title: On the Spectral theory of Isogeny Graphs and Quantum Sampling of Hard Supersingular Elliptic curves
• Title（参考訳）: 硬超特異楕円曲線の等質グラフのスペクトル理論と量子サンプリングについて
• Authors: David Jao, Maher Mamah,
• Abstract要約: 確率の高いランダムなハード超特異楕円曲線をサンプリングする最初の証明可能な量子時間アルゴリズムを提案する。 我々のアルゴリズムはハッシュ関数や他の暗号プリミティブをセキュアにインスタンス化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study the problem of sampling random supersingular elliptic curves with unknown endomorphism rings. This task has recently attracted significant attention, as the secure instantiation of many isogeny-based cryptographic protocols relies on the ability to sample such ``hard'' curves. Existing approaches, however, achieve this only in a trusted-setup setting. We present the first provable quantum polynomial-time algorithm that samples a random hard supersingular elliptic curve with high probability.Our algorithm runs heuristically in $\tilde{O}\!\left(\log^{4}p\right)$ quantum gate complexity and in $\tilde{O}\!\left(\log^{13} p\right)$ under the Generalized Riemann Hypothesis. As a consequence, our algorithm gives a secure instantiation of the CGL hash function and other cryptographic primitives. Our analysis relies on a new spectral delocalization result for supersingular $\ell$-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture, and we further provide numerical evidence for complete eigenvector delocalization; this theoretical result may be of independent interest. Along the way, we prove a stronger $\varepsilon$-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction.
• Abstract（参考訳）: 本稿では,未知の自己準同型環を持つランダム超特異楕円曲線のサンプリング問題について検討する。 このタスクは、多くの同種暗号プロトコルのセキュアなインスタンス化は、そのような `hard'' 曲線をサンプリングする能力に依存しているため、近年大きな注目を集めている。 しかし、既存のアプローチは信頼された設定でのみこれを達成する。 我々は、確率の高いランダムなハード超特異楕円曲線をサンプリングする最初の証明可能な量子多項式時間アルゴリズムを示し、我々のアルゴリズムは$\tilde{O}\! \left(\log^{4}p\right)$ quantum gate complexity and in $\tilde{O}\! 一般化リーマン仮説の下での \left(\log^{13} p\right)$ である。 その結果,アルゴリズムはCGLハッシュ関数や他の暗号プリミティブをセキュアにインスタンス化する。 我々の分析は、超特異な$\ell$-isogenyグラフに対する新しいスペクトル非局在化結果に依存している: 量子一様エルゴーディニティ予想を証明し、さらに完全固有ベクトル非局在化の数値的証拠を提供する。 その過程で、同種グラフの固有値に対する$\varepsilon$-セパレーション特性が、Ke, Sharif, Silverbergの量子マネープロトコルで予測されるものよりも強いことを証明し、したがって構成において重要なヒューリスティックな仮定を取り除く。

関連論文リスト

• Ancilla-Free Fast-Forwarding Lindbladian Simulation Algorithms by Hamiltonian Twirling [2.8802622551493773]
  時間=t$進化写像は、ユニタリ軌道上のガウスのツワールを正確に表すことができる。 この構造的洞察により、リンドブラディアンシミュレーションのための高速フォワードアルゴリズムを設計できる。
  論文  参考訳（メタデータ） (2025-11-13T12:39:18Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• Operator-Level Quantum Acceleration of Non-Logconcave Sampling [4.711981119026701]
  ランゲヴィン力学はターゲットギブを量子状態の振幅に符号化する。 この接続は、最初の証明可能な量子拡散係数設定によるギブスサンプリングを可能にする。
  論文  参考訳（メタデータ） (2025-05-08T14:43:17Z)
• Avoided-crossings, degeneracies and Berry phases in the spectrum of quantum noise through analytic Bloch-Messiah decomposition [49.1574468325115]
  解析的ブロッホ・メシア分解 (analytic Bloch-Messiah decomposition) は量子光学系の力学を特徴づけるためのアプローチを提供する。 単一パラメータが変化した場合,回避された交差は自然に発生し,特異ベクトルの過敏性をもたらすことを示す。 我々は,避けられた交差を意図的に設計することで,フォトニックシステムのスペクトル応答をプログラムできる可能性を強調した。
  論文  参考訳（メタデータ） (2025-04-29T13:14:15Z)
• Quantum tomography of helicity states for general scattering processes [55.2480439325792]
  量子トモグラフィーは、物理学における量子系の密度行列$rho$を計算するのに欠かせない道具となっている。 一般散乱過程におけるヘリシティ量子初期状態の再構成に関する理論的枠組みを提案する。
  論文  参考訳（メタデータ） (2023-10-16T21:23:42Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• The complexity of quantum support vector machines [1.7887848708497243]
  量子サポートベクトルマシンは、カーネル関数を定義するために量子回路を使用する。 二重問題は$O(M4.67/varepsilon2)$量子回路評価で解けることを示す。
  論文  参考訳（メタデータ） (2022-02-28T19:01:17Z)
• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry [9.695960412426672]
  我々は,スプリアスミニマの様々な家系でヘッセンを解析的に特徴付ける。 特に、$dge k$ 標準ガウス入力について、 (a) ヘッセンの $dk$ 固有値の内、$dk - O(d)$ が 0 に近づき、 (b) $Omega(d)$ 固有値は $k$ で線型的に増加することを証明している。
  論文  参考訳（メタデータ） (2020-08-04T20:08:35Z)

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

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