Partial Stabilizer Learning under Fixed Commuting Constraints and the Absence of a Copy-Rate Discount

AI summary

Overview

Research area: Quantum information theory — specifically quantum state learning / sample complexity of stabilizer states, with ties to Pauli (Weyl) measurement theory and symplectic geometry over finite fields.

Technical level: Advanced. The paper is a pure mathematical/theoretical treatment (symplectic vector spaces over $\mathbb{F}_p$, Lagrangian subspaces, pretty good measurement optimality, tensor-power moment counting). No experiments, no datasets, and no numerical benchmarks are reported anywhere in the content.

Scope (one sentence): The paper proves that learning only the complementary stabilizer information needed after a fixed commuting Pauli measurement — rather than the whole stabilizer state — still requires a copy rate $k/n$ of at least one, so there is no leading-order discount in quantum copies.

What This Paper Is About

An unknown pure stabilizer state of $n$ qudits (prime local dimension $p$) is presented to a learner, together with a fixed set of commuting Pauli observables specified by an isotropic subspace $W$ of dimension $n-m$. The learner does not have to reconstruct the whole state: it only has to output an $m$-dimensional subspace $K$ of stabilizer directions that commute with $W$, plus their eigenvalues, so that the reported data together with the eventual measurement outcome pins down the conditional post-measurement state.

The question is whether this reduced target lowers the number of copies $k$ needed, measured as the copy rate $k/n$. The answer is no: for targets with $m = \beta n + o(n)$, the threshold copy rate remains exactly one, both for exact learning and for a post-measurement verification game, and both in the worst case and under the uniform prior.

Key Contributions

1. Formal operational model for "partial" stabilizer learning. The paper defines the report alphabet $\mathsf{Out}{W,m}$ of admissible complementary stabilizer descriptions, defines validity relative to the unknown input, and shows (via the extension map $\mathrm{Ext}{W\oplus K}(\nu,\eta)$) that any valid report plus the observed outcome uniquely specifies the conditional pure stabilizer state — justifying the reduced target operationally.

2. A no-discount theorem (Theorem 2.2). For $m_n = \beta n + o(n)$ with fixed $0 < \beta \le 1$, all four optima — exact worst-case, exact uniform-average, verification worst-case, verification uniform-average — tend to zero when $k_n = \alpha n + o(n)$ with $\alpha < 1$, and tend to one when $k_n - n \to +\infty$. The resulting rate identities are $R_{\mathrm{wc}}(p,\beta,\epsilon) = R_{\mathrm{av}}(p,\beta,\epsilon) = 1$ for every $0 < \epsilon < 1$.

3. An auxiliary fixed-frame technique yielding a quadratic exponent. By giving the learner an ordered Lagrangian basis (a "frame") $R$ and restricting to inputs transverse to it, the problem becomes discrimination of a mixed conditioned ensemble; the authors prove the pretty good measurement (PGM) is optimal there by decomposing into orthogonal blocks and optimizing each block, then count tensor-power moments to get the bound with exponent $J(\alpha,\beta)n^2$.

4. A Lean 4 formalization of the main theorem (Theorem 2.2), with verification records and reproducibility instructions in version 1.0.0 of the accompanying repository [HL26b].

Main Findings

• Exact-learning converse: With $k_n = \alpha n + o(n)$, $0 \le \alpha < 1$, and $m_n = \beta n + o(n)$, the worst-case optimum obeys $P_{W_n,\mathrm{wc}}^{(k_n),}(n,m_n;p) \le p^{-J(\alpha,\beta)n^2 + e_n} \to 0$, where $e_n/n^2 \to 0$; the uniform-average optimum obeys $P_{W_n,\mathrm{av}}^{(k_n),}(n,m_n;p) \le C_p p^{-m_n} + p^{-J(\alpha,\beta)n^2+e_n} \to 0$ for a constant $C_p > 0$.

