In this note, we consider tomography of $n$-qubit quantum states $|ψ\rangle$ that are promised to have stabilizer rank $k$ i.e., admit a stabilizer decomposition of $|ψ\rangle = \sum_{i=1}^k c_i |φ_i\rangle$ where each $|φ_i\rangle$ is a stabilizer state. We give a tomography protocol for such states up to trace distance $\varepsilon > 0$ running in $\textsf{poly}(n,2^k,1/\varepsilon)$ time and thus can handle $k=O(\log n)$ efficiently. This follows from first showing that the stabilizer extent $ξ(|ψ\rangle)$, which is the minimal $\ell_1$ norm over the coefficients $\{c_i\}$ of any stabilizer decomposition of $|ψ\rangle$, can be bounded as $ξ(|ψ\rangle) \leq 2^{O(k)}$ and improving upon the previous best bound of $k^{O(k)}$. The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.
AI Summary
The paper asks how efficiently an unknown $n$-qubit pure state can be reconstructed when it is promised to have stabilizer rank $k$, without assumptions on the coefficients or overlaps in its stabilizer decomposition. The target is tomography in $\mathrm{poly}(n,k,1/\varepsilon)$ time.
The main result bounds the stabilizer extent, defined here as the **unsquared** minimum coefficient $\ell_1$ norm, by $\xi(\psi)\leq (1+\sqrt{2})^k\|\psi\|$, improving the previous $k^{O(k)}$ bound to $2^{O(k)}$. Combined with an existing bounded-extent tomography algorithm, this gives time and copy complexity $\mathrm{poly}(n,2^k,1/\varepsilon,\log(1/\delta))$. With probability at least $1-\delta$, the output has squared overlap at least $1-\varepsilon$ with the unknown state and stabilizer rank $\mathrm{poly}(2^k/\varepsilon)$. Thus rank $O(\log n)$ is efficiently learnable.
The extent bound follows by induction on rank. Relative to one stabilizer component, sequential commuting Pauli projections split off branches of rank at most $k-1$, while reducing the residual squared norm by at least half per step. This geometric decay bounds the sum of branch norms independently of $n$.
The paper also derives an $\Omega(n)$ rank lower bound for states whose squared overlap with $|T\rangle^{\otimes n}$ is at least $\alpha^n$, for fixed $\alpha>\cos^2(\pi/8)$. Polynomial-time tomography for polynomial rank remains unresolved. The lower bound does not improve the known nearly quadratic bounds for exact or constant-error magic-state approximations; stronger extent–rank relations are discussed as a possible route to both goals.
Little sign of AI-generated textAI use disclosed
The first proof of Theorem~\ref{lem:ub_extent_rank} was obtained using GPT 6 Astra.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
In this note, we consider tomography of n-qubit quantum states ∣ψ⟩ that are promised to have stabilizer rank k i.e., admit a stabilizer decomposition of ∣ψ⟩=∑i=1kci∣φi⟩ where each ∣φi⟩ is a stabilizer state. We give a tomography protocol for such states up to trace distance ε>0 running in poly(n,2k,1/ε) time and thus can handle k=O(logn) efficiently. This follows from first showing that the stabilizer extent ξ(∣ψ⟩), which is the minimal ℓ1 norm over the coefficients {ci} of any stabilizer decomposition of ∣ψ⟩, can be bounded as ξ(∣ψ⟩)≤2O(k) and improving upon the previous best bound of kO(k). The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.
The paper asks how efficiently an unknown n-qubit pure state can be reconstructed when it is promised to have stabilizer rank k, without assumptions on the coefficients or overlaps in its stabilizer decomposition. The target is tomography in poly(n,k,1/ε) time.
The main result bounds the stabilizer extent, defined here as the unsquared minimum coefficient ℓ1 norm, by ξ(ψ)≤(1+2)k∥ψ∥, improving the previous kO(k) bound to 2O(k). Combined with an existing bounded-extent tomography algorithm, this gives time and copy complexity poly(n,2k,1/ε,log(1/δ)). With probability at least 1−δ, the output has squared overlap at least 1−ε with the unknown state and stabilizer rank poly(2k/ε). Thus rank O(logn) is efficiently learnable.
The extent bound follows by induction on rank. Relative to one stabilizer component, sequential commuting Pauli projections split off branches of rank at most k−1, while reducing the residual squared norm by at least half per step. This geometric decay bounds the sum of branch norms independently of n.
The paper also derives an Ω(n) rank lower bound for states whose squared overlap with ∣T⟩⊗n is at least αn, for fixed α>cos2(π/8). Polynomial-time tomography for polynomial rank remains unresolved. The lower bound does not improve the known nearly quadratic bounds for exact or constant-error magic-state approximations; stronger extent–rank relations are discussed as a possible route to both goals.
We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let C be a family of n-qubit states such that: (i)C is succinctly representable and (ii) there is a weak agnostic learner of C. We give a tomography protocol for an unknown state ∣ψ⟩ that is promised to admit a decomposition of the form ∣ψ⟩=∑ici∣φi⟩, where ∣φi⟩∈C with bounded ℓ1-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for C can be boosted into a tomography algorithm for states with bounded extent with respect to C.
Our reduction is black-box and applies broadly across model classes. As an application, when C is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent ξ up to trace distance ε, in time poly(n,(ξ/ε)log(ξ/ε)), which is improvable to $ \textsf{poly}(n,ξ,1/\varepsilon)$ assuming the algorithmic polynomial Freiman-Ruzsa conjecture in the high-doubling regime. When the unknown state ∣ψ⟩ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to C and show that the structure in ∣ψ⟩ that is explainable by C can be efficiently learned. Our main conceptual message is that agnostic learning of a structured base class automatically yields learnability of its low-complexity linear span.
We prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2O(klog(k+1)), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-k operators. This implies stabilizer fidelity at least 2−O(klog(k+1)), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/logn) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of T-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states.
As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n2/logn) lower bound for exact representations of n-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((logn)2/loglogn), respectively, a logn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with poly(n)2O(klog(k+1)) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most t samples. For sufficiently small ε, estimating an unknown state on Cd of rank at most r to trace norm error ε with constant success probability requires, and is achievable with, Θ(ε2drmax{1,tr}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most t samples improve the complexity of algorithms making single-sample measurements by at most a factor t. Further, measuring order r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate.
For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on t samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
We study the task of agnostic tomography: given copies of an unknown n-qubit state ρ which has fidelity τ with some state in a given class C, find a state which has fidelity ≥τ−ε with ρ. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time poly(n,1/ε)⋅(1/τ)O(log(1/τ)), answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time exp(Θ(n)) or required τ>cos2(π/8). States with stabilizer dimension n−t: We give a protocol that runs in time n3⋅(2t/τ)O(log(1/ε)), extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where τ=1 [33, 40, 49, 66]. Discrete product states: If C=K⊗n for some μ-separated discrete set K of single-qubit states, we give a protocol that runs in time (n/μ)O((1+log(1/τ))/μ)/ε2. This strictly generalizes a prior guarantee which applied to stabilizer product states [42]. For stabilizer product states, we give a further improved protocol that runs in time (n2/ε2)⋅(1/τ)O(log(1/τ)). As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error ε in n3quasipoly(1/ε) time.
The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩=∑j=1rcj|φj⟩ for cj∈C and stabilizer states φj . The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n -th tensor power of single-qubit magic states.We prove a lower bound of Ω(n) on the stabilizer rank of such states, improving a previous lower bound of Ω(n) of Bravyi, Smith and Smolin \cite{BSS16}. Further, we prove that for a sufficiently small constant δ , the stabilizer rank of any state which is δ -close to those states is Ω(n/logn) . This is the first non-trivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F2n , and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.