Quantum information · Theory (AI-assisted)

Lower bounds for testing the completely depolarizing channel

Hirak Ghosh, Andrew Jackson, Animesh Datta

arXiv:2611.20366v1 ↗PDF ↗Submitted 16 November 2026

Question
Given black-box access to a channel from \(d_{\mathrm{in}}\) to \(d_{\mathrm{out}}\) dimensions, how many uses are needed to decide whether it is the completely depolarizing channel or at least \(\varepsilon\) away from it in diamond distance, when the tester may entangle its inputs with an ancilla, measure coherently and adapt later inputs to earlier outputs? A coherent non-adaptive test with \(O(d_{\mathrm{in}}^2d_{\mathrm{out}}/\varepsilon^2)\) uses was known, but the best lower bound for adaptive testers was only \(\Omega(\sqrt{d_{\mathrm{in}}}/\varepsilon)\).
Result
Every coherent adaptive tester needs \(\Omega(d_{\mathrm{in}}d_{\mathrm{out}}/\varepsilon^2)\) uses, and every coherent non-adaptive tester needs \(\max\{\Omega(d_{\mathrm{in}}^{1.5}d_{\mathrm{out}}/\varepsilon^2),\Omega(d_{\mathrm{in}}^2/\varepsilon^2)\}\). The same bounds hold for deciding whether a channel replaces every input by one fixed state, for any state, or is \(\varepsilon\)-far from all such channels.

The paper in detail

The completely depolarizing channel \(\mathcal N(X)=\mathrm{tr}(X)\,I/d_{\mathrm{out}}\) forgets its input and outputs the maximally mixed state. Testing for it is the channel version of mixedness testing for states, which needs \(\Theta(d/\varepsilon^2)\) copies, and of uniformity testing for distributions. A channel tester has freedoms a state tester lacks: it chooses the inputs, may entangle them with a private ancilla, may use the channel in parallel or one use after another, and may let later inputs depend coherently on earlier outputs. Known results covered testers that measure each output separately and gave a coherent non-adaptive test with \(O(d_{\mathrm{in}}^2d_{\mathrm{out}}/\varepsilon^2)\) uses.

The lower bounds use one family of hard channels. A Haar-random unit vector \(v\) marks a hidden input direction, and a Haar-random unitary \(U\) rotates a fixed traceless perturbation \(\Delta_0\) with eigenvalues \(\pm1/\sqrt{d_{\mathrm{out}}}\) (for even \(d_{\mathrm{out}}\); an appendix treats odd dimensions). The channel acts as the depolarizing channel except on \(v\), where it outputs \(\tau+\frac{\varepsilon}{\sqrt{d_{\mathrm{out}}}}U\Delta_0U^\dagger\). Each use behaves like a two-outcome measurement, a hit along \(v\) or a miss, and only hits carry information. Every instance is a valid channel for \(\varepsilon\le1\) and sits at diamond distance \(\varepsilon\) from \(\mathcal N\).

For non-adaptive testers the proof bounds the trace distance between the averaged final states under the two hypotheses, splitting it into records with few hits and records with many. Since an unknown direction is hit with probability \(1/d_{\mathrm{in}}\) per use on average, Markov's inequality controls the records with many hits. For the others the authors pass to a chi-squared bound and average over Haar-random \(v\) and \(U\): odd-order terms vanish, the two-hit term leads, and controlling higher orders gives \(\Omega(d_{\mathrm{in}}^{1.5}d_{\mathrm{out}}/\varepsilon^2)\). Fixing \(U=I\) keeps single-hit terms, which form a geometric series with ratio \(m\varepsilon^2/d_{\mathrm{in}}\), giving the second bound \(\Omega(d_{\mathrm{in}}^2/\varepsilon^2)\).

Adaptive testers can steer later inputs toward \(v\), so the fixed-input averaging no longer applies. The authors truncate: in a modified experiment, every hit after the \(m\)-th returns the maximally mixed state. They then express the truncated experiment as a parameter-independent, completely positive, trace-nonincreasing map acting on \(m\) copies of the perturbed output, in the spirit of Das and Wilde's adaptive-to-non-adaptive reduction, and bound \(m\)-copy state discrimination. An appendix extends both bounds to the problem of testing whether a channel replaces every input by a fixed state.

