論文の概要: A Meta-Complexity Characterization of Quantum Cryptography
- arxiv url: http://arxiv.org/abs/2410.04984v1
- Date: Mon, 7 Oct 2024 12:29:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 00:57:50.151181
- Title: A Meta-Complexity Characterization of Quantum Cryptography
- Title（参考訳）: 量子暗号のメタ複雑性評価
- Authors: Bruno P. Cavalar, Eli Goldin, Matthew Gray, Peter Hall,
- Abstract要約: 量子暗号プリミティブの最初のメタ複雑性のキャラクタリゼーションを証明した。
片方向パズルが存在することは、カルモゴロフ複雑性を近似することが困難であるような二進弦の量子サンプリング可能な分布が存在する場合に限る。
- 参考スコア（独自算出の注目度）: 2.8311451575532156
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in NP or QMA, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.
- Abstract（参考訳）: 量子暗号プリミティブの最初のメタ複雑性のキャラクタリゼーションを証明した。
片方向パズルが存在することは、カルモゴロフ複雑性を近似することが困難であるような二進弦の量子サンプリング可能な分布が存在する場合に限る。
そこで,計算不能な問題の平均ケース硬さによって一方向パズルを特徴づける。
これは、LiuとPassによって始められたメタ複雑問題の平均ケース硬さで古典暗号を特徴づける最近の研究の行に量子設定をもたらす。
さらに、古典的に多項式時間サンプリング可能な分布上のコルモゴロフ複雑性の平均ケース硬さは片道関数を特徴づけるので、この結果は片道関数を量子設定に自然に一般化するものとして片道パズルを表わす。
さらに、我々の同値性は確率推定を通し、確率推定が難しい量子サンプリング可能な分布が存在する場合に限り、一方のパズルが存在するという追加の同値性を与える。
また、Kretschmerらによって定義されたオラクルの世界は、NPやQMAの問題の硬さによる片道パズルの相対的特徴付けを除外しているため、現在の手法では別のメタ複雑性問題で片道パズルを特徴づけることができない可能性がある。
関連論文リスト
- Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。
量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
論文 参考訳（メタデータ） (2024-09-23T17:45:33Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Krylov Complexity of Fermionic and Bosonic Gaussian States [9.194828630186072]
本稿では,量子複雑性の特殊形式であるemphKrylov複雑性に焦点を当てる。
量子状態があらゆる可能な基底に広がることの明確で本質的に意味のある評価を提供する。
論文 参考訳（メタデータ） (2023-09-19T07:32:04Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - How smooth is quantum complexity? [0.0]
ユニタリ作用素の「量子複雑性」は、基本量子ゲートの集合から構成の難しさを測定する。
本稿では、ユニタリ作用素の空間上の関数と見なされる様々な量子複雑性の概念について統一的な視点を示す。
論文 参考訳（メタデータ） (2021-06-15T17:58:08Z) - Quantum Oracle Separations from Complex but Easily Specified States [1.52292571922932]
量子オラクル (quantum oracle) は、量子計算中に呼び出し可能なブラックボックスである。
私たちは、タスクの複雑さの分離を維持しながら、古典的に簡単に指定できるようにマークされた状態を制約します。
古典的に定義されたオラクルは、量子アルゴリズムがステップ内の他のハードな状態を準備できるという事実を利用して、重出力サンプリングにおいて量子古典的なオラクル分離を観察する。
論文 参考訳（メタデータ） (2021-04-15T05:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。