CS Paper Radar

Minimax Quantum State Tomography in a Known Trace-Distance Ball

Yonglong Li

cs.IT quant-ph ·submitted 2026-10-04 17:06 UTC · v1
theory

Abstract

We study quantum state tomography when the unknown state lies in a trace-distance ball of radius $R$ around a known reference state $ρ$. For arbitrary collective measurements, we determine the minimax expected risk and confidence radius up to universal constants, uniformly over the dimension, center spectrum, radius, and sample size. Write $Γ=d(\mathrm{Tr}\sqrtρ)^2+d^2R$. For $d\ge2$, $0<R\le1$, and $n\ge1$ copies, the expected risk is $Θ(\min\{R,\sqrt{Γ/n}\})$. At failure probability $0<δ\le1/3$, the minimax confidence radius is \[ Θ\!\left(\min\left\{R,\sqrt{\frac{Γ+\log(1/δ)}{n}}\right\}\right). \] For $\varepsilon\le c_0R$ with a universal $c_0>0$, the copy complexity is $Θ((Γ+\log(1/δ))/\varepsilon^2)$. For the lower bound we use a weighted trace-norm witness to retain all spectral scales in a square-root perturbation family. For the upper bound, we give a direct spectral and concentration analysis of a modified existing purification-based procedure.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS quant-phcs.ITcs.LG ·2026-09-09 ·Ashwin Nayak, Xingyu Zhou
theoryhighly cited similarity 0.61
Abstract · 70 pages; v2: minor revisions

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.

0.51

Tight Lower Bounds for State Tomography with Limited Entanglement

cs.IT quant-phcs.LG ·2026-09-04 ·Ufuk Keskin, Jason Luo, Mahbod Majid, Matthew Radzihovsky
theoryhighly cited similarity 0.61
Abstract · 36 pages

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $ε$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}ε^2),d^2/ε^2\}$ for every $k$ and all sufficiently small $ε$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

0.41

Optimal spectrum estimation

cs.CC quant-phcs.DS ·2026-09-24 ·Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
theoryhighly cited similarity 0.59
Abstract · 37 pages

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

0.35

Fourier Ratio and Restricted Isometry via Entropic Descent

cs.IT math.CA ·2026-09-18 ·Will Burstein, Alex Iosevich, Ben Krause
theory similarity 0.59
Abstract

