論文の概要: A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles
- arxiv url: http://arxiv.org/abs/2401.14319v3
- Date: Tue, 30 Jan 2024 01:59:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 08:17:26.314944
- Title: A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles
- Title（参考訳）: ランダムオラクルからの擬似乱数発生器構築のための量子「リフティング定理」
- Authors: Jonathan Katz, Ben Sela,
- Abstract要約: ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。
我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
- 参考スコア（独自算出の注目度）: 7.454028086083526
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle.
- Abstract（参考訳）: ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。
我々は、大まかに言えば、そのようなPRGが古典的敵に対して無条件に安全であり、多項式的に多くのクエリをランダムなオラクルに生成するならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
独立な関心の結果として、疑似決定論的量子軌道アルゴリズム(すなわち、確率の高い量子アルゴリズムは繰り返し実行時に同じ値を返す)は、計算的に非有界であるが、クエリ数に多項式の爆発しか持たない有界な古典軌道アルゴリズムによってシミュレートできることを示す。
これは、我々の持ち上げ定理が、ランダムなオラクルへの量子クエリをそれ自体が生成するPRGに対しても成り立つという結論である。
関連論文リスト
- Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
量子世界と古典世界における擬似ランダム性の概念の関連について研究する。
量子擬似乱数発生器(QPRGs)と呼ばれる擬似乱数発生器の自然変種は対数出力長PSRGsの存在に基づいていることを示す。
また、擬似乱数関数のような状態生成器と擬似乱数関数の関係についても検討する。
論文 参考訳（メタデータ） (2023-06-09T01:16:58Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Verifiable Quantum Advantage without Structure [15.701707809084716]
ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換える。
以上の結果の最小限のインスタンス化が可能である。
論文 参考訳（メタデータ） (2022-04-05T08:58:24Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳（メタデータ） (2021-03-16T20:54:12Z) - Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。
オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。
乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
論文 参考訳（メタデータ） (2021-03-16T11:05:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。