Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Fang, Wang; Wang, Qisheng

doi:10.4230/LIPIcs.ESA.2025.4

Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Wang Fang

School of Informatics, University of Edinburgh, UK Qisheng Wang

School of Informatics, University of Edinburgh, UK

Abstract

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 $\varepsilon$ by using $\Theta\lparen 1/\varepsilon\rparen$ queries to their state-preparation circuits, achieving a quadratic speedup over the folklore $O\lparen 1/\varepsilon^{2}\rparen$ . Our approach is technically simple, and can moreover estimate the quantity $\sqrt{\operatorname{tr}(\rho\sigma^{2})}$ 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.

Keywords and phrases:

Quantum computing, fidelity estimation, quantum algorithms, quantum query complexity

Funding:

Wang Fang: Supported by the Engineering and Physical Sciences Research Council under Grant EP/X025551/1.

Qisheng Wang: Supported by the Engineering and Physical Sciences Research Council under Grant EP/X026167/1.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum query complexity ; Theory of computation

\rightarrow

Quantum information theory

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The fidelity between quantum states [24, 13] is a closeness measure that is commonly used in quantum physics and quantum computing [20, 34, 12, 33]. Formally, for two (mixed) quantum states $\rho$ and $\sigma$ , their (square root) fidelity is defined by (see [20, Equation (9.53)])

\mathrm{F}\lparen\rho,\sigma\rparen=\operatorname{tr}\left\lparen\sqrt{\sqrt{% \sigma}\rho\sqrt{\sigma}}\right\rparen.

The fidelity is generally bounded by $0\leq\mathrm{F}\lparen\rho,\sigma\rparen\leq 1$ . In particular, when $\mathrm{F}\lparen\rho,\sigma\rparen=1$ , the two states $\rho$ and $\sigma$ are identical; and when $\mathrm{F}\lparen\rho,\sigma\rparen=0$ , the two states are orthogonal.

The estimation of fidelity turns out to be central in quantum property testing (cf. [18]). The earliest approach is now known as the SWAP test [5], allowing us to estimate to within additive error $\varepsilon$ the squared fidelity $\mathrm{F}^{2}\lparen\rho,\sigma\rparen=\operatorname{tr}\lparen\rho\sigma\rparen$ when $\rho$ and $\sigma$ are pure states, using $O\lparen 1/\varepsilon^{2}\rparen$ samples of $\rho$ and $\sigma$ . Moreover, the squared fidelity $\mathrm{F}^{2}\lparen\rho,\sigma\rparen$ for pure states $\rho$ and $\sigma$ can be estimated using $O\lparen 1/\varepsilon\rparen$ queries to their state-preparation circuits through the SWAP test [5] equipped with quantum amplitude estimation [4]. The approach based on the SWAP test has been found to have various applications [21]. Fidelity estimation for pure states was also considered in some restricted models: a direct fidelity estimation [7] was proposed when only Pauli measurements are allowed and a distributed approach was developed in [1]. Recently, query-optimal and sample-optimal quantum algorithms for estimating the fidelity $\mathrm{F}\lparen\rho,\sigma\rparen=\sqrt{\operatorname{tr}\lparen\rho\sigma\rparen}$ for pure states $\rho$ and $\sigma$ have been found in [25] and [28], respectively.

Although fidelity estimation is known to be $\mathsf{BQP}$ -complete when one of the quantum states is pure [22], fidelity estimation for mixed states is $\mathsf{QSZK}$ -hard in general [31, 32], which means that there is no polynomial-time quantum algorithm for fidelity estimation unless $\mathsf{BQP}=\mathsf{QSZK}$ . Nevertheless, efficient quantum algorithms for fidelity estimation for low-rank states were recently discovered [29] and later improved [26, 10] with time complexity $\operatorname{poly}\lparen r,1/\varepsilon\rparen$ , where $r$ is the rank of the states. Quantum algorithms for fidelity estimation for well-conditioned states was recently proposed with query complexity $\operatorname{poly}\lparen\kappa\rparen\cdot\widetilde{O}\lparen 1/\varepsilon\rparen$ [15], achieving almost optimal dependence on the precision $\varepsilon$ , where $\kappa$ is the condition number such that $\rho,\sigma\geq I/\kappa$ .

In this paper, we present an optimal quantum algorithm for estimating the fidelity of a mixed state $\rho$ to a pure state $\sigma=\lvert\psi\rangle\!\langle\psi\rvert$ , using queries to the state-preparation circuits of both states. The input model is known as the “purified quantum query access” model, where we assume query access to (the controlled version of) a quantum unitary oracle that prepares the purification of the input quantum state, and its inverse. This input model is commonly employed in quantum computational complexity [31] and quantum algorithms [8]. Our main result is stated in the following theorem.

Theorem 1 (Estimating fidelity to a pure state, Theorem 6 simplified).

Given purified quantum query access to a mixed state $\rho$ and a pure state $\sigma=\lvert\psi\rangle\!\langle\psi\rvert$ , the fidelity $\mathrm{F}\lparen\rho,\sigma\rparen=\sqrt{\langle\psi\rvert\rho\lvert\psi\rangle}$ can be estimated to within additive error $\varepsilon$ with query complexity $O\lparen 1/\varepsilon\rparen$ .

Prior to the result of Theorem 1, we are only aware of a folklore quantum algorithm based on the SWAP test (which was mentioned above and will be explained in detail in Section 3.1). This folklore approach computes $\mathrm{F}^{2}\lparen\rho,\sigma\rparen=\langle\psi\rvert\rho\lvert\psi\rangle$ to within additive error $\varepsilon$ with query complexity $O(1/\varepsilon)$ , thereby resulting in a query complexity of $O(1/\varepsilon^{2})$ for estimating $\mathrm{F}\lparen\lvert\psi\rangle,\rho\rparen$ to within additive error $\varepsilon$ . By comparison, Theorem 1 exhibits a quadratic improvement.

The quantum query algorithm given in Theorem 1 generalizes the pure-state fidelity estimation in [25] where unitary oracles are required to directly prepare the pure states. In comparison, our result in Theorem 1 allows the unitary oracles to have redundant output qubits (see Section 5 for more details).

Our approach is actually optimal, as it can be used to estimate the fidelity between two pure states and the quantum query lower bound $\Omega\lparen 1/\varepsilon\rparen$ is due to [2, 19] (noted in [25]). In Section 6, we further show that the optimality holds even if $\rho$ is of an arbitrary rank.

We compare fidelity estimations for pure states in Table 1.

Table 1: Complexity of estimating the fidelity

\mathrm{F}\lparen\rho,\sigma\rparen

.

Reference	Condition	Complexity	Notes
[5]	One of $\rho$ and $\sigma$ is pure	$O\lparen 1/\varepsilon^{4}\rparen$ samples	/
[5, 4]		$O\lparen 1/\varepsilon^{2}\rparen$ queries	/
This Work		$\bm{\Theta(1/\varepsilon)}$ queries	Optimal
[25]	Both $\rho$ and $\sigma$ are pure	$\Theta\lparen 1/\varepsilon\rparen$ queries	Optimal
[28]	Both $\rho$ and $\sigma$ are pure	$\Theta\lparen 1/\varepsilon^{2}\rparen$ samples	Optimal
[29, 26, 10]	Either $\rho$ or $\sigma$ is of rank $r$	$\operatorname{poly}\lparen r,1/\varepsilon\rparen$ queries	/
[10]	Either $\rho$ or $\sigma$ is of rank $r$	$\operatorname{poly}\lparen r,1/\varepsilon\rparen$ samples	/
[15]	$\rho,\sigma\geq I/\kappa$	$\operatorname{poly}\lparen\kappa\rparen\cdot\widetilde{\Theta}\lparen 1/\varepsilon\rparen$ queries	Almost optimal in $\varepsilon$
[15]	$\rho,\sigma\geq I/\kappa$	$\operatorname{poly}\lparen\kappa,1/\varepsilon\rparen$ samples	/

