Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.13383 · Advanced Quantum Technologies

Efficient algorithm for fidelity estimation of two quantum states

Anumita Mukhopadhyay, Shibdas Roy, Arun Kumar Pati

quant-phSubmitted Nov 17, 2025• Announced Nov 18, 2025• 0 citations• Revised Sep 4, 2026 (v4)
v1 · Nov 17, 2025v2 · May 8, 2026v3 · Aug 21, 2026v4 · Sep 4, 2026
arXivHTMLPDF

Abstract

The fidelity estimation between two quantum states is crucial for quantum computation and information science. However, an efficacious method for this, especially for mixed states and higher-dimensional density matrices, remains elusive. While there are many existing algorithms on computing the fidelity between two pure states, there is not much work on how to obtain the fidelity between two mixed states. Here, an efficient quantum algorithm for the fidelity estimation is proposed, based primarily on the density matrix exponentiation and interferometeric scheme for mixed states, with a time complexity of $O(κ^2N^2/ε^7)$, where $N$ is the system size, $κ$ is the larger of the condition number of the density matrices and $ε$ is a precision error. This algorithm may serve as a resource-efficient technique to deduce fidelity of any two (pure or mixed) unknown or known quantum states, when the density matrices of the quantum states commute with each other.

Journal reference
Advanced Quantum Technologies, Volume 9, no. 8 (2026)
DOI
10.1002/qute.70406
Comments
8 pages, 2 figure

Related papers

Quantum Algorithm for Fidelity Estimation

Qisheng Wang, Zhicheng Zhang, Kean Chen +4 more

For two unknown mixed quantum states$\rho $and$\sigma $in an$N$-dimensional Hilbert space, computing their fidelity$F(\rho,\sigma)$is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in${\mathrm{ poly}}(\log (N), r, 1/\varepsilon)$time, where$r$is the lower rank of$\rho $and$\sigma $, and$\varepsilon $is the desired precision, provided that the purifications of$\rho $and$\sigma $are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in$N$.

arXiv:2103.09076•IEEE Transactions on Information Theory•Sep 5, 2022•37 citations

Estimation of trace distance between two arbitrary quantum states

Sanchita Ghosh, Anumita Mukhopadhyay, Anindita Bera +2 more

When it comes to discriminating between two quantum states, trace distance is one of the well-known metrics used in quantum computation and quantum information theory. While there are several quantum algorithms for calculating the trace distance between two quantum states, computing it for any two general density matrices remains computationally demanding. In this paper, we propose a quantum algorithm based on the exponentiation of the density matrix and the improved quantum phase estimation (IQPE) to determine the trace distance for both pure and mixed states, with a time complexity of $O(N^2/\varepsilon^6)$ where $N$ is the number of qubits of the given states and $\varepsilon$ is the simulation or estimation precision error. We demonstrate its ability to predict the quantity with proof-of-principle simulations and also quantum hardware computations on the IBM quantum computers, confirming its promise for near-term quantum devices.

quant-pharXiv:2604.05628•Apr 8, 2026•0 citations

Efficient Quantum Algorithm for Mixed-State Quantum Geometry

Chenyang Wang, Qi Zhao, Xiao Yuan +1 more

Mixed-state quantum geometry plays a fundamental role in quantum metrology, multiparameter estimation, and the characterization of quantum many-body systems. Yet, unlike its pure-state counterpart, accessing mixed-state geometry requires solving an ill-conditioned Lyapunov equation for the symmetric logarithmic derivative (SLD), posing a major challenge for resource-efficient quantum computation. Here we address the challenge and develop a novel quantum algorithmic framework for efficiently accessing the quantum Fisher information matrix (QFIM) and quantum geometric tensor (QGT) of mixed states. Our key insight is to uncover a previously unexplored connection between the positive semidefinite structure of density matrices and exponentially convergent Gauss-Laguerre quadrature, enabling an efficient integral-based construction of the SLD. A rigorous complexity analysis further establishes the resource efficiency of our algorithm, demonstrating logarithmic precision dependence and double-logarithmic ancillary-qubit overhead at fixed conditioning. Building on this construction, we achieve near-Heisenberg precision scaling for diagonal QFI estimation without quantum phase estimation and construct unified block encodings of the full QFIM and QGT under a bounded spectral-gap assumption. A complementary regularized algorithm extends efficient diagonal estimation to exponentially small spectral gaps under a bounded-response condition. Our results establish a resource-efficient route to coherent mixed-state quantum geometry, enabling its direct integration into quantum linear-algebra algorithms without classical reconstruction and opening new possibilities for quantum-enhanced multiparameter metrology.

