No Size-Preserving Amplification with Quantum Advice

AI summary

Overview

Research area: Quantum complexity theory — specifically error reduction ("amplification") for polynomial-time quantum algorithms that receive quantum advice, and the resource cost of that advice measured in qubits.

Technical level: Advanced. The paper assumes familiarity with quantum complexity classes, density operators, random access codes, the binary entropy function, and diagonalization arguments. The introduction and Section 1.1 are readable by a graduate student in theory; the technical body is research-level.

Scope: The paper proves that, unlike the QMA case of Marriott and Watrous (Computational Complexity, 2005), reducing error for polynomial-time quantum computation with quantum advice cannot in general be done while preserving the advice length — even for a vanishing additive improvement in error.

What This Paper Is About

Marriott and Watrous showed that quantum Merlin–Arthur protocols can have their completeness and soundness errors reduced exponentially without increasing the witness size. This paper asks whether the analogous statement holds when the auxiliary quantum state is advice — a state depending only on the input length, with no soundness obligation toward arbitrary states. The authors answer no: for a wide range of advice lengths and error bounds, they exhibit decision problems for which any reduction in error forces the advice to grow.

Key Contributions

1. A refutation of size-preserving amplification for quantum advice. For every polynomially bounded advice length m(n) ≥ n⁴ and every error bound ε(n) that stays below 1/2 by at least an inverse polynomial, the paper exhibits a positive function δ with δ(n) = O(min{(log m/m)^{1/4}, √(log m/m)/(1/2 − ε(n))}) such that BQP_ε/qm ⊊ BQP_{ε+δ}/qm. For constant ε the gap is O(√(log m/m)).

2. A stronger separation against classical randomized advice. The result is obtained by proving P_{ε+δ}/rm ⊄ BQP_ε/qm, where P_ε/rm is deterministic polynomial-time computation with an m(n)-bit advice string sampled from a distribution depending only on n. Since randomized classical advice is a special case of mixed-state quantum advice, the quantum separation follows.

3. Efficiently decodable random access codes from random Toeplitz codes. The paper builds systematic linear codes with codewords of the form (u, Tu), where T is a random Toeplitz matrix specified by only ℓ − 1 bits, and proves a second-moment bound on the expected distance of a uniform word from the code (Corollary 3.4).

4. A shared-header block symmetrization. Adapting the symmetrization of Ambainis, Nayak, Ta-Shma and Vazirani to a block construction, the authors reuse one matrix, mask, and cyclic shift across all blocks so that the header cost is amortized, yielding normalized overhead of order log ℓ/ℓ + ℓ/k and hence the stated vanishing error gap.

Main Findings