As a bonus, our approach in Theorem 1 can further estimate the quantity $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ with optimal query complexity (see Section 4.2), which is of independent interest as this quantity is not common in the literature.

Organization of this paper.

We give a formal definition of the purified quantum query access model and the problem statement of fidelity estimation in Section 2. Then, we review previous approaches in Section 3 with their subroutines. In Section 4, we present our approach and its generalization. An implication of our results is discussed in Section 5. Lower bounds for fidelity estimation are given in Section 6. Finally, a brief discussion is drawn in Section 7.

2 Problem Settings

In this paper, we assume purified quantum query access to the input quantum states. This input model is widely used in the literature, e.g., [8, 23, 11, 10, 30, 27, 16].

Definition 2 (Purified quantum query access).

For a mixed quantum state $\rho$ , purified quantum query access to $\rho$ means query access to a unitary oracle $U$ that prepares a purification of $\rho$ . Specifically, suppose $U_{\mathsf{A}\mathsf{B}}$ acts on two subsystems $\mathsf{A}$ and $\mathsf{B}$ , then $\rho_{\mathsf{A}}=\operatorname{tr}_{\mathsf{B}}\lparen\lvert\rho\rangle\!% \langle\rho\rvert_{\mathsf{A}\mathsf{B}}\rparen$ , where $\lvert\rho\rangle_{\mathsf{A}\mathsf{B}}=U_{\mathsf{A}\mathsf{B}}\lvert 0% \rangle_{\mathsf{A}\mathsf{B}}$ . Moreover, we are allowed to use queries to (controlled-) $U$ and its inverse.

We consider the problem of fidelity estimation, formally stated as follows.

Problem 1 (Fidelity estimation).

Given purified quantum query access to two mixed quantum states $\rho$ and $\sigma$ , the task is to compute $\mathrm{F}\lparen\rho,\sigma\rparen$ to within additive error $\varepsilon$ .

In particular, this paper focuses on the case of Problem 1 where $\sigma=\lvert\psi\rangle\!\langle\psi\rvert$ is pure.

3 Warm-Ups

As a warm-up, we review the previous approaches to fidelity estimation involving pure states, together with their useful subroutines.

3.1 SWAP Test

It is well known that the SWAP test [5] can be used to estimate the fidelity $\mathrm{F}\lparen\rho,\sigma\rparen$ when one of $\rho$ and $\sigma$ is pure. In particular, if $\sigma=\lvert\psi\rangle\!\langle\psi\rvert$ is pure, the SWAP test on input $\rho$ and $\sigma$ (see Figure 1) outputs a bit $x\in\{0,1\}$ such that (adapted from [14, Proposition 9])

\Pr[x=0]=\frac{1+\mathrm{F}^{2}\lparen\rho,\lvert\psi\rangle\rparen}{2}.

(1)

With this, we can estimate $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ . Specifically, suppose that $\tilde{p}$ is an estimate of $\Pr[x=0]$ such that $\lvert\tilde{p}-\Pr[x=0]\rvert\leq\delta$ . Then, it can be shown that $\sqrt{2\tilde{p}-1}$ is an estimate of $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ with $\lvert\sqrt{2\tilde{p}-1}-\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen\rvert% \leq\Theta\lparen\sqrt{\delta}\rparen$ . An estimate of $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ can be obtained by setting $\delta=\Theta\lparen\varepsilon^{2}\rparen$ .

Figure 1: The SWAP test for estimating

\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen

.

To estimate $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ when given purified quantum query access to $\rho$ and $\lvert\psi\rangle$ , we need the quantum subroutine for amplitude estimation [4].

Theorem 3 (Quantum amplitude estimation, [4]).

Suppose that $U$ is a unitary operator such that $U\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}=\sqrt{p}\lvert 0% \rangle_{\mathsf{A}}\lvert\varphi_{0}\rangle_{\mathsf{B}}+\sqrt{1-p}\lvert 1% \rangle_{\mathsf{A}}\lvert\varphi_{1}\rangle_{\mathsf{B}}$ , where $p\in[0,1]$ and $\lvert\varphi_{0}\rangle,\lvert\varphi_{1}\rangle$ are normalized pure states. Then, we can estimate $p$ to within additive error $\delta$ using $O\lparen 1/\delta\rparen$ queries to (controlled-) $U$ and its inverse.

By Theorem 3, we can therefore obtain an estimate of $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ using $O\lparen 1/\varepsilon^{2}\rparen$ queries to the state-preparation circuits of $\rho$ and $\lvert\psi\rangle$ , based on the SWAP test in Figure 1.

3.2 Pure-State Fidelity Estimation

Recently, a new approach was proposed in [25] for estimating the fidelity $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ between two pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , improving the folklore approach in Section 3.1. However, the approach in [25] assumes a slightly more restricted input model, where $U_{{\varphi}}$ and $U_{{\psi}}$ are two unitary quantum circuits that respectively prepare $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , i.e., $U_{{\varphi}}\lvert 0\rangle=\lvert\varphi\rangle$ and $U_{{\psi}}\lvert 0\rangle=\lvert\psi\rangle$ .

The key idea of [25] is to encode the value of $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ in the amplitudes of a quantum state, rather than the $\sqrt{\lparen 1+\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle% \rparen\rparen/{2}}$ (in Equation 1). Specifically, $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ can be encoded by the unitary operator $W=U_{\varphi}^{\dagger}U_{\psi}$ such that

W\lvert 0\rangle=\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle% \rparen\lvert 0\rangle+\lvert\perp\rangle,

(2)

where $\lvert\perp\rangle$ is an (unnormalized) pure state that is orthogonal to $\lvert 0\rangle$ . The circuit $W$ is depicted in Figure 2 and it outputs a bit $x\in\{0,1\}$ such that

\Pr[x=0]=\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen.

(3)

Figure 2: The quantum circuit for estimating

\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen

.

Finally, the value of $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ can be estimated by the square root amplitude estimation provided in [25].

Theorem 4 (Quantum square root amplitude estimation, [25, Theorem I.5]).

Suppose that $U$ is a unitary operator such that $U\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}=\sqrt{p}\lvert 0% \rangle_{\mathsf{A}}\lvert\varphi_{0}\rangle_{\mathsf{B}}+\sqrt{1-p}\lvert 1% \rangle_{\mathsf{A}}\lvert\varphi_{1}\rangle_{\mathsf{B}}$ , where $p\in[0,1]$ and $\lvert\varphi_{0}\rangle,\lvert\varphi_{1}\rangle$ are normalized pure states. Then, we can estimate $\sqrt{p}$ to within additive error $\delta$ using $O\lparen 1/\delta\rparen$ queries to (controlled-) $U$ and its inverse.

For convenience, throughout this paper, we use $\mathsf{SqrtAmpEst}\lparen U,\varepsilon\rparen$ to denote (the returned value of) the square root amplitude estimation process.

Compared to Theorem 3, Theorem 4 gives an estimate of $\sqrt{p}$ (instead of $p$ ), thereby allowing us to skip taking square roots. By Theorem 4, we can therefore obtain an estimate of $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ using $O\lparen 1/\varepsilon\rparen$ queries to the state-preparation circuits of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , based on the construction of $W$ in Equation 2.

