Agnostic Product Mixed State Tomography via Robust Statistics

• URL: http://arxiv.org/abs/2510.08472v1
• Date: Thu, 09 Oct 2025 17:13:03 GMT
• Title: Agnostic Product Mixed State Tomography via Robust Statistics
• Authors: Alvan Arulandu, Ilias Diakonikolas, Daniel Kane, Jerry Li,
• Abstract summary: We consider the problem of agnostic tomography with emphmixed state ansatz.<n>The goal is to output a nearly-trivial product mixed state approximation to $rho$.<n>We demonstrate a novel, black-box efficient reduction from agnostic tomography of product mixed states to the classical task of emphrobustly learning binary product distributions.
• Score: 43.0170609941244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of agnostic tomography with \emph{mixed state} ansatz, and specifically, the natural ansatz class of product mixed states. In more detail, given $N$ copies of an $n$-qubit state $\rho$ which is $\epsilon$-close to a product mixed state $\pi$, the goal is to output a nearly-optimal product mixed state approximation to $\rho$. While there has been a flurry of recent work on agnostic tomography, prior work could only handle pure state ansatz, such as product states or stabilizer states. Here we give an algorithm for agnostic tomography of product mixed states which finds a product state which is $O(\epsilon \log 1 / \epsilon)$ close to $\rho$ which uses polynomially many copies of $\rho$, and which runs in polynomial time. Moreover, our algorithm only uses single-qubit, single-copy measurements. To our knowledge, this is the first efficient algorithm that achieves any non-trivial agnostic tomography guarantee for any class of mixed state ansatz. Our algorithm proceeds in two main conceptual steps, which we believe are of independent interest. First, we demonstrate a novel, black-box efficient reduction from agnostic tomography of product mixed states to the classical task of \emph{robustly learning binary product distributions} -- a textbook problem in robust statistics. We then demonstrate a nearly-optimal efficient algorithm for the classical task of robustly learning a binary product, answering an open problem in the literature. Our approach hinges on developing a new optimal certificate of closeness for binary product distributions that can be leveraged algorithmically via a carefully defined convex relaxation. Finally, we complement our upper bounds with a lower bound demonstrating that adaptivity is information-theoretically necessary for our agnostic tomography task, so long as the algorithm only uses single-qubit two-outcome projective measurements.

Related papers

• Mixed state tomography reduces to pure state tomography [1.4842441810416076]
  A longstanding belief in quantum tomography is that estimating a mixed state is far harder than estimating a pure state.<n>We present a new approach to tomography demonstrating that, contrary to this belief, state-of-the-art mixed state tomography follows easily and naturally from pure state algorithms.
  arXiv  Detail & Related papers  (2025-11-19T19:01:11Z)
• Learning the closest product state [12.421740476704759]
  We study the problem of finding a (pure) product state with optimal fidelity to an unknown $n$-qubit quantum state $rho$, given copies of $rho$.<n>We give an algorithm which finds a product fidelity $varepsilon$-close to optimal, using $N = ntextpoly (1/varepsilon)$ copies of $rho$ and $textpoly(N)$ classical overhead.
  arXiv  Detail & Related papers  (2024-11-06T22:08:08Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Agnostic Tomography of Stabilizer Product States [0.43123403062068827]
  We give an efficient agnostic tomography algorithm for the class $mathcalC$ of $n$-qubit stabilizer product states.<n>We output a succinct description of a state that approximates at least as well as any state in $mathcalC$.
  arXiv  Detail & Related papers  (2024-04-04T21:39:47Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• A Spectral Approach to Item Response Theory [6.5268245109828005]
  We propose a emphnew item estimation algorithm for the Rasch model. The core of our algorithm is the computation of the stationary distribution of a Markov chain defined on an item-item graph. Experiments on synthetic and real-life datasets show that our algorithm is scalable, accurate, and competitive with the most commonly used methods in the literature.
  arXiv  Detail & Related papers  (2022-10-09T18:57:08Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  We study the design of tester-learner pairs $(mathcalA,mathcalT)$. We show that if the distribution on examples in the data passes the tester $mathcalT$ then one can safely trust the output of the agnostic $mathcalA$ on the data.
  arXiv  Detail & Related papers  (2022-04-14T19:10:53Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  We present a sharp analysis of model-based self-play algorithms for multi-agent Markov games. We design an algorithm -- Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games. We further adapt our analysis to designing a provably efficient task-agnostic algorithm for zero-sum Markov games.
  arXiv  Detail & Related papers  (2020-10-04T15:27:39Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

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.