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:2606.07425

Tomography of quantum states with bounded extent

Srinivasan Arunachalam, Arkopal Dutt

quant-phcs.CCmath.COSubmitted Jun 5, 2026• Announced Jun 8, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
56 pages

Related papers

A note on tomography of states with low stabilizer rank

Arkopal Dutt

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.

quant-pharXiv:2610.03658•Oct 5, 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

Learning Clifford-structured quantum unitaries and Hamiltonians

Arkopal Dutt, Dale Jacobs, John Jeang +2 more

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

quant-pharXiv:2608.09912•Aug 11, 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

Efficient Noisy Quantum State and Process Tomography

Chenyang Li, Shengxin Zhuang, Yukun Zhang +4 more

Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy $n$-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit ($γ= 0$) and the strong-decoherence regime ($γ= Θ(1)$). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.

quant-pharXiv:2603.01521•Quantum Science and Technology•Mar 3, 2026•0 citations

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

Sitan Chen, Weiyuan Gong, Qi Ye +1 more

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.

arXiv:2408.06967•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•5 citations
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 poly(n,ξ,1/ε) \textsf{poly}(n,ξ,1/\varepsilon)poly(n,ξ,1/ε) 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.
In this note, we consider tomography of nnn-qubit quantum states ∣ψ⟩|ψ\rangle∣ψ⟩ that are promised to have stabilizer rank kkk i.e., admit a stabilizer decomposition of ∣ψ⟩=∑i=1kci∣φi⟩|ψ\rangle = \sum_{i=1}^k c_i |φ_i\rangle∣ψ⟩=∑i=1k​ci​∣φi​⟩ where each ∣φi⟩|φ_i\rangle∣φi​⟩ is a stabilizer state. We give a tomography protocol for such states up to trace distance ε>0\varepsilon > 0ε>0 running in poly(n,2k,1/ε)\textsf{poly}(n,2^k,1/\varepsilon)poly(n,2k,1/ε) time and thus can handle k=O(log⁡n)k=O(\log n)k=O(logn) efficiently. This follows from first showing that the stabilizer extent ξ(∣ψ⟩)ξ(|ψ\rangle)ξ(∣ψ⟩), which is the minimal ℓ1\ell_1ℓ1​ norm over the coefficients {ci}\{c_i\}{ci​} of any stabilizer decomposition of ∣ψ⟩|ψ\rangle∣ψ⟩, can be bounded as ξ(∣ψ⟩)≤2O(k)ξ(|ψ\rangle) \leq 2^{O(k)}ξ(∣ψ⟩)≤2O(k) and improving upon the previous best bound of kO(k)k^{O(k)}kO(k). The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.
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 τ .
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning nnn-qubit quantum unitaries UUU and Hamiltonians HHH, given query access to UUU or the unitary evolution of HHH, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCiU = \sum_i α_i C_iU=∑i​αi​Ci​ over Cliffords CiC_iCi​ with bounded Clifford extent ∑i∣αi∣\sum_i |α_i|∑i​∣αi​∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary UUU with optimal Clifford fidelity opt\textsf{opt}opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε\geq \textsf{opt} - \varepsilon≥opt−ε for some error ε>0\varepsilon > 0ε>0, in time poly(n,(1/ε)log⁡(1/ε))\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)Ω(2^n)Ω(2n)) in the Pauli basis but are Clifford structured.
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).
Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy nnn-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit (γ=0γ= 0γ=0) and the strong-decoherence regime (γ=Θ(1)γ= Θ(1)γ=Θ(1)). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.
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.