We establish a fundamental limit on the number of experimental repetitions (samples) required to estimate the quantum mutual information I(A:B)I(A:B)—a key measure of total correlations—when the quantum system is in a pure bipartite state. By leveraging the Schmidt decomposition, we rely on the exact relation I(A:B)=2S(ρA)I(A:B)=2S(ρA), which connects this correlation measure to the local von Neumann entropy S(ρA)S(ρA). This allows us to directly import a recently proven lower bound by Wang for entropy estimation. Concretely, we show that achieving an estimate of I(A:B)I(A:B) with a prescribed accuracy ϵϵ demands a number of samples that scales as Ω~(d2/ϵ)Ω~(d2/ϵ)—where dd denotes the effective dimension of each subsystem and the Ω~Ω~ notation absorbs logarithmic corrections. This conclusion follows rigorously from Wang's results without introducing extra hypotheses. In addition, we briefly explore the implications for emergent spacetime models, pointing out that transferring this sample-complexity barrier to geometric reconstruction requires an extra condition of stability—namely, that small changes in geometry must translate into small changes in mutual information. Without such stability, the bound does not automatically apply to the geometric sector.
We establish a fundamental limit on the number of experimental repetitions (samples) required to estimate the quantum mutual information I(A:B)I(A:B)—a key measure of total correlations—when the quantum system is in a pure bipartite state. By leveraging the Schmidt decomposition, we rely on the exact relation I(A:B)=2S(ρA)I(A:B)=2S(ρA), which connects this correlation measure to the local von Neumann entropy S(ρA)S(ρA). This allows us to directly import a recently proven lower bound by Wang for entropy estimation. Concretely, we show that achieving an estimate of I(A:B)I(A:B) with a prescribed accuracy ϵϵ demands a number of samples that scales as Ω~(d2/ϵ)Ω~(d2/ϵ)—where dd denotes the effective dimension of each subsystem and the ΩΩ notation absorbs logarithmic corrections. This conclusion follows rigorously from Wang's results without introducing extra hypotheses. In addition, we briefly explore the implications for emergent spacetime models, pointing out that transferring this sample-complexity barrier to geometric reconstruction requires an extra condition of stability—namely, that small changes in geometry must translate into small changes in mutual information. Without such stability, the bound does not automatically apply to the geometric sector.
We study the sample complexity of the prototypical tasks and . The former has been a key subroutine for experimental benchmarking and entropy estimation, while the latter is a core task for cross-platform validation that compares the unknown quantum states produced by different physical platforms. In purity estimation, we are to estimate tr ( ρ 2 ) of an unknown quantum state ρ to additive error ɛ . Meanwhile, for quantum inner product estimation, Alice and Bob are to estimate tr ( ρ σ ) to additive error ɛ , given copies of the unknown quantum states ρ and σ using classical communication and restricted quantum communication. We propose a protocol that solves quantum inner product estimation with k -qubit quantum communication and unentangled local measurements using O ( median { 1 / ɛ 2 , 2 n / 2 / ɛ , 2 n − k / ɛ 2 } ) copies of ρ and σ . Our protocol can be modified to estimate the purity of an unknown quantum state ρ using k -qubit quantum memory with the same sample complexity. We also prove that arbitrary protocols with k -qubit quantum memory that estimate purity to error ɛ require Ω ( median { 1 / ɛ 2 , 2 n / 2 / ɛ , 2 n − k / ɛ 2 } ) copies of ρ . This indicates the same sample complexity lower bound for quantum inner product estimation with k -qubit quantum communication and classical communication, and unentangled local measurements. We further improve the sample complexity lower bound for any purity estimation protocols using an identical single-copy projection-valued measurement. Last, we investigate a decisional variant of quantum distributed inner product estimation without quantum communication for mixed states and provide a sample complexity lower bound.
Conventional compressed sensing (CS) has a measurement lower bound of M = Ω(K log(N/K)) under non-adaptive measurements. Recent experiments on quantum compressed sensing (QCS) have reported numbers of measurements below this classical lower bound. In this work, we establish lower bounds on the measurement complexity of QCS from an information-theoretic and quantum-physical perspective. QCS exploits quantum parallelism, enabling a unitary domain-alignment evolution to act on a superposition of all N basis states and map the sparse basis onto the measurement basis in a one-to-one manner. Consequently, the locations of nonzero components are explicitly carried by measurement-index labels. If only basic statistical information about the K nonzero components is required, the total number of effective index samples satisfies the coarse necessary condition Ms = Ω(K). Under independent single-index projective measurements, when the support is unknown, the nonzero probabilities satisfy pn = Θ(1/K), and exact support recovery is required with a fixed success probability, the sampling-coverage requirement leads to Ms = Θ(K ln K). If each nonzero amplitude coefficient is further required to achieve a coordinate-wise relative root-mean-square error ε, the optimal effective index sample complexity is Ms = Θ(K ln K + K/ε2), which reduces to Θ(K ln K) for fixed ε. Multimode photon-number-resolving detection can reduce the number of experimental rounds but not the total effective index sample complexity. These results show that quantum parallelism is not only a core resource for quantum computing but can also play a transformative role in measurement science.
For quantum state tomography on rank- r dimension- d states, we show that O~(r.5d1.5/ϵ)≤O~(d2/ϵ) copies suffice for accuracy ϵ with respect to (Bures) χ2 -divergence, and O~(rd/ϵ) copies suffice for accuracy ϵ with respect to quantum relative entropy. The best previous bound was O~(rd/ϵ)≤O~(d2/ϵ) with respect to infidelity; our results are an improvement since infidelity is bounded above by both the relative entropy and the χ2 -divergence. For algorithms that are required to use single-copy measurements, we show that O~(r1.5d1.5/ϵ)≤O~(d3/ϵ) copies suffice for χ2 -divergence, and O~(r2d/ϵ) suffice for relative entropy.Using this tomography algorithm, we show that O~(d2.5/ϵ) copies of a d×d -dimensional bipartite state suffice to test if it has quantum mutual information 0 or at least ϵ . As a corollary, we also improve the best known sample complexity for the classical version of mutual information testing to O~(d/ϵ) .
We show that the sample complexity required in quantum learning theory within a general parametric framework is fundamentally governed by the inverse Fisher information matrix. More specifically, we derive upper and lower bounds on the number of samples required to estimate the parameters of a quantum system within a prescribed small additive error, with high success probability under maximum-likelihood estimation. Notably, both the upper and lower bounds are determined by the supremum of the maximum diagonal entry of the inverse Fisher information matrix. We then apply the general bounds to Pauli channel learning and Pauli expectation value learning, which serve as representative tasks in quantum channel and state learning, respectively, in the asymptotic small-error regime. Furthermore, we identify the structural origin of exponential sample complexity in Pauli channel learning without entanglement and in Pauli expectation value learning without quantum memory by comparing the quantum Fisher information matrix and the classical Fisher information matrix. We then extend the analysis to an error criterion based on the Euclidean distance between the true parameter values and their estimators, deriving the corresponding upper and lower bounds on the sample complexity, which are likewise characterized by the inverse Fisher information matrix. As an application, we consider Pauli channel learning with entangled probes. We highlight two fundamental contributions to quantum learning theory. First, we establish a systematic framework that determines the task-independent sample complexity under maximum-likelihood estimation. Second, we show that, in the small-error regime, the learning sample complexity is governed by the inverse Fisher information matrix, which is the central quantity in quantum metrology that determines the ultimate achievable mean squared error.
Quantum mechanics has traditionally relied on entanglement as the primary resource for describing non-classical correlations between distinct physical systems. However, entanglement fails to capture the entirety of mutual information and systemic accessibility, particularly in open, mixed, or high-dimensional environments where local states and shared correlations exhibit distinct scaling behaviors. In this paper, we introduce the concept of Mutual Observability of Quantum States (MOQ), a novel theoretical framework that quantifies how effectively one quantum system can observe or be observed by another, independently of traditional entanglement constraints. We define the mutual observability index V_AB as the ratio of the mutual information I(A:B) to the sum of the local von Neumann entropies S(A) + S(B). Through rigorous mathematical formulation, we establish its strict analytical bounds within the closed interval from 0 to 1, explore its fundamental algebraic properties, and analyze its dynamical behavior in open quantum systems. We demonstrate that MOQ dictates the strength of measurable influence and information transfer between subsystems even when quantum entanglement vanishes entirely. This framework establishes a paradigm shift in understanding quantum correlations, paving the way for advanced applications in quantum communication networks, quantum state estimation, and quantum thermodynamics.
The entropy of a quantum system is a measure of its randomness, and has applications in measuring quantum entanglement. We study the problem of estimating the von Neumann entropy, S(ρ), and Rényi entropy, Sα(ρ) of an unknown mixed quantum state ρ in d dimensions, given access to independent copies of ρ. We provide algorithms with copy complexity O(d2/α) for estimating Sα(ρ) for α2) for estimating S(ρ), and Sα(ρ) for non-integral α > 1. These bounds are at least quadratic in d, which is the order dependence on the number of copies required for estimating the entire state ρ. For integral α > 1, on the other hand, we provide an algorithm for estimating Sα(ρ) with a sub-quadratic copy complexity of O(d2-2/α), and we show the optimality of the algorithms by providing a matching lower bound.