No Size-Preserving Amplification with Quantum Advice
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.03377
curl -X POST /api/v1/records/arxiv/2610.03377/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.03377/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'