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:2611.01163

On Estimating Quantum Divergences with ppp-Power Means

Jinge Bao, Minbo Gao, Qisheng Wang

quant-phSubmitted Oct 31, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

Abstract

We study the problem of estimating the quantum divergence with $p$-power means, $Φ_p(ρ\,\|\,σ)$. This quantity was investigated by Lam and Le (\textit{Linear Algebra Appl.}\ 2021). For any constant $p \in (0, 1)$, we present sample-efficient and query-efficient quantum algorithms for estimating $Φ_p(ρ\,\|\,σ)$ and further show that estimating $Φ_p(ρ\,\|\,σ)$ is $\mathsf{BQP}$-complete in the low-rank case.

AI Summary

The paper studies estimation of the symmetric quantum divergence $\Phi_p(\rho\|\sigma)=1-\operatorname{tr}[((\rho^p+\sigma^p)/2)^{1/p}]$ for fixed, polynomial-time computable $p\in(0,1)$. It seeks resource bounds independent of Hilbert-space dimension when both input states have rank at most a known bound $r$, considering both purified quantum query access and access to independent copies. For additive error $\varepsilon$ and success probability at least $2/3$, the query complexity is $\widetilde O(r^{3/p}\varepsilon^{-(1+2/p)})$ when $1/p$ is an even integer, and $\widetilde O(r^{2p+3/p}\varepsilon^{-(2p+1+2/p)})$ otherwise. Corresponding sample bounds are $\widetilde O(r^{6/p}\varepsilon^{-(3+4/p)})$ and $\widetilde O(r^{4p+6/p}\varepsilon^{-(4p+3+4/p)})$. For $n$-qubit inputs, the sample algorithm’s gate bounds acquire an additional factor of $n$. The algorithms combine nested QSVT approximations to matrix powers, an approximate support-projector construction, and trace estimation. The sample algorithm uses quantum sample-to-query simulation. Error analysis includes a rank-dependent operator-norm bound for differences of positive matrix powers. For circuit-described states of polynomial rank, the paper also establishes $\mathsf{BQP}$-completeness of divergence threshold testing with inverse-polynomial promise gaps under specified threshold conditions. Hardness already holds for pure states, through comparison with squared trace distance. The guarantees assume a known rank bound and fixed interior $p$; they do not cover the endpoint divergences. Practical applications remain a direction for future work, with quantum Boltzmann machine learning mentioned as a possibility.

Little sign of AI-generated textAI use disclosedIncremental
the authors used OpenAI Codex to assist with language editing, notation consistency checks, LaTeX debugging, and the review and revision of mathematical arguments.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
32 pages, 2 algorithms

Related papers

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm 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 ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, 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 ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf 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 $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905•Leibniz international proceedings in informatics•Jul 7, 2026•1 citation

Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu

We investigate the computational hardness of estimating the quantum $α$-Rényi entropy ${\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}$ and the quantum $q$-Tsallis entropy ${\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}$, 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 (TsallisQEA$_q$) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or ${\rm S}^{\tt T}_q(ρ)$, 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 $α=\infty$, the rank-$2$ variants Rank2RényiQEA$_α$ and Rank2TsallisQEA$_q$ 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 $α=\infty$, and for all real orders $0 < q \leq 1$, LowRankRényiQEA$_α$ and LowRankTsallisQEA$_q$ are BQP-complete, where both are restricted versions of RényiQEA$_α$ and TsallisQEA$_q$ with $ρ$ of polynomial rank. - For all real order $q>1$, TsallisQEA$_q$ 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.

quant-pharXiv:2601.03734•Leibniz international proceedings in informatics•Jan 8, 2026•1 citation

Time-Efficient Quantum Entropy Estimator via Samplizer

