論文の概要: Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

• arxiv url: http://arxiv.org/abs/2610.37635v1
• Date: Tue, 27 Oct 2026 17:54:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.738592
• Title: Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
• Title（参考訳）: 多項式階層を超えた量子計算の古典的検証
• Abstract要約: 古典的再帰時間検証器が任意の相関時間量子計算を、計算仮定なしで効率的な量子完全証明器で検証できるかどうかは不明である。 古典的なオラクルに対して、そのような検証は、量子時間で正確に決定される階層を超えた言語で可能であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.
• Abstract（参考訳）: 古典多項式時間検証器が任意の多項式時間量子計算を、計算仮定なしで効率的な量子完全証明器で検証できるかどうかは不明である。 古典的なオラクルに対して、そのような検証は、量子多項式時間で正確に決定される多項式階層を超えた言語で可能であることを示す。 プロトコルはパブリックコインであり、完全性と音質の誤差は最大1/4である。 我々の知る限り、そのような証明システムを持つ言語は、以前は、託宣に対してAMの外にあることが証明されなかった。 任意の非有界多項式時間計算可能関数に対して、メッセージカウントと量子アルゴリズム、検証器、および正直な証明器のオラクルクエリカウントが入力長のこの関数によって有界となるように、オラクルを選択することができる。 なぜなら、言語に対する全ての対話的証明システムは、このプロトコルのメッセージの少なくとも1つの定数を無限に多くの長さで使用し、検証者によっては一定であるからである。 この言語は、データテーブルに対処するシークレットをコードテーブルがエンコードする、再帰的なフーリエサンプリングの亜種である。 テーブルは再帰的に評価され、オラクルは葉のみを格納する。 量子アルゴリズムはすべてのシークレットを正確に復元し、検証者は証明者のシークレットをランダムコードエントリに対して再帰的にチェックする。 再帰は、同じ秘密が符号ビットを固定し、自由座標を選択するため、相関的な方法で入力を制限するため、ホーシュタットの切替補題は適用されない。 これらの制限に対してスイッチング定理を証明し、これは独立した関心を持つかもしれない。 十分な高さの場合には、270thrm{poly}(n)}$の一定の深さの回路は存在しないが、ランダムなインスタンスの解が1つの葉を変えて反転すると、その出力は2^{-Ω(n)}$以上の確率で変化する。

関連論文リスト

• Quantum State Search with Classical Interactive Advice [0.0]
  量子検証器は、量子状態を知っている非有界な証明者と古典的なメッセージを交換することで、隠れた量子状態を見つけることができるかどうかを考察する。 特に、言語が$LinmathrmQMAmathcalU$だが$LnotinmathrmQCIPmathcalU$が存在するようなユニタリオラクルに$mathcalU$を与える。
  論文  参考訳（メタデータ） (2026-10-19T02:03:35Z)
• Succinct Arguments for QMA in the Quantum Random Oracle Model [50.20559283775139]
  量子乱数オラクルモデル(QROM)におけるQMAの最初の簡潔な議論を、暗号的仮定や証明されていない予想に頼ることなく構築する。 我々の結果は、量子インタラクティブなオラクル証明(QIOP)を同じ言語の量子引数にコンパイルする効率保存変換である。
  論文  参考訳（メタデータ） (2026-09-29T12:54:55Z)
• EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity [0.0]
  片道パズルは EFI 対であり、ホールドがオープンかどうかを暗示する。 単方向パズルが存在しない1つの古典的オラクルを、有界検証器でも構成する。 EFIペアは、古典的に神託をクエリするすべての区別器を生き残り、それについてアドバイスし、最後に1つの重ね合わせクエリを作る。
  論文  参考訳（メタデータ） (2026-09-10T17:54:55Z)
• Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity [0.30458514384586394]
  量子暗号の時間境界メタ複雑化プログラムを開始する。 最近の研究は、ワンウェイ関数を持たない量子暗号の最小探索プリミティブであるワンウェイパズルを特徴づけている。
  論文  参考訳（メタデータ） (2026-09-02T14:54:44Z)
• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• 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)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

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

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