Transferable methods

  1. Hiding the deviation in a random input direction

    A tester learns about the deviation only when its input overlaps the hidden direction. Making that direction Haar-random forces any tester to spend about \(d_{\mathrm{in}}\) uses per informative hit, and the output perturbation on each hit is itself a hard mixedness-testing instance.

    The hard channel is \(\mathcal M(X)=\mathcal N(X)+\frac{\varepsilon}{\sqrt{d_{\mathrm{out}}}}\mathrm{tr}(PX)\,\Delta\) with \(P=\ket v\bra v\) and \(\Delta=U\Delta_0U^\dagger\), where \(\Delta_0\) is traceless with \(\|\Delta_0\|_2=1\), \(\|\Delta_0\|_\infty=1/\sqrt{d_{\mathrm{out}}}\) and \(\|\Delta_0\|_1=\sqrt{d_{\mathrm{out}}}\). The output on a hit has eigenvalues \((1\pm\varepsilon)/d_{\mathrm{out}}\), so the map is completely positive exactly when \(\varepsilon\le1\).

    Editorial step: for any input \(\rho\) on the channel and an ancilla, \[(\mathcal M-\mathcal N)\otimes\mathrm{id}(\rho)=\frac{\varepsilon}{\sqrt{d_{\mathrm{out}}}}\,\Delta\otimes\mathrm{tr}_A\bigl[(P\otimes I)\rho\bigr],\] whose trace norm is at most \(\frac{\varepsilon}{\sqrt{d_{\mathrm{out}}}}\|\Delta\|_1=\varepsilon\), with equality for the input \(P\). So the diamond distance is exactly \(\varepsilon\), which an SDP confirms numerically. For any fixed input the Haar average gives \(\mathbb E_vP=I/d_{\mathrm{in}}\), so \(n\) uses produce \(n/d_{\mathrm{in}}\) hits on average, and more generally \(\mathbb E_vP^{\otimes j}=\Pi^{(j)}_{\mathrm{sym}}/\binom{d+j-1}{j}\).

    Editorial heuristic for the adaptive bound: each hit yields one copy of \(\tau+\frac{\varepsilon}{d_{\mathrm{out}}}U\Sigma U^\dagger\), and distinguishing \(m\) such copies from the maximally mixed state needs \(m\gtrsim d_{\mathrm{out}}/\varepsilon^2\). Hits arrive at rate \(1/d_{\mathrm{in}}\), so \(n\gtrsim d_{\mathrm{in}}d_{\mathrm{out}}/\varepsilon^2\). The paper's truncation argument makes this rigorous for adaptive testers.

    How to reuse it

    Lower bounds for testing an operation often reduce to state testing by planting the deviation where the tester has to search for it. The bound is then roughly the cost of finding one informative use multiplied by the number of samples a state tester needs.

  2. Truncation and simulation for adaptive testers

    An adaptive tester can correlate later inputs with the hidden direction, which breaks averaging over fixed inputs. Capping the number of informative events, and then absorbing every adaptive step into a map that does not depend on the hidden parameters, reduces the problem to non-adaptive discrimination of a bounded number of copies.

    Split the trace distance between the null and averaged alternative final states by hit records: \[\tfrac12\|\sigma_0-\bar\sigma\|_1\le\tfrac12\|X_m\|_1+\tfrac12\|Y_m\|_1,\] with \(X_m\) from records with at most \(m\) hits and \(Y_m\) from the rest. Markov's inequality bounds the second term by \(n/(md_{\mathrm{in}})\).

    In the truncated experiment, hits after the \(m\)-th output \(\tau\). Its final state can be written as a completely positive, trace-nonincreasing map, independent of \(v\) and \(U\), applied to at most \(m\) copies of the perturbed output, so data processing bounds the low-hit term by an \(m\)-copy discrimination problem. The quantum chi-squared bound \(\|\sigma-\rho\|_1^2\le\mathrm{tr}[(\sigma-\rho)\rho^{-1}(\sigma-\rho)]\), with \(\rho\) maximally mixed, turns that problem into Haar moment calculations.

    Editorial remark on why odd orders vanish: \(\Delta_0\) and \(-\Delta_0\) are unitarily equivalent, since swapping each pair of basis vectors flips the sign, so \(U\Delta_0U^\dagger\) and \(-U\Delta_0U^\dagger\) have the same Haar distribution. Any term containing an odd number of perturbations therefore averages to zero, and the first surviving contribution comes from two hits.

    How to reuse it

    Truncation plus a parameter-free simulation map applies whenever the unknown parameter matters only through rare events: cap the number of informative events, show the cap rarely binds, and treat the rest as non-adaptive discrimination. The same pattern appears in lower bounds for adaptive channel estimation.

Source: Section 1.1 (proof overview), Section 2.2 (Haar moments), Section 3.1 (hard family), Section 4 as summarised in Section 1.1. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. With one input dimension the adaptive bound reduces to the optimal \(\Theta(d/\varepsilon^2)\) for testing whether a state is maximally mixed, so the result shows how the input dimension multiplies the cost of state testing when the deviation hides in an unknown input direction. It raises the adaptive lower bound from \(\sqrt{d_{\mathrm{in}}}/\varepsilon\) to \(d_{\mathrm{in}}d_{\mathrm{out}}/\varepsilon^2\).

Limitations. No matching upper bounds are given: a factor of \(d_{\mathrm{in}}\) separates the adaptive lower bound from the best known test, and \(\sqrt{d_{\mathrm{in}}}\) separates the non-adaptive bounds. The two non-adaptive bounds cross at \(d_{\mathrm{out}}\sim\sqrt{d_{\mathrm{in}}}\), which the authors say may be an artefact of the analysis. All bounds come from one family of hard channels. The authors state that ChatGPT 5.6 Sol, through the University of Warwick's NebulaOne, suggested the beta-function representation used to bound \(h(k)\) in Appendix B, and the LaTeX code for Figures 1 and 2.

Description based on the full arXiv HTML of v1, read 2026-11-18: Section 1 (results and proof overview), Section 2 (notation, Haar moments, access models and the reduction lemma) and Sections 3.1–3.2 (hard family, validity checks and reduction to an averaged trace distance). The moment expansions in Sections 3.3–3.5, the adaptive proof in Section 4 and the appendices (odd output dimension, the beta-function bound, the state-replacement extension) were read only through the overview. Editorial checks: for \(d_{\mathrm{in}}=3\), \(d_{\mathrm{out}}=4\), \(\varepsilon=0.6\) and a Haar-random instance, \(\Delta_0\) has trace 0, Hilbert–Schmidt norm 1, operator norm \(1/\sqrt{d_{\mathrm{out}}}\) and trace norm \(\sqrt{d_{\mathrm{out}}}\); a semidefinite program gives the diamond norm of \(\mathcal M-\mathcal N\) as 0.600, so the hard instance is exactly \(\varepsilon\) away; and an average of \(P\otimes P\) over 20,000 Haar-random vectors in dimension 3 matches \(\Pi_{\mathrm{sym}}/6\) to \(2\times10^{-3}\).