論文の概要: Single-Round Proofs of Quantumness from Knowledge Assumptions

• arxiv url: http://arxiv.org/abs/2405.15736v1
• Date: Fri, 24 May 2024 17:33:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-27 13:01:17.389915
• Title: Single-Round Proofs of Quantumness from Knowledge Assumptions
• Title（参考訳）: 知識推定による量子性の単行証明
• Authors: Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, Tony Metger,
• Abstract要約: 量子性の証明は、効率的な量子コンピュータが通過できる、効率よく検証可能な対話型テストである。 既存のシングルラウンドプロトコルは大きな量子回路を必要とするが、マルチラウンドプロトコルはより小さな回路を使用するが、実験的な中間回路測定を必要とする。 我々は、既存の知識仮定に基づいて、量子性の効率的なシングルラウンド証明を構築した。
• 参考スコア（独自算出の注目度）: 41.94295877935867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass, but all efficient classical computers cannot (under some cryptographic assumption). Such protocols play a crucial role in the certification of quantum devices. Existing single-round protocols (like asking the quantum computer to factor a large number) require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. As such, current proofs of quantumness are out of reach for near-term devices. In this work, we construct efficient single-round proofs of quantumness based on existing knowledge assumptions. While knowledge assumptions have not been previously considered in this context, we show that they provide a natural basis for separating classical and quantum computation. Specifically, we show that multi-round protocols based on Decisional Diffie-Hellman (DDH) or Learning With Errors (LWE) can be "compiled" into single-round protocols using a knowledge-of-exponent assumption or knowledge-of-lattice-point assumption, respectively. We also prove an adaptive hardcore-bit statement for a family of claw-free functions based on DDH, which might be of independent interest. Previous approaches to constructing single-round protocols relied on the random oracle model and thus incurred the overhead associated with instantiating the oracle with a cryptographic hash function. In contrast, our protocols have the same resource requirements as their multi-round counterparts without necessitating mid-circuit measurements, making them, arguably, the most efficient single-round proofs of quantumness to date. Our work also helps in understanding the interplay between black-box/white-box reductions and cryptographic assumptions in the design of proofs of quantumness.
• Abstract（参考訳）: 量子性の証明は、効率的な量子コンピュータが通過できるような、効率よく検証可能なインタラクティブなテストである。 このようなプロトコルは、量子デバイスの認証において重要な役割を果たす。 既存のシングルラウンドプロトコル(例えば、量子コンピュータに大量の因子を求めるなど)は大きな量子回路を必要とするが、マルチラウンドプロトコルはより小さな回路を使用するが、実験的な中間回路測定を必要とする。 そのため、量子性の現在の証明は、短期的なデバイスには届かない。 本研究では,既存の知識仮定に基づいて,量子性の効率的な単一ラウンド証明を構築する。 この文脈では知識仮定はこれまでに検討されていないが、古典計算と量子計算を分離するための自然な基礎を提供することを示す。 具体的には,Decisional Diffie-Hellman (DDH) やLearning With Errors (LWE) に基づくマルチラウンドプロトコルを,経験的仮定や相対的仮定を用いて,それぞれ単一ラウンドプロトコルに"コンパイル"可能であることを示す。 また,DDHに基づく無爪関数群に対する適応型ハードコアビットステートメントの証明を行った。 シングルラウンドプロトコルを構築するための従来のアプローチは、ランダムなオラクルモデルに頼っていたため、暗号ハッシュ関数でオラクルをインスタンス化する際のオーバーヘッドを発生させた。 対照的に、我々のプロトコルは、中間回路の測定を必要とせずに、マルチラウンドのプロトコルと同じリソース要件を持ち、量子性の最も効率的な単一ラウンド証明であることは間違いない。 我々の研究は、量子性の証明の設計におけるブラックボックス/ホワイトボックスの削減と暗号的仮定の間の相互作用を理解するのにも役立ちます。

関連論文リスト

• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  No-Free-Lunch(NFL)定理は、最適化プロセスに関係なく問題とデータ非依存の一般化誤差を定量化する。 我々は、様々な量子学習アルゴリズムを、特定の観測可能条件下で量子力学を学習するために設計された3つの学習プロトコルに分類する。 得られたNFL定理は, CLC-LP, ReQu-LP, Qu-LPにまたがるサンプルの複雑性を2次的に低減することを示した。 この性能差は、非直交量子状態のグローバル位相に関する情報を間接的に活用するために、量子関連学習プロトコルのユニークな能力に起因している。
  論文  参考訳（メタデータ） (2024-05-12T09:05:13Z)
• Entropy Accumulation under Post-Quantum Cryptographic Assumptions [4.416484585765028]
  デバイス非依存(DI)量子プロトコルでは、セキュリティステートメントは量子装置の特性を損なう。 本稿では,量子情報理論のツールの組み合わせを利用して,そのようなプロトコルの安全性を証明するフレキシブルなフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-07-02T12:52:54Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Classical verification of quantum depth [1.8613536568358358]
  量子深さの古典的検証のための2つのプロトコルを提案する。 第1のプロトコルは、情報理論のセキュリティとほぼ最適な分離により、ターゲットマシンの深さを認証する。 第2のプロトコルは、エラーを伴う学習の量子硬度に基づいて、単一のデバイスの量子深さを認証する。
  論文  参考訳（メタデータ） (2022-05-10T03:55:24Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• Simpler Proofs of Quantumness [16.12500804569801]
  量子性の証明は、量子デバイスが古典的なデバイスでは不可能な計算タスクを実行できることを示す方法である。 現在、量子性の証明を示すための3つのアプローチがある。 トラップドアの爪のない関数をベースとした量子性の2次元証明(Challenge-Response)を与える。
  論文  参考訳（メタデータ） (2020-05-11T01:31:18Z)
• Forging quantum data: classically defeating an IQP-based quantum test [0.0]
  古典的)証明器が量子であることを検証者に納得させる古典的アルゴリズムについて述べる。 キー抽出アルゴリズムは,実際に数百量子ビットの問題を解くのに有効であることを示す。
  論文  参考訳（メタデータ） (2019-12-11T19:00:00Z)

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

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