arXiv:2610.03377
No Size-Preserving Amplification with Quantum Advice
Shih-Han Hung, Han-Hsuan Lin
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)=ω(1)$ 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$.
AI Summary
Marriott–Watrous amplification reduces QMA verification error without enlarging the witness. This paper asks whether computation with quantum advice admits an analogous guarantee when the advice length is fixed, even if both the algorithm and advice encoding may be redesigned. For every polynomially bounded $m(n)=\omega(1)$ and error bound $\varepsilon(n)<1/2$ with inverse-polynomial bias, it establishes $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m\subsetneq\mathsf{BQP}_{\varepsilon+\delta}/\mathsf{q}m$ for a positive gap $\delta=O(\min\{(\log m/m)^{1/4},\sqrt{\log m/m}/(1/2-\varepsilon)\})$. For constant $0<\varepsilon<1/2$, the gap is $O_\varepsilon(\sqrt{\log m/m})$, and the larger error remains below $1/2$ eventually. The separating language already has a deterministic polynomial-time algorithm supplied with randomized classical advice of the same length; the lower bound allows mixed quantum advice and arbitrary computation time. The proof combines Nayak’s quantum random-access-code bound, $m\geq(1-H(\varepsilon))k$, with diagonalization over uniform quantum decoders. The upper bound constructs efficiently decodable classical random access codes using systematic Toeplitz linear codes, a second-moment distance estimate, and shared random masks and cyclic shifts across blocks. Sharing the randomization amortizes its description cost; balancing block redundancy and header size gives normalized overhead $O(\sqrt{\log k/k})$. Encoding may be computationally expensive because advice preparation is unrestricted. The result concerns fixed advice budgets, not amplification within $\mathsf{BQP}/\mathsf{qpoly}$, where extra copies are allowed. The optimal separation gap remains open, including whether arbitrarily small improvements can require longer advice or some nonzero error reduction is always possible at fixed size.
Beyond assistance with writing and presentation, AI contributed to the technical development of the paper.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.