論文の概要: On Limits on the Provable Consequences of Quantum Pseudorandomness

• arxiv url: http://arxiv.org/abs/2510.05393v1
• Date: Mon, 06 Oct 2025 21:38:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-08 17:57:07.99746
• Title: On Limits on the Provable Consequences of Quantum Pseudorandomness
• Title（参考訳）: 量子擬似乱数確率の極限について
• Authors: Samuel Bouaziz--Ermann, Minki Hhan, Garazi Muguruza, Quoc-Huy Vu,
• Abstract要約: 量子擬似ランダム性が他のものから構築される可能性は低いことを示すいくつかの証拠を示す。 我々は、1つの量子擬似ランダム性が存在するが、別の擬似ランダム性が存在しない新しい神託世界を研究する。
• 参考スコア（独自算出の注目度）: 2.683233968306505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs) and pseudorandom function-like state generators (PRSFGs). Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relation between quantum pseudorandomness has yet to be fully established. We present some evidence suggesting that some quantum pseudorandomness is unlikely to be constructed from the others, or at least is hard to construct unless some conjectures are false. This indicates that quantum pseudorandomness could behave quite differently from classical pseudorandomness. We study new oracle worlds where one quantum pseudorandomness exists but another pseudorandomness does not under some assumptions or constraints, and provide potential directions to achieve the full black-box separation. More precisely: - We give a unitary oracle relative to which PRFSGs exist but PRUs without using ancilla do not. This can be extended to the general PRUs if we can prove a structural property of the PRU algorithm. - Assuming an isoperimetric inequality-style conjecture, we show a unitary oracle world where log-length output PRFSGs exist but proving the existence of quantum-computable pseudorandom generators (QPRGs) with negligible correctness error is as hard as proving that ${\sf BQP}\neq {\sf QCMA}$. This result suggests that the inverse-polynomial error in the state of the art construction of QPRGs from log-length PRSGs is inherent. - Assuming the same conjecture, we prove that some natural way of constructing super-log-length output PRSGs from log-length output PRFSGs is impossible. This partly complements the known hardness of shrinking the PRSG output lengths. Along the way, we also discuss other potential approaches to extend the PRSG output lengths.
• Abstract（参考訳）: 量子擬似乱数性の概念としては、擬似乱数ユニタリ(PRU)、擬似乱数状態発生器(PRSG)、擬似乱数関数様状態発生器(PRSFG)などがある。 互いに存在的に等価であることが知られている古典的擬似ランダム性の異なる概念とは異なり、量子擬似ランダム性との関係は未だ完全に確立されていない。 量子擬似ランダム性(英語版)が他のものから構築されることはありそうになく、少なくともいくつかの予想が偽でない限りは構築が困難であることを示す証拠を提示する。 これは量子擬似ランダム性が古典的擬似ランダム性とは全く異なる振る舞いをすることができることを示している。 1つの量子擬似ランダム性が存在するが、別の擬似ランダム性はいくつかの仮定や制約の下では存在せず、完全なブラックボックス分離を達成するための潜在的方向を提供する。 より正確には: - PRFSGが存在するが、ancillaを使わずにPRUは存在しないユニタリオラクルを与える。 これは、PRUアルゴリズムの構造的性質を証明できれば、一般のPRUにも拡張できる。 -等長不等式予想を仮定すると、対数長出力PRFSGが存在するユニタリオラクル世界を示すが、量子計算可能な擬ランドーム生成器(QPRG)の存在は、${\sf BQP}\neq {\sf QCMA}$を証明するのと同じくらい難しい。 この結果は、ログ長PSRGからのQPRGの最先端構築における逆多項式誤差が本質的であることを示唆している。 -同じ予想を仮定すると、ログ長出力PRFSGから超log長出力PSSGを構築する自然な方法は不可能であることが証明される。 これはPSRG出力長を縮小する既知の硬さを部分的に補完する。 また、PSSG出力長を拡大する他の潜在的アプローチについても論じる。

関連論文リスト

• Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators [7.921901082060529]
  Pseudorandom quantum state (PRS) と pseudorandom function-like quantum state (PRFS) は擬似乱数生成器と擬似乱数関数の量子類似体である。 本研究では,環境との絡み合いや相関を生じさせないスケーラブルPSSの新しい手法を提案する。 これにより、量子セキュアな片方向関数を仮定して、スケーラブルで量子アクセス可能で適応的なPRFSを初めて構築することが可能になる。
  論文  参考訳（メタデータ） (2025-07-30T10:02:45Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• Existential Unforgeability in Quantum Authentication From Quantum Physical Unclonable Functions Based on Random von Neumann Measurement [45.386403865847235]
  物理的非閉包関数(PUF)は、固有の非閉包不可能な物理的ランダム性を利用して、ユニークな入出力ペアを生成する。 量子PUF(Quantum PUFs)は、量子状態を入出力ペアとして使用することによって、この概念を拡張している。 ランダムなユニタリQPUFは、量子多項式時間に対する実存的非偽造性を達成できないことを示す。 本稿では,QPUFが非単体量子チャネルとして機能する2番目のモデルを提案する。
  論文  参考訳（メタデータ） (2024-04-17T12:16:41Z)
• Pseudorandom unitaries with non-adaptive security [43.15464425520681]
  本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。 このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
  論文  参考訳（メタデータ） (2024-02-22T18:56:37Z)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。 我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
  論文  参考訳（メタデータ） (2024-01-25T17:13:51Z)
• Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
  量子世界と古典世界における擬似ランダム性の概念の関連について研究する。 量子擬似乱数発生器(QPRGs)と呼ばれる擬似乱数発生器の自然変種は対数出力長PSRGsの存在に基づいていることを示す。 また、擬似乱数関数のような状態生成器と擬似乱数関数の関係についても検討する。
  論文  参考訳（メタデータ） (2023-06-09T01:16:58Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  おもちゃの光ファイバーをベースとしたセットアップを用いてバイナリシリーズを生成し、そのランダム度をVilleの原理に従って評価する。 標準統計指標の電池、ハースト、コルモゴロフ複雑性、最小エントロピー、埋め込みのTakensarity次元、および拡張ディッキー・フラーとクワイアトコフスキー・フィリップス・シュミット・シン(英語版)でテストされ、ステーション指数をチェックする。 Toeplitz 抽出器を不規則級数に適用することにより得られる系列のランダム性のレベルは、非還元原料のレベルと区別できない。
  論文  参考訳（メタデータ） (2022-08-31T17:39:29Z)

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

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