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.
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.
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.
Consider the following optimization problem over stabilizer product states: given an n-qubit stabilizer state ∣ψ⟩ and a set of single-qubit stabilizer states S, maximize ∣⟨ψ∣φ1,…,φn⟩∣2 over single-qubit stabilizer states ∣φi⟩∈S. By varying the set S, we show that solutions to this problem can be useful in a variety of settings: tighter runtime bounds for certain classical simulation algorithms; measures of entanglement; and the complexity of low-rank matrix completion. Moreover, we give a complete complexity classification of this nearest stabilizer product state problem. After accounting for the symmetries in the Clifford group, there are 9 distinct possible sets S, and we show that all but the two simplest of these are $\NP$-complete.
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.