Learning stabilizer structure of quantum states

• URL: http://arxiv.org/abs/2510.05890v2
• Date: Wed, 05 Nov 2025 21:47:58 GMT
• Title: Learning stabilizer structure of quantum states
• Authors: Srinivasan Arunachalam, Arkopal Dutt,
• Abstract summary: We consider the task of learning a structured stabilizer decomposition of an arbitrary $n$-qubit quantum state $|psirangle$.<n>As far as we know, learning arbitrary states with even stabilizer-rank $2$ was unknown.
• Score: 2.8074191213147652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of learning a structured stabilizer decomposition of an arbitrary $n$-qubit quantum state $|\psi\rangle$: for $\epsilon > 0$, output a state $|\phi\rangle$ with stabilizer-rank $\textsf{poly}(1/\epsilon)$ such that $|\psi\rangle=|\phi\rangle+|\phi'\rangle$ where $|\phi'\rangle$ has stabilizer fidelity $< \epsilon$. We first show the existence of such decompositions using the recently established inverse theorem for the Gowers-$3$ norm of states [AD,STOC'25]. To learn this structure, we initiate the task of self-correction of a state $|\psi\rangle$ with respect to a class of states $S$: given copies of $|\psi\rangle$ which has fidelity $\geq \tau$ with a state in $S$, output $|\phi\rangle \in S$ with fidelity $|\langle \phi | \psi \rangle|^2 \geq \tau^C$ for a constant $C>1$. Assuming the algorithmic polynomial Frieman-Rusza (APFR) conjecture in the high doubling regime (whose combinatorial version was recently resolved [GGMT,Annals of Math.'25]), we give a polynomial-time algorithm for self-correction of stabilizer states. Given access to the state preparation unitary $U_\psi$ for $|\psi\rangle$ and its controlled version $cU_\psi$, we give a polynomial-time protocol that learns a structured decomposition of $|\psi\rangle$. Without assuming APFR, we give a quasipolynomial-time protocol for the same task. As our main application, we give learning algorithms for states $|\psi\rangle$ promised to have stabilizer extent $\xi$, given access to $U_\psi$ and $cU_\psi$. We give a protocol that outputs $|\phi\rangle$ which is constant-close to $|\psi\rangle$ in time $\textsf{poly}(n,\xi^{\log \xi})$, which can be improved to polynomial-time assuming APFR. This gives an unconditional learning algorithm for stabilizer-rank $k$ states in time $\textsf{poly}(n,k^{k^2})$. As far as we know, learning arbitrary states with even stabilizer-rank $2$ was unknown.

Related papers

• Efficiently learning depth-3 circuits via quantum agnostic boosting [41.9957758385623]
  We study the study of quantum agnostic learning of phase states with respect to a function class $mathsfC$.<n>Our main technical contribution is a quantum boosting protocol which converts a weak learner.<n>Using quantum agnostic boosting, we obtain a $nO(log log n cdot log(1/varepsilon))$-time algorithm for learning $textsfpoly(n)$-sized depth-$3$ circuits.
  arXiv  Detail & Related papers  (2025-09-17T22:28:29Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  We introduce $mathsfPREM$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that a relative error guarantee for statistical queries under $(varepsilon, delta)$ differential privacy (DP)<n>We complement our algorithm with nearly matching lower bounds.
  arXiv  Detail & Related papers  (2025-02-20T18:32:02Z)
• A note on polynomial-time tolerant testing stabilizer states [6.458742319938316]
  We show an improved inverse theorem for the Gowers-$3$ of $n$-qubit quantum states $|psirangle. For every $gammageq 0$, if the $textsfGowers(|psi rangle,3)8 geq gamma then stabilizer fidelity of $|psirangle$ is at least $gammaC$ for some constant $C>1$.
  arXiv  Detail & Related papers  (2024-10-29T16:49:33Z)
• Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation [16.499689832762765]
  We study the task of tomography: given copies of an unknown $n$-qubit state $rho$ which has fidelity $tau$ with some state in a given class $C$, find a state which has fidelity $ge tau - epsilon$ with $rho$.<n>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 and discrete product states.
  arXiv  Detail & Related papers  (2024-08-13T15:23:17Z)
• Polynomial-time tolerant testing stabilizer states [4.65004369765875]
  An algorithm is given copies of an unknown $n$-qubit quantum state $|psirangle promised $(i)$ $|psirangle$. We show that for every $varepsilon_1>0$ and $varepsilonleq varepsilon_C$, there is a $textsfpoly that decides which is the case. Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for
  arXiv  Detail & Related papers  (2024-08-12T16:56:33Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
  We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. We prove that $omega(log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states.
  arXiv  Detail & Related papers  (2022-09-29T03:34:03Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions. For tensor train decomposition, we give a bicriteria $(1 + eps)$-approximation algorithm with a small bicriteria rank and $O(q cdot nnz(A))$ running time. In addition, we extend our algorithm to tensor networks with arbitrary graphs.
  arXiv  Detail & Related papers  (2022-07-15T11:55:09Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.