Qisheng Wang, Zhicheng Zhang

Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(ρ)$ and Rényi entropy $S_α(ρ)$ of an $N$-dimensional quantum state $ρ$, given access to independent samples of $ρ$. Specifically, we provide the following: 1. A quantum estimator for $S(ρ)$ with time complexity $\tilde O(N^2)$, improving the prior best time complexity $\tilde O(N^6)$ by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for $S_α(ρ)$ with time complexity $\tilde O(N^{4/α-2})$ for $0<α<1$ and $\tilde O(N^{4-2/α})$ for $α>1$, improving the prior best time complexity $\tilde O(N^{6/α})$ for $0<α<1$ and $\tilde O(N^6)$ for $α>1$ by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound for estimating $S_α(ρ)$. Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle $U$ block-encodes a mixed quantum state $ρ$, any quantum query algorithm using $Q$ queries to $U$ can be samplized to a $δ$-close (in the diamond norm) quantum algorithm using $\tildeΘ(Q^2/δ)$ samples of $ρ$. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.

arXiv:2401.09947•Leibniz international proceedings in informatics•Jan 1, 2024•15 citations

Quantum Algorithms for Computing Maximal Quantum $f$-divergence and Kubo-Ando means

Trung Hoa Dinh, Nhat A. Nghiem

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.

quant-pharXiv:2511.10607•Quantum Information Processing•Nov 14, 2025•0 citations

Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform

Yupan Liu, Qisheng Wang

