Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2408.06967 · ACM Symposium on Theory of Computing (STOC)

Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation

Sitan Chen, Weiyuan Gong, Qi Ye, Z.H. Zhang

Published Jun 15, 2025• 5 citations
arXivHTMLPDF

Abstract

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 $\ge τ- ε$ 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 $\mathrm{poly}(n,1/ε)\cdot (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 $\mathrm{exp}(Θ(n))$ or required $τ>\cos^2(π/8)$. States with stabilizer dimension $n - t$: We give a protocol that runs in time $n^3\cdot(2^t/τ)^{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^{\otimes 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 $(n^2/ε^2)\cdot (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 $n^3 \mathrm{quasipoly}(1/ε)$ time.

DOI
10.1145/3717823.3718191

Related papers

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng +1 more

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

quant-pharXiv:2607.15559•Jul 20, 2026•0 citations

Agnostic Tomography of Stabilizer Product States

Sabee Grewal, Vishnu Iyer, William Kretschmer +1 more

We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ⁡ ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .

arXiv:2404.03813•Quantum•Mar 13, 2026•1 citation

Tomography of quantum states with bounded extent

Srinivasan Arunachalam, Arkopal Dutt

We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let $\textsf{C}$ be a family of $n$-qubit states such that: $(i)$ $\textsf{C}$ is succinctly representable and $(ii)$ there is a weak agnostic learner of $\textsf{C}$. We give a tomography protocol for an unknown state $|ψ\rangle$ that is promised to admit a decomposition of the form $|ψ\rangle = \sum_i c_i |φ_i\rangle$, where $|φ_i\rangle \in \textsf{C}$ with bounded $\ell_1$-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for $\textsf{C}$ can be boosted into a tomography algorithm for states with bounded extent with respect to $\textsf{C}$. Our reduction is black-box and applies broadly across model classes. As an application, when $\textsf{C}$ is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent $ξ$ up to trace distance $\varepsilon$, in time $\textsf{poly}(n,(ξ/\varepsilon)^{\log(ξ/\varepsilon)})$, 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 $|ψ\rangle$ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to $\textsf{C}$ and show that the structure in $|ψ\rangle$ that is explainable by $\textsf{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.

quant-pharXiv:2606.07425•Jun 8, 2026•0 citations

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown $d$-dimensional quantum state $ρ$ and a known collection of observables $E_1,\ldots,E_M$, the goal is to estimate all expectation values $\{\text{Tr}(ρE_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ with probability at least $1-δ$. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on $M$, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity \[ O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), \] which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.

quant-pharXiv:2608.06345•Aug 7, 2026•0 citations

Agnostic Product Mixed State Tomography via Robust Statistics

Alvan Caleb Arulandu, Ilias Diakonikolas, Daniel M. Kane +1 more

We study the complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given $N$ copies of an $n$-qubit state $ρ$, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on ${0,1}^n$, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error $O(\mathrm{opt}\log(1/\mathrm{opt}))$, where $\mathrm{opt}$ is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).

arXiv:2510.08472•Oct 9, 2025•0 citations

Finding Gaussian Structure in Bosonic States

Alvan Arulandu, Sitan Chen, Ziyun Chen +2 more

We study agnostic tomography of pure bosonic Gaussian states: given copies of an arbitrary $n$-mode bosonic state $ρ$, the goal is to output a pure Gaussian state whose infidelity with $ρ$ is at most $\mathrm{opt} + ε$, where $\mathrm{opt}$ is the minimum infidelity achievable by any pure Gaussian state. We give efficient protocols achieving this in both the high and low fidelity regimes. When $\mathrm{opt}$ is below some universal constant, our protocol has runtime and copy complexity which is strongly polynomial in $n, 1/ε$ and $\log \log E$, where $E$ is the energy of the closest pure Gaussian state. For arbitrary $\mathrm{opt}$, our protocol uses $(n+1)^{\mathrm{poly}(1/ε)} \mathrm{poly}\left(1+\log\log(E)\right)$ copies and runtime. As a corollary, we obtain the first truly tolerant Gaussianity testing protocol for distinguishing whether $\mathrm{opt} > c + ε$ or $\mathrm{opt} < c - ε$, for any threshold $c\in(0,1)$. We also prove $\mathrm{poly}(n,1/ε)$ runtime is impossible, unless $\mathrm{NP}\subseteq\mathrm{BQP}$. Our protocols follow a shared paradigm: first, we iteratively use general Gaussian measurements combined with techniques from classical robust statistics to obtain a good warm start estimate, then we leverage non-Gaussian measurements to refine this warm start using convex and non-convex optimization methods. Interestingly, we prove that non-Gaussian measurements are necessary to match the strong agnostic guarantees we obtain, and in fact these guarantees are provably superior to what is possible for robustly estimating classical Gaussians.

quant-pharXiv:2610.06810•Oct 6, 2026•0 citations
We study the task of agnostic tomography: given copies of an unknown nnn-qubit state ρρρ which has fidelity τττ with some state in a given class CCC, find a state which has fidelity ≥τ−ε\ge τ- ε≥τ−ε 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/τ))\mathrm{poly}(n,1/ε)\cdot (1/τ)^{O(\log(1/τ))}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))\mathrm{exp}(Θ(n))exp(Θ(n)) or required τ>cos⁡2(π/8)τ>\cos^2(π/8)τ>cos2(π/8). States with stabilizer dimension n−tn - tn−t: We give a protocol that runs in time n3⋅(2t/τ)O(log⁡(1/ε))n^3\cdot(2^t/τ)^{O(\log(1/ε))}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τ= 1τ=1 [33, 40, 49, 66]. Discrete product states: If C=K⊗nC = K^{\otimes n}C=K⊗n for some μμμ-separated discrete set KKK of single-qubit states, we give a protocol that runs in time (n/μ)O((1+log⁡(1/τ))/μ)/ε2(n/μ)^{O((1 + \log (1/τ))/μ)}/ε^2(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/τ))(n^2/ε^2)\cdot (1/τ)^{O(\log(1/τ))}(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/ε)n^3 \mathrm{quasipoly}(1/ε)n3quasipoly(1/ε) time.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown nnn-qudit pure state ∣ψ⟩|ψ\rangle∣ψ⟩ that has fidelity τττ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩|φ\rangle∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log⁡(1/τ))⋅poly(n,1/ε)(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension ddd is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos⁡2(π/8)τ> \cos^2(π/8)τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ⁡ ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .
We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let C\textsf{C}C be a family of nnn-qubit states such that: (i)(i)(i) C\textsf{C}C is succinctly representable and (ii)(ii)(ii) there is a weak agnostic learner of C\textsf{C}C. We give a tomography protocol for an unknown state ∣ψ⟩|ψ\rangle∣ψ⟩ that is promised to admit a decomposition of the form ∣ψ⟩=∑ici∣φi⟩|ψ\rangle = \sum_i c_i |φ_i\rangle∣ψ⟩=∑i​ci​∣φi​⟩, where ∣φi⟩∈C|φ_i\rangle \in \textsf{C}∣φi​⟩∈C with bounded ℓ1\ell_1ℓ1​-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for C\textsf{C}C can be boosted into a tomography algorithm for states with bounded extent with respect to C\textsf{C}C. Our reduction is black-box and applies broadly across model classes. As an application, when C\textsf{C}C is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent ξξξ up to trace distance ε\varepsilonε, in time poly(n,(ξ/ε)log⁡(ξ/ε))\textsf{poly}(n,(ξ/\varepsilon)^{\log(ξ/\varepsilon)})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 ∣ψ⟩|ψ\rangle∣ψ⟩ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to C\textsf{C}C and show that the structure in ∣ψ⟩|ψ\rangle∣ψ⟩ that is explainable by C\textsf{C}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.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown ddd-dimensional quantum state ρρρ and a known collection of observables E1,…,EME_1,\ldots,E_ME1​,…,EM​, the goal is to estimate all expectation values {Tr(ρEi)}i=1M\{\text{Tr}(ρE_i)\}_{i=1}^M{Tr(ρEi​)}i=1M​ to additive accuracy ε\varepsilonε with probability at least 1−δ1-δ1−δ. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on MMM, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(log⁡(M)log⁡(M/δ)ε2), O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), O(ε2log(M)log(M/δ)​), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
We study the complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given NNN copies of an nnn-qubit state ρρρ, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on 0,1n{0,1}^n0,1n, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error O(optlog⁡(1/opt))O(\mathrm{opt}\log(1/\mathrm{opt}))O(optlog(1/opt)), where opt\mathrm{opt}opt is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).
We study agnostic tomography of pure bosonic Gaussian states: given copies of an arbitrary nnn-mode bosonic state ρρρ, the goal is to output a pure Gaussian state whose infidelity with ρρρ is at most opt+ε\mathrm{opt} + εopt+ε, where opt\mathrm{opt}opt is the minimum infidelity achievable by any pure Gaussian state. We give efficient protocols achieving this in both the high and low fidelity regimes. When opt\mathrm{opt}opt is below some universal constant, our protocol has runtime and copy complexity which is strongly polynomial in n,1/εn, 1/εn,1/ε and log⁡log⁡E\log \log EloglogE, where EEE is the energy of the closest pure Gaussian state. For arbitrary opt\mathrm{opt}opt, our protocol uses (n+1)poly(1/ε)poly(1+log⁡log⁡(E))(n+1)^{\mathrm{poly}(1/ε)} \mathrm{poly}\left(1+\log\log(E)\right)(n+1)poly(1/ε)poly(1+loglog(E)) copies and runtime. As a corollary, we obtain the first truly tolerant Gaussianity testing protocol for distinguishing whether opt>c+ε\mathrm{opt} > c + εopt>c+ε or opt<c−ε\mathrm{opt} < c - εopt<c−ε, for any threshold c∈(0,1)c\in(0,1)c∈(0,1). We also prove poly(n,1/ε)\mathrm{poly}(n,1/ε)poly(n,1/ε) runtime is impossible, unless NP⊆BQP\mathrm{NP}\subseteq\mathrm{BQP}NP⊆BQP. Our protocols follow a shared paradigm: first, we iteratively use general Gaussian measurements combined with techniques from classical robust statistics to obtain a good warm start estimate, then we leverage non-Gaussian measurements to refine this warm start using convex and non-convex optimization methods. Interestingly, we prove that non-Gaussian measurements are necessary to match the strong agnostic guarantees we obtain, and in fact these guarantees are provably superior to what is possible for robustly estimating classical Gaussians.