Fugu-MT 論文翻訳(概要): No Size-Preserving Amplification with Quantum Advice

論文の概要: No Size-Preserving Amplification with Quantum Advice

arxiv url: http://arxiv.org/abs/2610.03377v1
Date: Fri, 02 Oct 2026 14:32:20 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-06 00:14:30.421307
Title: No Size-Preserving Amplification with Quantum Advice
Title（参考訳）: 量子アドバイザによるサイズ保存増幅
Abstract要約: この状態保存増幅特性は、量子アドバイスを伴う量子時間計算では成り立たないことを示す。付加的な誤りを減らしても長いアドバイスを必要とする決定問題を提示する。
参考スコア（独自算出の注目度）: 1.0862038266991652
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)\geq n^4$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.
Abstract（参考訳）: Marriott と Watrous は、量子メルリン-アーサーゲームは目撃者のサイズを増大させることなく総称誤差の減少を認めることを示した(Computational Complexity, 2005)。本研究では, この状態保存増幅特性が, 量子アドバイス付き多項式時間量子計算では成り立たないことを示す。特に,加法的誤りの低減であっても,より長いアドバイスを必要とする決定問題を提示する。より正確には、すべての多項式有界アドバイス長 $m(n)\geq n^4$ と、少なくとも逆多項式によって 1/2$ 未満の任意の誤差有界な$\varepsilon(n)$ に対して、正の函数 $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ が成立する。ここで、$\mathsf{BQP}_\varepsilon/\mathsf{q}m$は、入力長$n$にのみ依存する$m(n)$-qubitアドバイス状態を持つ多項式時間量子アルゴリズムによって、最大で$\varepsilon(n)$の誤差で認識可能な言語のクラスである。ここでは、$\mathsf{P}_{\varepsilon +δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r} m$は、$n$のみに依存する分布からサンプリングされた$m(n)$-bitアドバイス文字列を持つ決定論的多項式時アルゴリズムにより、最大$\varepsilon(n)$で誤りを認識可能な言語のクラスであることを示す。

論文の概要: No Size-Preserving Amplification with Quantum Advice

関連論文リスト