Fugu-MT 論文翻訳(概要): ${\sf QMA}={\sf QMA}

論文の概要: ${\sf QMA}={\sf QMA}_1$ with an infinite counter

arxiv url: http://arxiv.org/abs/2506.15551v1
Date: Wed, 18 Jun 2025 15:23:40 GMT
ステータス: 翻訳完了
システム内更新日: 2025-06-19 19:35:51.71365
Title: ${\sf QMA}={\sf QMA}_1$ with an infinite counter
Title（参考訳）: ${\sf QMA}={\sf QMA}_1$ with an infinite counter
Authors: Stacey Jeffery, Freek Witteveen,
Abstract要約: sf QMA=sf QMAinfty=sf QMA_1inftyを示す。完全性を増幅するだけで、音性ではなく、以前の$sf QMA$アンプよりもはるかに少ない時間で、$sf QMA$アンプが得られます。我々の新しい構成は、元の検証子とその逆数に対する$O(1)$呼び出しと$O(log q)$他のゲートを使用して、完全性1-2-q$を達成する。
参考スコア（独自算出の注目度）: 0.5064404027153093
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A long-standing open problem in quantum complexity theory is whether ${\sf QMA}$, the quantum analogue of ${\sf NP}$, is equal to ${\sf QMA}_1$, its one-sided error variant. We show that ${\sf QMA}={\sf QMA}^{\infty}= {\sf QMA}_1^{\infty}$, where ${\sf QMA}_1^\infty$ is like ${\sf QMA}_1$, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an ``infinite counter'', and compare it to a program counter in a Las Vegas algorithm. The result ${\sf QMA}={\sf QMA}^\infty$ means such an infinite register does not increase the power of ${\sf QMA}$, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a ${\sf QMA}$-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous ${\sf QMA}$ amplifiers. Our new construction achieves completeness $1-2^{-q}$ using $O(1)$ calls to each of the original verifier and its inverse, and $O(\log q)$ other gates, proving that ${\sf QMA}$ has completeness doubly exponentially close to 1, i.e. ${\sf QMA}={\sf QMA}(1-2^{-2^r},2^{-r})$ for any polynomial $r$.
Abstract（参考訳）: 量子複雑性理論における長年の未解決問題は、${\sf QMA}$、${\sf NP}$の量子アナログである${\sf QMA}_1$が、その一方の誤り変種である${\sf QMA}_1$に等しいかどうかである。ここでは、${\sf QMA}={\sf QMA}^{\infty}= {\sf QMA}_1^{\infty}$, where ${\sf QMA}_1^\infty$ is like ${\sf QMA}_1$, but the verifier have a infinite register as as his witness system, which they can performed a shift (increment) operation。我々はこのレジスタを ' `infinite counter'' と呼び、ラスベガスのアルゴリズムでプログラムカウンタと比較する。その結果、${\sf QMA}={\sf QMA}^\infty$は、そのような無限レジスタが${\sf QMA}$のパワーを増加させるわけではないが、完全に完備であることを意味する。構成を有限次元に切り詰めることで、完全性のみを増幅する${\sf QMA}$アンプが得られるが、それ以前の${\sf QMA}$アンプよりもはるかに少ない時間で得られる。我々の新しい構成は、元の検証子とその逆数に対する$O(1)$呼び出しと$O(\log q)$他のゲートを使い、${\sf QMA}$が2倍に指数関数的に 1 に近い完全性を持つこと、すなわち${\sf QMA}={\sf QMA}(1-2^{-2^r},2^{-r})$ を任意の多項式 $r$ に対して達成する。

関連論文リスト

On estimating the quantum $\ell_α$ distance [2.637436382971936]
時間複雑性を持つ$mathrmT_alpha(rho_0,rho_1)$に対する効率的なランク独立量子推定器を開発した。我々のアルゴリズムは、量子状態微分可能性問題の計算複雑性の2分法をSchatten $alpha$-norm (QSD$_alpha$)で明らかにしている。この硬さは、1leq α leq infty$ の量子 $ell_alpha$ 距離に対する新しい階数依存の不等式に基づく還元の結果に続く。
論文参考訳（メタデータ） (2025-05-01T11:15:20Z)
Low-degree approximation of QAC$^0$ circuits [0.0]
パリティ関数はQAC$0$で計算できないことを示す。また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
論文参考訳（メタデータ） (2024-11-01T19:04:13Z)
On estimating the trace of quantum state powers [2.637436382971936]
量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
論文参考訳（メタデータ） (2024-10-17T13:57:13Z)
A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文参考訳（メタデータ） (2024-06-17T20:54:11Z)
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)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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