4 Our Approach

For the task of estimating the fidelity $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ of a mixed state to a pure state, the approach in Section 3.1 only gives a query complexity of $O\lparen 1/\varepsilon^{2}\rparen$ , while the approach in Section 3.2, however, turns out not to be applicable (as a more restricted input model is assumed). In this section, we present a simple quantum algorithm that estimates $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ using $O\lparen 1/\varepsilon\rparen$ queries to the state-preparation circuits of $\rho$ and $\lvert\psi\rangle$ .

Suppose that the purified quantum query access to $\rho$ and $\lvert\psi\rangle$ is given by two quantum circuits $U$ and $V$ , respectively:

	$\displaystyle U_{\mathsf{AB}}\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{% \mathsf{B}}$	$\displaystyle=\lvert\rho\rangle_{\mathsf{AB}},$		(4)
	$\displaystyle V_{\mathsf{A^{\prime}B^{\prime}}}\lvert 0\rangle_{\mathsf{A^{% \prime}}}\lvert 0\rangle_{\mathsf{B^{\prime}}}$	$\displaystyle=\lvert\psi\rangle_{\mathsf{A^{\prime}}}\lvert\psi^{\prime}% \rangle_{\mathsf{B^{\prime}}},$		(5)

where $\rho_{\mathsf{A}}=\operatorname{tr}_{\mathsf{B}}\lparen\lvert\rho\rangle\!% \langle\rho\rvert_{\mathsf{AB}}\rparen$ and $\lvert\psi^{\prime}\rangle_{\mathsf{B^{\prime}}}$ is any pure state. Here, $\mathsf{A}$ , $\mathsf{B}$ , $\mathsf{A^{\prime}}$ , and $\mathsf{B^{\prime}}$ are subscripts of subsystems for clarity, where the subsystems $\mathsf{A}$ and $\mathsf{A^{\prime}}$ have the same dimension. Without loss of generality, we can also assume that the subsystems $\mathsf{B}$ and $\mathsf{B^{\prime}}$ have the same dimension.¹¹1If the subsystem $\mathsf{B}$ has a larger dimension than $\mathsf{B^{\prime}}$ , then $V_{\mathsf{A^{\prime}B^{\prime}}}\otimes I_{\mathsf{C}}$ (for certain subsystem $\mathsf{C}$ ) can be a purified quantum query oracle for $\lvert\psi\rangle$ with the ancilla system $\mathsf{B^{\prime}C}$ having the same dimension as $\mathsf{B}$ . A similar construction also applies to the case that the subsystem $\mathsf{B^{\prime}}$ has a larger dimension than $\mathsf{B}$ .

4.1 Fidelity to a Pure State

Our idea is to encode $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ in the amplitudes of an efficiently preparable quantum state, and then take use of the square root amplitude estimation in Theorem 4. To this end, we present a quantum circuit

W=\lparen V_{\mathsf{AB}}^{\dagger}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}% \rparen\cdot\mathsf{SWAP}_{\mathsf{BB^{\prime}}}\cdot\lparen U_{\mathsf{AB}}% \otimes V_{\mathsf{A^{\prime}B^{\prime}}}\rparen.

(6)

This circuit is depicted in Figure 3 and it outputs two bits $x_{\mathsf{A}},x_{\mathsf{B}}\in\{0,1\}$ such that

\Pr[x_{\mathsf{A}}=x_{\mathsf{B}}=0]=\mathrm{F}^{2}\lparen\rho,\lvert\psi% \rangle\rparen.

(7)

Equation 7 is comparable to Equation 1 for the SWAP test and Equation 3 for the pure-state fidelity estimation, and it can be verified by the following proposition.

Figure 3: The encoding unitary operator

W

for

\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen

.

Proposition 5.

$\left\lVert\left\lparen\langle 0\rvert_{\mathsf{A}}\langle 0\rvert_{\mathsf{B}% }\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen W\lvert 0\rangle_{% \mathsf{A}}\lvert 0\rangle_{\mathsf{B}}\lvert 0\rangle_{\mathsf{A^{\prime}}}% \lvert 0\rangle_{\mathsf{B^{\prime}}}\right\rVert^{2}=\mathrm{F}^{2}\lparen% \rho,\lvert\psi\rangle\rparen$ , where $W$ is defined by Equation 6, $U_{\mathsf{AB}}$ is defined by Equation 4, and $V_{\mathsf{A}^{\prime}\mathsf{B}^{\prime}}$ is defined by Equation 5.

Proof.

