No Size-Preserving Amplification with Quantum Advice

1 Introduction

• Unlike a QMA witness, quantum advice must work across all inputs of a given length, so Marriott–Watrous amplification guarantees do not directly apply [1].QMA soundness is required for every witness on a no-instance, whereas advice computation has no correctness obligation on other advice states.Source: §1 · pp. 1–2
• Even a vanishing additive error improvement can require longer advice, and the obstruction persists when the larger-error computation uses classical information.Copying a sampled advice string does not provide independent samples from its distribution.Source: §1 · p. 2
• The separation is stronger: deterministic polynomial-time computation with randomized m-bit advice at error ε+δ is not contained in quantum computation with m-qubit advice at error ε.The classical advice distribution depends only on input length, and its sample error remains below 1/2 for sufficiently large m.Source: §1 · p. 2
• A QRAC-based diagonalization turns Nayak’s lower bound [9] into an advice lower bound by treating answers on designated inputs as bits that must be individually recoverable.Below the encoding threshold, each fixed decoder fails on some string; choosing such a string at a separate input length for each machine yields a language outside the smaller-error class.Source: §1 · p. 2

1.1 Technical overview

• Randomized classical random-access codes approach the entropy bound up to an additive logarithmic term, but applying them requires an efficient uniform decoder and accounting for code and randomness descriptions.The paper addresses this by constructing efficiently decodable codes from systematic linear codes whose codewords have form (u, Tu), with T a random Toeplitz matrix.Source: §1 · pp. 2–3, §1.1 · p. 3
• Blockwise masking and a random cyclic shift spread expected reconstruction error across coordinates, giving every input string and queried bit the required error guarantee.The same matrix, mask, and shift can be reused across blocks because the guarantee is marginal per query, not independence across blocks.Source: §1.1 · p. 3
• Larger blocks reduce code redundancy but increase shared-header cost and coordinate-reconstruction work, so block length controls the overhead tradeoff.Choosing the parameters and translating overhead through binary entropy yields the vanishing error gap.Source: §1.1 · p. 3

1.2 Open questions

• The optimal quantitative limits remain open, including whether smaller additive error changes suffice and how the answer depends on initial error and decoding time.The paper also leaves open whether any nontrivial error reduction is always possible at fixed advice length.Source: §1.2 · p. 3

2.1 Notation and the binary entropy function

• Φ measures how much an error parameter may grow when its entropy budget increases by η; Φ(ε,η) ≤ κ√η, and Φ(ε,η) ≤ κ2η/(1/2−ε) when ε < 1/2.H is strictly increasing on [0, 1/2], with H(1/2) = 1; H−1:[0, 1]→[0, 1/2] denotes the inverse of that restriction.Source: §2.1 · p. 4

2.2 Random access codes

• A random access code encodes a k-bit string so a decoder can recover a requested bit; Nayak’s bound requires m ≥ (1−H(ε))k for quantum codes [9].Classical randomized codes are also quantum codes with the same parameters.Source: §2.2 · p. 5
• Classical randomized codes attain the lower bound up to O(log k) bits [2], while the paper’s Toeplitz-based construction supplies an efficient decoder.The earlier covering-code construction is not known to have an efficiently computable decoder.Source: §2.2 · pp. 5–6

2.3 Computational model and advice classes

• Pε/rm uses deterministic polynomial time with a length-dependent distribution over m-bit advice, while BQPε/qm uses polynomial-time quantum computation with an m-qubit state depending only on input length.The quantum advice may be mixed; random access to advice is built into the stated machine models.Source: §2.3 · p. 6

3 Efficiently decodable random access codes

• The construction combines second-moment covering inspired by Potukuchi and Zhang [11] with Toeplitz-based universal hashing [6], adapting random-access-code symmetrization to shared-parameter blocks.The shared Toeplitz matrix, mask, and cyclic shift amortize their description length while retaining efficient coordinate decoding.Source: §3 · p. 7

3.1 Random Toeplitz codes

• For a uniform random Toeplitz matrix, T u is uniform over F^q_2, and the probability that no vector in a radius-r Hamming ball has a specified syndrome is at most 2^q/V(ℓ,r).The covering bound supports a bound on the average distance to a random Toeplitz code.Source: §3.1 · pp. 8–9

3.2 Construction from a random Toeplitz code

• The block code shares one Toeplitz matrix, cyclic shift, and mask, stores each nearest codeword's systematic part, and reconstructs only the queried coordinate; its error ε*(ℓ,d) does not depend on B.Nearest-codeword search may be expensive, but it occurs during advice preparation; the header cost is shared across blocks.Source: §3.2 · p. 10

3.3 Trading decoding time for error

• For a decoder restricted to t steps, the additive loss above the information-theoretic lower bound H⁻¹(1−m/k) is governed by η=(log t)/t+t/k; its two terms balance at t₀=⌈√k log k⌉.Source: §3.3 · p. 14

4.2 The upper bound

• For admissible lengths, a random-access encoding gives a deterministic time-t algorithm with randomized m-bit advice and error ε′.The advice includes a header for parameters the machine cannot compute within its time bound.Source: §4.2 · pp. 15–16

4.1 The lower bound

• If m(n)<(1−H(ε(n)))k(n) at infinitely many lengths, some truth table cannot be decoded from any m-qubit advice state, yielding a language outside BQP_{ε}/qm.Decoding every truth-table bit with error at most ε(n) would require m(n) ≥ (1−H(ε(n)))k(n), by the random-access-code bound.Source: §4.1 · pp. 14–15, §4.3 · p. 17

4.3 The separations

• The lower and upper bounds make computation with randomized classical advice strictly more powerful than quantum advice at the smaller error bound, for polynomial decoding time.The separation statements apply only where ε+δ<1/2; beyond that, the classical class contains every language at that length.Source: §4.3 · pp. 16–17
• For polynomially bounded m(n) ≥ n^4 and 1/2−ε(n) ≥ n^-b, the paper obtains BQP_{ε}/qm ⊊ BQP_{ε+δ}/qm for a positive δ.The separations are meaningful at lengths where ε(n)+δ(n)<1/2; the paper also gives a stronger separation from polynomial-time randomized classical advice.Source: §4.3 · pp. 17–18

• AI assistance contributed to the technical development, including adapting the diagonalization argument and proposing a Toeplitz-matrix-based coding construction to reduce advice overhead.Source: AI statement · p. 18
• AI tools were used to explore constructions and parameter choices, derive and check intermediate bounds, identify potential proof gaps, and improve presentation.Source: AI statement · p. 19
• The authors examined and modified AI-generated ideas where necessary, independently checked them, and take responsibility for the final statements and proofs.Source: AI statement · p. 19