• Amplification fails for quantum advice. The inclusion BQP_{ε'}/qm ⊆ BQP_ε/qm for ε < ε' does not hold in general: there are languages in the larger-error class that are outside the smaller-error class at the same advice length.

• A vanishing gap already suffices to break the property. The separation holds even for an additive error change of order O(m^{−1/4} log^{1/4} m) in the polynomial-advice regime, with ε + δ(m) < 1/2 for sufficiently large m, and O(√(log m/m)) for constant ε.

• The obstruction survives classical larger-error computation. Because the separating class P_{ε+δ}/rm uses only classical randomized advice, the failure is not an artifact of quantum advice on the larger-error side. Copying a sampled advice string does not produce independent samples, so ordinary repetition does not remove the obstruction.

• The mechanism is an information-theoretic threshold. Nayak's bound (m ≥ (1 − H(ε))k for a k ↦^ε m quantum random access code) says that below this budget every fixed decoder fails on some string. The Ambainis–Nayak–Ta-Shma–Vazirani result (m = (1 − H(ε))k + O(log k) for classical randomized codes, for every constant ε in (0, 1/2)) shows a slightly larger error fits a string into a budget that is insufficient at the smaller error.

• Efficiency of the decoder is the technical bottleneck. The known entropy-achieving classical random access codes rely on nonconstructive covering codes and are not known to be efficiently decodable; the paper's Toeplitz-based construction supplies an explicit, efficient decoder so the encoding can be used inside polynomial-time advice computation.

• Explicit constants in the perturbation analysis. The analysis uses κ = √(ln 2/2) ≈ 0.589 and η̄ = 1/(4κ²) = 1/(2 ln 2) ≈ 0.721, with Φ(ε, η) = min{κ√η, κ²η/(1/2 − ε)} measuring how much the error parameter may grow when its entropy budget grows by η (Lemma 2.1).

• Possible triviality above 1/2. Lemma 2.7(b) records that if ε ≥ 1/2 pointwise, every language is in DTIME(t)_ε/rm; and Lemma 2.7(c) records that if m(n) ≤ n^{O(1)} then P_ε/rm ⊆ BQP_ε/qm, which is why the separation is stated with 1/2 − ε bounded below by an inverse polynomial.

Methodology in Plain English

The proof is a diagonalization against all polynomial-time quantum algorithms with short advice, combined with an encoding construction that is efficient enough to be run by such an algorithm.

• Diagonalization. At a carefully chosen input length, the language's answers on k designated inputs are treated as a k-bit string. An algorithm that answers any one of those inputs using an m-qubit advice state is, by definition, a random access decoder for that string: given the advice, it can recover any requested bit. Nayak's lower bound then says that if m is too small relative to k and the target error ε, no advice state can serve all strings. The authors pick, at a separate input length for each machine, a string on which that machine must fail, producing a language outside BQP_ε/qm.

• Closing the gap from above. To place the same language inside the larger-error class, the authors need random access encodings that approach the entropy bound and that can be decoded in polynomial time. They build these from systematic linear codes whose codewords are (u, Tu) for a random Toeplitz matrix T. A Toeplitz matrix is specified by ℓ − 1 bits and a requested coordinate can be reconstructed from that description and u. The universality of Toeplitz hashing gives a second-moment bound on how far a random word sits from the code. Finding the nearest codeword may be expensive, but that search happens during advice preparation, which need not be efficient; decoding with the advice only reconstructs the requested coordinate.

• Symmetrizing the error. Following Ambainis et al., the authors split the string into blocks of length ℓ, apply a random additive mask (so each fixed input block is uniformly distributed) and a random cyclic shift (so the expected reconstruction error spreads evenly over coordinates). This turns an average-distance estimate into a guarantee for every input string and every requested bit. The same matrix, mask, and shift are reused across blocks, since the guarantee is only marginal per query, so their descriptions form one shared header amortized over the whole encoding.

• Choosing the block size. Larger blocks reduce the redundancy of the code but enlarge the shared header and the reconstruction work. Translating the overhead log ℓ/ℓ + ℓ/k through the binary entropy function produces the stated δ.

Why This Matters

Impact on research. Error reduction is usually treated as free; this paper identifies a resource setting — bounded-length quantum advice — where it provably is not. It also separates the witness model from the advice model more sharply than before: the Marriott–Watrous amplification for QMA does not transfer, because a witness may depend on the input while advice must work for all inputs of a length and carries no soundness requirement against other states. The paper supplies a new efficiently decodable random access code construction, which may be independently useful.

Real-world applications. The paper reports no applications, benchmarks, datasets, or implementations; it is a theorem-and-proof paper. The following are adjacent areas where bounded quantum advice is a natural model, not claims made by the authors:

• Certificate or specification design for small quantum devices, where a fixed state is prepared once and reused across many inputs.
• Quantum pseudorandomness and one-time preprocessing, where short quantum keys serve many queries.
• Compressed sensing-style encoding tasks where a decoder must recover individual coordinates rather than whole strings.
• Theory-side guidance for benchmarking proposals that claim error reduction at fixed quantum memory.

Industry relevance. Direct industrial relevance is not reported. The result is a constraint on claims: any proposal to improve the reliability of a quantum-aided computation without enlarging the quantum memory it consumes must contend with these separations, and the paper's separation is against classical randomized advice, so classical derandomization or repetition does not escape it.

Future Directions

• Optimal quantitative limits. The authors ask whether separations can be established for asymptotically smaller additive changes in error than the δ they obtain.

• Dependence on the starting error and decoding time. They ask how the achievable gap depends on the initial error ε and the permitted decoding time.

• A converse. They ask whether any nontrivial error reduction is always possible at fixed advice length, or whether arbitrarily small improvements can require additional advice; such a converse would give a lower bound on possible separation gaps.

• Redundancy bounds for random access constructions. Bounds on the redundancy of particular constructions would illuminate the limits of the present approach, while a general converse would require a statement about all algorithms and advice encodings.

Target Audience

Researchers in quantum complexity theory and quantum information who work on advice classes, error reduction, random access codes, or derandomization; graduate students seeking a concrete example of how witness-based amplification fails to transfer to advice; and theoretically inclined readers evaluating claims that quantum error reduction is free at fixed memory. Readers without a complexity-theory background will find the introduction accessible but the technical sections demanding.

Authors’ 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$.