In this second paper on descent methods as proof mechanisms in harmonic analysis (the first treated Bourgain's $Λ(p)$ selection theorem), entropic mirror descent gives an improved restricted isometry bound, improving sampling and recovery bounds in the Fourier Ratio program. Let $H$ be a complex $n\times n$ matrix with $H^*H=nI$ and $|H_{ij}|=1$. For fixed $0<\varepsilon<\frac14$ and $A_0>0$, independent Bernoulli row selection with expected cardinality $C_{\varepsilon,A_0}r\log\frac{2en}{r}\log(2r)\leq m\leq n/2$ preserves, after normalization by $\sqrt m$, the squared norm of every complex vector $y$ with $\|y\|_1\leq\sqrt r\|y\|_2$ within a factor $1\pm\varepsilon$, with failure probability at most $Cn^{-A_0}$. This includes every $r$-sparse vector and also fully supported ones; support size enters only through this inequality. For $y=\widehat f$ the condition is exactly $\operatorname{FR}(f)^2\leq r$, where $\operatorname{FR}(f)=\|\widehat f\|_1/\|\widehat f\|_2$, giving uniform energy sampling and approximate recovery even for signals with full Fourier support. The same holds for a uniform subset of prescribed cardinality, and for discrete Fourier and real Hadamard matrices. At fixed accuracy the bound removes one sparsity logarithm from the earlier count and replaces $\log n$ by $\log\frac{2en}{r}$; for Walsh matrices it matches, up to constants, the lower bound of Błasiok et al.\ in their range. One relative-entropy potential controls the corrections of an amplitude predictor at every scale; counting them on the symmetric difference of two samples gives the uniform estimate. We also prove the sufficient bound $C_{A_0}\varepsilon^{-5}r\log\frac{2en}{r}\log\frac{2r}{\varepsilon}$, and stable sparse recovery from $Cs\log\frac{2en}{s}\log(2s)$ measurements, with error controlled by the noise and the best $s$-term approximation.

0.42

Optimal Query Complexity for Ground-State Preparation

cs.CC quant-phcs.DS ·2026-09-28 ·Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou
theoryhighly cited similarity 0.58
Abstract · 48 pages

We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $α$-block-encoding of a Hamiltonian with unique ground state $|ψ_0\rangle$, and suppose $|\langleψ_0|U_I|0\rangle|\geγ$ for a state-preparation oracle $U_I$. The threshold lies at least $Δ/2$ above the ground-state energy and at least $Δ/2$ below every excited-state energy. We give two algorithms that prepare a state within trace distance $\varepsilon$ of the ground state. One uses $O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((α/(γΔ))\log(1/\varepsilon))$ calls to $U_H$ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to $U_I$ are $O(1/γ)$ in expectation and $O(γ^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((α/Δ)\sqrt N)$. Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.

0.49

Quantum channel tomography: optimal bounds in the near-boundary regime

cs.IT quant-ph ·2026-11-02 ·Kean Chen, Aadil Oufkir
theory similarity 0.57
Abstract · 40 pages

Quantum channel tomography (also known as quantum process tomography) is a fundamental task in quantum information and quantum computing, aiming to learn the full description of an unknown quantum channel from black-box queries. For channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, [CGO+26] identifies the dilation rate $τ=rd_2/d_1\geq 1$ as a key parameter governing a Heisenberg-to-classical transition in query complexity. While the optimal bounds in the boundary regime ($τ=1$) and the away-from-boundary regime ($τ\geq 1+Ω(1)$) are now known, the precise behavior in the near-boundary regime ($1<τ<1+o(1)$) has remained unresolved. In this paper, we close this gap, thereby fully settling the query complexity of quantum channel tomography. Specifically, we show that the query complexity is - $Ω(rd_1d_2/\varepsilon^2)$ for diamond norm error $\varepsilon$, matching the upper bound by [MB26, CGO+26], - $Θ(d_1^2/\varepsilon+\min\{(τ-1)d_1^2,(τ-1)^2d_1^2d_2^2\}/\varepsilon^2)$ for Choi trace norm error $\varepsilon$. Our results reveal two qualitatively different forms of the Heisenberg-to-classical transition. For diamond norm tomography, the Heisenberg scaling disappears suddenly as soon as $τ$ leaves the boundary regime. In contrast, Choi trace norm tomography exhibits a gradual transition from Heisenberg to classical scaling as $τ$ moves from the boundary regime to the away-from-boundary regime.

0.33

Near-Optimal Oracle Bounds for Isotropic Rounding

cs.DS ·2026-10-05 ·Yang P. Liu, Richard Peng, Alicia Stepin, Colin Tang
theoryhighly cited similarity 0.56
Abstract

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower bound, even when $R/r=n^{O(1)}$. The key lemma states that if $B(0,1)\subseteq K$ and $\Cov(\Unif(K))\preceqκI_n$, with $κ\ge1$, then approximate uniform sampling from an initial density bounded by a constant times the uniform density uses $\Ot(n^2\sqrtκ)$ expected membership queries. We prove this by simulating reflected kinetic dynamics using the analysis of Eberle and Lörler~\cite{EL26:journal}. Combining this sampler with the ideas of Jia, Laddha, Lee, and Vempala~\cite{JLLV26:journal} for rounding well-rounded bodies yields our $\Ot(n^3)$ query rounding algorithm. We also give a counterexample to an ellipsoid-growth conjecture from previous papers on this topic.

0.50

Optimal Joint Bounds for Sparse Ground-State Energy Estimation and Ground-State Preparation

cs.CC quant-phcs.DS ·2026-11-17 ·Dhrumil Patel
theory similarity 0.56
Abstract · 77 pages

Ground-state energy estimation (GSEE) and ground-state preparation (GSP) are fundamental problems in quantum computing. Given a Hamiltonian $H$ with $\|H\|\le1$ and a guiding state $|ψ\rangle$ with overlap at least $γ>0$ with the ground space of $H$, the goal in GSEE is to estimate the ground-state energy of $H$ to additive error $δ$ with failure probability at most $\varepsilon$, while in GSP it is to prepare a state with ground-space weight at least $1-\varepsilon$, given a gap lower bound $Δ$. Their costs are measured by quantum query complexity, i.e., the number of oracle calls needed to access $H$. Recent work proved optimal bounds $Θ(\log(1/\varepsilon)/(γδ))$ for GSEE and $Θ(\log(1/\varepsilon)/(γΔ))$ for GSP in the time-evolution and block-encoding models. However, these models do not directly account for the sparsity of $H$, measured by the maximum number $s$ of nonzero entries in any row or column. In the sparse-access model, oracles instead return the locations and values of these entries. This introduces the additional parameter $s$, and it remained open how query complexity depends jointly on $s$, $γ$, $δ$ or $Δ$, and $\varepsilon$. We resolve this by proving sparse-query lower bounds $Ω(\sqrt{s}\log(1/\varepsilon)/(γδ))$ for GSEE and $Ω(\sqrt{s}\log(1/\varepsilon)/(γΔ))$ for GSP, even for stoquastic Hamiltonians. We also show that these constructions recover the earlier time-evolution and block-encoding lower-bound scalings. We then give matching upper-bound algorithms in the reversible in-place sparse-location model. Thus, we obtain $Θ(\sqrt{s}\log(1/\varepsilon)/(γδ))$ for GSEE and $Θ(\sqrt{s}\log(1/\varepsilon)/(γΔ))$ for GSP, showing that $\sqrt{s}$ is necessary and sufficient and completing the joint dependence on all problem parameters.

0.21