論文の概要: Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions

• arxiv url: http://arxiv.org/abs/2602.18034v1
• Date: Fri, 20 Feb 2026 07:27:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-23 18:01:41.25626
• Title: Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions
• Title（参考訳）: Falsably Assumptions による量子計算の非対話的古典的検証
• Authors: Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki, Takashi Yamakawa,
• Abstract要約: マハデフはラーニング・ウィズ・エラー(Learning-with-Errors)の仮定に基づく量子計算の古典的検証のための最初のプロトコルを導入した。 このブレークスルーは、プレーンモデルでメッセージが少ないかどうかという疑問を自然に提起した。 我々は、$textsfQMA$の量子計算の非対話的古典的検証を、どんな偽りの仮定に対しても、量子ブラックボックスによる還元は存在しないことを証明した。
• 参考スコア（独自算出の注目度）: 11.346579815543075
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-message interactive scheme. This breakthrough naturally raised the question of whether fewer messages are possible in the plain model. Despite its importance, this question has remained unresolved. In this work, we prove that there is no quantum black-box reduction of non-interactive classical verification of quantum computation of $\textsf{QMA}$ to any falsifiable assumption. Here, "non-interactive" means that after an instance-independent setup, the protocol consists of a single message. This constitutes a strong negative result given that falsifiable assumptions cover almost all standard assumptions used in cryptography, including LWE. Our separation holds under the existence of a $\textsf{QMA} \text{-} \textsf{QCMA}$ gap problem. Essentially, these problems require a slightly stronger assumption than $\textsf{QMA}\neq \textsf{QCMA}$. To support the existence of such problems, we present a construction relative to a quantum unitary oracle.
• Abstract（参考訳）: マハデフ(SIAM J. Comput. 2022)は、LWE(Learning-with-Errors)仮定に基づく量子計算の古典的検証のための最初のプロトコルを導入し、4メッセージの対話型スキームを実現した。 このブレークスルーは、プレーンモデルでメッセージが少ないかどうかという疑問を自然に提起した。 その重要性にもかかわらず、この問題は未解決のままである。 本研究は,量子計算における非インタラクティブな古典的検証の量子ブラックボックスの削減が,任意の偽りの仮定に対して,$\textsf{QMA}$の量子計算に存在しないことを証明した。 ここでの"非インタラクティブ"とは、インスタンスに依存しないセットアップの後、プロトコルが単一のメッセージで構成されることを意味する。 これは、フェルス可能な仮定がLWEを含む暗号で使われるほとんどすべての標準仮定をカバーすることを考えると、強い負の結果である。 我々の分離は、$\textsf{QMA} \text{-} \textsf{QCMA}$ギャップ問題の存在の下で成り立つ。 本質的に、これらの問題は$\textsf{QMA}\neq \textsf{QCMA}$よりも少し強い仮定を必要とする。 このような問題の存在を支持するために、量子ユニタリオラクルに対する構成を提案する。

関連論文リスト

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  量子計算のための古典的簡潔な対話的引数(BQP)を構築する。 我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
  論文  参考訳（メタデータ） (2022-06-29T22:19:12Z)
• Indistinguishability Obfuscation of Null Quantum Circuits and Applications [17.72516323214125]
  我々は、ヌル量子回路(量子ヌル-iO)の不明瞭性難解化の概念を研究する。 我々は、量子null-iOが、我々の研究に先立って、仮定さえも存在しないような、新しい暗号プリミティブのシリーズを実現する方法を示す。
  論文  参考訳（メタデータ） (2021-06-11T00:08:14Z)
• 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 copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。 我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。 補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
  論文  参考訳（メタデータ） (2020-09-29T08:41:53Z)
• Simpler Proofs of Quantumness [16.12500804569801]
  量子性の証明は、量子デバイスが古典的なデバイスでは不可能な計算タスクを実行できることを示す方法である。 現在、量子性の証明を示すための3つのアプローチがある。 トラップドアの爪のない関数をベースとした量子性の2次元証明(Challenge-Response)を与える。
  論文  参考訳（メタデータ） (2020-05-11T01:31:18Z)
• Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
  我々は新しい普遍的な盲点量子計算プロトコルを提供する。 プロトコルの最初のフェーズは簡潔であり、その複雑さは回路サイズとは無関係である。
  論文  参考訳（メタデータ） (2020-04-27T07:47:11Z)

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

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