quant-pharXiv:2610.24686•Oct 20, 2026•0 citations

Polynomial-time certification of fidelity for many-body mixed states and mixed-state universality classes

Yuhan Liu, Yijian Zou

Computation of Uhlmann fidelity between many-body mixed states generally involves full diagonalization of exponentially large matrices. In this work, we introduce a polynomial-time algorithm to compute certified lower and upper bounds for the fidelity between matrix product density operators (MPDOs). Our method maps the fidelity estimation problem to a variational optimization of sequential quantum circuits, allowing for systematic improvement of the lower bounds by increasing the circuit depth. Complementarily, we obtain certified upper bounds on fidelity by variational lower bounds on the trace distance through the same framework. We demonstrate the power of this approach with two examples: fidelity correlators in critical mixed states, and codeword distinguishability in an approximate quantum error-correcting code. Remarkably, the variational lower bound accurately track the universal scaling behavior of the fidelity with a size-consistent relative error, allowing for the extraction of previously unknown critical exponents. Our results offer an exponential improvement in precision over known moment-based bounds and establish a scalable framework for the verification of many-body quantum systems.

quant-pharXiv:2601.13333•Jan 21, 2026•0 citations

Improved Quantum Algorithms for Fidelity Estimation

András Gilyén, Alexander Poremba

Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficult to give good estimates of fidelity, especially when one works with mixed states over Hilbert spaces of very high dimension. Although, there has been some progress on fidelity estimation, all prior work either requires a large number of identical copies of the relevant states, or relies on unproven heuristics. In this work, we improve on both of these aspects by developing new and efficient quantum algorithms for fidelity estimation with provable performance guarantees in case at least one of the states is approximately low-rank. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation, as well as density matrix exponentiation and quantum spectral sampling. As a complementary result, we prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general, by giving a sample complexity lower bound that depends polynomially on the dimension. Moreover, if circuit descriptions for the relevant states are provided, we show that the task is hard for the complexity class called (honest verifier) quantum statistical zero knowledge via a reduction to a closely related result by Watrous.

arXiv:2203.15993•Mar 30, 2022•14 citations

Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Wang Sheng Fang, Qisheng Wang

We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error ε by using Θ(1/ε) queries to their state-preparation circuits, achieving a quadratic speedup over the folklore O(1/ε²). Our approach is technically simple, and can moreover estimate the quantity √{tr(ρσ²)} that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.

