The development of quantum computation has resulted in many quantum algorithms for a wide array of tasks. Recently, there is a growing interest in using quantum computing techniques to estimate or compute quantum information-theoretic quantities such as Renyi entropy, Von Neumann entropy, matrix means, etc. Motivated by these results, we present quantum algorithms for computing the maximal quantum $f$-divergences and the operator-theoretic matrix Kubo--Ando means. Both of them involve Renyi entropies, matrix means as special cases, thus implying the universality of our framework.
Quantum Algorithms for Computing Maximal Quantum f-divergence and Kubo-Ando means
The development of quantum computation has resulted in many quantum algorithms for a wide array of tasks. Recently, there is a growing interest in using quantum computing techniques to estimate or compute quantum information-theoretic quantities such as Renyi entropy, Von Neumann entropy, matrix means, etc. Motivated by these results, we present quantum algorithms for computing the maximal quantum f-divergences and the operator-theoretic matrix Kubo--Ando means. Both of them involve Renyi entropies, matrix means as special cases, thus implying the universality of our framework.
Quantum generalizations of the Fisher information are important in quantum information science, with applications in high energy and condensed matter physics and in quantum estimation theory, machine learning, and optimization. One can derive a quantum generalization of the Fisher information matrix in a natural way as the Hessian matrix arising in a Taylor expansion of a smooth divergence. Such an approach is appealing for quantum information theorists, given the ubiquity of divergences in quantum information theory. In contrast to the classical case, there is not a unique quantum generalization of the Fisher information matrix, similar to how there is not a unique quantum generalization of the relative entropy or the Rényi relative entropy. In this paper, I derive information matrices arising from the log-Euclidean, α-z, and geometric Rényi relative entropies, with the main technical tool for doing so being the method of divided differences for calculating matrix derivatives. Interestingly, for all non-negative values of the Rényi parameter α, the log-Euclidean Rényi relative entropy leads to the Kubo-Mori information matrix, and the geometric Rényi relative entropy leads to the right-logarithmic derivative Fisher information matrix. Thus, the resulting information matrices obey the data-processing inequality for all non-negative values of the Rényi parameter α even though the original quantities do not. Additionally, I derive and establish basic properties of α-z information matrices resulting from the α-z Rényi relative entropies. For parameterized thermal states and time-evolved states, I establish formulas for their α-z information matrices and hybrid quantum-classical algorithms for estimating them, with applications in quantum Boltzmann machine learning.
Quantum information processing is limited, in practice, to efficiently implementable operations. This motivates the study of quantum divergences that preserve their operational meaning while faithfully capturing these computational constraints. Using geometric, computational, and information theoretic tools, we define two new types of computational divergences, which we termcomputational max-divergence and computational measured Rényi divergences. Both are constrained by a family of efficient binary measurements, and thus useful for state discrimination tasks in the computational setting. We prove that, in the infinite-order limit, the computational measured Rényi divergence coincides with the computational max-divergence, mirroring the corresponding relation in the unconstrained information-theoretic setting. For the many-copy regime, we introduce regularized versions and establish a one-sided computational Stein bound on achievable hypothesis-testing exponents under efficient measurements, giving the regularized computational measured relative entropy an operational meaning. We further define resource measures induced by our computational divergences and prove an asymptotic continuity bound for the computational measured relative entropy of resource. Focusing on entanglement, we relate our results to previously proposed computational entanglement measures and provide explicit separations from the information-theoretic setting. Together, these results provide a principled, cohesive approach towards state discrimination tasks and resource quantification under computational constraints.
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.
We investigate the computational hardness of estimating the quantum α-Rényi entropy SαR(ρ)=1−αlnTr(ρα) and the quantum q-Tsallis entropy SqT(ρ)=q−11−Tr(ρq), both of which converge to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEAα) and Quantum q-Tsallis Entropy Approximation (TsallisQEAq) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or SqT(ρ), is at least τ1 or at most τ2, where τ1−τ2 is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders.
We establish that for all positive real α and q, and also for α=∞, the rank-2 variants Rank2RényiQEAα and Rank2TsallisQEAq are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), as well as the one derived from O'Donnell and Wright (STOC 2016), our results imply:
- For all real orders α>0 or α=∞, and for all real orders 0<q≤1, LowRankRényiQEAα and LowRankTsallisQEAq are BQP-complete, where both are restricted versions of RényiQEAα and TsallisQEAq with ρ of polynomial rank.
- For all real order q>1, TsallisQEAq is BQP-complete.
Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.
The study of quantum and classical correlations between subsystems is fundamental to understanding many-body physics. In quantum information theory, the quantum mutual information, I(A;B), is a measure of correlation between the subsystems A,B in a quantum state, and is defined by the means of the von Neumann entropy: I(A;B)=S(ρA)+S(ρB)−S(ρAB). However, such a computation requires an exponential amount of resources. This is a defining feature of quantum systems, the infamous ``curse of dimensionality'' . Other measures, which are based on Rényi divergences instead of von Neumann entropy, were suggested as alternatives in a recent paper showing them to possess important theoretical features, and making them leading candidates as mutual information measures. In this work, we concentrate on the maximal Rényi divergence. This measure can be shown to be the solution of a generalized eigenvalue problem. To calculate it efficiently for a 1D state represented as a matrix product state, we develop a generalized eigenvalue version of the density matrix renormalization group algorithm. We benchmark our method for the paradigmatic XXZ chain, and show that the maximal Rényi divergence may exhibit different trends than the von Neumann mutual information.
The concept of classical f-divergences gives a unified framework to construct and study measures of dissimilarity of probability distributions; special cases include the relative entropy and the R\'enyi divergences. Various quantum versions of this concept, and more narrowly, the concept of R\'enyi divergences, have been introduced in the literature with applications in quantum information theory; most notably Petz' quasi-entropies (standard f-divergences), Matsumoto's maximal f-divergences, measured f-divergences, and sandwiched and α-z-R\'enyi divergences. In this paper we give a systematic overview of the various concepts of quantum f-divergences with a main focus on their monotonicity under quantum operations, and the implications of the preservation of a quantum f-divergence by a quantum operation. In particular, we compare the standard and the maximal f-divergences regarding their ability to detect the reversibility of quantum operations. We also show that these two quantum f-divergences are strictly different for non-commuting operators unless f is a polynomial, and obtain some analogous partial results for the relation between the measured and the standard f-divergences. We also study the monotonicity of the α-z-R\'enyi divergences under the special class of bistochastic maps that leave one of the arguments of the R\'enyi divergence invariant, and determine domains of the parameters α,z where monotonicity holds, and where the preservation of the α-z-R\'enyi divergence implies the reversibility of the quantum operation.