This can be shown by direct calculations.

		$\displaystyle\left\lVert\left\lparen\langle 0\rvert_{\mathsf{A}}\langle 0% \rvert_{\mathsf{B}}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen W% \lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}\lvert 0\rangle_{% \mathsf{A^{\prime}}}\lvert 0\rangle_{\mathsf{B^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\left\lVert\left\lparen\langle 0\rvert_{\mathsf{A}}\langle 0% \rvert_{\mathsf{B}}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen% \lparen V_{\mathsf{AB}}^{\dagger}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}% \rparen\cdot\mathsf{SWAP}_{\mathsf{BB^{\prime}}}\cdot\lparen U_{\mathsf{AB}}% \otimes V_{\mathsf{A^{\prime}B^{\prime}}}\rparen\lvert 0\rangle_{\mathsf{A}}% \lvert 0\rangle_{\mathsf{B}}\lvert 0\rangle_{\mathsf{A^{\prime}}}\lvert 0% \rangle_{\mathsf{B^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\left\lVert\left\lparen\langle\psi\rvert_{\mathsf{A}}\langle\psi^% {\prime}\rvert_{\mathsf{B}}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right% \rparen\cdot\mathsf{SWAP}_{\mathsf{BB^{\prime}}}\cdot\lvert\rho\rangle_{% \mathsf{AB}}\lvert\psi\rangle_{\mathsf{A^{\prime}}}\lvert\psi^{\prime}\rangle_% {\mathsf{B^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\left\lVert\left\lparen\langle\psi\rvert_{\mathsf{A}}\otimes I_{% \mathsf{BA^{\prime}}}\otimes\langle\psi^{\prime}\rvert_{\mathsf{B^{\prime}}}% \right\rparen\cdot\lvert\rho\rangle_{\mathsf{AB}}\lvert\psi\rangle_{\mathsf{A^% {\prime}}}\lvert\psi^{\prime}\rangle_{\mathsf{B^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\left\lVert\left\lparen\langle\psi\rvert_{\mathsf{A}}\otimes I_{% \mathsf{BA^{\prime}}}\right\rparen\cdot\lvert\rho\rangle_{\mathsf{AB}}\lvert% \psi\rangle_{\mathsf{A^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\langle\rho\rvert_{\mathsf{AB}}\langle\psi\rvert_{\mathsf{A^{% \prime}}}\cdot\left\lparen\lvert\psi\rangle\!\langle\psi\rvert_{\mathsf{A}}% \otimes I_{\mathsf{BA^{\prime}}}\right\rparen\cdot\lvert\rho\rangle_{\mathsf{% AB}}\lvert\psi\rangle_{\mathsf{A^{\prime}}}$
	$\displaystyle={}$	$\displaystyle\langle\rho\rvert_{\mathsf{AB}}\cdot\left\lparen\lvert\psi\rangle% \!\langle\psi\rvert_{\mathsf{A}}\otimes I_{\mathsf{B}}\right\rparen\cdot\lvert% \rho\rangle_{\mathsf{AB}}$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\left\lparen\lvert\psi\rangle\!% \langle\psi\rvert_{\mathsf{A}}\otimes I_{\mathsf{B}}\right\rparen\cdot\lvert% \rho\rangle\!\langle\rho\rvert_{\mathsf{AB}}\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\Big\lparen\operatorname{tr}_{\mathsf{B}}\big% \lparen\left\lparen\lvert\psi\rangle\!\langle\psi\rvert_{\mathsf{A}}\otimes I_% {\mathsf{B}}\right\rparen\cdot\lvert\rho\rangle\!\langle\rho\rvert_{\mathsf{AB% }}\big\rparen\Big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\lvert\psi\rangle\!\langle\psi\rvert_% {\mathsf{A}}\cdot\operatorname{tr}_{\mathsf{B}}\left\lparen\lvert\rho\rangle\!% \langle\rho\rvert_{\mathsf{AB}}\right\rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\left\lparen\lvert\psi\rangle\!\langle\psi\rvert% _{\mathsf{A}}\cdot\rho_{\mathsf{A}}\right\rparen$
	$\displaystyle={}$	$\displaystyle\mathrm{F}^{2}\lparen\rho,\lvert\psi\rangle\rparen.\$

$\hfill\blacktriangleleft$

According to Proposition 5, we can write

W\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}\lvert 0\rangle_{% \mathsf{A^{\prime}}}\lvert 0\rangle_{\mathsf{B^{\prime}}}=\mathrm{F}\lparen% \rho,\lvert\psi\rangle\rparen\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{% \mathsf{B}}\lvert\phi\rangle_{\mathsf{A^{\prime}B^{\prime}}}+\sqrt{1-\mathrm{F% }^{2}\lparen\rho,\lvert\psi\rangle\rparen}\lvert\phi^{\perp}\rangle_{\mathsf{% ABA^{\prime}B^{\prime}}}

(8)

for some normalized pure states $\lvert\phi\rangle$ and $\lvert\phi^{\perp}\rangle$ such that $\left\lparen\lvert 0\rangle\!\langle 0\rvert_{\mathsf{A}}\otimes\lvert 0% \rangle\!\langle 0\rvert_{\mathsf{B}}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}% \right\rparen\lvert\phi^{\perp}\rangle=0$ . With this, we can therefore estimate $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ using the square root amplitude estimation (Theorem 4). We formally state the result and give its rigorous proof as follows.

Algorithm 1 Quantum query algorithm for estimating fidelity to a pure state.

Theorem 6 (Estimating fidelity to a pure state).

Suppose that $U$ and $V$ are quantum unitary operators that prepare $n$ -qubit purifications of a $k$ -qubit mixed state $\rho=\operatorname{tr}_{\mathsf{B}}\lparen\lvert\rho\rangle\!\langle\rho\rvert% _{\mathsf{AB}}\rparen$ and a $k$ -qubit pure state $\lvert\psi\rangle\!\langle\psi\rvert=\lvert\psi\rangle\!\langle\psi\rvert_{% \mathsf{A^{\prime}}}$ , respectively, as in Equations 4 and 5. For $\varepsilon\in\lparen 0,1\rparen$ , there is a quantum query algorithm that estimates $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ with probability at least $2/3$ using $O\lparen 1/\varepsilon\rparen$ queries to (controlled-) $U$ , (controlled-) $V$ , and their inverses.

Proof.

The formal algorithm is given in Algorithm 1. To make the proof rigorous, we introduce an auxiliary system $\mathsf{C}$ that consists of one qubit. Let

W^{\prime}=\left\lparen\big\lparen I_{\mathsf{C}}\otimes\lvert 0\rangle\!% \langle 0\rvert_{\mathsf{A}}\otimes\lvert 0\rangle\!\langle 0\rvert_{\mathsf{B% }}+X_{\mathsf{C}}\otimes\left\lparen I_{\mathsf{AB}}-\lvert 0\rangle\!\langle 0% \rvert_{\mathsf{A}}\otimes\lvert 0\rangle\!\langle 0\rvert_{\mathsf{B}}\right% \rparen\big\rparen\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen W,

(9)

where $W$ is defined by Equation 6. According to Equation 8, we have

W^{\prime}\lvert 0\rangle_{\mathsf{C}}\lvert 0\rangle_{\mathsf{A}}\lvert 0% \rangle_{\mathsf{B}}\lvert 0\rangle_{\mathsf{A^{\prime}}}\lvert 0\rangle_{% \mathsf{B^{\prime}}}=\mathrm{F}\lparen\lvert\psi\rangle,\rho\rparen\lvert 0% \rangle_{\mathsf{C}}\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}% \lvert\phi\rangle_{\mathsf{A^{\prime}B^{\prime}}}+\sqrt{1-\mathrm{F}\lparen% \lvert\psi\rangle,\rho\rparen^{2}}\lvert 1\rangle_{\mathsf{C}}\lvert\phi^{% \perp}\rangle_{\mathsf{ABA^{\prime}B^{\prime}}}.

Finally, we can obtain an estimate $\tilde{x}=\mathsf{SqrtAmpEst}\lparen W^{\prime},\varepsilon\rparen$ of $\mathrm{F}\lparen\lvert\psi\rangle,\rho\rparen$ to within additive error $\varepsilon$ (i.e., $\left\lvert\tilde{x}-\mathrm{F}\lparen\lvert\psi\rangle,\rho\rparen\right% \rvert<\varepsilon$ ) with probability at least $2/3$ using $O\lparen 1/\varepsilon\rparen$ queries to $W^{\prime}$ . According to Equations 9 and 6, one query to $W^{\prime}$ consists of one query to $U$ and two queries to $V$ . Therefore, the way we obtain $\tilde{x}$ uses $O\lparen 1/\varepsilon\rparen$ queries to both $U$ and $V$ . $\hfill\blacktriangleleft$

4.2 Generalization to Two Mixed States

In this subsection, we naturally extend the unitary operator in Figure 3 to the scenario where $V$ prepares a purification of an arbitrary mixed state $\sigma$ . That is, we replace Equation 5 with

V_{\mathsf{A^{\prime}B^{\prime}}}\lvert 0\rangle_{\mathsf{A^{\prime}}}\lvert 0% \rangle_{\mathsf{B^{\prime}}}=\lvert\sigma\rangle_{\mathsf{A^{\prime}B^{\prime% }}},

(10)

where $\sigma_{\mathsf{A^{\prime}}}=\operatorname{tr}_{\mathsf{B^{\prime}}}\lparen% \lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\rparen$ . In this case, it turns out that $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ is encoded in the amplitude. Note that when $\sigma$ is pure, $\sigma^{2}=\sigma$ , the quantity $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ equals the fidelity $\mathrm{F}\lparen\rho,\sigma\rparen$ . Specifically, the circuit in Figure 3 outputs two bits $x_{\mathsf{A}},x_{\mathsf{B}}\in\{0,1\}$ such that

\Pr[x_{\mathsf{A}}=x_{\mathsf{B}}=0]=\operatorname{tr}\lparen\rho\sigma^{2}\rparen,

(11)

which generalizes Equation 7. This can be verified by the following proposition.

Proposition 7.

$\left\lVert\left\lparen\langle 0\rvert_{\mathsf{A}}\langle 0\rvert_{\mathsf{B}% }\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen W\lvert 0\rangle_{% \mathsf{A}}\lvert 0\rangle_{\mathsf{B}}\lvert 0\rangle_{\mathsf{A^{\prime}}}% \lvert 0\rangle_{\mathsf{B^{\prime}}}\right\rVert^{2}=\operatorname{tr}\lparen% \rho\sigma^{2}\rparen$ , where $W$ is defined by Equation 6, $U_{\mathsf{AB}}$ is defined by Equation 4, and $V_{\mathsf{A}^{\prime}\mathsf{B}^{\prime}}$ is defined by Equation 10.

Proof.

This can be shown by direct calculations generalizing the proof of Proposition 5.

		$\displaystyle\left\lVert\left\lparen\langle 0\rvert_{\mathsf{A}}\langle 0% \rvert_{\mathsf{B}}\otimes I_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen W% \lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}\lvert 0\rangle_{% \mathsf{A^{\prime}}}\lvert 0\rangle_{\mathsf{B^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\left\lVert\left\lparen\langle\sigma\rvert_{\mathsf{AB}}\otimes I% _{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\cdot\mathsf{SWAP}_{\mathsf{BB^{% \prime}}}\cdot\lvert\rho\rangle_{\mathsf{AB}}\lvert\sigma\rangle_{\mathsf{A^{% \prime}B^{\prime}}}\right\rVert^{2}$
	$\displaystyle={}$	$\displaystyle\langle\rho\rvert_{\mathsf{AB}}\langle\sigma\rvert_{\mathsf{A^{% \prime}B^{\prime}}}\cdot\mathsf{SWAP}_{\mathsf{BB^{\prime}}}\cdot\left\lparen% \lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{AB}}\otimes I_{\mathsf{A^{% \prime}B^{\prime}}}\right\rparen\cdot\mathsf{SWAP}_{\mathsf{BB^{\prime}}}\cdot% \lvert\rho\rangle_{\mathsf{AB}}\lvert\sigma\rangle_{\mathsf{A^{\prime}B^{% \prime}}}$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\mathsf{SWAP}_{\mathsf{BB^{\prime}}}% \left\lparen\lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{AB}}\otimes I_{% \mathsf{A^{\prime}B^{\prime}}}\right\rparen\mathsf{SWAP}_{\mathsf{BB^{\prime}}% }\cdot\left\lparen\lvert\rho\rangle\!\langle\rho\rvert_{\mathsf{AB}}\otimes% \lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right% \rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}% \left\lparen I_{\mathsf{AB}}\otimes\lvert\sigma\rangle\!\langle\sigma\rvert_{% \mathsf{A^{\prime}B^{\prime}}}\right\rparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}% }\cdot\left\lparen\lvert\rho\rangle\!\langle\rho\rvert_{\mathsf{AB}}\otimes% \lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right% \rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\Big\lparen\operatorname{tr}_{\mathsf{B}}\big% \lparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}\left\lparen I_{\mathsf{AB}}\otimes% \lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right% \rparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}\cdot\left\lparen\lvert\rho\rangle% \!\langle\rho\rvert_{\mathsf{AB}}\otimes\lvert\sigma\rangle\!\langle\sigma% \rvert_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\big\rparen\Big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}% \left\lparen I_{\mathsf{A}}\otimes\lvert\sigma\rangle\!\langle\sigma\rvert_{% \mathsf{A^{\prime}B^{\prime}}}\right\rparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}% }\cdot\left\lparen\operatorname{tr}_{\mathsf{B}}\left\lparen\lvert\rho\rangle% \!\langle\rho\rvert_{\mathsf{AB}}\right\rparen\otimes\lvert\sigma\rangle\!% \langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}% \left\lparen I_{\mathsf{A}}\otimes\lvert\sigma\rangle\!\langle\sigma\rvert_{% \mathsf{A^{\prime}B^{\prime}}}\right\rparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}% }\cdot\left\lparen\rho_{\mathsf{A}}\otimes\lvert\sigma\rangle\!\langle\sigma% \rvert_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\big\lparen\left\lparen I_{\mathsf{A}}\otimes% \langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\cdot\mathsf{% SWAP}_{\mathsf{AA^{\prime}}}\left\lparen I_{\mathsf{A}}\otimes\lvert\sigma% \rangle\!\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen% \mathsf{SWAP}_{\mathsf{AA^{\prime}}}\cdot\left\lparen\rho_{\mathsf{A}}\otimes% \lvert\sigma\rangle_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}\left\lparen\big\lparen\left\lparen I_{\mathsf{A% }}\otimes\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen% \mathsf{SWAP}_{\mathsf{AA^{\prime}}}\left\lparen I_{\mathsf{A}}\otimes\lvert% \sigma\rangle_{\mathsf{A^{\prime}B^{\prime}}}\right\rparen\big\rparen^{2}\cdot% {\rho_{\mathsf{A}}}\right\rparen.$

