論文の概要: On quantum interactive proofs with a laconic prover

• arxiv url: http://arxiv.org/abs/2609.39495v2
• Date: Mon, 05 Oct 2026 15:39:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.464207
• Title: On quantum interactive proofs with a laconic prover
• Title（参考訳）: ラキニック証明器を用いた量子インタラクティブ証明について
• Abstract要約: クラス $sf QIP_elltext-rm bit(2)$, $ell$ は証明者の応答の長さである。 QSD$[a,b]$(および$sf QIP_elltext-rm bit(2)$)が$sf QSZK$のとき、$a(n)-b(n)geq 1/O(log n)$のとき、$sf QIP_elltext-rm bit(2)$)が$sf QSZK$であり、これを$sf QIP_からの回答圧縮と組み合わせる。
• 参考スコア（独自算出の注目度）: 0.8594140167290097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge ($\sf QSZK$), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to $\sf BQP$, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, where $\ell$ is the length of the prover's response, and establish: 1. A natural complete characterization of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is ${\sf QIP}_{\rm bit}$-complete. Since QSD is $\sf QSZK$-hard, our result places ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, for $\ell\geq 2$, in a landscape "just above" $\sf QSZK$. 2. Easy regimes for ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ collapsing to $\sf QSZK$. We prove that QSD$[a,b]$ (and thus ${\sf QIP}_{\rm bit}[a,b]$) is in $\sf QSZK$ when $a(n)-b(n)\geq 1/O(\log n)$, and combine this with an answer compression from ${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ to ${\sf QIP}_{\rm bit}$ to obtain another easy regime when $2c>(1+2^{\ell/2})s$. Remarkably, our improved polarization applies to SD and $\sf SZK$, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: ${\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]$ with constant gap is in $\sf BQP$, where ${\sf qc}\text{-}{\sf QAM}[\ell]$ is a subclass of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in which the verifier's question is exactly halves of EPR pairs.
• Abstract（参考訳）: Goldreich, Vadhan, and Wigderson (CC, 2002) により研究され、古典的な環境での対数的証明器通信で検証可能な問題を捉える。 2メッセージの量子アナログに対して、シングルビットの証明応答でさえ、Watrous (FOCS 2002) によって導入された量子統計ゼロ知識 (\sf QSZK$) を含む。 しかし、検証者の質問を古典的な公開硬貨に限定すると、Beigi、Shor、Watrous (ToC, 2011) が示すように、対応するクラスは$\sf BQP$に崩壊する。 さらに、ラキニック証明器を用いた2次元量子対話型証明システムについて検討する。 この目的のために、${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, where $\ell$ is the length of the prover's response, and established: 1. A natural complete characterization of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ by Multi-State Distinguishability。 特に量子状態分散性(QSD)は${\sf QIP}_{\rm bit}$-completeである。 QSD は $\sf QSZK$-hard であるため、この結果は ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, for $\ell\geq 2$, in a landscape " just above" $\sf QSZK$ となる。 2.${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$$$\sf QSZK$の簡単なレシエーション。 QSD$[a,b]$ (and ${\sf QIP}_{\rm bit}[a,b]$) is in $\sf QSZK$ when $a(n)-b(n)\geq 1/O(\log n)$, そしてこれを${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ to ${\sf QIP}_{\rm bit}$と組み合わせて、2c>(1+2^{\ell/2})のときの別の簡単なレシームを得る。 注目すべきは、改良された偏極化はSDと$\sf SZK$に適用され、Sahai and Vadhan (JACM, 2003) の開問題を解くことである。 一定のギャップを持つ$は$\sf BQP$であり、${\sf qc}\text{-}{\sf QAM}[\ell]$は${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$である。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference [0.5586191108738564]
  Sf StoqMA(2)$ は非絡み合いのメルリン・アーサー証明系のクラスである。 $sf StoqMA(2)$は半量子であり、$sf MA$に崩壊することもあるが、$sf StoqMA(2)$は驚くほど強力である。
  論文  参考訳（メタデータ） (2026-04-30T14:04:22Z)
• ${\sf QMA}={\sf QMA}_1$ with an infinite counter [0.5064404027153093]
  sf QMA=sf QMAinfty=sf QMA_1inftyを示す。 完全性を増幅するだけで、音性ではなく、以前の$sf QMA$アンプよりもはるかに少ない時間で、$sf QMA$アンプが得られます。 我々の新しい構成は、元の検証子とその逆数に対する$O(1)$呼び出しと$O(log q)$他のゲートを使用して、完全性1-2-q$を達成する。
  論文  参考訳（メタデータ） (2025-06-18T15:23:40Z)
• Space-bounded quantum interactive proof systems [2.623117146922531]
  空間有界量子対話型証明システムの2つのモデル、$sf QIPL$と$sf QIP_rm UL$を紹介する。 一方、$sf QIPL$は検証動作毎に多数のピンチ中間測度を対数的に許容する。
  論文  参考訳（メタデータ） (2024-10-31T14:11:08Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)

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

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