Nonasymptotic bounds for quantum purity amplification

• URL: http://arxiv.org/abs/2605.27262v1
• Date: Tue, 26 May 2026 16:39:24 GMT
• Title: Nonasymptotic bounds for quantum purity amplification
• Abstract summary: In quantum purity amplification, one is given $n$ copies of a noisy quantum state $in mathbbCd times d$ and asked to prepare $k$ copies of its principal eigenstate $|v_drangle$.<n>Several prior works have derived information-theoretically optimal algorithms for this problem, but the they prove are only shown in the regime as the number of samples $n$ tends to infinity.
• Score: 0.9969485010222057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In quantum purity amplification, one is given $n$ copies of a noisy quantum state $ρ\in \mathbb{C}^{d \times d}$ and asked to prepare $k$ copies of its principal eigenstate $|v_d\rangle$. Several prior works have derived information-theoretically optimal algorithms for this problem, but the bounds they prove are only shown in the asymptotic regime as the number of samples $n$ tends to infinity. In this paper, we establish the following nonasymptotic guarantee: if $ρ$'s eigenvalues are sorted $p_1 \leq \cdots \leq p_d$ and $p_{d-1} < p_d$, then \begin{equation*} n = O\Big(k + \frac{k}δ \cdot \frac{1-p_d}{(p_d-p_{d-1})^2}\Big) \end{equation*} copies suffice to output a state with fidelity at least $1-δ$ with $|v_d^{\otimes k}\rangle$. Our bound holds for arbitrary spectra, and is independent of the dimension $d$. In the case of depolarizing noise, our finite-sample guarantee matches the optimal asymptotic scaling. Our proof is based on the combinatorics of random Young diagrams.

Related papers

• Isospectral majorization and isoperimetric inequalities for coherent states on the Bloch sphere [0.0]
  We prove an isospectral version of Lieb-Solovej inequality.<n>Spherical caps maximize every partial sum of the eigenvalues of Toeplitz operators with symbol $1_$.
  arXiv  Detail & Related papers  (2026-08-12T16:46:26Z)
• Optimal Quantum de Finetti Theorems via Argmax Rounding [42.55259086694773]
  We prove optimal finite quantum de Finetti upper bounds for bosonic states and arbitrary exchangeable states.<n>Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program.<n> spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance.
  arXiv  Detail & Related papers  (2026-08-03T17:57:15Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
  We significantly improve the sample complexity of estimating $operatornametr(rhoq)$ in both the upper and lower bounds.<n>Our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling.
  arXiv  Detail & Related papers  (2025-05-14T17:06:33Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Smooth min-entropy lower bounds for approximation chains [0.0]
  We prove a simple entropic triangle inequality, which allows us to bound the smooth min-entropy of a state in terms of the R'enyi entropy of an arbitrary auxiliary state. Using this triangle inequality, we create lower bounds for the smooth min-entropy of a state in terms of the entropies of its approximation chain in various scenarios.
  arXiv  Detail & Related papers  (2023-08-22T18:55:16Z)
• Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
  We show that a phase estimation algorithm with precision $delta$ and error probability $epsilon$ has cost $Omegaleft(frac1deltalog1epsilonright)$. We also show that having lots advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of $U$.
  arXiv  Detail & Related papers  (2023-05-08T17:46:01Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
  arXiv  Detail & Related papers  (2023-04-25T15:32:37Z)
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
  We propose a unified quantum algorithm framework for estimating properties of discrete probability distributions. Our framework estimates $alpha$-R'enyi entropy $H_alpha(p)$ to within additive error $epsilon$ with probability at least $2/3$.
  arXiv  Detail & Related papers  (2022-12-03T08:01:55Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)

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.