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)≥ n4 and every error bound ε(n) that stays below 1/2 by at least an inverse polynomial, there is a positive function δ with δ(n)=O(min{(log m/m)1/4, √(log m/m) /(1/2−ε(n))}) such that BQPε/qm subsetneq BQPε + δ/qm; for constant ε the gap is O(√(log m/m)). Here, BQPε/qm is the class of languages recognizable with error at most ε(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 Pε+δ/r m not⊂ BQPε/q m, where Pε/rm is the class of languages recognizable with error at most ε(n) by a deterministic polynomial-time algorithm with an m(n)-bit advice string sampled from a distribution that depends only on n.
Related
- Quantum Noise Limited Nonlinear Phase-Preserving Amplification of a Bosonic Mode
- An Operator-Norm Approach to Security with Quantum Advice
- Quantum State Search with Classical Interactive Advice
- Securing quantum error correction against misleading advice from AI agents
- Optimal Quantum Purity Amplification: A Top-Down Approach to Error Suppression via Symmetry and Reversibility
BibTeX
@misc{hung2026sizepreserving,
title = {{No Size-Preserving Amplification with Quantum Advice}},
author = {Shih-Han Hung and Han-Hsuan Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03377},
eprint = {2610.03377},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03377},
}
RIS
TY - UNPB
TI - No Size-Preserving Amplification with Quantum Advice
AU - Shih-Han Hung
AU - Han-Hsuan Lin
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03377
UR - https://arxiv.org/abs/2610.03377
AB - 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)≥ n^4 and every error bound ε(n) that stays below 1/2 by at least an inverse polynomial, there is a positive function δ with δ(n)=O(min{(log m/m)^1/4, √(log m/m) /(1/2−ε(n))}) such that BQP_ε/qm subsetneq BQP_ε + δ/qm; for constant ε the gap is O(√(log m/m)). Here, BQP_ε/qm is the class of languages recognizable with error at most ε(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 P_ε+δ/r m not⊂ BQP_ε/q m, where P_ε/rm is the class of languages recognizable with error at most ε(n) by a deterministic polynomial-time algorithm with an m(n)-bit advice string sampled from a distribution that depends only on n.
ER -