論文の概要: The Knowledge Complexity of Quantum Problems

• arxiv url: http://arxiv.org/abs/2510.06923v1
• Date: Wed, 08 Oct 2025 12:00:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.470722
• Title: The Knowledge Complexity of Quantum Problems
• Title（参考訳）: 量子問題における知識複雑性
• Authors: Giulio Malavolta,
• Abstract要約: 対話プロトコルで証明可能な全ての量子問題は、ゼロ知識でも証明可能であることを示す。 本プロトコルは,暗号における標準的な仮定の下で,無条件の音質と計算ゼロ知識を実現する。
• 参考スコア（独自算出の注目度）: 15.563172757398293
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Foundational results in theoretical computer science have established that everything provable, is provable in zero knowledge. However, this assertion fundamentally assumes a classical interpretation of computation and many interesting physical statements that one can hope to prove are not characterized. In this work, we consider decision problems, where the problem instance itself is specified by a (pure) quantum state. We discuss several motivating examples for this notion and, as our main technical result, we show that every quantum problem that is provable with an interactive protocol, is also provable in zero-knowledge. Our protocol achieves unconditional soundness and computational zero-knowledge, under standard assumptions in cryptography. In addition, we show how our techniques yield a protocol for the Uhlmann transformation problem that achieves a meaningful notion of zero-knowledge, also in the presence of a malicious verifier.
• Abstract（参考訳）: 理論計算機科学における基礎的な結果は、すべてが証明可能であり、ゼロの知識で証明可能であることを証明している。 しかし、この主張は基本的に計算の古典的な解釈を前提としており、証明を希望する多くの興味深い物理的言明は特徴づけられていない。 本研究では、問題インスタンス自体が(純粋な)量子状態によって特定される決定問題について考察する。 この概念のいくつかのモチベーションの例について議論し、主要な技術的結果として、対話型プロトコルで証明可能な全ての量子問題は、ゼロ知識でも証明可能であることを示す。 本プロトコルは,暗号における標準的な仮定の下で,無条件の音質と計算ゼロ知識を実現する。 さらに、我々の手法が、悪質な検証器の存在下でも、ゼロ知識という意味のある概念を達成するウルマン変換問題に対するプロトコルをいかに生み出すかを示す。

関連論文リスト

• 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)
• Unitary Complexity and the Uhlmann Transformation Problem [39.6823854861458]
  本稿では, 単項合成問題の枠組みを導入し, 還元と単項複雑性クラスについて考察する。 このフレームワークは、ある絡み合った状態が局所的な操作によって別の状態に変換される複雑さを研究するのに使用します。 そこで我々は,多くの自然量子情報処理タスクの計算複雑性を研究するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-06-22T17:46:39Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Unclonability and Quantum Cryptanalysis: From Foundations to Applications [0.0]
  不規則性(Unclonability)は、量子理論の基本概念であり、量子情報の主要な非古典的性質の1つである。 我々は、量子世界、すなわち量子物理学的不閉性(quantum physical unclonability)という新しい非閉性の概念を導入する。 本稿では、暗号資源として、この新しいタイプの無拘束性(unclonability)のいくつかの応用について論じ、確実に安全な量子プロトコルを設計する。
  論文  参考訳（メタデータ） (2022-10-31T17:57:09Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。 我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
  論文  参考訳（メタデータ） (2020-11-05T05:40:05Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• Quantum entanglement recognition [0.0]
  機械学習技術に基づく絡み合いを探索するための枠組みを定式化する。 得られた量子エンタングルメント認識タスクは正確であり、よく制御されたエラーを割り当てることができることを示す。
  論文  参考訳（メタデータ） (2020-07-28T18:00:00Z)
• Classical proofs of quantum knowledge [10.432041176720842]
  検証者が古典的な設定で知識の証明という概念を定義する。 量子知識の非破壊的な古典的証明が何らかの状態に存在すれば、その状態は敵によってクローンできることを示す。
  論文  参考訳（メタデータ） (2020-05-04T17:45:21Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  本稿では、量子誤り訂正符号の品質と、論理ゲートの普遍的な集合を達成する能力とを結びつける、近似したイージン・クニル定理の証明を示す。 我々の導出は、一般的な量子気象プロトコルにおける量子フィッシャー情報に強力な境界を用いる。
  論文  参考訳（メタデータ） (2020-04-24T17:58:10Z)

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

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