The Uhlmann fidelity ${\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_1}|$ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error $\varepsilon$ requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of $ρ_0$ and $ρ_1$. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on $1/\varepsilon$. However, the known optimal estimator for ${\rm F}(ρ,|ψ\rangle\!\langleψ|)$ due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for ${\rm F}(ρ, |ψ\rangle\!\langleψ|)$ under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of ${\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|ψ_1\rangle$ (or $|ψ_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.

quant-pharXiv:2608.10674•Aug 12, 2026•2 citations

A Note on Quantum Phase Estimation

Yao-Ting Lin

In this work, we study the phase estimation problem. We show an alternative, simpler and self-contained proof of query lower bounds. Technically, compared to the previous proofs [NW99, Bes05], our proof is considerably elementary. Specifically, our proof consists of basic linear algebra without using the knowledge of Boolean function analysis and adversary methods. Qualitatively, our bound is tight in the low success probability regime and offers a more fine-grained trade-off. In particular, we prove that for any $ε> 0, p \geq 0$, every algorithm requires at least $Ω(p/ε)$ queries to obtain an $ε$-approximation for the phase with probability at least p. However, the existing bounds hold only when $p > 1/2$. Quantitatively, our bound is tight since it matches the well-known phase estimation algorithm of Cleve, Ekert, Macchiavello, and Mosca [CEMM98] which requires $O(1/ε)$ queries to obtain an $ε$-approximation with a constant probability. Following the derivation of the lower bound in our framework, we give a new and intuitive interpretation of the phase estimation algorithm of [CEMM98], which might be of independent interest.

arXiv:2304.02241•Apr 5, 2023•3 citations
We study the problem of estimating the quantum divergence with ppp-power means, Φp(ρ ∥ σ)Φ_p(ρ\,\|\,σ)Φp​(ρ∥σ). This quantity was investigated by Lam and Le (\textit{Linear Algebra Appl.}\ 2021). For any constant p∈(0,1)p \in (0, 1)p∈(0,1), we present sample-efficient and query-efficient quantum algorithms for estimating Φp(ρ ∥ σ)Φ_p(ρ\,\|\,σ)Φp​(ρ∥σ) and further show that estimating Φp(ρ ∥ σ)Φ_p(ρ\,\|\,σ)Φp​(ρ∥σ) is BQP\mathsf{BQP}BQP-complete in the low-rank case.
The paper studies estimation of the symmetric quantum divergence Φp(ρ∥σ)=1−tr⁡[((ρp+σp)/2)1/p]\Phi_p(\rho\|\sigma)=1-\operatorname{tr}[((\rho^p+\sigma^p)/2)^{1/p}]Φp​(ρ∥σ)=1−tr[((ρp+σp)/2)1/p] for fixed, polynomial-time computable p∈(0,1)p\in(0,1)p∈(0,1). It seeks resource bounds independent of Hilbert-space dimension when both input states have rank at most a known bound rrr, considering both purified quantum query access and access to independent copies.
For additive error ε\varepsilonε and success probability at least 2/32/32/3, the query complexity is O~(r3/pε−(1+2/p))\widetilde O(r^{3/p}\varepsilon^{-(1+2/p)})O(r3/pε−(1+2/p)) when 1/p1/p1/p is an even integer, and O~(r2p+3/pε−(2p+1+2/p))\widetilde O(r^{2p+3/p}\varepsilon^{-(2p+1+2/p)})O(r2p+3/pε−(2p+1+2/p)) otherwise. Corresponding sample bounds are O~(r6/pε−(3+4/p))\widetilde O(r^{6/p}\varepsilon^{-(3+4/p)})O(r6/pε−(3+4/p)) and O~(r4p+6/pε−(4p+3+4/p))\widetilde O(r^{4p+6/p}\varepsilon^{-(4p+3+4/p)})O(r4p+6/pε−(4p+3+4/p)). For nnn-qubit inputs, the sample algorithm’s gate bounds acquire an additional factor of nnn.
The algorithms combine nested QSVT approximations to matrix powers, an approximate support-projector construction, and trace estimation. The sample algorithm uses quantum sample-to-query simulation. Error analysis includes a rank-dependent operator-norm bound for differences of positive matrix powers.
For circuit-described states of polynomial rank, the paper also establishes BQP\mathsf{BQP}BQP-completeness of divergence threshold testing with inverse-polynomial promise gaps under specified threshold conditions. Hardness already holds for pure states, through comparison with squared trace distance.
The guarantees assume a known rank bound and fixed interior ppp; they do not cover the endpoint divergences. Practical applications remain a direction for future work, with quantum Boltzmann machine learning mentioned as a possibility.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1){\rm T}_{\infty}(ρ_0,ρ_1)T∞​(ρ0​,ρ1​), defined via the operator norm ∥A∥∞=σmax⁡(A)\|A\|_{\infty} = σ_{\max}(A)∥A∥∞​=σmax​(A), given poly(n){\rm poly}(n)poly(n)-size state-preparation circuits of nnn-qubit quantum states ρ0ρ_0ρ0​ and ρ1ρ_1ρ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/ε)Θ(1/ε)Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5ε=1/5ε=1/5, our estimator runs in poly(n){\rm poly}(n)poly(n) time. Since the operator norm distance T∞(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)T∞​(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}(|ψ\rangle\!\langleψ|,ρ)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(ρ){\rm rank}(ρ)rank(ρ), which can be exp⁡(n)\exp(n)exp(n) in general. 2. For general quantum states, we also provide a quantum estimator using O~(1/ε3/2)\widetilde{O}(1/ε^{3/2})O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP{\sf BQP}BQP-complete and improves the QMA{\sf QMA}QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε)Ω(1/ε)Ω(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 ∣ψ⟩|ψ\rangle∣ψ⟩ has overlap at least 1/21/21/2 with the top unit eigenvector of ∣ψ⟩ ⁣⟨ψ∣−ρ|ψ\rangle\!\langleψ|-ρ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
We investigate the computational hardness of estimating the quantum ααα-Rényi entropy SαR(ρ)=ln⁡Tr(ρα)1−α{\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}SαR​(ρ)=1−αlnTr(ρα)​ and the quantum qqq-Tsallis entropy SqT(ρ)=1−Tr(ρq)q−1{\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}SqT​(ρ)=q−11−Tr(ρq)​, both of which converge to the von Neumann entropy as the order approaches 111. The promise problems Quantum ααα-Rényi Entropy Approximation (RényiQEAα_αα​) and Quantum qqq-Tsallis Entropy Approximation (TsallisQEAq_qq​) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or SqT(ρ){\rm S}^{\tt T}_q(ρ)SqT​(ρ), is at least τ1τ_1τ1​ or at most τ2τ_2τ2​, where τ1−τ2τ_1 - τ_2τ1​−τ2​ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 111) and some cases of the quantum qqq-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real ααα and qqq, and also for α=∞α=\inftyα=∞, the rank-222 variants Rank2RényiQEAα_αα​ and Rank2TsallisQEAq_qq​ 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α> 0α>0 or α=∞α=\inftyα=∞, and for all real orders 0<q≤10 < q \leq 10<q≤1, LowRankRényiQEAα_αα​ and LowRankTsallisQEAq_qq​ are BQP-complete, where both are restricted versions of RényiQEAα_αα​ and TsallisQEAq_qq​ with ρρρ of polynomial rank. - For all real order q>1q>1q>1, TsallisQEAq_qq​ is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the ααα-Rényi or qqq-Tsallis binary entropies of different orders. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ)S(ρ)S(ρ) and Rényi entropy Sα(ρ)S_α(ρ)Sα​(ρ) of an NNN-dimensional quantum state ρρρ, given access to independent samples of ρρρ. Specifically, we provide the following: 1. A quantum estimator for S(ρ)S(ρ)S(ρ) with time complexity O~(N2)\tilde O(N^2)O~(N2), improving the prior best time complexity O~(N6)\tilde O(N^6)O~(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for Sα(ρ)S_α(ρ)Sα​(ρ) with time complexity O~(N4/α−2)\tilde O(N^{4/α-2})O~(N4/α−2) for 0<α<10<α<10<α<1 and O~(N4−2/α)\tilde O(N^{4-2/α})O~(N4−2/α) for α>1α>1α>1, improving the prior best time complexity O~(N6/α)\tilde O(N^{6/α})O~(N6/α) for 0<α<10<α<10<α<1 and O~(N6)\tilde O(N^6)O~(N6) for α>1α>1α>1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound for estimating Sα(ρ)S_α(ρ)Sα​(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle UUU block-encodes a mixed quantum state ρρρ, any quantum query algorithm using QQQ queries to UUU can be samplized to a δδδ-close (in the diamond norm) quantum algorithm using Θ~(Q2/δ)\tildeΘ(Q^2/δ)Θ~(Q2/δ) samples of ρρρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
Quantum Algorithms for Computing Maximal Quantum fff-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 fff-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.
The Uhlmann fidelity F(ρ0,ρ1)=tr∣ρ0ρ1∣{\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_1}|F(ρ0​,ρ1​)=tr∣ρ0​​ρ1​​∣ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error ε\varepsilonε requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of ρ0ρ_0ρ0​ and ρ1ρ_1ρ1​. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on 1/ε1/\varepsilon1/ε. However, the known optimal estimator for F(ρ,∣ψ⟩ ⁣⟨ψ∣){\rm F}(ρ,|ψ\rangle\!\langleψ|)F(ρ,∣ψ⟩⟨ψ∣) due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for F(ρ,∣ψ⟩ ⁣⟨ψ∣){\rm F}(ρ, |ψ\rangle\!\langleψ|)F(ρ,∣ψ⟩⟨ψ∣) under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of trA(∣ψ0⟩ ⁣⟨ψ1∣){\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)trA​(∣ψ0​⟩⟨ψ1​∣) (or its inverse) to the reference register R\sf RR of the purification ∣ψ1⟩|ψ_1\rangle∣ψ1​⟩ (or ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩) on the registers A\sf AA and R\sf RR, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.
In this work, we study the phase estimation problem. We show an alternative, simpler and self-contained proof of query lower bounds. Technically, compared to the previous proofs [NW99, Bes05], our proof is considerably elementary. Specifically, our proof consists of basic linear algebra without using the knowledge of Boolean function analysis and adversary methods. Qualitatively, our bound is tight in the low success probability regime and offers a more fine-grained trade-off. In particular, we prove that for any ε>0,p≥0ε> 0, p \geq 0ε>0,p≥0, every algorithm requires at least Ω(p/ε)Ω(p/ε)Ω(p/ε) queries to obtain an εεε-approximation for the phase with probability at least p. However, the existing bounds hold only when p>1/2p > 1/2p>1/2. Quantitatively, our bound is tight since it matches the well-known phase estimation algorithm of Cleve, Ekert, Macchiavello, and Mosca [CEMM98] which requires O(1/ε)O(1/ε)O(1/ε) queries to obtain an εεε-approximation with a constant probability. Following the derivation of the lower bound in our framework, we give a new and intuitive interpretation of the phase estimation algorithm of [CEMM98], which might be of independent interest.