論文の概要: A slightly improved upper bound for quantum statistical zero-knowledge

• arxiv url: http://arxiv.org/abs/2512.11597v1
• Date: Fri, 12 Dec 2025 14:33:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-15 15:48:11.801981
• Title: A slightly improved upper bound for quantum statistical zero-knowledge
• Title（参考訳）: 量子統計ゼロ知識のためのわずかに改善された上界
• Authors: François Le Gall, Yupan Liu, Qisheng Wang,
• Abstract要約: 複雑性クラスであるQuantum Statistical Zero-Knowledge(mathsfQSZK$)は、最もよく知られた上限である$mathsfQIP(2) cap textco-mathsfQIP(2)$を持つ。 我々はこれを$mathsfQIP(2) cap textco-mathsfQIP(2)$に改善する。 我々の主な手法は、量子線型空間で実装可能なホレボ・ヘルストロム測度複雑性とウルマン変換のアルゴリズム版である。
• 参考スコア（独自算出の注目度）: 11.384500557173867
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, which was simplified following the inclusion $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\mathsf{QIP(2)}$ denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically \textit{computationally unbounded}, and $\text{co-}\mathsf{QIP(2)}$ denotes the complement of $\mathsf{QIP(2)}$. We slightly improve this upper bound to $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$ with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are an algorithmic version of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).
• Abstract（参考訳）: 複雑性クラスQuantum Statistical Zero-Knowledge$\mathsf{QSZK}$, Watrous (FOCS 2002), and later refined in Watrous (SICOMP, 2009), have the most known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, in the include $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009)。 ここで、$\mathsf{QIP(2)}$は、正直な証明者が典型的に \textit{computationally unbounded} であり、$\text{co-}\mathsf{QIP(2)}$ が $\mathsf{QIP(2)}$ の補集合であるような、2メッセージの量子対話的証明システムを認める約束問題のクラスを表す。 この上限を$\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$にわずかに改善する。 同様の改善は、非相互作用不変量 $\mathsf{NIQSZK}$ の上限にも適用される。 我々の主な手法は、Holevo-Helstrom測定のアルゴリズム版とUhlmann変換であり、どちらも量子線型空間で実装可能であり、L Gall, Liu, Wang (CC) の最近の空間効率のよい量子特異値変換を用いて、状態次元の多項式時間複雑性を示唆している。

関連論文リスト

• QIP $ \subseteq $ AM(2QCFA) [0.0]
  我々は、$mathsfPSPACE$は、Arthur-Merlin証明システムを持つ言語のクラスである$mathsfAM (2QCFA)$のサブセットであることを示す。 我々のプロトコルは、有理値量子遷移のみを使用し、二重指数期待時間で実行される。
  論文  参考訳（メタデータ） (2025-08-28T17:22:31Z)
• Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy [0.7321157455672144]
  証明に特有の量子古典的PCPの制限は、そのパワーを低下させるものではないことを示す。 また、カルプ・リプトンの定理の非一様量子類似性も証明する。 これらの結果は、量子証明システムの構造に関する新たな洞察を与える。
  論文  参考訳（メタデータ） (2025-06-24T16:59:50Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• 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)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)

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

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