論文の概要: Space-bounded quantum interactive proof systems

• arxiv url: http://arxiv.org/abs/2410.23958v1
• Date: Thu, 31 Oct 2024 14:11:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 17:00:04.385591
• Title: Space-bounded quantum interactive proof systems
• Title（参考訳）: 空間有界量子対話型証明システム
• Authors: François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang,
• Abstract要約: 空間有界量子対話型証明システムの2つのモデル、$sf QIPL$と$sf QIP_rm UL$を紹介する。 $sf QIP_rm UL$モデルは、検証動作をユニタリ回路に制限する。対照的に、$sf QIPL$は検証動作ごとに、対数的に多くの中間測定を可能にする。
• 参考スコア（独自算出の注目度）: 2.623117146922531
• License:
• Abstract: We introduce two models of space-bounded quantum interactive proof systems, ${\sf QIPL}$ and ${\sf QIP_{\rm U}L}$. The ${\sf QIP_{\rm U}L}$ model, a space-bounded variant of quantum interactive proofs (${\sf QIP}$) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, ${\sf QIPL}$ allows logarithmically many intermediate measurements per verifier action (with a high-concentration condition on yes instances), making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995). We characterize the computational power of ${\sf QIPL}$ and ${\sf QIP_{\rm U}L}$. When the message number $m$ is polynomially bounded, ${\sf QIP_{\rm U}L} \subsetneq {\sf QIPL}$ unless ${\sf P} = {\sf NP}$: - ${\sf QIPL}$ exactly characterizes ${\sf NP}$. - ${\sf QIP_{\rm U}L}$ is contained in ${\sf P}$ and contains ${\sf SAC}^1 \cup {\sf BQL}$, where ${\sf SAC}^1$ denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits. However, this distinction vanishes when $m$ is constant. Our results further indicate that intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where ${\sf BQL}={\sf BQ_{\rm U}L}$. We also introduce space-bounded unitary quantum statistical zero-knowledge (${\sf QSZK_{\rm U}L}$), a specific form of ${\sf QIP_{\rm U}L}$ proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (${\sf QSZK}$) defined by Watrous (SICOMP 2009). We prove that ${\sf QSZK_{\rm U}L} = {\sf BQL}$, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.
• Abstract（参考訳）: 空間有界量子対話型証明システムの2つのモデル、${\sf QIPL}$と${\sf QIP_{\rm U}L}$を紹介する。 The ${\sf QIP_{\rm U}L}$ model, a space-bounded variant of quantum interactive proofs ({\sf QIP}$) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000)。 これとは対照的に、${\sf QIPL}$ は検証者アクションごとに対数的に多くの中間測度を許容し(イエスのインスタンスに高濃度の条件で)、コンドンとラドナーの古典的モデル(JCSS 1995)を包含する最も弱いモデルである。 我々は${\sf QIPL}$と${\sf QIP_{\rm U}L}$の計算能力を特徴づける。 メッセージ番号 $m$ が多項式境界であるとき、${\sf QIP_{\rm U}L} \subsetneq {\sf QIPL}$ は、${\sf P} = {\sf NP}$: - ${\sf QIPL}$ が${\sf NP}$ を正確に特徴づける。 -${\sf QIP_{\rm U}L}$は${\sf P}$に含まれ、${\sf SAC}^1 \cup {\sf BQL}$を含む。 しかし、この区別は$m$が一定であるときに消える。 さらに、中間測度が空間有界量子インタラクティブ証明に一意に影響を及ぼすことを示すが、これは空間有界量子計算では${\sf BQL}={\sf BQ_{\rm U}L}$である。 また、空間有界なユニタリ量子統計ゼロ知識({\sf QSZK_{\rm U}L}$)を導入し、任意の検証に対して統計的ゼロ知識を持つ証明系を${\sf QIP_{\rm U}L}$とする。 このクラスは、Watrous (SICOMP 2009) によって定義された量子統計ゼロ知識({\sf QSZK}$)の空間有界変種である。 我々は、${\sf QSZK_{\rm U}L} = {\sf BQL}$であることを証明する。

関連論文リスト

• Low-degree approximation of QAC$^0$ circuits [0.0]
  パリティ関数はQAC$0$で計算できないことを示す。 また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
  論文  参考訳（メタデータ） (2024-11-01T19:04:13Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• On estimating the trace of quantum state powers [2.637436382971936]
  量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。 我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
  論文  参考訳（メタデータ） (2024-10-17T13:57:13Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
  制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。 十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
  論文  参考訳（メタデータ） (2024-08-29T09:40:55Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• On the Role of Entanglement and Statistics in Learning [3.729242965449096]
  我々は,絡み合った,分離可能な,統計的に測定された学習モデルと学習モデルとの関係を理解することを進める。 我々は、QSQ学習と量子学習を交絡測定で指数関数的に分離するクラスC$を示す。 我々は,純度テスト,シャドウトモグラフィ,アベリア隠れ部分群問題,次数2$関数,植込み双斜め状態,クリフォード深度回路の出力状態について,超ポリノミカルQSQの下界を証明した。
  論文  参考訳（メタデータ） (2023-06-05T18:16:03Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
  論文  参考訳（メタデータ） (2023-03-03T16:53:30Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)

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

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