The proof is completed by showing that $\left\lparen I_{\mathsf{A}}\otimes\langle\sigma\rvert_{\mathsf{A^{\prime}B^{% \prime}}}\right\rparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}\left\lparen I_{% \mathsf{A}}\otimes\lvert\sigma\rangle_{\mathsf{A^{\prime}B^{\prime}}}\right% \rparen=\sigma_{\mathsf{A}}$ . To see this, note that

		$\displaystyle\left\lparen I_{\mathsf{A}}\otimes\langle\sigma\rvert_{\mathsf{A^% {\prime}B^{\prime}}}\right\rparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}\left% \lparen I_{\mathsf{A}}\otimes\lvert\sigma\rangle_{\mathsf{A^{\prime}B^{\prime}% }}\right\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}_{\mathsf{A^{\prime}B^{\prime}}}\big\lparen% \mathsf{SWAP}_{\mathsf{AA^{\prime}}}\cdot\left\lparen I_{\mathsf{A}}\otimes% \lvert\sigma\rangle\!\langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\right% \rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}_{\mathsf{A^{\prime}}}\Big\lparen\mathsf{SWAP}_{% \mathsf{AA^{\prime}}}\cdot\big\lparen I_{\mathsf{A}}\otimes\operatorname{tr}_{% \mathsf{B^{\prime}}}\left\lparen\lvert\sigma\rangle\!\langle\sigma\rvert_{% \mathsf{A^{\prime}B^{\prime}}}\right\rparen\big\rparen\Big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}_{\mathsf{A^{\prime}}}\big\lparen\mathsf{SWAP}_{% \mathsf{AA^{\prime}}}\cdot\left\lparen I_{\mathsf{A}}\otimes\sigma_{\mathsf{A^% {\prime}}}\right\rparen\big\rparen$
	$\displaystyle={}$	$\displaystyle\operatorname{tr}_{\mathsf{A^{\prime}}}\big\lparen\left\lparen% \sigma_{\mathsf{A}}\otimes I_{\mathsf{A^{\prime}}}\right\rparen\cdot\mathsf{% SWAP}_{\mathsf{AA^{\prime}}}\big\rparen$
	$\displaystyle={}$	$\displaystyle\sigma_{\mathsf{A}}\cdot\operatorname{tr}_{\mathsf{A^{\prime}}}% \lparen\mathsf{SWAP}_{\mathsf{AA^{\prime}}}\rparen$
	$\displaystyle={}$	$\displaystyle\sigma_{\mathsf{A}}\cdot I_{\mathsf{A}}$
	$\displaystyle={}$	$\displaystyle\sigma_{\mathsf{A}}.\$

$\hfill\blacktriangleleft$

Therefore, with a similar analysis, we can estimate the quantity $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ by Proposition 7 with the same complexity as Theorem 6, stated as follows.

