CS Paper Radar

Exact Posterior Prediction from Product Haar Measurements and a Randomized-Mesh Maximum-Likelihood Bridge

Naqueeb Ahmad Warsi, Ayanava Dasgupta, Masahito Hayashi

cs.IT quant-ph ·submitted 2026-09-09 12:01 UTC · v1
theory

Abstract

We study prediction of one unmeasured copy of an unknown finite-dimensional pure quantum state after independently measuring the observed copies with the one-copy Haar POVM. For the resulting fixed separable observation, the Bayes predictive state under quantum relative-entropy loss is the full-rank posterior mean. We evaluate it exactly through permanents of minors of the outcome Gram matrix, prove positivity and normalization of the permanent representation, and establish minimaxity among decision rules based on these fixed outcomes. Using Hilbert--Schmidt projection of the posterior mean and an exactly analyzed linear-inversion competitor, we prove a finite-sample posterior-purity bound and an explicit relative-entropy guarantee with sample count $O((d^2/ε)\log(d/ε))$. Using the exact collective benchmarks proved in a companion paper, we also obtain entropy and posterior-purity comparisons. To connect the fine product data to a regular ray-valued experiment without assuming deterministic finite-sample uniqueness, we draw one random orientation for a finite projective mesh, retain it for the entire sample, and apply a selected finite-alphabet MLE in the resulting reference experiment. A nested recovering mesh uniformly recovers the fine Fisher information. Consequently every sufficiently fine fixed mesh gives a regular finite-alphabet model. Its selected MLE has Haar-averaged inverse-Fisher coefficient $\overline a_k$, and refining the mesh after the fixed-mesh large-sample limit makes $\overline a_k$ approach $d-1$. This yields epsilon-optimal leading relative-entropy and posterior-overlap bounds for the fine posterior and the sharper fixed-dimensional asymptotic scale $(d/ε)\log(d/ε)$. The latter is not asserted as a uniform finite-sample guarantee. No deterministic finite-sample MLE uniqueness or triangular mesh schedule is used.

Comment
15 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Haar-Bayesian Pure-State Prediction under Relative-Entropy Loss: Arbitrary-Effect Reduction and Global Optimality

cs.IT quant-ph ·2026-09-09 ·Masahito Hayashi, Ayanava Dasgupta, Naqueeb Ahmad Warsi
theory similarity 0.72
Abstract · 12 pages, 1 table

We study Haar-Bayesian prediction of one unmeasured copy of an unknown finite-dimensional pure quantum state after an arbitrary collective measurement on $n$ observed copies. Performance is evaluated by quantum relative entropy. For a fixed measurement, the Bayes predictive state is the posterior mean and the optimized conditional loss is its entropy. We then optimize the measurement over all POVMs on the symmetric subspace. For every nonzero positive effect $E$, the corresponding posterior predictive state is $μ_E=(I+nρ_E)/(n+d)$, where $ρ_E$ is the normalized one-particle marginal of $E$. Since a pure spectrum majorizes every density-operator spectrum, this identity gives an outcome-wise entropy lower bound. Coherent rank-one effects attain the bound, and their Haar orbit yields the highest-weight covariant POVM. Hence this POVM is globally Bayes optimal over all collective measurements and, by covariance, globally minimax. Its exact risk is $h_d((n+1)/(n+d))$, where $h_d(r)=-r\log r-(1-r)\log((1-r)/(d-1))$. The same arbitrary-effect reduction shows that the highest-weight POVM also maximizes the joint overlap between the latent pure state and its posterior predictive state, equivalently the mean posterior purity, with optimum $((n+1)^2+d-1)/(n+d)^2$.

0.54

Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform

cs.DS quant-phcs.IT ·2026-08-11 ·Yupan Liu, Qisheng Wang
similarity 0.65
Abstract · 11 pages, 1 algorithm, 1 table, 3 figures

The Uhlmann fidelity ${\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_1}|$ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error $\varepsilon$ requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of $ρ_0$ and $ρ_1$. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on $1/\varepsilon$. However, the known optimal estimator for ${\rm F}(ρ,|ψ\rangle\!\langleψ|)$ due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for ${\rm F}(ρ, |ψ\rangle\!\langleψ|)$ under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of ${\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|ψ_1\rangle$ (or $|ψ_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.

0.38

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

cs.CC quant-ph ·2026-10-27 ·Kuan Cheng, Ruiyang Wu
similarity 0.63
Abstract

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler-extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $$ m+O_α(\log(D/δ))\text{ random bits and } O_α\!\left(\varepsilon^{-2-α}\log^{1+α}(D/δ)\right)\text{ samples}, $$ for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1+α} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

0.09

Optimal von Neumann Entropy Estimation

cs.IT quant-ph ·2026-08-11 ·Ziyun Chen, Minbo Gao, Qisheng Wang
theoryhighly cited similarity 0.62
Abstract · 22 pages, 1 table, 1 algorithm. Improved the sample complexity to optimal

We show that the von Neumann entropy of an unknown $d$-dimensional quantum state $ρ$ can be estimated to within additive error $\varepsilon$ using \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) \] samples of $ρ$, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.

0.49

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

cs.CR quant-ph ·2026-10-05 ·Keshav Bhateja, Mehdi Esmaili, Atul Mantri
benchmark similarity 0.61
Abstract

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires $Ω(N^{1/3})$ queries for the Haar and Fourier oracle ensembles with $N$ outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, for Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the $n$-bit output of a device that makes polynomially many queries and scores within $o(1)$ of the ideal score has $n-O(\log n)$ bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity $Θ(N^{1/3})$, and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling the measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation.

0.09

Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means

cs.LG math.STquant-phstat.ML ·2026-10-15 ·Yen-Huan Li, Wei-Fu Tseng
theory similarity 0.61
Abstract

We study the problem of online learning of quantum states with logarithmic loss, which is a quantum generalization of online portfolio selection and has applications to quantum state tomography, the task of estimating an unknown quantum state from measurement outcomes. We first establish a regret lower bound, showing that the regret rates of Exponential Weights and the algorithm of Tseng et al. (2025) have optimal polynomial dependence on the dimension. Our analysis leads to two further results. First, our lower-bound proof leads to a quantum state tomography algorithm that is sample optimal up to polylogarithmic factors in the sample size. Second, we develop an algorithm for constructing confidence sequences for the mean of a matrix-valued random variable. A numerical experiment shows that the latter algorithm is competitive with existing methods.

0.17

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

Advantage of Entangled Learning Rules in Quantum Measurement Class Learning

cs.LG quant-ph ·2026-10-05 ·Arka Prabha Das, Abram Magner
similarity 0.60
Abstract · 9 pages

Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).

0.16