pith. sign in

arxiv: 2511.13383 · v2 · submitted 2025-11-17 · 🪐 quant-ph

Efficient algorithm for fidelity estimation of two quantum states

Anumita Mukhopadhyay , Shibdas Roy , Arun Kumar Pati This is my paper

Pith reviewed 2026-05-17 22:25 UTC · model grok-4.3

classification 🪐 quant-ph
keywords fidelity estimationquantum algorithmmixed statesdensity matrix exponentiationcommuting density matricesinterferometric schemequantum information
0
0 comments X

The pith

Quantum algorithm estimates fidelity of two commuting mixed states using density matrix exponentiation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a quantum algorithm for estimating the fidelity between two quantum states, focusing on the case of mixed states whose density matrices commute. The method relies on density matrix exponentiation and an interferometric scheme, resulting in a time complexity of O(κ²N²/ε⁷). This is important because existing techniques are limited for mixed states in higher dimensions, and fidelity is central to assessing similarity in quantum information processing. If correct, it offers a practical tool for verifying quantum operations and characterizing unknown states under the commuting condition.

Core claim

When the density matrices of two quantum states commute, their fidelity can be estimated efficiently on a quantum computer by exponentiating the density matrices to simulate unitary evolutions and employing an interferometric scheme to extract the overlap information, achieving a runtime of O(κ² N² / ε⁷).

What carries the argument

Density matrix exponentiation combined with an interferometric scheme for mixed states, which enables the simulation of quantum evolution generated by the density operator to compute the fidelity.

If this is right

  • The algorithm applies to both pure and mixed states provided their density matrices commute.
  • It serves as a resource-efficient technique for deducing fidelity of unknown or known quantum states.
  • The time complexity scales polynomially with system size N and inverse precision 1/ε, modulated by the condition number κ.
  • The method provides a way to handle higher-dimensional density matrices where direct classical computation is intractable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the commuting assumption can be relaxed, the approach might generalize to arbitrary states using additional quantum resources.
  • Such an algorithm could integrate into protocols for quantum state certification or benchmarking of quantum devices.
  • Testing the method on small-scale quantum simulators would verify the claimed scaling.

Load-bearing premise

The density matrices of the two quantum states commute with each other.

What would settle it

Running the proposed algorithm on two non-commuting density matrices and comparing the output to the classically computed fidelity value would show if the method fails as expected outside the commuting case.

Figures

Figures reproduced from arXiv: 2511.13383 by Anumita Mukhopadhyay, Arun Kumar Pati, Shibdas Roy.

Figure 1
Figure 1. Figure 1: FIG. 1. Circuit diagram of the Mach-Zehnder interferometer. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original 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(\kappa^2N^2/\epsilon^7)$, where $N$ is the system size, $\kappa$ is the condition number of the density matrices and $\epsilon$ 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes a quantum algorithm for estimating the fidelity between two quantum states (pure or mixed) that relies on density-matrix exponentiation combined with an interferometric scheme. The algorithm is stated to achieve time complexity O(κ² N² / ε⁷) and is explicitly restricted to the case where the two density matrices commute ([ρ, σ] = 0).

Significance. If the derivation and error analysis are correct, the result would supply a concrete quantum procedure for fidelity estimation in the commuting case, which is relevant for certain quantum information tasks involving jointly diagonalizable states. The use of density-matrix exponentiation and interferometry is a standard toolkit, but the commuting restriction means the headline scaling applies only inside a regime where classical eigenvalue summation is already feasible given access to the states.

major comments (3)
  1. [Abstract and §3] Abstract and §3 (Algorithm): the claimed O(κ² N² / ε⁷) scaling is derived under the explicit assumption [ρ, σ] = 0, yet the manuscript provides no argument that the interferometric scheme or block-encoding primitives remain efficient without simultaneous diagonalization; when the states commute the fidelity reduces to a classical sum over eigenvalues, so the quantum overhead must be justified against direct classical computation of the same sum.
  2. [§4] §4 (Complexity and Error Analysis): the 1/ε⁷ dependence arises from the combination of density-matrix exponentiation and interferometry, but the manuscript does not show an explicit query-complexity calculation or compare it to amplitude-estimation variants that could reduce the exponent; without this derivation the polynomial scaling cannot be verified as load-bearing for the central claim.
  3. [§2] §2 (Preliminaries): the condition number κ is introduced in the complexity bound, but the paper does not specify how κ is bounded for density matrices with small eigenvalues or how the algorithm behaves when κ grows with system size N, which directly affects whether the stated runtime remains sub-exponential.
