論文の概要: Cryptographic Characterization of Quantum Advantage
- arxiv url: http://arxiv.org/abs/2410.00499v2
- Date: Fri, 1 Nov 2024 08:46:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-05 05:16:55.532750
- Title: Cryptographic Characterization of Quantum Advantage
- Title（参考訳）: 量子アドバンテージの暗号解析
- Authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa,
- Abstract要約: 古典的な一方向パズル(OWPuzzs)が存在する場合に限って、量子性の非効率検証(IV-PoQ)が存在することを示す。
量子優位性の完全な暗号的特徴が得られたのはこれが初めてである。
- 参考スコア（独自算出の注目度）: 8.093227427119325
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ capture various types of quantum advantage previously studied, such as sampling-based quantum advantage and searching-based one. Previous work [Morimae and Yamakawa, Crypto 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before. Our result shows that quantum advantage is another application of OWPuzzs, which solves the open question of [Chung, Goldin, and Gray, Crypto 2024]. Moreover, it is the first quantum-computation-classical-communication (QCCC) application of OWPuzzs.
- Abstract（参考訳）: 量子計算の優位性は、量子コンピューティングでは容易だが古典的な計算では困難である計算タスクの存在を指す。
無条件で量子的優位性を示すことは、現在の複雑性理論の理解以上のものであり、従っていくつかの計算的な仮定が必要である。
どの複雑性の仮定が必要で、量子的優位性に十分か?
本稿では,古典的一方向パズル(OWPuzzs)が存在する場合にのみ,量子性の非効率検証証明(IV-PoQ)が存在することを示す。
私たちが知る限りでは、量子優位性の完全な暗号的特徴が得られたのはこれが初めてである。
IV-PoQは、サンプリングベースの量子アドバンテージや探索ベースの利点など、以前に研究された様々な種類の量子アドバンテージをキャプチャする。
これまでの研究(森前、山川、暗号2024)では、IV-PoQはOWFから構築できるが、弱い仮定によるIV-PoQの構築は未解決であった。
私たちの結果はオープンな問題を解決します。
OWPuzzsは、ワンウェイ関数(OWF)よりも弱い多くの量子暗号プリミティブによって暗示される最も基本的な量子暗号プリミティブの1つである。
したがって、IV-PoQと古典的なセキュリティを持つOWPuzzsの同値性は、量子的優位性がなければ、これらの基本原始は存在しないことを強調する。
等価性はまた、量子的優位性はOWPuzzsの応用の例であることを意味する。
コミットメントを除いて、OWPuzzsの応用は以前には知られていなかった。
この結果は,[Chung, Goldin, and Gray, Crypto 2024] の解答であるOWPuzzsの別の応用であることを示す。
さらに、OWPuzzsの最初の量子計算古典通信(QCCC)応用である。
関連論文リスト
- Quantum Cryptography and Meta-Complexity [2.6089354079273512]
古典暗号では、ワンウェイ関数(OWF)は最小の仮定であるが、量子暗号ではそうではない。
片方向パズル(OWPuzzs)がGapKが弱量子平均ハードである場合にのみ存在することを示す。
また、量子PRGが存在する場合、GapKは量子平均ハードであることを示す。
論文 参考訳（メタデータ） (2024-10-02T09:30:06Z) - Hard Quantum Extrapolations in Quantum Cryptography [9.214658764451348]
普遍外挿タスクの量子アナログについて検討する。
量子コミットメントが存在すれば困難であり、量子空間にとって容易であることを示す。
論文 参考訳（メタデータ） (2024-09-25T00:09:42Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - A Quantum-Classical Collaborative Training Architecture Based on Quantum
State Fidelity [50.387179833629254]
我々は,コ・テンク (co-TenQu) と呼ばれる古典量子アーキテクチャを導入する。
Co-TenQuは古典的なディープニューラルネットワークを41.72%まで向上させる。
他の量子ベースの手法よりも1.9倍も優れており、70.59%少ない量子ビットを使用しながら、同様の精度を達成している。
論文 参考訳（メタデータ） (2024-02-23T14:09:41Z) - A Cryptographic Perspective on the Verifiability of Quantum Advantage [5.857929080874288]
本稿では,暗号的観点からの量子優位性の検証について検討する。
量子優位性と暗号および複雑性プリミティブの妥当性の強い関係を確立する。
我々の研究は、検証可能な量子長所を求めることが量子暗号の応用につながる可能性を示唆している。
論文 参考訳（メタデータ） (2023-10-23T00:31:51Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
サンプルとクエリ(SQ)アクセスを持つ古典的アルゴリズムは量子状態入力を持つ量子アルゴリズムよりも指数関数的に高速に学習タスクを実現できることを示す。
これらの結果から,SQアクセスが量子状態入力に対して強すぎるため,指数的量子優位性が欠如していることが示唆された。
論文 参考訳（メタデータ） (2021-12-01T20:05:56Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
量子カーネルの利点は,大規模データセット,計測回数の少ないもの,システムノイズなどにおいて消失することを示した。
我々の研究は、NISQデバイス上で量子優位性を得るための先進量子カーネルの探索に関する理論的ガイダンスを提供する。
論文 参考訳（メタデータ） (2021-03-31T02:41:36Z) - Forging quantum data: classically defeating an IQP-based quantum test [0.0]
古典的)証明器が量子であることを検証者に納得させる古典的アルゴリズムについて述べる。
キー抽出アルゴリズムは,実際に数百量子ビットの問題を解くのに有効であることを示す。
論文 参考訳（メタデータ） (2019-12-11T19:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。