No Size-Preserving Amplification with Quantum Advice

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)\ge n^4$ and every error bound $\epsilon (n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $\delta$ with $\delta (n)=O(\min \{(\log m/m{)}^{1/4},\sqrt{\log m/m}/(1/2-\epsilon (n))\})$ such that ${\mathsf{BQP}}_{\epsilon }/\mathsf{q}m⊊{\mathsf{BQP}}_{\epsilon +\delta }/\mathsf{q}m$; for constant $\epsilon$ the gap is $O(\sqrt{\log m/m})$. Here, ${\mathsf{BQP}}_{\epsilon }/\mathsf{q}m$ is the class of languages recognizable with error at most $\epsilon (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}}_{\epsilon +\delta }/\mathsf{r}m\not\subset {\mathsf{BQP}}_{\epsilon }/\mathsf{q}m$, where ${\mathsf{P}}_{\epsilon }/\mathsf{r}m$ is the class of languages recognizable with error at most $\epsilon (n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.