Optimal lower bounds for quantum state tomography

• URL: http://arxiv.org/abs/2510.07699v1
• Date: Thu, 09 Oct 2025 02:36:48 GMT
• Title: Optimal lower bounds for quantum state tomography
• Authors: Thilo Scharnhorst, Jack Spilecki, John Wright,
• Abstract summary: We show that $n = Omega(rd/varepsilon2)$ copies are necessary to learn a rank $r$ mixed state $rho in mathbbCd times d$ up to error $varepsilon$ in trace distance.<n>A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error $varepsilon$ in trace distance to an algorithm which learns to error $O(varepsilon)$ in the more stringent Bures
• Score: 0.9969485010222057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that $n = \Omega(rd/\varepsilon^2)$ copies are necessary to learn a rank $r$ mixed state $\rho \in \mathbb{C}^{d \times d}$ up to error $\varepsilon$ in trace distance. This matches the upper bound of $n = O(rd/\varepsilon^2)$ from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which $\rho$ is promised to be of the form $\rho = P/r$, where $P \in \mathbb{C}^{d \times d}$ is a rank $r$ projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error $\varepsilon$ in trace distance to an algorithm which learns to error $O(\varepsilon)$ in the more stringent Bures distance.

Related papers

• Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
  We study the sample complexity of shadow tomography in the high-precision regime.<n>We use possibly adaptive measurements that act on $O(mathrmpolylog(d))$ number of copies of $$ at a time.
  arXiv  Detail & Related papers  (2026-02-04T19:00:00Z)
• Quantum channel tomography and estimation by local test [32.904052887092284]
  Heisenberg scaling $O(1/varepsilon)$ can be achieved, even if $mathcalE$ is not a unitary channel.<n>We show that for parallel (possibly coherent) testers, access to dilations does not help.
  arXiv  Detail & Related papers  (2025-12-15T18:07:42Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• The debiased Keyl's algorithm: a new unbiased estimator for full state tomography [1.4302622916198997]
  We present the debiased Keyl's algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal.<n>We show that $n = O(rd/varepsilon2)$ copies are sufficient to learn a rank-$r$ mixed state to trace distance error $varepsilon$, which is optimal.<n>We further show that $n = O(rd/varepsilon2)$ copies are sufficient to learn to error $varepsilon$ in the more challenging Bures distance, which is also optimal.
  arXiv  Detail & Related papers  (2025-10-09T05:07:12Z)
• Pauli Measurements Are Near-Optimal for Single-Qubit Tomography [34.83118849281207]
  We show that at least $Omegaleft(frac10NsqrtN varepsilon2right)$ copies are required to learn an $N$-qubit state $rhoinmathbbCdtimes d,d=2N$ to within $varepsilon$ trace distance.
  arXiv  Detail & Related papers  (2025-07-29T16:50:19Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• When Does Adaptivity Help for Quantum State Learning? [19.89243001385691]
  We show that any protocol using incoherent measurements requires $Omega(d3/epsilon2)$ copies, matching the best known upper bound. We give an adaptive algorithm that outputs a state which is $gamma$-close in infidelity to $rho$ using only $tildeO(d3/gamma)$ copies, which is optimal for incoherent measurements.
  arXiv  Detail & Related papers  (2022-06-10T17:59:16Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)

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.