• The exponent $J(\alpha,\beta)$: defined piecewise as $J(\alpha,\beta) = \beta(1-\alpha-\beta/2)$ for $0 \le \alpha \le 1-\beta$, and $J(\alpha,\beta) = (1-\alpha)^2/2$ for $1-\beta \le \alpha < 1$.

• Uniformity over constraints: Both exact limits and both verification limits hold uniformly over every legal isotropic $W_n$ of dimension $n-m_n$; the threshold $N$ may depend on the sequences $(m_n), (k_n)$, but no uniformity over all admissible sequence pairs is claimed.

• Verification converse is separate: Under the same subcritical copy-rate hypothesis, $S_{W_n,\mathrm{ver,wc}}^{(k_n),}(n,m_n;p) \to 0$ and $S_{W_n,\mathrm{ver,av}}^{(k_n),}(n,m_n;p) \to 0$, proved with a distinct compatible-list argument rather than the coordinate bound.

• Direct part from full identification: If $k_n - n \to +\infty$, complete stabilizer identification succeeds with probability tending to one, and classical postprocessing then extracts a valid complementary report, so all four optima tend to one. The subcritical hypothesis is not assumed here.

• Dimension-only covariance (Proposition 2.1): All four finite-size optima depend on the prescribed constraint only through $n$, $m$, and $p$ — any two isotropic subspaces of the same dimension $n-m$ give identical optima.

• Special case $\beta = 1$ (complete identification): $W = {0}$ and the theorem recovers $P_{\mathrm{stab,id}}^{(k),*}(n;p) \le p^{-\frac{1}{2}(1-\alpha)^2 n^2 + o(n^2)} \to 0$ for $k = \alpha n + o(n)$, $0 \le \alpha < 1$.

• A worked two-qubit illustration: With $W$ generated by $Z$ on the second qubit, both $\lvert +0\rangle$ and $\lvert +1\rangle$ admit the report $K = \mathrm{span}{X_1}$ with eigenvalue $+1$, and $\lvert +0\rangle$ additionally admits $X_1 Z_2$ with eigenvalue $+1$ — showing both the omission of outcome-distribution information and the multi-validity of reports for exceptional inputs.

• Explicitly unresolved regimes: The theorem does not determine the full success profile in the fixed-offset window $k = n + O(1)$, nor the copy requirements for sublinear targets $m = o(n)$.

Methodology in Plain English

The argument works by making the problem harder in a controlled way, bounding the harder problem, and then transferring the bound back.

First, the authors introduce an auxiliary task in which the learner is handed extra classical side information: an ordered basis $R$ of a Lagrangian subspace, called a frame, and a promise that the unknown state's stabilizer subspace intersects that frame trivially. This promise makes the target unique — pairing with the frame vectors defines an isomorphism, giving unique "reference-dual" stabilizers $S_1(x;R),\dots,S_n(x;R)$ with $\langle S_i(x;R), R_j\rangle_{\mathrm{sp}} = \delta_{ij}$ — so the goal becomes identification of the first $m$ of these directions and their restricted character.

Second, in suitable coordinates, all inputs sharing the same refined target are averaged into one mixed state, turning exact learning into a discrimination problem among these mixed states. The authors prove that the pretty good measurement is optimal for this ensemble, which pure geometrically uniform ensembles alone would not cover, by splitting the ensemble into orthogonal blocks and optimizing block by block. Counting the tensor-power moments with their actual probability weights then gives a bound that vanishes quadratically in $n$ whenever the copy rate is below one. They also compare this bound in Section 8 against the cruder estimate that comes from merely counting the dimension of the ambient tensor space.

Third, they lift the result back to the original, basis-free problem: the uniform prior over generic inputs is written as a weighted mixture of the frame-conditioned distributions, so the exact bound transfers, with exceptional inputs carrying only small total mass. Verification needs separate handling — keeping the full report alphabet, they show that a report with appreciable acceptance probability defines a bounded list of compatible exact targets, and randomizing over that list compares verification against exact learning. Finally, complete-state identification supplies a statewise direct bound and, via classical postprocessing, a valid report.

Why This Matters

