Quantum advice length must grow for smaller error in computations
No Size-Preserving Amplification with Quantum Advice
Computational Complexity
Summary
The paper investigates how giving a quantum computer extra information (called quantum advice) helps it make decisions with fewer mistakes. The authors show that reducing error in certain quantum computations requires longer quantum advice, meaning you cannot keep the advice size fixed while improving accuracy. This contrasts with some earlier results in quantum complexity where error could be reduced without increasing witness size. Their work also compares quantum advice with classical advice and finds fundamental limits on advice size growth for error reduction.
What this means in practice
- •For quantum algorithm designers: Guide resource allocation by showing that smaller error probabilities require longer quantum advice states for some problems.
- •For quantum computing system builders: Inform system design limits on quantum advice size needed for achieving low error in quantum computations with fixed-time constraints.
A theory result. No direct application yet.
Authors
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)\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$.