arXiv:2506.23650•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations
The fidelity estimation between two quantum states is crucial for quantum computation and information science. However, an efficacious method for this, especially for mixed states and higher-dimensional density matrices, remains elusive. While there are many existing algorithms on computing the fidelity between two pure states, there is not much work on how to obtain the fidelity between two mixed states. Here, an efficient quantum algorithm for the fidelity estimation is proposed, based primarily on the density matrix exponentiation and interferometeric scheme for mixed states, with a time complexity of O(κ2N2/ε7)O(κ^2N^2/ε^7)O(κ2N2/ε7), where NNN is the system size, κκκ is the larger of the condition number of the density matrices and εεε is a precision error. This algorithm may serve as a resource-efficient technique to deduce fidelity of any two (pure or mixed) unknown or known quantum states, when the density matrices of the quantum states commute with each other.
For two unknown mixed quantum states$\rho andandand\sigma inanin aninanN−dimensionalHilbertspace,computingtheirfidelity-dimensional Hilbert space, computing their fidelity−dimensionalHilbertspace,computingtheirfidelityF(\rho,\sigma)isabasicproblemwithmanyimportantapplicationsinquantumcomputingandquantuminformation,forexampleverificationandcharacterizationoftheoutputsofaquantumcomputer,anddesignandanalysisofquantumalgorithms.Inthispaper,weproposeaquantumalgorithmthatsolvesthisprobleminis a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem inisabasicproblemwithmanyimportantapplicationsinquantumcomputingandquantuminformation,forexampleverificationandcharacterizationoftheoutputsofaquantumcomputer,anddesignandanalysisofquantumalgorithms.Inthispaper,weproposeaquantumalgorithmthatsolvesthisproblemin{\mathrm{ poly}}(\log (N), r, 1/\varepsilon)time,wheretime, wheretime,whereristhelowerrankofis the lower rank ofisthelowerrankof\rho andandand\sigma ,and, and,and\varepsilon isthedesiredprecision,providedthatthepurificationsofis the desired precision, provided that the purifications ofisthedesiredprecision,providedthatthepurificationsof\rho andandand\sigma arepreparedbyquantumoracles.Thisalgorithmexhibitsanexponentialspeedupoverthebestknownalgorithm(basedonquantumstatetomography)whichhastimecomplexitypolynomialinare prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial inarepreparedbyquantumoracles.Thisalgorithmexhibitsanexponentialspeedupoverthebestknownalgorithm(basedonquantumstatetomography)whichhastimecomplexitypolynomialinN$.
When it comes to discriminating between two quantum states, trace distance is one of the well-known metrics used in quantum computation and quantum information theory. While there are several quantum algorithms for calculating the trace distance between two quantum states, computing it for any two general density matrices remains computationally demanding. In this paper, we propose a quantum algorithm based on the exponentiation of the density matrix and the improved quantum phase estimation (IQPE) to determine the trace distance for both pure and mixed states, with a time complexity of O(N2/ε6)O(N^2/\varepsilon^6)O(N2/ε6) where NNN is the number of qubits of the given states and ε\varepsilonε is the simulation or estimation precision error. We demonstrate its ability to predict the quantity with proof-of-principle simulations and also quantum hardware computations on the IBM quantum computers, confirming its promise for near-term quantum devices.
Mixed-state quantum geometry plays a fundamental role in quantum metrology, multiparameter estimation, and the characterization of quantum many-body systems. Yet, unlike its pure-state counterpart, accessing mixed-state geometry requires solving an ill-conditioned Lyapunov equation for the symmetric logarithmic derivative (SLD), posing a major challenge for resource-efficient quantum computation. Here we address the challenge and develop a novel quantum algorithmic framework for efficiently accessing the quantum Fisher information matrix (QFIM) and quantum geometric tensor (QGT) of mixed states. Our key insight is to uncover a previously unexplored connection between the positive semidefinite structure of density matrices and exponentially convergent Gauss-Laguerre quadrature, enabling an efficient integral-based construction of the SLD. A rigorous complexity analysis further establishes the resource efficiency of our algorithm, demonstrating logarithmic precision dependence and double-logarithmic ancillary-qubit overhead at fixed conditioning. Building on this construction, we achieve near-Heisenberg precision scaling for diagonal QFI estimation without quantum phase estimation and construct unified block encodings of the full QFIM and QGT under a bounded spectral-gap assumption. A complementary regularized algorithm extends efficient diagonal estimation to exponentially small spectral gaps under a bounded-response condition. Our results establish a resource-efficient route to coherent mixed-state quantum geometry, enabling its direct integration into quantum linear-algebra algorithms without classical reconstruction and opening new possibilities for quantum-enhanced multiparameter metrology.
Computation of Uhlmann fidelity between many-body mixed states generally involves full diagonalization of exponentially large matrices. In this work, we introduce a polynomial-time algorithm to compute certified lower and upper bounds for the fidelity between matrix product density operators (MPDOs). Our method maps the fidelity estimation problem to a variational optimization of sequential quantum circuits, allowing for systematic improvement of the lower bounds by increasing the circuit depth. Complementarily, we obtain certified upper bounds on fidelity by variational lower bounds on the trace distance through the same framework. We demonstrate the power of this approach with two examples: fidelity correlators in critical mixed states, and codeword distinguishability in an approximate quantum error-correcting code. Remarkably, the variational lower bound accurately track the universal scaling behavior of the fidelity with a size-consistent relative error, allowing for the extraction of previously unknown critical exponents. Our results offer an exponential improvement in precision over known moment-based bounds and establish a scalable framework for the verification of many-body quantum systems.
Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficult to give good estimates of fidelity, especially when one works with mixed states over Hilbert spaces of very high dimension. Although, there has been some progress on fidelity estimation, all prior work either requires a large number of identical copies of the relevant states, or relies on unproven heuristics. In this work, we improve on both of these aspects by developing new and efficient quantum algorithms for fidelity estimation with provable performance guarantees in case at least one of the states is approximately low-rank. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation, as well as density matrix exponentiation and quantum spectral sampling. As a complementary result, we prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general, by giving a sample complexity lower bound that depends polynomially on the dimension. Moreover, if circuit descriptions for the relevant states are provided, we show that the task is hard for the complexity class called (honest verifier) quantum statistical zero knowledge via a reduction to a closely related result by Watrous.
We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error ε by using Θ(1/ε) queries to their state-preparation circuits, achieving a quadratic speedup over the folklore O(1/ε²). Our approach is technically simple, and can moreover estimate the quantity √{tr(ρσ²)} that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.