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:2510.07788 · ACM Symposium on Theory of Computing (STOC)

The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography

Angelos Pelecanos, Jack Spilecki, John Wright

Published Jun 9, 2026• 0 citations
arXivHTMLPDF

Abstract

In the problem of quantum state tomography, one is given n copies of an unknown rank-r mixed state ρ ∈ ℂd × d and asked to produce an estimator of ρ. In this work, we present the debiased Keyl’s algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal. We derive an explicit formula for the second moment of our estimator, with which we show the following five applications. First, we give a new proof that n = O(rd/ε2) copies are sufficient to learn a rank-r mixed state to trace distance error ε, which is optimal. Second, we show that n = O(rd/ε2) copies are sufficient to learn to error ε in the more challenging Bures distance, which is also optimal. Third, we consider full state tomography when one is only allowed to measure k copies at once. We show that n =O(max(d3/√kε2, d2/ε2 ) ) copies suffice to learn in trace distance. This improves on the prior work of Chen et al. and matches their lower bound. Fourth, for shadow tomography, we show that O(log(m)/ε2) copies are sufficient to learn m given observables O1, …, Om in the ”high accuracy regime”, when ε = O(1/d), improving on a result of Chen et al. More generally, we show that if tr(Oi2) ≤ F for all i, then n = O(log(m) · (min{√r F/ε, F2/3/ε4/3}+ 1/ε2)) copies suffice, improving on existing work. Finally, for quantum metrology, we give a locally unbiased algorithm whose mean squared error matrix is upper bounded by twice the inverse of the quantum Fisher information matrix in the asymptotic limit of large n, which is optimal.

DOI
10.1145/3798129.3800837

Related papers

Efficient quantum tomography

Ryan O’Donnell, John Wright

In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.

arXiv:1508.01907•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•181 citations

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography

Sitan Chen, Jerry Zheng Li, Allen Liu

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.

arXiv:2402.16353•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•11 citations

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

Ashwin Nayak, Xingyu Zhou

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

quant-pharXiv:2609.10514•Sep 10, 2026•0 citations

The Keyl-Werner algorithm is not optimal for spectrum estimation

Angelos Pelecanos, Jack Spilecki, Ewin Tang +1 more

We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.

quant-pharXiv:2607.27117•Jul 30, 2026•0 citations

Optimal lower bounds for quantum state tomography

Thilo Scharnhorst, Jack Spilecki, Wright, John

We show that $n = Ω(rd/\varepsilon^2)$ copies are necessary to learn a rank $r$ mixed state $ρ\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 $ρ$ is promised to be of the form $ρ= 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.

arXiv:2510.07699•Oct 9, 2025•0 citations

Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach

Senrui Chen, Weiyuan Gong, Sisi Zhou

We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown $d$-dimensional quantum state $ρ$ and a known set of observables $\{O_i\}_{i=1}^m$, the goal is to estimate expectation values $\{\mathrm{tr}(O_iρ)\}_{i=1}^m$ to accuracy $ε$ in $L_p$-norm, using possibly adaptive measurements that act on $O(\mathrm{polylog}(d))$ number of copies of $ρ$ at a time. We focus on the regime where $ε$ is below an instance-dependent threshold. Our main contribution is an instance-optimal characterization of the sample complexity as $\tildeΘ(Γ_p/ε^2)$, where $Γ_p$ is a function of $\{O_i\}_{i=1}^m$ defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with $L_\infty$-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form $\sum_{i=1}^m α_i O_i$ with $\|α\|_q = 1$ (where $q$ is dual to $p$) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of $Θ(Γ^{\mathrm{ob}}_p/ε^2)$. We then show $\tildeΘ(Γ_p/ε^2)$ is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, $Γ^{\mathrm{ob}}_\infty = Γ_\infty$. In both cases, allowing $c$-copy measurements improves the sample complexity by at most $Ω(1/c)$. Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.

