論文の概要: A Meta-Complexity Characterization of Minimal Quantum Cryptography
- arxiv url: http://arxiv.org/abs/2510.07859v1
- Date: Thu, 09 Oct 2025 07:00:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:14.918217
- Title: A Meta-Complexity Characterization of Minimal Quantum Cryptography
- Title（参考訳）: 最小量子暗号のメタ複雑性評価
- Authors: Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, Xingjian Li,
- Abstract要約: EFIペアは量子暗号における「最小」プリミティブと見なされている。
我々は、あるコルモゴロフのような複雑性測度を推定する問題は、1つのコピーで困難であるような、純粋状態上の一様でないサンプリング可能な分布が存在することを示した。
- 参考スコア（独自算出の注目度）: 6.324405323851617
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy. A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair.
- Abstract（参考訳）: 量子暗号における「最小」プリミティブと見なされる(量子コミットメントと等価である)EFIペアのメタ複雑性の特徴を与える。
より正確には、EFI対の存在は以下の通りである: あるコルモゴロフのような複雑性測度を推定する問題は、1つのコピーで困難となるような純粋状態上の非一様サンプリング可能な分布が存在する。
我々の証明における重要な技術的ステップは、EFI対の存在は、一様でない単一コピー安全な擬似ランダム状態発生器(nu 1-PRS)の存在と等価であることを示すことである。
結論として、普遍的な EFI 対の構築という選択肢が得られます。
関連論文リスト
- Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
パウリ分解において、与えられたハミルトニアンに対する量子状態準備のエネルギーを推定する問題を考える。
状態の実際の分散を用いた適応推定器を構築する。
論文 参考訳（メタデータ） (2025-02-03T19:00:01Z) - Predicting symmetries of quantum dynamics with optimal samples [41.42817348756889]
量子力学における対称性の同定は、量子技術に深く影響する重要な課題である。
グループ表現理論とサブグループ仮説テストを組み合わせた統合フレームワークを導入し,これらの対称性を最適効率で予測する。
我々は,並列戦略が適応プロトコルや不定値順序プロトコルと同じ性能を達成することを証明した。
論文 参考訳（メタデータ） (2025-02-03T15:57:50Z) - Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。
我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。
仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
論文 参考訳（メタデータ） (2024-10-10T16:10:10Z) - A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID [16.5193119873963]
EFI対が存在する量子ユニタリオラクルが存在することを示すが、OWSGは存在しない。
私たちは、オラクル、QEFID、片道パズルを通じて、OWSGや他のMicrocryptプリミティブから切り離しています。
論文 参考訳（メタデータ） (2024-10-04T14:11:56Z) - Pseudo-Entanglement is Necessary for EFI Pairs [0.0]
我々は、新しい量子資源、擬似絡み合いを考察し、EFI対の存在が擬似絡み合いの存在を意味することを示す。
この結果は,計算暗号の分野において重要な意味を持つ。
論文 参考訳（メタデータ） (2024-06-11T01:44:16Z) - Exponential Quantum One-Wayness and EFI Pairs [18.481934628015004]
古典暗号では、一方通行関数は最小の計算仮定であると広く考えられている。
片方向関数の探索量子一般化は片方向状態発生器(OWSG)である。
その結果,IV-OWSGs は EFI 対と正確に等価であり,比例的に減少することがわかった。
論文 参考訳（メタデータ） (2024-04-21T15:55:00Z) - On the computational hardness needed for quantum cryptography [10.760579667794476]
大規模な量子暗号アプリケーションにはEFIペアが必要であることを示す。
我々は、最小限のコミットメントスキーム、曖昧な転送、そして一般的なセキュアなマルチパーティ証明からEFIペアを構築する。
これは、量子暗号の多くにおいて、EFIペアが古典的な環境でのOWFと同じような役割を果たすことを示唆している。
論文 参考訳（メタデータ） (2022-09-09T03:22:05Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。