Theorem 8.

Suppose that $U$ and $V$ are quantum unitary operators that prepare $n$ -qubit purifications of a $k$ -qubit mixed states $\rho=\operatorname{tr}_{\mathsf{B}}\lparen\lvert\rho\rangle\!\langle\rho\rvert% _{\mathsf{AB}}\rparen$ and $\sigma=\operatorname{tr}_{\mathsf{B^{\prime}}}\lparen\lvert\sigma\rangle\!% \langle\sigma\rvert_{\mathsf{A^{\prime}B^{\prime}}}\rparen$ , respectively, as in Equations 4 and 10. For $\varepsilon\in\lparen 0,1\rparen$ , there is a quantum query algorithm that estimates $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ to within additive error $\varepsilon$ with probability at least $2/3$ using $O\lparen 1/\varepsilon\rparen$ queries to (controlled-) $U$ , (controlled-) $V$ , and their inverses.

To provide an intuitive understanding of our encoding scheme, we restructure the circuit in Figure 3 into the form shown in Figure 4.

Figure 4: Restructured circuit of Figure 3, illustrating the operator

\sigma_{\mathsf{A}}\otimes I_{\mathsf{B}}

and its action on the purification

\lvert\rho\rangle_{\mathsf{AB}}

.

This revised visualization explicitly reveals the construction of an operator $\sigma_{\mathsf{A}}\otimes I_{\mathsf{B}}$ acting on the purification $\lvert\rho\rangle_{\mathsf{AB}}$ of $\rho_{\mathsf{A}}$ . Since

\left\lVert\left\lparen\sigma_{\mathsf{A}}\otimes I_{\mathsf{B}}\right\rparen% \lvert\rho\rangle_{\mathsf{AB}}\right\rVert^{2}=\operatorname{tr}\left\lparen% \rho\sigma^{2}\right\rparen,

we clearly see that $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ is encoded into the amplitude of an efficiently preparable quantum state. While the encoding pattern for $\sigma$ in Figure 4 had previously appeared in [17], people mainly focused on operator properties without explicitly deriving the amplitude structure of the resulting pure state.

5 An Implication: Generalized Pure-State Fidelity Estimation

Our quantum algorithm provided in Theorem 1 suggests a new approach to estimating the fidelity between pure states, where the pure states are given through purified quantum query access, or equivalently prepared by (purified) quantum channels. The purified quantum query access to a (mixed) quantum state can be understood as a purified version of the quantum channel that prepares the quantum state (cf. [9]). Formally, a quantum channel $\mathcal{E}$ is said to prepare a quantum state $\rho$ , if $\rho=\mathcal{E}\lparen\lvert 0\rangle\!\langle 0\rvert\rparen$ . A purified version of $\mathcal{E}$ is a unitary operator $U$ acting on two subsystems $\mathsf{A}$ and $\mathsf{B}$ such that $\mathcal{E}\lparen\sigma\rparen=\operatorname{tr}_{\mathsf{B}}\lparen U\lparen% \sigma_{\mathsf{A}}\otimes\lvert 0\rangle\!\langle 0\rvert_{\mathsf{B}}\rparen U% ^{\dagger}\rparen$ for every mixed quantum state $\sigma$ . Then, $\rho$ can be prepared by the unitary operator $U$ in the way that its purification is prepared by $\lvert\rho\rangle_{\mathsf{AB}}=U\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{% \mathsf{B}}$ and $\rho$ is obtained by tracing out the subsystem $\mathsf{B}$ , i.e., $\rho=\operatorname{tr}_{\mathsf{B}}\lparen\lvert\rho\rangle\!\langle\rho\rvert% _{\mathsf{AB}}\rparen$ . In the following, we state the special case of Theorem 1 for pure-state fidelity estimation.

Corollary 9 (Pure-state fidelity estimation).

Given purified quantum query access to two pure states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , the fidelity $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\lvert\left<% \varphi\vphantom{\psi}\middle|\psi\vphantom{\varphi}\right>\rvert$ can be estimated to within additive error $\varepsilon$ with query complexity $O\lparen 1/\varepsilon\rparen$ .

Corollary 9 generalizes the pure-state fidelity estimation in [25, Theorem IV.2] to a more general input model. By comparison, the prior approach for pure-state fidelity estimation [25] requires that the pure states should be prepared by a unitary quantum channel. Specifically, Ref. [25] assumes two unitary oracles $U_{\varphi}$ and $U_{\psi}$ such that $U_{\varphi}\lvert 0\rangle=\lvert\varphi\rangle$ and $U_{\psi}\lvert 0\rangle=\lvert\psi\rangle$ (see Section 3.2 for details). The input model employed in [25] is more restricted than the purified quantum query access model. For example, $U_{\varphi}\otimes I$ always provides purified quantum query access to $\lvert\varphi\rangle$ , where $I$ is the identity operator; however, it is unlikely that $U_{\varphi}$ could be implemented by purified quantum query access to $\lvert\varphi\rangle$ .

In addition to adopting a more general input model than [25], Corollary 9 attains the same optimal query complexity of $O(1/\varepsilon)$ , where the lower bound (noted in [25]) is implied in [2, 19] (see Theorem 10).

6 Lower Bounds

For completeness, we discuss the lower bounds for estimating the fidelity. In fact, a lower bound of $\Omega\lparen 1/\varepsilon\rparen$ is implied in [2, 19] when both quantum states are pure (as noted in [25]).

Theorem 10 (Adapted from [2, 19]).

Given purified quantum query access to quantum states $\rho$ and $\lvert\psi\rangle$ , any quantum query algorithm that estimates $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ requires query complexity $\Omega\lparen 1/\varepsilon\rparen$ , even if $\rho$ is pure.

We strengthen this lower bound so that it applies to the case where $\rho$ is a mixed quantum state of an arbitrary rank.

Theorem 11.

Given purified quantum query access to quantum states $\rho$ and $\lvert\psi\rangle$ , any quantum query algorithm that estimates $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\varepsilon$ requires query complexity $\Omega\lparen 1/\varepsilon\rparen$ , even if $\rho$ is of an arbitrary rank.

To prove Theorem 11, we need the following tool.

Theorem 12 ([3, Theorem 4]).

Let $p$ and $q$ be probability distributions over $n$ elements. Then, any quantum algorithm that determines whether an unknown unitary oracle $U$ is

U_{p}=\sum_{j=1}^{n}\sqrt{p_{j}}\lvert j\rangle\textup{ or }U_{q}=\sum_{j=1}^{% n}\sqrt{q_{j}}\lvert j\rangle

requires $\Omega\lparen 1/d_{\textup{H}}\lparen p,q\rparen\rparen$ queries to $U$ , where

d_{\textup{H}}\lparen p,q\rparen=\sqrt{\frac{1}{2}\sum_{j=1}^{n}\left\lparen% \sqrt{p_{j}}-\sqrt{q_{j}}\right\rparen^{2}}

is the Hellinger distance.

Now we are ready to prove the lower bounds.

Proof of Theorem 11.

Let $r=\operatorname{rank}\lparen\rho\rparen\geq 2$ be an arbitrary rank parameter. Now we reduce the distinguishing problem in Theorem 12 to the estimation of $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ . Consider the two probability distributions $p^{\pm}$ such that

p^{\pm}_{1}=p\pm\varepsilon,\nobreak\ p^{\pm}_{j}=\frac{1-p\mp\varepsilon}{r-1% }\textup{ for }2\leq j\leq r,\textup{ and }p^{\pm}_{j}=0\textup{ for }r<j\leq n,

