The trace distance between two quantum states, $\ensuremath{\rho}$ and $\ensuremath{\sigma}$, is an operationally meaningful quantity in quantum information theory. However, in general it is difficult to compute, involving the diagonalization of $\ensuremath{\rho}\ensuremath{-}\ensuremath{\sigma}$. In contrast, the Hilbert-Schmidt distance can be computed without diagonalization, although it is less operationally significant. Here, we relate the trace distance and the Hilbert-Schmidt distance with a bound that is particularly strong when either $\ensuremath{\rho}$ or $\ensuremath{\sigma}$ is low rank. Our bound is stronger than the bound one could obtain via the norm equivalence of the Frobenius and trace norms. We also consider bounds that are useful not only for low-rank states but also for low-entropy states. Our results have relevance to quantum information theory, quantum algorithm design, and quantum complexity theory.
The trace distance between two quantum states, \ensuremathρ and \ensuremathσ, is an operationally meaningful quantity in quantum information theory. However, in general it is difficult to compute, involving the diagonalization of \ensuremathρ\ensuremath−\ensuremathσ. In contrast, the Hilbert-Schmidt distance can be computed without diagonalization, although it is less operationally significant. Here, we relate the trace distance and the Hilbert-Schmidt distance with a bound that is particularly strong when either \ensuremathρ or \ensuremathσ is low rank. Our bound is stronger than the bound one could obtain via the norm equivalence of the Frobenius and trace norms. We also consider bounds that are useful not only for low-rank states but also for low-entropy states. Our results have relevance to quantum information theory, quantum algorithm design, and quantum complexity theory.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1), defined via the operator norm ∥A∥∞=σmax(A), given poly(n)-size state-preparation circuits of n-qubit quantum states ρ0 and ρ1. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states:
1. When one state is pure, we establish an optimal quantum estimator using Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5, our estimator runs in poly(n) time. Since the operator norm distance T∞(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩⟨ψ∣,ρ), our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with rank(ρ), which can be exp(n) in general.
2. For general quantum states, we also provide a quantum estimator using O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP-complete and improves the QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε) quantum query complexity lower bound, this leaves only square-root room for improvement.
The key intuition behind our estimators is that, when one state is pure, the pure state ∣ψ⟩ has overlap at least 1/2 with the top unit eigenvector of ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
We consider a quantum version of the famous low-rank approximation problem. Specifically, we consider the distance D(ρ,σ) between two normalized quantum states, ρ and σ, where the rank of σ is constrained to be at most R. For both the trace distance and Hilbert-Schmidt distance, we analytically solve for the optimal state σ that minimizes this distance. For the Hilbert-Schmidt distance, the unique optimal state is σ=τR+NR, where τR=ΠRρΠR is given by projecting ρ onto its R principal components with projector ΠR, and NR is a normalization factor given by NR=R1−Tr(τR)ΠR. For the trace distance, this state is also optimal but not uniquely optimal, and we provide the full set of states that are optimal. We briefly discuss how our results have application for performing principal component analysis (PCA) via variational optimization on quantum computers.
We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, forN-dimensional quantum states of rankr, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error ε have time complexity of Õ(r/ε2), Õ(r5/ε6) and Õ(r6.5/ε7.5), respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity Ω(N), and the prior best one for fidelity has time complexity Õ(r12.5/ε13.5). The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.
The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, in the case of Pauli measurements) with explicit dependence of the bounds on the rank and other complexity parameters. Such bounds are established for several statistically relevant distances, including quantum versions of Kullback-Leibler divergence (relative entropy distance) and of Hellinger distance (so called Bures distance), and Schatten p-norm distances. Sharp upper bounds and oracle inequalities for least squares estimator with von Neumann entropy penalization are obtained showing that minimax lower bounds are attained (up to logarithmic factors) for these distances.
Abstract. We consider a family of vector and operator norms which we refer to as Schmidt norms. We show that these norms have several uses in quantum information theory – they can be used to help classify k-positive linear maps (and hence entanglement witnesses), they are useful for approaching the problem of finding non-positive partial transpose bound entangled Werner states, they are related to the quantum fidelity and trace distance measures, and they are connected to the recently-defined local numerical range. We show that the vector norms can be explicitly calculated, and we derive several inequalities in order to bound the operator norms and compute them in special cases. We show that one particular entangled Werner state is bound entangled if and only if a certain norm inequality holds on a given family of projections, and we use our inequalities to study that family of projections. We also develop a family of semidefinite programs that can be used to further bound the operator norms. We extend these norms to arbitrary convex mapping cones and explore their implications with positive partial transpose states. 1.
We address the ratio between the trace speed and the Hilbert-Schmidt speed for differentiable finite-dimensional quantum states, R=∥∂φρ∥1/∥∂φρ∥2. Since the tangent ∂φρ is Hermitian and traceless, R obeys stronger bounds than those for generic operators. For any nonzero tangent of rank r, we prove the sharp bounds 2≤R≤r for even r and 2≤R≤r−1/r for odd r, characterizing all equality cases. Nonstationary pure-state and qubit families saturate the lower bound R=2. For odd Hilbert-space dimension d, we further prove the sharp global maximum R≤d−1/d. Interpreting R2 as the participation ratio of the singular-value distribution yields an effective-rank picture, reff=R2. We decompose the effective rank into classical eigenvalue and quantum eigenvector contributions and obtain the bound reff≤rC+rQ, with equality when either component vanishes. Linking the effective rank to the quantum Fisher information F gives reff≥8TS2/F, showing that a large effective rank is required when this lower bound substantially exceeds the universal minimum value 2. Finally, a hierarchy of quantum speed limits shows how the effective rank controls the tightness of bounds expressed through the Hilbert-Schmidt speed.