We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $\gamma>0$, we prove a sample complexity lower bound of $\Omega(d^{2-\gamma})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.
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 $\mu_E=(I+n\rho_E)/(n+d)$, where $\rho_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$.
Masahito Hayashi, Ayanava Dasgupta, Naqueeb Ahmad Warsi· 0 citations
We study estimation of the trace polynomial $\operatorname{tr} p(P\rho P)$ from global classical shadows, where $\rho$ is an unknown quantum state and $P$ is a fixed projector. Disjoint batching and complete U-statistics yield unbiased estimators of the same trace moments, but assign different sample-size factors to the degenerate terms in their Hoeffding decompositions. Under the global Clifford protocol, exact degree-two variance formulas show that, on a null projected block of rank $s$, the quadratic degenerate term has order $s^2/N$ under batching and $s^2/N^2$ under complete symmetrization. For a logarithmic-degree polynomial used in entropy approximation, the quadratic coefficient raises the batched variance to at least order $s^2N\log^2N$ at the classical entropy cutoff. For complete U-statistics, we derive a cross-degree covariance identity and an exact variance decomposition for polynomial estimators. We also bound every Hoeffding order at a fixed degree and obtain a growing-dimensional risk bound for a small-spectrum entropy functional. The higher-order bounds retain a polynomial dependence on the ambient dimension and therefore do not cover logarithmically increasing degrees. Monte Carlo experiments confirm the degree-two formulas, and exact calculations illustrate the entropy risks.
We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $\rho$, estimates the eigenvalues of $\rho$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $\Theta(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 = \Theta(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 | \rho |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 $\chi^2$-divergence as corollaries.
Angelos Pelecanos, Jack Spilecki, Ewin Tang et al.· arXiv.org· 5 citations· ⚡5
The Rodeo algorithm is shown to provide a direct quantum analogue of the kernel polynomial method, derive the estimator and its uncertainties, establish an explicit dictionary between signal-processing window functions and quantum reconstruction kernels, and validate the method on the one-dimensional transverse-field Ising and spin-1 models.
Exhaustive moment fitting in this constant-dimensional space produces a proper mixture and, together with the dimension-free moment characterization of Gaussian mixtures, achieves the optimal Hellinger rate in polynomial arithmetic time for every fixed $k$.
Information distance and circuit complexity are both obtained by minimizing lengths, but they minimize over different objects. We make this distinction explicit for faithful one-mode Gaussian states. First, invariant-form uniqueness implies that no positive-definite quadratic gate cost can be invariant under the full adjoint action of the noncompact symplectic group; a positive Cartan majorant necessarily introduces additional reference data. The Uhlmann purification quotient realizes the Bures metric, and the radial covariance direction requires a system-ancilla coupling because system-only Gaussian unitaries preserve the Williamson eigenvalue. We then minimize fixed right-invariant quadratic norms on the minimal two-mode Gaussian gate algebra \(\mathfrak{sp}(4,\mathbb R)\). For the unweighted Frobenius norm, the quotient coefficients for radial and traceless covariance tangents are $G_0=[\hbar^2(u-1)]^{-1}$ and $G_2=[\hbar^2(3u-1)]^{-1}$, where $u=(2\nu/\hbar)^2$. Their ratio does not equal the Bures ratio. The radial coefficient, however, reproduces the Bures value exactly at every $u$; the mismatch is confined to the traceless sector. More generally, a constant block-diagonal two-weight schedule gives $G_0/G_2=1+2(\beta/\alpha)u/(u-1)$; matching Bures throughout the isotropic family would require the state-dependent relation $\beta/\alpha=1/u$. At the Bures-Fisher determinant crossing \(u=\varphi\), pointwise matching is possible only by inserting $\beta/\alpha=\varphi^{-1}$. Thus the Bures purification quotient is an exact state-geometric cost, but it is neither an unweighted symplectic gate cost nor a member of this fixed two-weight Nielsen family. The existence of a more general fixed positive gate norm realizing the quotient remains open.
C. Kerskens· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