quant-pharXiv:2602.04952•Feb 6, 2026•0 citations
In the problem of quantum state tomography, one is given n copies of an unknown rank-r mixed state ρ ∈ ℂd × d and asked to produce an estimator of ρ. In this work, we present the debiased Keyl’s algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal. We derive an explicit formula for the second moment of our estimator, with which we show the following five applications. First, we give a new proof that n = O(rd/ε2) copies are sufficient to learn a rank-r mixed state to trace distance error ε, which is optimal. Second, we show that n = O(rd/ε2) copies are sufficient to learn to error ε in the more challenging Bures distance, which is also optimal. Third, we consider full state tomography when one is only allowed to measure k copies at once. We show that n =O(max(d3/√kε2, d2/ε2 ) ) copies suffice to learn in trace distance. This improves on the prior work of Chen et al. and matches their lower bound. Fourth, for shadow tomography, we show that O(log(m)/ε2) copies are sufficient to learn m given observables O1, …, Om in the ”high accuracy regime”, when ε = O(1/d), improving on a result of Chen et al. More generally, we show that if tr(Oi2) ≤ F for all i, then n = O(log(m) · (min{√r F/ε, F2/3/ε4/3}+ 1/ε2)) copies suffice, improving on existing work. Finally, for quantum metrology, we give a locally unbiased algorithm whose mean squared error matrix is upper bounded by twice the inverse of the quantum Fisher information matrix in the asymptotic limit of large n, which is optimal.
In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most ttt samples. For sufficiently small ε\varepsilonε, estimating an unknown state on Cd\mathbb{C}^dCd of rank at most rrr to trace norm error ε\varepsilonε with constant success probability requires, and is achievable with, Θ(drε2max{1,rt})Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)Θ(ε2dr​max{1,t​r​}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most ttt samples improve the complexity of algorithms making single-sample measurements by at most a factor t\sqrt{t}t​. Further, measuring order r2r^2r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on ttt samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
We give an algorithm which, given n=O(d2⋅(log⁡log⁡(d)/log⁡(d))2)n = O(d^2 \cdot (\log\log(d)/\log(d))^2)n=O(d2⋅(loglog(d)/log(d))2) copies of ρρρ, estimates the eigenvalues of ρρρ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the Θ(d2)Θ(d^2)Θ(d2) needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses n=Θ(d2)n = Θ(d^2)n=Θ(d2) copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction ∣w⟩|w\rangle∣w⟩ scales with ⟨w∣ρ∣w⟩\langle w | ρ|w\rangle⟨w∣ρ∣w⟩ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in χ2χ^2χ2-divergence as corollaries.
We show that n=Ω(rd/ε2)n = Ω(rd/\varepsilon^2)n=Ω(rd/ε2) copies are necessary to learn a rank rrr mixed state ρ∈Cd×dρ\in \mathbb{C}^{d \times d}ρ∈Cd×d up to error ε\varepsilonε in trace distance. This matches the upper bound of n=O(rd/ε2)n = O(rd/\varepsilon^2)n=O(rd/ε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 ρρρ is promised to be of the form ρ=P/rρ= P/rρ=P/r, where P∈Cd×dP \in \mathbb{C}^{d \times d}P∈Cd×d is a rank rrr 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(ε)O(\varepsilon)O(ε) in the more stringent Bures distance.
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown ddd-dimensional quantum state ρρρ and a known set of observables {Oi}i=1m\{O_i\}_{i=1}^m{Oi​}i=1m​, the goal is to estimate expectation values {tr(Oiρ)}i=1m\{\mathrm{tr}(O_iρ)\}_{i=1}^m{tr(Oi​ρ)}i=1m​ to accuracy εεε in LpL_pLp​-norm, using possibly adaptive measurements that act on O(polylog(d))O(\mathrm{polylog}(d))O(polylog(d)) number of copies of ρρρ at a time. We focus on the regime where εεε is below an instance-dependent threshold. Our main contribution is an instance-optimal characterization of the sample complexity as Θ~(Γp/ε2)\tildeΘ(Γ_p/ε^2)Θ~(Γp​/ε2), where ΓpΓ_pΓp​ is a function of {Oi}i=1m\{O_i\}_{i=1}^m{Oi​}i=1m​ defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with L∞L_\inftyL∞​-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi\sum_{i=1}^m α_i O_i∑i=1m​αi​Oi​ with ∥α∥q=1\|α\|_q = 1∥α∥q​=1 (where qqq is dual to ppp) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2)Θ(Γ^{\mathrm{ob}}_p/ε^2)Θ(Γpob​/ε2). We then show Θ~(Γp/ε2)\tildeΘ(Γ_p/ε^2)Θ~(Γp​/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, Γ∞ob=Γ∞Γ^{\mathrm{ob}}_\infty = Γ_\inftyΓ∞ob​=Γ∞​. In both cases, allowing ccc-copy measurements improves the sample complexity by at most Ω(1/c)Ω(1/c)Ω(1/c). Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.