where $p\in\lparen 0,1\rparen$ is an arbitrary constant. It can be verified that

d_{\textup{H}}\lparen p^{+},p^{-}\rparen=\sqrt{1-\sqrt{p^{2}-\varepsilon^{2}}-% \sqrt{\lparen 1-p\rparen^{2}-\varepsilon^{2}}}\leq O\lparen\varepsilon\rparen.

To distinguish whether an unknown unitary oracle $U$ is $U_{p^{+}}$ or $U_{p^{-}}$ , we can prepare a mixed state $\rho$ that is either of the following two mixed states

\rho_{\pm}=\lparen p\pm\varepsilon\rparen\lvert 0\rangle\!\langle 0\rvert+\sum% _{j=2}^{r}\frac{1-p\mp\varepsilon}{r-1}\lvert j\rangle\!\langle j\rvert,

using one query to $U$ . By taking $\lvert\psi\rangle=\lvert 0\rangle$ , we can distinguish which the case is by noting that the fidelity $\mathrm{F}\lparen\rho_{\pm},\lvert 0\rangle\rparen=\sqrt{p\pm\varepsilon}=% \sqrt{p}\pm\Theta\lparen\varepsilon\rparen$ . Therefore, any quantum algorithm for estimating $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ to within additive error $\Theta\lparen\varepsilon\rparen$ requires query complexity $\Omega\lparen 1/d_{\textup{H}}\lparen p^{+},p^{-}\rparen\rparen=\Omega\lparen 1% /\varepsilon\rparen$ , even if $\rho$ is of rank $r$ . $\hfill\blacktriangleleft$

7 Discussion

In this paper, we present an optimal quantum algorithm for estimating the fidelity of a mixed state to a pure state, given purified quantum query access. Our approach is simple, which moreover estimates the quantity $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ that has not been commonly considered in the literature. Here, we raise some questions for future research.

1.

Can we encode $\sqrt{\operatorname{tr}\lparen\rho\sigma\rparen}$ rather than $\sqrt{\operatorname{tr}\lparen\rho\sigma^{2}\rparen}$ in the amplitudes? In addition to its relationship with fidelity estimation, this may also estimate the Frobenius norm of a quantum state, $\lVert\rho\rVert_{F}=\sqrt{\operatorname{tr}\lparen\rho^{2}\rparen}$ , which is also the square root of purity.
2.

Can we estimate the fidelity $\mathrm{F}\lparen\rho,\lvert\psi\rangle\rparen$ with optimal sample complexity, generalizing the result of [28]?

References

[1] Anurag Anshu, Zeph Landau, and Yunchao Liu. Distributed quantum inner product estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 44–51, 2022. doi:10.1145/3519935.3519974.
[2] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. doi:10.1145/502090.502097.
[3] Aleksandrs Belovs. Quantum algorithms for classical probability distributions. In Proceedings of the 27th Annual European Symposium on Algorithms, pages 16:1–16:11, 2019. doi:10.4230/LIPIcs.ESA.2019.16.
[4] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. AMS, 2002. doi:10.1090/conm/305/05215.
[5] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. doi:10.1103/PhysRevLett.87.167902.
[6] Wang Fang and Qisheng Wang. Optimal quantum algorithm for estimating fidelity to a pure state. ArXiv e-prints, 2025. doi:10.48550/arXiv.2506.23650.
[7] Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106(23):230501, 2011. doi:10.1103/PhysRevLett.106.230501.
[8] András Gilyén and Tongyang Li. Distributional property testing in a quantum world. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference, pages 25:1–25:19, 2020. doi:10.4230/LIPIcs.ITCS.2020.25.
[9] András Gilyén, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M. Wilde. Quantum algorithm for Petz recovery channels and pretty good measurements. Physical Review Letters, 128(22):220502, 2022. doi:10.1103/PhysRevLett.128.220502.
[10] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation. ArXiv e-prints, 2022. arXiv:2203.15993.
[11] Tom Gur, Min-Hsiu Hsieh, and Sathyawageeswar Subramanian. Sublinear quantum algorithms for estimating von Neumann entropy. ArXiv e-prints, 2021. arXiv:2111.11139.
[12] Masahito Hayashi. Quantum Information Theory: Mathematical Foundation. Springer, 2017. doi:10.1007/978-3-662-49725-8.
[13] Richard Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics, 41(12):2315–2323, 1994. doi:10.1080/09500349414552171.
[14] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur? Chicago Journal of Theoretical Computer Science, 2009:3, 2009. doi:10.4086/cjtcs.2009.003.
[15] Nana Liu, Qisheng Wang, Mark M. Wilde, and Zhicheng Zhang. Quantum algorithm for matrix geometric means. npj Quantum Information, 11:101, 2025. doi:10.1038/s41534-025-00973-7.
[16] Yupan Liu and Qisheng Wang. On estimating the trace of quantum state powers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 947–993, 2025. doi:10.1137/1.9781611978322.28.
[17] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3:163, 2019. doi:10.22331/q-2019-07-12-163.
[18] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. In Theory of Computing Library, number 7 in Graduate Surveys, pages 1–81. University of Chicago, 2016. doi:10.4086/toc.gs.2016.007.
[19] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 384–393, 1999. doi:10.1145/301250.301349.
[20] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010.
[21] Harumichi Nishimura. A survey: SWAP test and its applications to quantum complexity theory. In Shin-ichi Minato, Takeaki Uno, Norihito Yasuda, Takashi Horiyama, Ken-ichi Kawarabayashi, Shigeru Yamashita, and Hirotaka Ono, editors, Algorithmic Foundations for Social Advancement: Recent Progress on Theory and Practice, pages 243–261. Springer, 2025. doi:10.1007/978-981-96-0668-9_16.
[22] Soorya Rethinasamy, Rochisha Agarwal, Kunal Sharma, and Mark M. Wilde. Estimating distinguishability measures on quantum computers. Physical Review A, 108(1):012409, 2023. doi:10.1103/PhysRevA.108.012409.
[23] Sathyawageeswar Subramanian and Min-Hsiu Hsieh. Quantum algorithm for estimating $\alpha$ -renyi entropies of quantum states. Physical Review A, 104(2):022428, 2021. doi:10.1103/PhysRevA.104.022428.
[24] Armin Uhlmann. The “transition probability” in the state space of a *-algebra. Reports on Mathematical Physics, 9(2):273–279, 1976. doi:10.1016/0034-4877(76)90060-4.
[25] Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory, 70(12):8791–8805, 2024. doi:10.1109/TIT.2024.3447915.
[26] Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying. New quantum algorithms for computing quantum entropies and distances. IEEE Transactions on Information Theory, 70(8):5653–5680, 2024. doi:10.1109/TIT.2024.3399014.
[27] Qisheng Wang and Zhicheng Zhang. Fast quantum algorithms for trace distance estimation. IEEE Transactions on Information Theory, 70(4):2720–2733, 2024. doi:10.1109/TIT.2023.3321121.
[28] Qisheng Wang and Zhicheng Zhang. Sample-optimal quantum estimators for pure-state trace distance and fidelity via samplizer. ArXiv e-prints, 2024. doi:10.48550/arXiv.2410.21201.
[29] 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, 2023. doi:10.1109/TIT.2022.3203985.
[30] Xinzhao Wang, Shengyu Zhang, and Tongyang Li. A quantum algorithm framework for discrete probability distributions with applications to Rényi entropy estimation. IEEE Transactions on Information Theory, 70(5):3399–3426, 2024. doi:10.1109/TIT.2024.3382037.
[31] John Watrous. Limits on the power of quantum statistical zero-knowledge. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 459–468, 2002. doi:10.1109/SFCS.2002.1181970.
[32] John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25–58, 2009. doi:10.1137/060670997.
[33] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. doi:10.1017/9781316848142.
[34] Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2013. doi:10.1017/9781316809976.

