論文の概要: Quantum Lazy Sampling and Path Recording for Any Group

• arxiv url: http://arxiv.org/abs/2606.30281v1
• Date: Mon, 29 Jun 2026 13:23:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-30 18:07:16.245472
• Title: Quantum Lazy Sampling and Path Recording for Any Group
• Title（参考訳）: 任意のグループに対する量子遅延サンプリングとパス記録
• Abstract要約: 遅延サンプリングの量子アナログの研究:圧縮オークル(または記録オークル) 我々のオラクルは、重ね合わせで t 入力出力ペアを格納し、グループのテンソルパワー表現の可換性の観点から更新を記述する。 経路記録の興味深い応用の1つは、異なるグループの圧縮オラクル間の直接比較を可能にし、擬似ランダム性を示す新しい手法を提供することである。
• 参考スコア（独自算出の注目度）: 3.495214699450807
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability. We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of $U(N)$. Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability. One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing $S_N$ and $U(N)$ yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).
• Abstract（参考訳）: 量子アルゴリズムと暗号における中心的な課題は、ランダムなグループ要素(例えば、ランダム関数、置換、ユニタリ)へのオラクルアクセスを持つアルゴリズムを推論することである。 そのようなアルゴリズムを効率的にシミュレートできますか。 tクエリの後に何を知っているか、決定できますか? オラクルはすべてのグループ要素を前もってコミットするのではなく、その部分的な情報をその場でサンプリングする。 遅延サンプリングの量子アナログである圧縮オークル(または記録オークル)について検討する。 これらは、もともとZhandry (CRYPTO '19) がランダム関数のために導入し、Ma-Huang (STOC '25) と Carolan (STOC '26) の置換によりユニタリに一般化した量子クエリのオンザフライシミュレーションを可能にする量子データ構造であり、その解釈可能性によるセキュリティ証明と下位境界に大きな影響を及ぼした。 我々は、U(N)$ の任意の閉部分群のランダムな元を完全にシミュレートする第一原理から導かれる汎用的で解釈可能な経路記録オラクルを定義し、解析する。 我々のオラクルは、重ね合わせで t 入力出力ペアを格納し、グループのテンソルパワー表現の可換性の観点から更新を記述する。 これはアルゴリズムが学んだ情報を透過的に記録する。 我々の託宣は近年のGrinko-Yoshida(QIP '26)の業績に基づいており、彼らは明確な解釈不可能な汎用的な圧縮託宣を施した。 経路記録の興味深い応用の1つは、異なるグループの圧縮オラクル間の直接比較を可能にし、擬似ランダム性を示す新しい手法を提供することである。 例えば、$S_N$ と $U(N)$ を比較すると、疑似ランダムユニタリの現在の最も単純な構成である:擬ランダムな置換とランダムなクリフォードの積 PC は、以前の PFC の構成を改善している(Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25)。

関連論文リスト

• Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
  我々は新しい量子クエリローバウンドフレームワークを導入する。 このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。 特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
  論文  参考訳（メタデータ） (2026-04-06T19:52:58Z)
• Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms [0.0]
  任意のコンパクト群に対するハール乱ユニタリの$t$コピーの作用をシミュレートする一般的な方法を提案する。 概念的には単純で正確であり、クレブシュ・ゴルダン変換を主構成要素として利用する。
  論文  参考訳（メタデータ） (2025-09-30T17:57:08Z)
• Compressed Permutation Oracles [0.6768558752130311]
  我々は、圧縮された置換オラクルの音質を発達させ、証明する。 我々は、基本的にすべての既知の量子クエリの低い境界をランダムな置換モデルで再証明する。
  論文  参考訳（メタデータ） (2025-09-23T03:13:48Z)
• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  入力-出力ペアの述語に対するアルゴリズムの成功確率を、結果のオラクルシミュレーションを用いてバウンドする方法を示す。 本研究では, 1ラウンドスポンジ構成がランダムな置換モデルに対して無条件に事前画像に抵抗可能であることを示す。
  論文  参考訳（メタデータ） (2024-07-12T19:27:13Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。 この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2024-04-15T04:01:50Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。 我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
  論文  参考訳（メタデータ） (2024-01-25T17:13:51Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。 オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。 乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
  論文  参考訳（メタデータ） (2021-03-16T11:05:48Z)

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

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