minor comments (2)
  1. Notation for the fidelity functional and the interferometric circuit diagram should be made consistent between the abstract and the main text.
  2. A brief comparison table with existing fidelity algorithms (e.g., for pure states or non-commuting mixed states) would clarify the scope of the new result.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We respond to each major comment below, indicating where revisions will be incorporated.

read point-by-point responses

  1. Referee: [Abstract and §3] the claimed O(κ² N² / ε⁷) scaling is derived under the explicit assumption [ρ, σ] = 0, yet the manuscript provides no argument that the interferometric scheme or block-encoding primitives remain efficient without simultaneous diagonalization; when the states commute the fidelity reduces to a classical sum over eigenvalues, so the quantum overhead must be justified against direct classical computation of the same sum.

    Authors: The algorithm is developed specifically for the case where the density matrices commute, allowing the density matrix exponentiation to be performed in a manner consistent with the shared eigenbasis. The interferometric scheme estimates the fidelity by measuring overlaps in the quantum domain. We acknowledge that for commuting states, the fidelity is ∑_i √(λ_i μ_i), which can be computed classically if the eigenvalues are available. However, in the quantum setting where states are accessed via oracles or quantum circuits (as is common in quantum algorithms), obtaining the full spectrum classically can be resource-intensive for large N. Our quantum algorithm provides an efficient way under the given access model. We will revise §3 to include a discussion justifying the quantum approach and clarifying the role of the commuting assumption in maintaining efficiency of the primitives. revision: yes

  2. Referee: [§4] the 1/ε⁷ dependence arises from the combination of density-matrix exponentiation and interferometry, but the manuscript does not show an explicit query-complexity calculation or compare it to amplitude-estimation variants that could reduce the exponent; without this derivation the polynomial scaling cannot be verified as load-bearing for the central claim.

    Authors: We agree that providing an explicit step-by-step query complexity derivation is important for verifying the scaling. The ε^{-7} arises from the precision needed for DME combined with the number of interferometry measurements and error bounds in the overall estimation. In the revised version, we will add a detailed calculation in §4, including the query complexity breakdown, and include a short comparison noting that while amplitude estimation could potentially lower the exponent, it may introduce additional assumptions or overheads not present in our interferometric approach. revision: yes

  3. Referee: [§2] the condition number κ is introduced in the complexity bound, but the paper does not specify how κ is bounded for density matrices with small eigenvalues or how the algorithm behaves when κ grows with system size N, which directly affects whether the stated runtime remains sub-exponential.

    Authors: We define κ as the condition number of the density matrices, specifically κ = λ_max / λ_min where λ_min is the smallest non-zero eigenvalue. For density matrices with eigenvalues close to zero, κ can be large, leading to worse scaling. The algorithm's runtime is polynomial in κ, N, and 1/ε, but if κ scales exponentially with N, it would not be efficient. We will update §2 to explicitly define and discuss the assumptions on κ, and add a remark in the complexity section about the implications when κ grows with N. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithm is a new construction under explicit commuting assumption

full rationale

The paper presents a quantum algorithm for fidelity estimation of commuting density matrices using density-matrix exponentiation and an interferometric scheme, with explicit time complexity O(κ²N²/ε⁷). No derivation step reduces by construction to its own inputs, fitted parameters renamed as predictions, or load-bearing self-citations that are themselves unverified. The commuting condition [ρ, σ] = 0 is stated upfront as a restriction rather than smuggled in via definition or prior self-work. The central claim remains an independent algorithmic construction whose correctness can be checked against external benchmarks for the special case of jointly diagonalizable states. No self-definitional loops, ansatz smuggling, or renaming of known results appear in the provided abstract or derivation outline.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review based solely on abstract; no explicit free parameters, axioms, or invented entities are detailed. The commuting condition is a domain restriction rather than a new axiom or entity.