[bib.bib1] [1] Anurag Anshu, Zeph Landau, and Yunchao Liu. Distributed quantum inner product estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 44–51, 2022. doi:10.1145/3519935.3519974.

[bib.bib2] [2] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. doi:10.1145/502090.502097.

[bib.bib3] [3] Aleksandrs Belovs. Quantum algorithms for classical probability distributions. In Proceedings of the 27th Annual European Symposium on Algorithms, pages 16:1–16:11, 2019. doi:10.4230/LIPIcs.ESA.2019.16.

[bib.bib4] [4] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. AMS, 2002. doi:10.1090/conm/305/05215.

[bib.bib5] [5] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. doi:10.1103/PhysRevLett.87.167902.

[bib.bib6] [6] Wang Fang and Qisheng Wang. Optimal quantum algorithm for estimating fidelity to a pure state. ArXiv e-prints, 2025. doi:10.48550/arXiv.2506.23650.

[bib.bib7] [7] Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106(23):230501, 2011. doi:10.1103/PhysRevLett.106.230501.

[bib.bib8] [8] András Gilyén and Tongyang Li. Distributional property testing in a quantum world. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference, pages 25:1–25:19, 2020. doi:10.4230/LIPIcs.ITCS.2020.25.

[bib.bib9] [9] András Gilyén, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M. Wilde. Quantum algorithm for Petz recovery channels and pretty good measurements. Physical Review Letters, 128(22):220502, 2022. doi:10.1103/PhysRevLett.128.220502.

[bib.bib10] [10] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation. ArXiv e-prints, 2022. arXiv:2203.15993.

[bib.bib11] [11] Tom Gur, Min-Hsiu Hsieh, and Sathyawageeswar Subramanian. Sublinear quantum algorithms for estimating von Neumann entropy. ArXiv e-prints, 2021. arXiv:2111.11139.

[bib.bib12] [12] Masahito Hayashi. Quantum Information Theory: Mathematical Foundation. Springer, 2017. doi:10.1007/978-3-662-49725-8.

[bib.bib13] [13] Richard Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics, 41(12):2315–2323, 1994. doi:10.1080/09500349414552171.

[bib.bib14] [14] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur? Chicago Journal of Theoretical Computer Science, 2009:3, 2009. doi:10.4086/cjtcs.2009.003.

[bib.bib15] [15] Nana Liu, Qisheng Wang, Mark M. Wilde, and Zhicheng Zhang. Quantum algorithm for matrix geometric means. npj Quantum Information, 11:101, 2025. doi:10.1038/s41534-025-00973-7.

[bib.bib16] [16] Yupan Liu and Qisheng Wang. On estimating the trace of quantum state powers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 947–993, 2025. doi:10.1137/1.9781611978322.28.

[bib.bib17] [17] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3:163, 2019. doi:10.22331/q-2019-07-12-163.

[bib.bib18] [18] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. In Theory of Computing Library, number 7 in Graduate Surveys, pages 1–81. University of Chicago, 2016. doi:10.4086/toc.gs.2016.007.

[bib.bib19] [19] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 384–393, 1999. doi:10.1145/301250.301349.

[bib.bib20] [20] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010.

[bib.bib21] [21] Harumichi Nishimura. A survey: SWAP test and its applications to quantum complexity theory. In Shin-ichi Minato, Takeaki Uno, Norihito Yasuda, Takashi Horiyama, Ken-ichi Kawarabayashi, Shigeru Yamashita, and Hirotaka Ono, editors, Algorithmic Foundations for Social Advancement: Recent Progress on Theory and Practice, pages 243–261. Springer, 2025. doi:10.1007/978-981-96-0668-9_16.

[bib.bib22] [22] Soorya Rethinasamy, Rochisha Agarwal, Kunal Sharma, and Mark M. Wilde. Estimating distinguishability measures on quantum computers. Physical Review A, 108(1):012409, 2023. doi:10.1103/PhysRevA.108.012409.

[bib.bib23] [23] Sathyawageeswar Subramanian and Min-Hsiu Hsieh. Quantum algorithm for estimating $\alpha$ -renyi entropies of quantum states. Physical Review A, 104(2):022428, 2021. doi:10.1103/PhysRevA.104.022428.

[bib.bib24] [24] Armin Uhlmann. The “transition probability” in the state space of a *-algebra. Reports on Mathematical Physics, 9(2):273–279, 1976. doi:10.1016/0034-4877(76)90060-4.

[bib.bib25] [25] Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory, 70(12):8791–8805, 2024. doi:10.1109/TIT.2024.3447915.

[bib.bib26] [26] Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying. New quantum algorithms for computing quantum entropies and distances. IEEE Transactions on Information Theory, 70(8):5653–5680, 2024. doi:10.1109/TIT.2024.3399014.

[bib.bib27] [27] Qisheng Wang and Zhicheng Zhang. Fast quantum algorithms for trace distance estimation. IEEE Transactions on Information Theory, 70(4):2720–2733, 2024. doi:10.1109/TIT.2023.3321121.

[bib.bib28] [28] Qisheng Wang and Zhicheng Zhang. Sample-optimal quantum estimators for pure-state trace distance and fidelity via samplizer. ArXiv e-prints, 2024. doi:10.48550/arXiv.2410.21201.

[bib.bib29] [29] 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, 2023. doi:10.1109/TIT.2022.3203985.

[bib.bib30] [30] Xinzhao Wang, Shengyu Zhang, and Tongyang Li. A quantum algorithm framework for discrete probability distributions with applications to Rényi entropy estimation. IEEE Transactions on Information Theory, 70(5):3399–3426, 2024. doi:10.1109/TIT.2024.3382037.

[bib.bib31] [31] John Watrous. Limits on the power of quantum statistical zero-knowledge. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 459–468, 2002. doi:10.1109/SFCS.2002.1181970.

[bib.bib32] [32] John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25–58, 2009. doi:10.1137/060670997.

[bib.bib33] [33] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. doi:10.1017/9781316848142.

[bib.bib34] [34] Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2013. doi:10.1017/9781316809976.

Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Estimating fidelity to a pure state, Theorem 6 simplified).

Organization of this paper.

2 Problem Settings

Definition 2 (Purified quantum query access).

Problem 1 (Fidelity estimation).

3 Warm-Ups

3.1 SWAP Test

Theorem 3 (Quantum amplitude estimation, [4]).

3.2 Pure-State Fidelity Estimation

Theorem 4 (Quantum square root amplitude estimation, [25, Theorem I.5]).

4 Our Approach

4.1 Fidelity to a Pure State

Proposition 5.

Proof.

Theorem 6 (Estimating fidelity to a pure state).

Proof.

4.2 Generalization to Two Mixed States

Proposition 7.

Proof.

Theorem 8.

5 An Implication: Generalized Pure-State Fidelity Estimation

Corollary 9 (Pure-state fidelity estimation).

6 Lower Bounds

Theorem 10 (Adapted from [2, 19]).

Theorem 11.

Theorem 12 ([3, Theorem 4]).

Proof of Theorem 11.

7 Discussion

References