Impact on research. The paper places a sharp negative result against a natural intuition from property estimation, shadow tomography, and reduced-state reconstruction, where learning less usually costs fewer samples. It shows that for stabilizer states, restricting the target to the post-measurement complement gives no leading-order saving: prior complete-stabilizer procedures already used linearly many copies [Got08, Mon17], and the converse here shows that even the much smaller complementary output cannot beat rate one when $m$ is linear in $n$. It also distinguishes itself from stabilizer testing and known-target verification [HM15, DHZ20, HH25] and from limited-memory learning [AS26], where either the target or the measurement architecture — not the output size — is what gets restricted. The PGM-optimality argument for a mixed conditioned ensemble extends square-root-measurement results known for pure geometrically uniform ensembles [EF01].

Potential application areas (not evaluated in the paper):

• Benchmarking near-term hardware where only a subset of stabilizer observables is measured routinely, and where one wants to know how many repetitions are needed to predict post-measurement states.
• Calibration and validation of Clifford-based error-characterization or randomized-benchmarking-style protocols that infer conditional states from commuting Pauli data.
• Compressed classical descriptions of quantum states for device-independent or network settings where only measurement-conditioned descriptions are exchanged.
• Resource planning for fault-tolerant architectures, where copy counts translate directly into experimental runtime.

Industry relevance. The rate-one threshold and the accompanying finite-size exponents give a concrete guide for how much data quantum computing and sensing groups must budget when the deliverable is a conditional stabilizer description rather than full tomography; the Lean 4 formalization also makes the central claim machine-checkable for groups that need certified guarantees.

Future Directions

1. The fixed-offset window. Determine the full success profile when $k = n + O(1)$, which the present theorem leaves open; the gap between the rate-one converse and the $k-n \to +\infty$ achievability is exactly here.

2. Sublinear targets. Establish the copy requirements for $m = o(n)$, where the linear-target analysis does not apply and a discount may or may not appear.

3. Beyond prime local dimension and beyond the odd-prime Weyl section. The paper notes that in characteristic two the coordinate sections may carry a nontrivial cocycle, handled through the "enhanced coordinates"; extending sharp finite-size bounds across all characteristics, and to qudit systems with composite or varying local dimension, is a natural next step.

4. Submodels and noise. The remaining sections treat fixed-diagonal graph-basis submodels and the unresolved regimes; extending the analysis to structured state families and to noisy or mixed inputs — where verification scores rather than exact identification become the operative figure of merit — is a further open direction.

Target Audience

Quantum information theorists and mathematical physicists working on state learning, sample complexity, and Pauli/Weyl measurement theory; researchers in quantum tomography and shadow tomography who need to know when reducing the learning target actually saves copies; mathematically inclined readers interested in symplectic/Lagrangian methods over finite fields and in PGM optimality arguments; and formal-verification groups interested in the Lean 4 formalization of the main theorem. A reader without a background in stabilizer formalism and finite-field symplectic geometry will find the technical sections demanding.

Authors’ abstract

We consider an unknown pure stabilizer state of \(n\) qudits with a fixed prime local dimension \(p\), together with prescribed commuting Pauli observables. Rather than learning the whole state, the learner must recover only complementary stabilizers that commute with the prescribed observables, together with their eigenvalues. Once the prescribed measurement is performed, this information and the observed outcome determine the corresponding conditional stabilizer state. We compare the number \(k\) of copies available to the learner with the number \(n\) of qudits and refer to their ratio \(k/n\) as the copy rate. Suppose that the dimension \(m\) of the requested complementary stabilizer subspace satisfies \(m=βn+o(n)\) for a fixed \(0&lt;β\leq1\). If the copy rate converges to a value below one, the optimal exact recovery probabilities and verification scores converge to zero, both in the worst case and under the uniform prior. Conversely, if the number \(k\) of copies minus the number \(n\) of qudits tends to positive infinity, the entire stabilizer state can be identified with probability tending to one, and the requested complementary information can then be extracted. Thus, restricting the learning target to the stabilizer information needed after the prescribed measurement yields no copy-rate discount.