pith-pipeline@v0.9.0 · 5456 in / 1133 out tokens · 29193 ms · 2026-05-17T22:25:48.360662+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    to exponentiate the density matrices, to be used as controlled unitaries in improved quantum phase estima- tion (IQPE) [27, 28] to estimate the eigenvalues ofρ1 and ρ2, followed by controlled rotation and post-selection, to get the normalised square roots of the density matrices. Subsequently, we use the interference of the mixed state scheme, which utili...

    work page

  2. [2]

    Implement Density Matrix Exponentiation (DME) on each of the statesρ=ρ 1 andρ=ρ 2 to ob- tain controlled unitaries for Improved Quantum Phase Estimation (IQPE) to be performed in the next step. DME by Lloyd-Mohseni-Rebentrost al- gorithm (LMR) [26] is implemented as follows using Swap operator,S: TrA eiS∆t(ρ⊗ς)e −iS∆t = TrA (eiς∆t ρe−iς∆t) ⊗(eiρ∆tςe −iρ∆t...

    work page

  3. [3]

    Perform Improved Quantum Phase Estimation (IQPE) [28] with the exponentiated density ma- trices (e iρ1t ande iρ2t) to estimate the eigenvalues ofρ=ρ 1 andρ=ρ 2, respectively, as follows: |0⟩⟨0| ⊗ 1 2N IQP E − − − − → eiρt 1 2N P u |˜φu⟩⟨˜φu| ⊗ |u⟩⟨u|, where Nis the number of qubits that constitute the state ρ= P u φu|u⟩⟨u|and ˜φu is an estimate ofφ u

    work page

  4. [4]

    We do this for both the statesρ=ρ 1 andρ=ρ 2

    We prepareznumber of ancilla qubits in state |0⟩⊗z, rotate it based on the phase estimates ˜φ u, and then we undo the phase estimation process, to get: 1 2N P u |u⟩⟨u| ⊗[ p 1− √ ˜φu|0⟩⊗z + p√ ˜φu|1⟩⊗z](15) [ p 1− √ ˜φu⟨0|⊗z + p√ ˜φu⟨1|⊗z], and post-select the above state for an ancilla qubit to be|1⟩, to obtain the state 1 λ P u √ ˜φu|u⟩⟨u|, which is an e...

    work page

  5. [5]

    We exponentiate χand perform phase estimation on the resulting unitarye iχt1 for eigenstate|1⟩, wheret 1 is a small time, to get an estimate ˜λofλ

    The effective state of each of the ancilla qubits in (15) isχ:= (1−λ)|0⟩⟨0|+λ|1⟩⟨1|. We exponentiate χand perform phase estimation on the resulting unitarye iχt1 for eigenstate|1⟩, wheret 1 is a small time, to get an estimate ˜λofλ. We do this for both the statesρ=ρ 1 andρ=ρ 2

    work page

  6. [6]

    To accomplish this, DME is performed onσ= λ+|χ+⟩⟨χ+|+λ −|χ−⟩⟨χ−|from Fig

    We compute Tr(ρ 1/2 1 ρ1/2 2 ) using Tr(ρ ′U), where ρ′ = √ρ1/Tr√ρ1, andU=e it2 √ρ2/Tr√ρ2 (again obtained by DME), for a small timet 2 =τwhere : Tr(ρ′U) =1−iτ Tr√ρ1ρ2 Tr√ρ1Tr√ρ2 . To accomplish this, DME is performed onσ= λ+|χ+⟩⟨χ+|+λ −|χ−⟩⟨χ−|from Fig. 1 to ex- ponentiate it, followed by IQPE on it to esti- mateλ + = 1 + √ αα† andλ − = 1− √ αα†. Here,|χ ...

    work page

  7. [7]

    Since we do this for bothρ 1 andρ 2, the com- plexity after taking both of them into considera- tion becomesO(2N t 2/ϵ)≈O(N t 2/ϵ).Here,ϵis the simulation error

    The Density Matrix Exponentiation (DME), using the LMR method, has a complexity of: O(log2(d)n) =O(N t 2/ϵ),(16) wheredis the dimension 2 N ofρ, andn=O(t 2/ϵ) is the number of copies ofρrequired to simulate eiρt. Since we do this for bothρ 1 andρ 2, the com- plexity after taking both of them into considera- tion becomesO(2N t 2/ϵ)≈O(N t 2/ϵ).Here,ϵis the ...

    work page

  8. [8]

    Since we perform Improved Quantum Phase Esti- mation (IQPE) after DME, we will have the time t=O(1/ϵ) in Eq. (16). Hence, the complexity of DME, followed by IQPE, isO(N/ϵ 3)

    work page

  9. [9]

    The complexity associated with the controlled ro- tation operation is not significant and therefore is disregarded in the overall complexity analysis

    work page

  10. [10]

    The algorithm involves another DME onχ, followed by IQPE, to estimate 5 λ

    To obtain √ρ/Tr(√ρ), we perform a post-selection, that is clearly efficient, since the probability of ob- taining|1⟩as measurement outcome is 1, given that λ= Tr( √ρ)≥Tr(ρ) = 1. The algorithm involves another DME onχ, followed by IQPE, to estimate 5 λ. The complexity of DME here isO((log 2 2)z), wherez=O(t 2 1/ϵ) is the required number of copies ofχ. Subs...

    work page

  11. [11]

    The complexity of DME here will beO(log 2(d)w) withw=O(t 2 2/ϵ), wheret 2 = 2, since there is only 1 control qubit for the controlled-Uopera- tion

    In finding out the quantity Tr √ρ1ρ2, we need the unitaryU=e it2 √ρ2/Tr√ρ2, for which we need to ex- ponentiate the state √ρ2/Tr√ρ2 obtained earlier. The complexity of DME here will beO(log 2(d)w) withw=O(t 2 2/ϵ), wheret 2 = 2, since there is only 1 control qubit for the controlled-Uopera- tion. Thus, the complexity of this DME isO(N/ϵ). Afterwards, we p...

    work page

  12. [12]

    Engineering Quantum Error Correction Codes Using Evolutionary Algorithms

    Mark Webster and Dan Browne. Engineering Quantum Error Correction Codes Using Evolutionary Algorithms. September 2024

    work page 2024

  13. [13]

    General Conditions for Approximate Quantum Error Correction and Near- Optimal Recovery Channels.Physical Review Letters, 104(12):120501, 2010

    C´ edric B´ eny and Ognyan Oreshkov. General Conditions for Approximate Quantum Error Correction and Near- Optimal Recovery Channels.Physical Review Letters, 104(12):120501, 2010

    work page 2010

  14. [14]

    Torosov and Nikolay V

    Boyan T. Torosov and Nikolay V. Vitanov. Smooth com- posite pulses for high-fidelity quantum information pro- cessing.Physical Review A, 83:053420, May 2011

    work page 2011

  15. [15]

    Reimpell and R

    M. Reimpell and R. F. Werner. Iterative optimization of quantum error correcting codes.Physical Review Letters, 94:080501, March 2005

    work page 2005

  16. [16]

    Op- timal measurements for quantum fidelity between gaus- sian states and its relevance to quantum metrology.Phys- ical Review A, 100:012323, July 2019

    Changhun Oh, Changhyoup Lee, Leonardo Banchi, Su- Yong Lee, Carsten Rockstuhl, and Hyunseok Jeong. Op- timal measurements for quantum fidelity between gaus- sian states and its relevance to quantum metrology.Phys- ical Review A, 100:012323, July 2019. 6

    work page 2019

  17. [17]

    Shahi F., Rezakhani

    A.T. Shahi F., Rezakhani. Fidelity-based supervised and unsupervised learning for binary classification of quan- tum states.The European Physical Journal Plus, 136, March 2021

    work page 2021

  18. [18]

    Figueiredo Roque T Clerk, A

    H . Figueiredo Roque T Clerk, A. A. & Ribeiro. Engi- neering fast high-fidelity quantum operations with con- strained interactions.npj Quantum Information, Febru- ary 2021

    work page 2021

  19. [19]

    R. Jozsa. Fidelity for mixed quantum states.Journal of Modern Optics, 41, 1994

    work page 1994

  20. [20]

    transition probability

    A. Uhlmann. The “transition probability” in the state space of a* -algebra.Reports on Mathematical Physics, 9:273–279, April 1976

    work page 1976

  21. [21]

    Quantum coding.Physical Re- view A, 51:2738–2747, April 1995

    Benjamin Schumacher. Quantum coding.Physical Re- view A, 51:2738–2747, April 1995

    work page 1995

  22. [22]

    M. A. Nielsen and I. L. Chuang.Quantum Computation and Quantum Information. Cambridge University Press, 2002

    work page 2002

  23. [23]

    Spin tomography

    Maccone L D ´Ariano G M and Paini M. Spin tomography. Journal of Optics B: Quantum and Semiclassical Optics, 5(1):77–84, January 2003

    work page 2003

  24. [24]

    Vogel and H

    K. Vogel and H. Risken. Determination of quasiproba- bility distributions in terms of probability distributions for the rotated quadrature phase.Physical Review A, 40:2847–2849, September 1989

    work page 1989

  25. [25]

    Quantum state tomography via compressed sensing.Physical Review Letters, 105:150401, October 2010

    Gross David, Liu Yi-Kai, Flammia Steven T, Becker Stephen, and Eisert Jens. Quantum state tomography via compressed sensing.Physical Review Letters, 105:150401, October 2010

    work page 2010

  26. [26]

    Efficient quantum tomog- raphy

    John Wright Ryan O ´Donnell. Efficient quantum tomog- raphy. InSTOC ’16: Proceedings of the forty-eighth an- nual ACM symposium on Theory of Computing, pages 899 – 912, June 2016

    work page 2016

  27. [27]

    Flammia S. et al. Cramer M., Plenio M. Efficient quan- tum state tomography.Nature Communication, Decem- ber 2010

    work page 2010

  28. [28]

    Fidelity estimation and entangle- ment verification for experimentally produced four-qubit cluster states.Physical Review A, 74:020301, August 2006

    Yuuki Tokunaga, Takashi Yamamoto, Masato Koashi, and Nobuyuki Imoto. Fidelity estimation and entangle- ment verification for experimentally produced four-qubit cluster states.Physical Review A, 74:020301, August 2006

    work page 2006

  29. [29]

    Implementation of swap test for two unknown states in photons via cross-kerr nonlineari- ties under decoherence effect.Scientific Reports, 9:6167, April 2019

    Min-Sung Kang, Jino Heo, Seong-Gon Choi, Sung Moon, and Sang-Wook Han. Implementation of swap test for two unknown states in photons via cross-kerr nonlineari- ties under decoherence effect.Scientific Reports, 9:6167, April 2019

    work page 2019

  30. [30]

    Paulo E. M. F. Mendon¸ ca, Reginaldo d. J. Napolitano, Marcelo A. Marchiolli, Christopher J. Foster, and Yeong- Cherng Liang. Alternative fidelity measure between quantum states.Physical Review A, 78:052330, Novem- ber 2008

    work page 2008

  31. [31]

    Direct fidelity esti- mation from few pauli measurements.Physical Review Letters, 106:230501, June 2011

    Flammia Steven T and Liu Yi-Kai. Direct fidelity esti- mation from few pauli measurements.Physical Review Letters, 106:230501, June 2011

    work page 2011

  32. [32]

    Practical characterization of quantum de- vices without tomography.Physical Review Letters, 107:210404, November 2011

    da Silva Marcus P, Landon-Cardinal Olivier, and Poulin David. Practical characterization of quantum de- vices without tomography.Physical Review Letters, 107:210404, November 2011

    work page 2011

  33. [33]

    Direct fidelity estima- tion for generic quantum states, December 2024

    Christopher Vairogs and Bin Yan. Direct fidelity estima- tion for generic quantum states, December 2024

    work page 2024

  34. [34]

    Variational quantum fidelity estimation

    Melody Cerezo, Alexander Poremba, Lukasz Cincio, and Patrick Coles. Variational quantum fidelity estimation. Quantum, 4:248, March 2020

    work page 2020

  35. [35]

    Quantum Algorithm for Fidelity Estimation.IEEE Transactions on Information Theory, 69(1):273–282, January 2023

    Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, and Mingsheng Ying. Quantum Algorithm for Fidelity Estimation.IEEE Transactions on Information Theory, 69(1):273–282, January 2023

    work page 2023

  36. [36]

    Baldwin and Jonathan A

    Andrew J. Baldwin and Jonathan A. Jones. Efficiently computing the uhlmann fidelity for density matrices. Physical Review A, 107:012427, January 2023

    work page 2023

  37. [37]

    Lloyd, M

    S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum prin- cipal component analysis.Nature Physics, 10:631–633, July 2014

    work page 2014

  38. [38]

    A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. 11 1995

    work page 1995

  39. [39]

    A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum al- gorithm for linear systems of equations.Physical Review Letters, 103(15):150502, 2009

    work page 2009

  40. [40]

    Sj¨ oqvist, A

    E. Sj¨ oqvist, A. K. Pati, A. Ekert, J. S. Anandan, M. Er- icsson, D. K. L. Oi, and V. Vedral. Geometric phases for mixed states in interferometry.Physical Review Letters, 85:2845–2849, October 2000

    work page 2000

  41. [41]

    Entanglement meter: estimation of entanglement with single copy in interferometer.New Journal of Physics, 25(4):043026, September 2023

    Som Kanjilal, Vivek Pandey, and Arun Kumar Pati. Entanglement meter: estimation of entanglement with single copy in interferometer.New Journal of Physics, 25(4):043026, September 2023

    work page 2023

  42. [42]

    Kjaergaard, M

    M. Kjaergaard, M. E. Schwartz, A. Greene, G. O. Samach, A. Bengtsson, M. O’Keeffe, et al. Demon- stration of density matrix exponentiation using a su- perconducting quantum processor.Physical Review X, 12(1):011005, January 2022

    work page 2022

  43. [43]

    D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. Ef- ficient quantum algorithms for simulating sparse Hamil- tonians.Communications in Mathematical Physics, 270:359–371, December 2006

    work page 2006

  44. [44]

    Kimmel, C

    S. Kimmel, C. Y-Y. Lin, G. H. Low, M. Ozols, and T. J. Yoder. Hamiltonian simulation with optimal sample com- plexity.npj Quantum Information, 3(13), March 2017

    work page 2017