論文の概要: QIP $ \subseteq $ AM(2QCFA)

• arxiv url: http://arxiv.org/abs/2508.21020v1
• Date: Thu, 28 Aug 2025 17:22:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-29 18:12:02.533158
• Title: QIP $ \subseteq $ AM(2QCFA)
• Title（参考訳）: QIP $ \subseteq $ AM(2QCFA)
• Authors: Abuzer Yakaryılmaz,
• Abstract要約: 我々は、$mathsfPSPACE$は、Arthur-Merlin証明システムを持つ言語のクラスである$mathsfAM (2QCFA)$のサブセットであることを示す。 我々のプロトコルは、有理値量子遷移のみを使用し、二重指数期待時間で実行される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness).
• Abstract（参考訳）: 多項式時間古典的あるいは量子的対話的証明システムを持つ言語のクラス(それぞれ$\mathsf{IP}$または$\mathsf{QIP}$)は$\mathsf{PSPACE}$と同一である。 我々は、$\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) が $\mathsf{AM(2QCFA)}$ の部分集合であることを示す。 我々のプロトコルは、有理値量子遷移のみを使用し、二重指数期待時間で実行される。 さらに、メンバー文字列は確率1(即ち完全性)で受け入れられる。

関連論文リスト

• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
  量子誤り訂正符号 (EAQECCs) は, 従来のシングルトン境界を, frackn = frac13$以下のコードレートの既知の方法よりも少ない共有エンタングルメントで飽和させる。 古典的な $[n,k,d]_q$ のコードはパラメータ $[n,k,d;2k]]_q$ の EAQECC に変換できる。
  論文  参考訳（メタデータ） (2024-10-05T11:56:15Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。 まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。 我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
  論文  参考訳（メタデータ） (2024-01-03T09:12:25Z)
• The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
  絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。 また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
  論文  参考訳（メタデータ） (2024-01-02T22:25:56Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• 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)
• The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem [0.0]
  量子および古典状態を持つ2方向有限オートマトン(2QCFA)は、量子部分が非常に限定された量子計算のモデルである。 2QCFA は期待時間で $L_eq=am bm :m mathbbN$ を認識でき、a,b*:w CFA CFA は期待指数時間で parindrome$ を認識できることを示す。
  論文  参考訳（メタデータ） (2020-03-22T12:46:37Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

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

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