Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer

Wang, Qisheng; Zhang, Zhicheng

doi:10.4230/LIPIcs.ICALP.2026.154

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer

Qisheng Wang

School of Computer Science, Shanghai Jiao Tong University, Shanghai, China Zhicheng Zhang

School of Information and Communication Technology, Griffith University, Brisbane, Australia

Abstract

We settle the problem of estimating the trace distance and (square root) fidelity between $n$ -qubit pure quantum states to within additive error $\varepsilon$ , given their independent samples, which was raised as an open question by Wang (IEEE Trans. Inf. Theory 2024). This is achieved by a quantum algorithm with optimal sample complexity $\Theta(1/\varepsilon^{2})$ , improving the long-standing folklore with sample complexity $O(1/\varepsilon^{4})$ . At the heart of our algorithm is a samplized phase estimation of the product of two Householder reflections. This is realized by an improved (multi-)samplizer for pure states, through which any quantum query algorithm using $Q$ queries to the reflection operator $I-2\lvert\psi\rangle\!\langle\psi\rvert$ can be converted to a $\delta$ -close (in the diamond norm distance) quantum sample algorithm using $\Theta(Q^{2}/\delta)$ samples of the state $\lvert\psi\rangle$ . This samplizer for pure states is also shown to be optimal.

Keywords and phrases:

Quantum algorithms, sample complexity, trace distance, fidelity, pure states, lower bounds, samplizer

Category:

Track A: Algorithms, Complexity and Games

Funding:

Qisheng Wang: Supported by startup funding from Shanghai Jiao Tong University.

Zhicheng Zhang: Supported in part by the Australian Research Council under Grant DP250102952.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum computation theory ; Theory of computation

\rightarrow

Algorithm design techniques

Related Version:

Full Version: https://arxiv.org/abs/2410.21201 [42]

Acknowledgements:

Part of the work of Zhicheng Zhang was done when the author was with the Centre for Quantum Software and Information, University of Technology Sydney, Australia.

DOI:

10.4230/LIPIcs.ICALP.2026.154

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

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

1 Introduction

Trace distance and fidelity are the two most commonly used measures of the closeness between quantum states in many fundamental problems of quantum computation and quantum information (cf. [33]), e.g., quantum state discrimination [10, 6, 4], certification [3], and tomography [21, 34]. The trace distance between two mixed quantum states $\rho$ and $\sigma$ is defined by

\mathrm{T}\lparen\rho,\sigma\rparen\coloneqq\frac{1}{2}\operatorname{tr}\left% \lparen\big\lvert\rho-\sigma\big\rvert\right\rparen.

(1)

The (square root) fidelity between $\rho$ and $\sigma$ is defined by

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

(2)

To clarify, the squared fidelity $\mathrm{F}^{2}\lparen\rho,\sigma\rparen\coloneqq\big\lparen\mathrm{F}\lparen% \rho,\sigma\rparen\big\rparen^{2}$ is also a closeness measure commonly used in the literature. As a quantum analog of estimating the closeness (e.g., total variation distance) between probability distributions [38], estimating the trace distance and (square root/squared) fidelity between quantum states turns out to be a basic problem of broad interest.

Figure 1: The SWAP test.

One of the earliest approach to this problem is the SWAP test [5, 9], as shown in Figure 1. On input two pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , the measurement outcome of the SWAP test will be $0$ with probability $\frac{1}{2}+\frac{1}{2}\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ ,¹¹1If we replace the pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ with mixed quantum states $\rho$ and $\sigma$ , respectively, then the probability of measurement outcome $0$ will be $\frac{1}{2}+\frac{1}{2}\operatorname{tr}\lparen\rho\sigma\rparen$ [28, Proposition 9]. where

\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\lvert% \langle\varphi|\psi\rangle\rvert^{2}.

(3)

An $\varepsilon$ -estimate (in terms of additive error) of $\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ can be obtained with high probability by repeating the SWAP test $O\lparen 1/\varepsilon^{2}\rparen$ times, which uses $O\lparen 1/\varepsilon^{2}\rparen$ samples of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ . Through this approach, $\varepsilon$ -estimates of their trace distance and square root fidelity can be obtained by using $O\lparen 1/\varepsilon^{4}\rparen$ samples,²²2This folklore approach was noted in [39, Appendix A]. according to the following identities

\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\sqrt{1-\mathrm% {F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen},\qquad\mathrm{F}% \lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\sqrt{\mathrm{F}^{2}% \lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen}.

(4)

Since the discovery of the SWAP test, there has been a series of work on testing/estimating the closeness of quantum states (see Section 3 for a comprehensive review). However, only a few special pure-state cases are known to have optimal algorithms. In [1], it was shown that $\varepsilon$ -estimating $\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ requires $\Omega\lparen 1/\varepsilon^{2}\rparen$ samples of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , thereby implying that the quantum circuit for the SWAP test in Figure 1 is the best (up to a constant factor) solution to this task that we can hope for; equipped with quantum amplitude estimation [8], the SWAP test further implies an optimal quantum query algorithm for $\varepsilon$ -estimating $\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ by using $O\lparen 1/\varepsilon\rparen$ queries to the state-preparation circuits of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , where the matching query complexity lower bound is due to [7, 32]. Given these results, one might presume that the SWAP test would also work best for estimating similar quantities such as $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ . A piece of evidence against this is a recent quantum query algorithm proposed in [39] for $\varepsilon$ -estimating $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ with optimal query complexity $\Theta\lparen 1/\varepsilon\rparen$ , which is not based on the SWAP test. Nonetheless, the sample complexity of estimating $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ remains unsolved. The prior best sample complexity upper bound is $O\lparen 1/\varepsilon^{4}\rparen$ due to the folklore approach just mentioned, while the prior best sample complexity lower bound is only $\Omega\lparen 1/\varepsilon^{2}\rparen$ as noted in [39]. These naturally raise a question:

	Can we improve the folklore sample complexity $O\lparen 1/\varepsilon^{4}\rparen$
	for estimating $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ ?

Surprisingly, we give a positive answer to this question by providing a novel quantum algorithm with optimal sample complexity $\Theta\lparen 1/\varepsilon^{2}\rparen$ for $\varepsilon$ -estimating $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ , matching the lower bound noted in [39].

We formally state our main result as follows.

Theorem 1 (Optimal quantum estimators for pure-state trace distance and square root fidelity, Theorem 14 restated).

Given sample access to two $n$ -qubit pure states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ can be $\varepsilon$ -estimated on a quantum computer with sample complexity $O\lparen 1/\varepsilon^{2}\rparen$ .

We summarize the complexity of pure-state trace distance and fidelity estimations in Table 1.

Table 1: Quantum complexity for pure-state trace distance and fidelity estimations.

Complexity Type

Trace Distance

Square Root Fidelity

Squared Fidelity

Sample Upper Bound

O(1/\varepsilon^{4})

folklore

O(1/\varepsilon^{2})

this work

O(1/\varepsilon^{4})

folklore

O(1/\varepsilon^{2})

this work

O(1/\varepsilon^{2})

[9]

Sample Lower Bound

\Omega(1/\varepsilon^{2})

[39]

\Omega(1/\varepsilon^{2})

[1, 39]

\Omega(1/\varepsilon^{2})

[1]

Query Upper Bound

O(1/\varepsilon)

[39]

O(1/\varepsilon)

[39]

O(1/\varepsilon)

[9, 8]

Query Lower Bound

\Omega(1/\varepsilon)

[39]

\Omega(1/\varepsilon)

[7, 32, 39]

\Omega(1/\varepsilon)

[7, 32]

Our quantum algorithm in Theorem 1 is quite different from the quantum query algorithm proposed in [39] and those under the framework of the SWAP test. Its key component is a samplized phase estimation of the product of two Householder reflections. To this end, we also extend the samplizer (for mixed states) employed in [43] to (multi-)samplizer for pure states, which is an algorithmic tool of independent interest.

Organization of this paper.

We will introduce the techniques in our quantum algorithm and the optimality of our (multi-)samplizer for pure states in Section 2, and give a brief review of related work in Section 3. Preliminaries are given in Section 4. A meta-algorithm using Householder reflections for estimating the trace distance and fidelity will be presented in Section 5. The samplizer for pure states will be defined and implemented in Section 6. The complete algorithm will be presented in Section 7. Optimality and lower bounds will be shown in Section 8.

2 Techniques

In this section, we introduce the observations and techniques for achieving our results. We first introduce our quantum algorithm in Sections 2.1 and 2.2, and then discuss the lower bounds and optimality in Section 2.3.

2.1 Properties of the product of Householder reflections

The first property of trace distance and square root fidelity we need to notice is that for any two pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , it always holds that

\big\lparen\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen\big% \rparen^{2}+\big\lparen\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle% \rparen\big\rparen^{2}=1.

(5)

Equation 5 allows us to represent the trace distance and the square root fidelity through trigonometric functions, i.e., one can assume that $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\cos\lparen\gamma\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\sin\lparen\gamma\rparen$ for some real number $\gamma\in[0,\frac{\pi}{2}]$ . This suggests us to estimate $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ at the same time by estimating the value of $\gamma$ . To this end, our major observation is that $\gamma$ appears to be encoded in the product of the reflection operators about the vectors $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ .

For convenience, suppose that $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ are two distinguishable pure quantum states, i.e., $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen\neq 0$ . Let $R_{\varphi}=I-2\lvert\varphi\rangle\!\langle\varphi\rvert$ and $R_{\psi}=I-2\lvert\psi\rangle\!\langle\psi\rvert$ be the reflection operators about $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , respectively. Our key observation (Lemma 8) is that the pure quantum state $\lvert\varphi\rangle$ lies in the subspace spanned by two eigenvectors $\lvert\Phi_{\pm}\rangle$ of $R_{\varphi}R_{\psi}$ with eigenvalues $-e^{\mp i2\gamma}$ , respectively. Specifically, $\lvert\varphi\rangle$ can be represented as

\lvert\varphi\rangle=\frac{1}{\sqrt{2}}\big\lparen\lvert\Phi_{+}\rangle+\lvert% \Phi_{-}\rangle\big\rparen,\text{ where }R_{\varphi}R_{\psi}\lvert\Phi_{\pm}% \rangle=-e^{\mp i2\gamma}\lvert\Phi_{\pm}\rangle.

(6)

According to the above observation, if we have quantum query access to the two reflection operators $R_{\varphi}$ and $R_{\psi}$ , then we can obtain an $\varepsilon$ -estimate of the value $\gamma$ , denoted by $\tilde{\gamma}$ , via the quantum phase estimation (cf. [33, Section 5.2]) of $R_{\varphi}R_{\psi}$ on the pure quantum state $\lvert\varphi\rangle$ , by using $O\lparen 1/\varepsilon\rparen$ queries to (controlled-) $R_{\varphi}$ and (controlled-) $R_{\psi}$ , despite that $\lvert\varphi\rangle$ is not an eigenvector of $R_{\varphi}R_{\psi}$ . Finally, $\Theta\lparen\varepsilon\rparen$ -estimates of trace distance and square root fidelity are given by $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen\approx\cos% \lparen\tilde{\gamma}\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen\approx\sin% \lparen\tilde{\gamma}\rparen$ (see Lemma 9 for details). For illustration, the quantum circuit for this specific quantum phase estimation is given in Figure 2.

Figure 2: Phase estimation of

R_{\varphi}R_{\psi}

on

\lvert\varphi\rangle

.

2.2 Multi-samplizer for pure states

The samplizer employed in [43] is a tool that allows us to convert quantum query algorithms to quantum sample algorithms (the latter use samples of quantum states as input). The algorithm outlined in Figure 2 can be treated as a quantum query algorithm with the two reflection operators $R_{\varphi}$ and $R_{\psi}$ being the quantum query oracles. Now to convert this quantum query algorithm to a quantum sample algorithm using samples of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , we define the notion of multi-samplizer for pure states, extending the samplizer in [43].

Definition 2 (Multi-samplizer for pure states, Definition 12 restated).

A $k$ -samplizer for $n$ -qubit pure states, denoted as $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ , is a converter such that: for any quantum query algorithm $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ with $n$ -qubit quantum unitary oracles $U_{1},U_{2},\dots,U_{k}$ and any $n$ -qubit pure states $\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert\psi_{k}\rangle$ , the quantum circuit instance $\mathcal{A}^{R_{\psi_{1}},R_{\psi_{2}},\dots,R_{\psi_{k}}}$ can be implemented to precision $\delta$ in diamond norm by using samples of $\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert\psi_{k}\rangle$ , i.e.,

\left\lVert\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\big\langle\mathcal{A}^{U% _{1},U_{2},\dots,U_{k}}\big\rangle\big[\lvert\psi_{1}\rangle,\lvert\psi_{2}% \rangle,\dots,\lvert\psi_{k}\rangle\big]-\mathcal{A}^{R_{\psi_{1}},R_{\psi_{2}% },\dots,R_{\psi_{k}}}\right\rVert_{\diamond}\leq\delta.

(7)

Using the notion of multi-samplizer for pure states in Definition 2, we can estimate the trace distance and square root fidelity between pure quantum states by extending the approach in Figure 2. Let $\mathsf{QPE}^{U}_{t}$ be the quantum circuit for the phase estimation of $U$ without specifying the input states (see Figure 3), which uses $t$ qubits to store the estimation result of the phase. Then, the quantum circuit in Figure 2 (without specifying the input state $\lvert 0\rangle^{\otimes t}\lvert\varphi\rangle$ ) can be described by $\mathcal{A}^{R_{\varphi},R_{\psi}}$ , which is a specialization of the quantum query algorithm $\mathcal{A}^{U_{1},U_{2}}\coloneqq\mathsf{QPE}^{U_{1}U_{2}}_{t}$ with $t=\Theta\lparen\log\lparen 1/\varepsilon\rparen\rparen$ . The algorithm is informally outlined as follows (see Algorithm 1 for the formal version).

Pure-state trace distance and fidelity estimations (informal):

Input: Pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ .

Output: $\varepsilon$ -estimates of $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ .

1.

Let $t=\Theta\lparen\log\lparen 1/\varepsilon\rparen\rparen$ and $\mathcal{A}^{U_{1},U_{2}}\coloneqq\mathsf{QPE}^{U_{1}U_{2}}_{t}$ .
2.

Prepare the quantum state $\rho\coloneqq\mathsf{Samplize}^{\mathsf{pure}}_{0.01}\big\langle\mathcal{A}^{U% _{1},U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]\big% \lparen\lvert 0\rangle\!\langle 0\rvert^{\otimes t}\otimes\lvert\varphi\rangle% \!\langle\varphi\rvert\big\rparen$ .
3.

Obtain an $\varepsilon$ -estimate $\tilde{\gamma}$ of $\gamma$ by measuring the first $t$ qubits of $\rho$ .
4.

Return $\cos\lparen\tilde{\gamma}\rparen$ and $\sin\lparen\tilde{\gamma}\rparen$ as the estimates of $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ , respectively.

To see the correctness of the above informally stated algorithm, we note that for any $2$ -samplizer $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ , we have

\big\lVert\mathsf{Samplize}^{\mathsf{pure}}_{0.01}\big\langle\mathcal{A}^{U_{1% },U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]-\mathcal{A% }^{R_{\varphi},R_{\psi}}\big\rVert_{\diamond}\leq 0.01.

(8)

Since an $\varepsilon$ -estimate of $\gamma$ can be obtained with high probability, say $\geq 0.99$ , by measuring the state $\mathcal{A}^{R_{\varphi},R_{\psi}}\lvert 0\rangle^{\otimes t}\lvert\varphi\rangle$ (in the computational basis), one can obtain an $\varepsilon$ -estimate of $\gamma$ with probability $\geq 0.95$ by measuring the following state

\mathsf{Samplize}^{\mathsf{pure}}_{0.01}\big\langle\mathcal{A}^{U_{1},U_{2}}% \big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]\big\lparen\lvert 0% \rangle\!\langle 0\rvert^{\otimes t}\otimes\lvert\varphi\rangle\!\langle% \varphi\rvert\big\rparen.

(9)

Let $\tilde{\gamma}$ be the $\varepsilon$ -estimate of $\gamma$ obtained from the above process. Then, we have that $\cos\lparen\tilde{\gamma}\rparen$ and $\sin\lparen\tilde{\gamma}\rparen$ are $\Theta\lparen\varepsilon\rparen$ -estimates of $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ and $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ , respectively, due to the observation introduced in Section 2.1.

To complete our approach, we provide an efficient implementation of the multi-samplizer for pure states.

Theorem 3 (Implementation of multi-samplizer for pure states, Theorem 13 restated).

There is an implementation of multi-samplizer for pure states $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ such that if $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ uses $Q_{j}$ queries to $U_{j}$ for each $1\leq j\leq k$ , then $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\rangle[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert% \psi_{k}\rangle]$ can be implemented by using

O\left\lparen\frac{Q_{j}}{\delta}\cdot\sum_{i=1}^{k}Q_{i}\right\rparen

(10)

samples of $\lvert\psi_{j}\rangle$ for each $1\leq j\leq k$ .

Using the efficient implementation of multi-samplizer for pure states given in Theorem 3 (with $k\coloneqq 2$ , $Q_{1}=Q_{2}\coloneqq O\lparen 1/\varepsilon\rparen$ and $\delta\coloneqq 0.01$ ), the quantum channel $\mathsf{Samplize}^{\mathsf{pure}}_{0.01}\big\langle\mathcal{A}^{U_{1},U_{2}}% \big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]$ can be implemented by using $O\lparen 1/\varepsilon^{2}\rparen$ samples of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ . This yields the upper bounds stated in Theorem 1 (see Theorem 14 for details).

$\blacktriangleright$ Remark 4.

Here, we clarify the difference between the samplizer defined in [43, Definition I.1] and the (multi-)samplizer for pure states defined in Definition 2.

1.

Types of oracles: The samplizer in [43] requires the oracle to be a (scaled) block-encoding of the density operator of a mixed quantum state. By comparison, the samplizer for pure states in Definition 2 requires the oracle to be the reflection operator about a pure state. More discussions on the relation between the two types of samplizers are given in [42, Appendix A].
2.

Single/multiple oracles: The samplizer in [43] only allows a single oracle, while the multi-samplizer for pure states in Definition 2 allows multiple oracles.
3.

Sample complexity: The sample complexity of the samplizer in [43] is $\widetilde{O}\lparen Q^{2}/\delta\rparen$ where $\widetilde{O}\lparen\cdot\rparen$ suppresses polylogarithmic factors in $Q$ and $1/\delta$ , while the sample complexity of the $k$ -samplizer for pure states given in Theorem 3 is $O\lparen Q^{2}/\delta\rparen$ (without polylogarithmic factors) for constant $k$ .
4.

Optimality: The optimality of the samplizer in [43] is shown via a reduction of Hamiltonian simulation. However, the same reduction does not work for the multi-samplizer for pure states in Definition 2. To show the optimality of the multi-samplizer for pure states, our proof uses the algorithm for pure-state trace distance estimation given in Section 2.1 and is also based on the optimal sample lower bound for pure-state trace distance estimation (see Section 8.2 for details).

2.3 Optimality

Our quantum algorithm in Theorem 1 for pure-state trace distance and square root fidelity estimations is sample-optimal due to the sample complexity lower bound $\Omega\lparen 1/\varepsilon^{2}\rparen$ noted in [39]. Based on these, we show a matching sample complexity lower bound (up to a constant factor) for the $k$ -samplizer for pure states when $k$ is constant.

Theorem 5 (Optimality of the samplizer for pure states, Theorem 17 restated).

For any $k$ -samplizer for pure states, $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ , if a quantum query algorithm $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ uses $Q_{j}$ queries to $U_{j}$ for each $j$ , then the implementation of $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\rangle[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert% \psi_{k}\rangle]$ requires $\Omega\lparen Q_{j}^{2}/\delta\rparen$ samples of $\lvert\psi_{j}\rangle$ for each $j$ .

Proof sketch.

To derive a sample lower bound for the samplizer, we need the meta-algorithm $\mathcal{A}^{U_{1},U_{2}}$ for estimating $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ , which is based on the observation in Section 2.1 and uses the phase estimation. As will be shown in Corollary 10, this meta-algorithm $\mathcal{A}^{U_{1},U_{2}}$ makes $O\lparen 1/\varepsilon\rparen$ queries to the reflection operators $U_{1}\coloneqq R_{\varphi}$ and $U_{2}\coloneqq R_{\psi}$ . Suppose that there is an implementation of the (multi-)samplizer for pure states $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ with sample complexity $\mathsf{S}\lparen Q,\delta\rparen$ , meaning that we can implement $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{B}^{V_{1},V_{2}}% \rangle[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle]$ by using $\mathsf{S}\lparen Q,\delta\rparen$ samples of $\lvert\psi_{1}\rangle$ and $\lvert\psi_{2}\rangle$ for every quantum query algorithm $\mathcal{B}^{V_{1},V_{2}}$ that makes $Q$ queries to $V_{1}$ and $V_{2}$ . On the other hand, $\mathsf{Samplize}^{\mathsf{pure}}_{0.01}\langle\mathcal{A}^{U_{1},U_{2}}% \rangle[\lvert\varphi\rangle,\lvert\psi\rangle]$ is an $\varepsilon$ -estimator for $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ with sample complexity $\mathsf{S}\lparen\Theta\lparen 1/\varepsilon\rparen,0.01\rparen$ , while any $\varepsilon$ -estimator for $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ requires sample complexity $\Omega\lparen 1/\varepsilon^{2}\rparen$ , which gives $\mathsf{S}\lparen\Theta\lparen 1/\varepsilon\rparen,0.01\rparen\geq\Omega% \lparen 1/\varepsilon^{2}\rparen$ . Hence, we can further obtain $\mathsf{S}\lparen Q,\delta\rparen\geq\Omega\lparen Q^{2}/\delta\rparen$ using the properties of $\mathsf{S}\lparen Q,\delta\rparen$ . More details will be presented in Theorem 16. $\hfill\blacktriangleleft$

It is worth mentioning that the sample complexity lower bound for the samplizer for pure states is based on the matching lower bound for pure-state trace distance and square root fidelity estimations, in sharp contrast to the proof for the optimality of the general samplizer in [43] (as discussed in Remark 4).

3 Related Work

There are also a few other approaches to estimating trace distance and fidelity in the literature. Except for those based on quantum state tomography [18, 21, 34], entanglement witnesses [37, 19, 20] are a practical technique for estimating the fidelity of certain pure states using few measurements; and direct fidelity estimation [13] is designed for pure-state fidelity estimation using only Pauli measurements. In [25], classical shadows were used to estimate the fidelity between a pure state and a mixed state. A distributed quantum algorithm for pure-state squared fidelity estimation was proposed in [1], which was recently extended to the case with limited quantum computation in [2, 17]. An optimal quantum query algorithm for pure-state trace distance and square root fidelity estimations was proposed in [39].

For the case of mixed quantum states, estimating their fidelity are known to have efficient quantum algorithms [44, 40, 14, 30]; especially, in [14], they proposed a sample-efficient quantum algorithm for fidelity estimation with sample complexity $\widetilde{O}\lparen r^{5.5}/\varepsilon^{12}\rparen$ , where $r$ is the rank of mixed quantum states and $\varepsilon$ is the desired additive error. Also, estimating the trace distance are known to have efficient quantum algorithms [40, 41, 29]; especially, in [41], they proposed a sample-efficient quantum algorithm for trace distance estimation with sample complexity $\widetilde{O}\lparen r^{2}/\varepsilon^{5}\rparen$ . Apart from estimation, the certification of $d$ -dimensional mixed quantum states is highly related and was studied in [3], where they provided quantum algorithms that determine whether two mixed quantum states are identical or $\varepsilon$ -far with sample complexity $\Theta\lparen d/\varepsilon^{2}\rparen$ (w.r.t. trace distance) and $\Theta\lparen d/\varepsilon\rparen$ (w.r.t. infidelity), which are optimal due to the lower bounds in [35].

4 Preliminaries

In this section, we introduce different norms used in this paper and list the quantum algorithmic tools essential for designing our quantum algorithms.

4.1 Norms

4.1.1 Vector norms

The $1$ -norm (a.k.a. Taxicab norm or Manhattan norm) of a $d$ -dimensional real-valued vector $v=\lparen v_{0},v_{1},\dots,v_{d-1}\rparen^{\mathrm{T}}\in\mathbb{R}^{d}$ is denoted by

\lVert v\rVert_{1}=\sum_{j=0}^{d-1}\lvert v_{j}\rvert.

(11)

The total variation distance between two $d$ -dimensional probability distributions $p,q\in\mathbb{R}^{d}$ (treated as real-valued vectors) is denoted by

d_{\textup{TV}}\lparen p,q\rparen=\frac{1}{2}\lVert p-q\rVert_{1}.

(12)

A $d$ -dimensional (pure) quantum state is described by a complex-valued vector

\lvert\psi\rangle=\sum_{j=0}^{d-1}\alpha_{j}\lvert j\rangle\in\mathbb{C}^{d},

(13)

where $\alpha_{j}\in\mathbb{C}$ for each $0\leq j<d$ is a complex number and $\{\lvert j\rangle\}$ is the computational basis. The inner product of two vectors $\lvert\varphi\rangle=\sum_{j=0}^{d-1}\beta_{j}\lvert j\rangle$ and $\lvert\psi\rangle=\sum_{j=0}^{d-1}\alpha_{j}\lvert j\rangle$ is denoted by

\langle\varphi|\psi\rangle=\sum_{j=0}^{d-1}\beta_{j}^{*}\alpha_{j},

(14)

where $z^{*}$ is the complex conjugate of the complex number $z$ . The $2$ -norm (a.k.a. Euclidean norm) of $\lvert\psi\rangle$ is denoted by

\lVert\lvert\psi\rangle\rVert=\sqrt{\langle\psi|\psi\rangle}.

(15)

4.1.2 Matrix norms

A $d$ -dimensional linear operator is described by a $d$ -dimensional matrix $A\in\mathbb{C}^{d\times d}$ . The matrix norm induced by vector $2$ -norm (a.k.a. operator norm and spectral norm) is denoted by

\lVert A\rVert=\sup_{\lvert\psi\rangle\in\mathbb{C}^{d}\colon\lVert\lvert\psi% \rangle\rVert\neq 0}\frac{\lVert A\lvert\psi\rangle\rVert}{\lVert\lvert\psi% \rangle\rVert}.

(16)

The Schatten $1$ -norm (a.k.a. trace norm and nuclear norm) of $A$ is denoted by

\lVert A\rVert_{\operatorname{tr}}=\operatorname{tr}\left\lparen\lvert A\rvert% \right\rparen=\operatorname{tr}\left\lparen\sqrt{A^{\dagger}A}\right\rparen,

(17)

where

\operatorname{tr}\lparen A\rparen=\sum_{j=0}^{d-1}\langle j\rvert A\lvert j\rangle.

(18)

4.2 Diamond norm

A $d$ -dimensional superoperator is described by a linear map on $d$ -dimensional linear operators, $\Phi\colon\mathbb{C}^{d\times d}\to\mathbb{C}^{d\times d}$ . The diamond norm (a.k.a completely bounded trace norm) of $\Phi$ is denoted by

\lVert\Phi\rVert_{\diamond}=\sup_{X\in\mathbb{C}^{d^{2}\times d^{2}}\colon% \lVert X\rVert_{\operatorname{tr}}\leq 1}\lVert\left\lparen\Phi\otimes\mathcal% {I}_{d}\right\rparen X\rVert_{\operatorname{tr}},

(19)

where the superoperator $\mathcal{I}_{d}$ is the identity operator. It is noteworthy that the diamond distance between two completely positive and trace-preserving maps (a.k.a. quantum channels) $\mathcal{E}$ and $\mathcal{F}$ is denoted by $\lVert\mathcal{E}-\mathcal{F}\rVert_{\diamond}$ .

4.3 Quantum phase estimation

Quantum phase estimation [27] is a basic quantum subroutine, which was used in Shor’s quantum algorithm for factorization [36]. Here, we use the version in [33].

Theorem 6 (Quantum phase estimation, [33, Section 5.2]).

Suppose that $U$ is a unitary operator. There is a quantum circuit $\mathsf{QPE}^{U}_{\varepsilon,\delta}$ using $O\lparen 1/\varepsilon\delta\rparen$ queries to controlled- $U$ that performs the transform

\mathsf{QPE}^{U}_{\varepsilon,\delta}\colon\lvert 0\rangle\lvert\psi\rangle% \mapsto\lvert\tilde{\lambda}\rangle\lvert\psi\rangle

(20)

for any eigenvector $\lvert\psi\rangle$ of $U$ with $U\lvert\psi\rangle=e^{i2\pi\lambda}$ and $\lambda\in[0,1)$ , where if we measure $\lvert\tilde{\lambda}\rangle$ in the computational basis (with some classical postprocessing), then with probability at least $1-\varepsilon$ we will obtain a real number $\tilde{\lambda}\in[0,1)$ satisfying

\min\left\{\lvert\tilde{\lambda}-\lambda\rvert,1-\lvert\tilde{\lambda}-\lambda% \rvert\right\}<\delta.

(21)

An implementation of the quantum phase estimation in Theorem 6 is also given in [33, Section 5.2] (see Figure 3), where the parameter $t$ is chosen to be $t=\Theta\lparen\log\lparen 1/\varepsilon\delta\rparen\rparen$ and $\mathrm{QFT}_{t}$ denotes the unitary operator for quantum Fourier transform

\mathrm{QFT}_{t}\colon\lvert j\rangle\mapsto\frac{1}{\sqrt{2^{t}}}\sum_{k=0}^{% 2^{t}-1}e^{i2\pi jk/2^{t}}\lvert k\rangle.

(22)

In addition to the queries to the controlled- $U^{2^{j}}$ gates, the implementation in Figure 3 uses $t$ Hadamard gates and an inverse $t$ -qubit QFT. In [22], it was shown that an (inverse) $t$ -qubit QFT can be implemented by using $O\lparen t\log t\rparen$ two-qubit quantum gates.

Figure 3: Phase estimation of

U

on

\lvert\psi\rangle

.

4.4 Density matrix exponentiation

Density matrix exponentiation, also called sample-based Hamiltonian simulation, was proposed in [31, 26, 16], which allows us to approximately implement the unitary operator $e^{-i\rho t}$ by using identical copies of mixed quantum states $\rho$ .

Theorem 7 ([26, Theorem 2]).

Given sample access to a mixed quantum state $\rho$ , for every $0<\delta\leq 1/6$ and $t\geq 6\pi\delta$ , it is necessary and sufficient to use $\Theta\lparen t^{2}/\delta\rparen$ samples of $\rho$ to implement a quantum channel that is $\delta$ -close to (controlled-) $e^{-i\rho t}$ in diamond norm. Moreover, the implementation uses additional $O\lparen nt^{2}/\delta\rparen$ one- and two-qubit quantum gates, if $\rho$ is an $n$ -qubit quantum state.

5 Estimation with Reflections

In this section, we study how to estimate the trace distance and square root fidelity between pure quantum states given their Householder reflection operators. We first introduce an important property of the product of two Householder reflections in Section 5.1. Then, using this property, in Section 5.2 we provide a meta-algorithm based on quantum phase estimation.

5.1 Product of Householder reflections

For a unit vector $\lvert\psi\rangle$ , we use $R_{\psi}=I-2\lvert\psi\rangle\!\langle\psi\rvert$ to denote the Householder reflection about $\lvert\psi\rangle$ . The following is the key property of the product of Householder reflections that enables our quantum algorithm for pure-state trace distance and fidelity estimations. We use $\arg\lparen a+bi\rparen=\arctan\lparen b/a\rparen$ to denote the argument of a complex number $a+bi$ .

Lemma 8.

Suppose that $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ are two unit vectors such that $\big\lvert\langle\varphi|\psi\rangle\big\rvert\neq 1$ . Let

\lvert\varphi^{\perp}\rangle=\frac{\lvert\psi\rangle-\langle\varphi|\psi% \rangle\lvert\varphi\rangle}{\left\lVert\lvert\psi\rangle-\langle\varphi|\psi% \rangle\lvert\varphi\rangle\right\rVert}.

(23)

Let $\theta=\arg\lparen\langle\varphi|\psi\rangle\rparen$ and $\theta^{\perp}=\arg\lparen\langle\varphi^{\perp}|\psi\rangle\rparen$ . Then,

\lvert\Phi_{\pm}\rangle=\frac{1}{\sqrt{2}}\left\lparen\lvert\varphi\rangle\pm e% ^{i\left\lparen\theta^{\perp}-\theta+\frac{\pi}{2}\right\rparen}\lvert\varphi^% {\perp}\rangle\right\rparen.

(24)

are unit eigenvectors of $R_{\varphi}R_{\psi}$ with eigenvalues $e^{i\left\lparen\pi\mp 2\gamma\right\rparen}$ , where $\gamma=\arcsin\lparen\lvert\langle\varphi|\psi\rangle\rvert\rparen$ .

Proof.

Since $\lvert\psi\rangle\in\mathcal{H}_{\varphi}=\operatorname{span}\{\lvert\varphi% \rangle,\lvert\varphi^{\perp}\rangle\}$ , we can represent $\lvert\psi\rangle$ in terms of $\lvert\varphi\rangle$ and $\lvert\varphi^{\perp}\rangle$ as follows:

$\displaystyle\lvert\psi\rangle$	$\displaystyle=\langle\varphi\|\psi\rangle\lvert\varphi\rangle+\langle\varphi^{% \perp}\|\psi\rangle\lvert\varphi^{\perp}\rangle$	(25)
	$\displaystyle=e^{i\theta}\cdot\lvert\langle\varphi\|\psi\rangle\rvert\cdot% \lvert\varphi\rangle+e^{i\theta^{\perp}}\cdot\lvert\langle\varphi^{\perp}\|\psi% \rangle\rvert\cdot\lvert\varphi^{\perp}\rangle$	(26)
	$\displaystyle=e^{i\theta}\sin\lparen\gamma\rparen\lvert\varphi\rangle+e^{i% \theta^{\perp}}\cos\lparen\gamma\rparen\lvert\varphi^{\perp}\rangle.$	(27)

Then, we write out an orthonormal basis of $R_{\psi}\mathcal{H}_{\varphi}$ , namely the vectors obtained by applying the reflection $R_{\psi}$ on $\lvert\varphi\rangle$ and $\lvert\varphi^{\perp}\rangle$ :

	$\displaystyle R_{\psi}\lvert\varphi\rangle$	$\displaystyle=\lvert\varphi\rangle-2\langle\psi\|\varphi\rangle\lvert\psi\rangle,$		(28)
	$\displaystyle R_{\psi}\lvert\varphi^{\perp}\rangle$	$\displaystyle=\lvert\varphi^{\perp}\rangle-2\langle\psi\|\varphi^{\perp}\rangle% \lvert\psi\rangle.$		(29)

By Equations 27, 28, and 29, we write the orthonormal basis $\{R_{\varphi}R_{\psi}\lvert\varphi\rangle,R_{\varphi}R_{\psi}\lvert\varphi^{% \perp}\rangle\}$ of $R_{\varphi}R_{\psi}\mathcal{H}_{\varphi}$ as follows:

$\displaystyle R_{\varphi}R_{\psi}\lvert\varphi\rangle$	$\displaystyle=R_{\varphi}\left\lparen\lvert\varphi\rangle-2\langle\psi\|\varphi% \rangle\lvert\psi\rangle\right\rparen$	(30)
	$\displaystyle=-\lvert\varphi\rangle-2\langle\psi\|\varphi\rangle\lvert\psi% \rangle+4\left\lvert\langle\psi\|\varphi\rangle\right\rvert^{2}\lvert\varphi\rangle$	(31)
	$\displaystyle=-\lvert\varphi\rangle-2e^{-i\theta}\sin\lparen\gamma\rparen% \lvert\psi\rangle+4\sin^{2}\lparen\gamma\rparen\lvert\varphi\rangle$	(32)
	$\displaystyle=\left\lparen 2\sin^{2}\lparen\gamma\rparen-1\right\rparen\lvert% \varphi\rangle-2e^{i\left\lparen\theta^{\perp}-\theta\right\rparen}\sin\lparen% \gamma\rparen\cos\lparen\gamma\rparen\lvert\varphi^{\perp}\rangle$	(33)
	$\displaystyle=-\cos\lparen 2\gamma\rparen\lvert\varphi\rangle-e^{i\left\lparen% \theta^{\perp}-\theta\right\rparen}\sin\lparen 2\gamma\rparen\lvert\varphi^{% \perp}\rangle,$	(34)
$\displaystyle R_{\varphi}R_{\psi}\lvert\varphi^{\perp}\rangle$	$\displaystyle=R_{\varphi}\left\lparen\lvert\varphi^{\perp}\rangle-2\langle\psi% \|\varphi^{\perp}\rangle\lvert\psi\rangle\right\rparen$	(35)
	$\displaystyle=\lvert\varphi^{\perp}\rangle-2\langle\psi\|\varphi^{\perp}\rangle% \lvert\psi\rangle+4\langle\varphi\|\psi\rangle\langle\psi\|\varphi^{\perp}% \rangle\lvert\varphi\rangle$	(36)
	$\displaystyle=\lvert\varphi^{\perp}\rangle-2e^{-i\theta^{\perp}}\cos\lparen% \gamma\rparen\lvert\psi\rangle+4e^{i\left\lparen\theta-\theta^{\perp}\right% \rparen}\sin\lparen\gamma\rparen\cos\lparen\gamma\rparen\lvert\varphi\rangle$	(37)
	$\displaystyle=2e^{i\left\lparen\theta-\theta^{\perp}\right\rparen}\sin\lparen% \gamma\rparen\cos\lparen\gamma\rparen\lvert\varphi\rangle+\left\lparen 1-2\cos% ^{2}\lparen\gamma\rparen\right\rparen\lvert\varphi^{\perp}\rangle$	(38)
	$\displaystyle=e^{i\left\lparen\theta-\theta^{\perp}\right\rparen}\sin\lparen 2% \gamma\rparen\lvert\varphi\rangle-\cos\lparen 2\gamma\rparen\lvert\varphi^{% \perp}\rangle.$	(39)

Combining the above, we can verify the following identity:

$\displaystyle R_{\varphi}R_{\psi}\lvert\Phi_{\pm}\rangle$	$\displaystyle=\frac{1}{\sqrt{2}}R_{\varphi}R_{\psi}\left\lparen\lvert\varphi% \rangle\pm e^{i\left\lparen\theta^{\perp}-\theta+\frac{\pi}{2}\right\rparen}% \lvert\varphi^{\perp}\rangle\right\rparen$	(40)
	$\displaystyle=\frac{1}{\sqrt{2}}\left\lparen R_{\varphi}R_{\psi}\lvert\varphi% \rangle\pm e^{i\left\lparen\theta^{\perp}-\theta+\frac{\pi}{2}\right\rparen}R_% {\varphi}R_{\psi}\lvert\varphi^{\perp}\rangle\right\rparen$	(41)
	$\displaystyle=\frac{1}{\sqrt{2}}\Big[\left\lparen-\cos\lparen 2\gamma\rparen% \lvert\varphi\rangle-e^{i\left\lparen\theta^{\perp}-\theta\right\rparen}\sin% \lparen 2\gamma\rparen\lvert\varphi^{\perp}\rangle\right\rparen$
	$\displaystyle\qquad\pm\left\lparen i\sin\lparen 2\gamma\rparen\lvert\varphi% \rangle-e^{i\left\lparen\theta^{\perp}-\theta+\frac{\pi}{2}\right\rparen}\cos% \lparen 2\gamma\rparen\lvert\varphi^{\perp}\rangle\right\rparen\Big]$	(42)
	$\displaystyle=\frac{1}{\sqrt{2}}\left\lparen e^{i\left\lparen\pi\mp 2\gamma% \right\rparen}\lvert\varphi\rangle\pm e^{i\left\lparen\theta^{\perp}-\theta+% \frac{3}{2}\pi\mp 2\gamma\right\rparen}\lvert\varphi^{\perp}\rangle\right\rparen$	(43)
	$\displaystyle=e^{i\left\lparen\pi\mp 2\gamma\right\rparen}\lvert\Phi_{\pm}\rangle,$	(44)

where the third equality is due to Equations 34 and 39. $\hfill\blacktriangleleft$

5.2 A meta-algorithm

We observe the identity

\lvert\varphi\rangle=\frac{1}{\sqrt{2}}\big\lparen\lvert\Phi_{+}\rangle+\lvert% \Phi_{-}\rangle\big\rparen,

(45)

where $\lvert\Phi_{\pm}\rangle$ are defined by Equation 24 and are eigenvectors of $R_{\varphi}R_{\psi}$ as shown in Lemma 8. We provide a meta-algorithm by performing the quantum phase estimation of $R_{\varphi}R_{\psi}$ on the quantum state $\lvert\varphi\rangle$ , as shown in Figure 2.

Lemma 9.

Suppose that $\varepsilon,\delta\in\lparen 0,1\rparen$ . Let $t=\Theta\lparen\log\lparen 1/\varepsilon\delta\rparen\rparen$ . After measuring the first $t$ qubits of $\mathsf{QPE}_{\varepsilon,\delta}^{R_{\varphi}R_{\psi}}\lvert 0\rangle^{% \otimes t}\lvert\varphi\rangle$ in the computational basis (followed by proper classical postprocessing), with probability at least $1-\varepsilon$ we will obtain a real number $\tilde{\gamma}\in[0,1)$ such that

	$\displaystyle\bigg\lvert\left\lvert\sin\left\lparen\pi\tilde{\gamma}-\frac{\pi% }{2}\right\rparen\right\rvert-\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi% \rangle\rparen\bigg\rvert$	$\displaystyle<\pi\delta,$		(46)
	$\displaystyle\bigg\lvert\left\lvert\cos\left\lparen\pi\tilde{\gamma}-\frac{\pi% }{2}\right\rparen\right\rvert-\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi% \rangle\rparen\bigg\rvert$	$\displaystyle<\pi\delta.$		(47)

Proof.

We first consider the special case that $\lvert\varphi\rangle=\lvert\psi\rangle$ (up to a global phase), i.e., $\big\lvert\langle\varphi|\psi\rangle\big\rvert=1$ . In this case, $R_{\varphi}R_{\psi}=I$ is the identity operator and $\lvert\varphi\rangle$ is an eigenvector of $R_{\varphi}R_{\psi}$ with eigenvalue $1$ . Thus the quantum phase estimation procedure of $\mathsf{QPE}_{\varepsilon,\delta}^{R_{\varphi}R_{\psi}}\lvert 0\rangle^{% \otimes t}\lvert\varphi\rangle$ will return $\tilde{\gamma}=0$ with certainty. By simple calculations, we can verify that $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=1=\left\lvert% \sin\left\lparen\pi\tilde{\gamma}-\frac{\pi}{2}\right\rparen\right\rvert$ and $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=0=\left\lvert% \cos\left\lparen\pi\tilde{\gamma}-\frac{\pi}{2}\right\rparen\right\rvert$ .

In the rest of this proof, we consider the general case that $\lvert\varphi\rangle\neq\lvert\psi\rangle$ (up to a global phase), i.e., $\big\lvert\langle\varphi|\psi\rangle\big\rvert\neq 1$ . By Lemma 8, the eigenvalue of $\lvert\Phi_{\pm}\rangle$ with respect to the unitary operator $R_{\varphi}R_{\psi}$ is $e^{i\lparen\pi\mp 2\gamma\rparen}$ , where $\gamma=\arcsin\lparen\lvert\langle\varphi|\psi\rangle\rvert\rparen$ . By Theorem 6, we have

	$\displaystyle\mathsf{QPE}_{\varepsilon,\delta}^{R_{\varphi}R_{\psi}}\lvert 0% \rangle^{\otimes t}\lvert\varphi\rangle$	$\displaystyle=\frac{1}{\sqrt{2}}\left\lparen\mathsf{QPE}_{\varepsilon,\delta}^% {R_{\varphi}R_{\psi}}\lvert 0\rangle^{\otimes t}\lvert\Phi_{+}\rangle+\mathsf{% QPE}_{\varepsilon,\delta}^{R_{\varphi}R_{\psi}}\lvert 0\rangle^{\otimes t}% \lvert\Phi_{-}\rangle\right\rparen$		(48)
		$\displaystyle=\frac{1}{\sqrt{2}}\left\lparen\lvert\tilde{\gamma}_{+}\rangle% \lvert\Phi_{+}\rangle+\lvert\tilde{\gamma}_{-}\rangle\lvert\Phi_{-}\rangle% \right\rparen,$		(49)

where if we measure the first $t$ qubits, then with probability at least $1-\varepsilon$ we will obtain a real number $\tilde{\gamma}\in[0,1)$ satisfying at least one of the following two inequalities:

	$\displaystyle\min\left\{\left\lvert\tilde{\gamma}-\left\lparen\frac{1}{2}-% \frac{\gamma}{\pi}\right\rparen\right\rvert,1-\left\lvert\tilde{\gamma}-\left% \lparen\frac{1}{2}-\frac{\gamma}{\pi}\right\rparen\right\rvert\right\}<\delta,$		(50)
	$\displaystyle\min\left\{\left\lvert\tilde{\gamma}-\left\lparen\frac{1}{2}+% \frac{\gamma}{\pi}\right\rparen\right\rvert,1-\left\lvert\tilde{\gamma}-\left% \lparen\frac{1}{2}+\frac{\gamma}{\pi}\right\rparen\right\rvert\right\}<\delta.$		(51)

To see Equation 46, we note that $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\sin\lparen\gamma\rparen$ and

$\displaystyle\bigg\lvert\left\lvert\sin\left\lparen\pi\tilde{\gamma}-\frac{\pi% }{2}\right\rparen\right\rvert-\sin\lparen\gamma\rparen\bigg\rvert$	$\displaystyle\leq\min\left\{\left\lvert\sin\left\lparen\pi\tilde{\gamma}-\frac% {\pi}{2}\right\rparen-\sin\lparen\gamma\rparen\right\rvert,\left\lvert\sin% \left\lparen\pi\tilde{\gamma}+\frac{\pi}{2}\right\rparen-\sin\lparen\gamma% \rparen\right\rvert\right\}$	(52)
	$\displaystyle\leq\min\Big\{\left\lvert\left\lparen\pi\tilde{\gamma}-\frac{\pi}% {2}\right\rparen-\gamma\right\rvert,\pi-\left\lvert\left\lparen\pi\tilde{% \gamma}-\frac{\pi}{2}\right\rparen-\gamma\right\rvert,$
	$\displaystyle\qquad\qquad\left\lvert\left\lparen\pi\tilde{\gamma}+\frac{\pi}{2% }\right\rparen-\gamma\right\rvert,\pi-\left\lvert{\left\lparen\pi\tilde{\gamma% }+\frac{\pi}{2}\right\rparen-\gamma}\right\rvert\Big\}$	(53)
	$\displaystyle<\pi\delta,$	(54)

where the third inequality is because $\tilde{\gamma}$ satisfies either Equation 50 or Equation 51. To see Equation 47, we note that $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen=\cos\lparen\gamma\rparen$ and similarly we have

$\displaystyle\bigg\lvert\left\lvert\cos\left\lparen\pi\tilde{\gamma}-\frac{\pi% }{2}\right\rparen\right\rvert-\cos\lparen\gamma\rparen\bigg\rvert$	$\displaystyle\leq\min\left\{\left\lvert\sin\left\lparen\pi\tilde{\gamma}\right% \rparen-\sin\left\lparen\gamma+\frac{\pi}{2}\right\rparen\right\rvert,\left% \lvert\sin\left\lparen\pi\tilde{\gamma}+\pi\right\rparen-\sin\left\lparen% \gamma+\frac{\pi}{2}\right\rparen\right\rvert\right\}$	(55)
	$\displaystyle\leq\min\Big\{\left\lvert\pi\tilde{\gamma}-\left\lparen\gamma+% \frac{\pi}{2}\right\rparen\right\rvert,\pi-\left\lvert\pi\tilde{\gamma}-\left% \lparen\gamma+\frac{\pi}{2}\right\rparen\right\rvert,$
	$\displaystyle\qquad\qquad\left\lvert\left\lparen\pi\tilde{\gamma}+\pi\right% \rparen-\left\lparen\gamma+\frac{\pi}{2}\right\rparen\right\rvert,\pi-\left% \lvert\left\lparen\pi\tilde{\gamma}+\pi\right\rparen-\left\lparen\gamma+\frac{% \pi}{2}\right\rparen\right\rvert\Big\}$	(56)
	$\displaystyle<\pi\delta.$	(57)

$\hfill\blacktriangleleft$

We restate Lemma 9 with normalized additive error in the following corollary, which will be used as a subroutine in Section 7.

Corollary 10.

Suppose that $\varepsilon,\delta\in\lparen 0,1\rparen$ . Let $t=\Theta\lparen\log\lparen 1/\varepsilon\delta\rparen\rparen$ . We can estimate the trace distance and square root fidelity between $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ to within additive error $\delta$ with probability at least $1-\varepsilon$ by measuring the first $t$ qubits of $\mathsf{QPE}_{\varepsilon,\frac{\delta}{\pi}}^{R_{\varphi}R_{\psi}}\lvert 0% \rangle^{\otimes t}\lvert\varphi\rangle$ in the computational basis (followed by proper classical postprocessing).

6 Samplizer for Pure States

In this section, we define the samplizer for pure states and then provide an efficient implementation for it. Roughly speaking, a samplizer converts a quantum query algorithm to a quantum sample algorithm, where the query oracle and the sample of quantum states are related.

6.1 Definition

In our case of pure states, we consider the reflection oracle for pure states, defined as follows.

Definition 11 (Reflection oracle for pure states).

Let $\lvert\psi\rangle$ be a pure quantum state. The reflection oracle for $\lvert\psi\rangle$ is defined to be $R_{\psi}=I-2\lvert\psi\rangle\!\langle\psi\rvert$ .

We give the definition of (multi-)samplizer for pure states in terms of reflection oracles as follows.

Definition 12 (Multi-samplizer for pure states).

A $k$ -samplizer for $n$ -qubit pure states, denoted as $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ , is a converter from a quantum circuit family to a quantum channel family such that: for any $\delta>0$ , quantum circuit family $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ with query access to $n$ -qubit unitary operators $U_{1},U_{2},\dots,U_{k}$ , and $n$ -qubit pure states $\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert\psi_{k}\rangle$ ,

\left\lVert\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{A}^{U_{1}% ,U_{2},\dots,U_{k}}\rangle[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,% \lvert\psi_{k}\rangle]-\mathcal{A}^{R_{\psi_{1}},R_{\psi_{2}},\dots,R_{\psi_{k% }}}\right\rVert_{\diamond}\leq\delta.

(58)

The sample complexity of $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ is a $k$ -tuple $\lparen\mathsf{S}_{1},\mathsf{S}_{2},\dots,\mathsf{S}_{k}\rparen$ for $\lparen k+1\rparen$ -ary functions $\mathsf{S}_{j}\lparen x_{1},x_{2},\dots,x_{k};y\rparen$ such that if $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ uses $Q_{j}$ queries to $U_{j}$ for each $1\leq j\leq k$ , then $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\rangle[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert% \psi_{k}\rangle]$ uses $\mathsf{S}_{j}\lparen Q_{1},Q_{2},\dots,Q_{k};\delta\rparen$ samples of $\lvert\psi_{j}\rangle$ for each $1\leq j\leq k$ . Especially when $k=1$ , we write $\mathsf{S}\lparen x,y\rparen\coloneqq\mathsf{S}_{1}\lparen x;y\rparen$ for convenience.

Similarly, we can also define the (additional) time complexity of $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ as a $\lparen k+1\rparen$ -ary function $\mathsf{T}\lparen x_{1},x_{2},\dots,x_{k};y\rparen$ such that if $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ uses $Q_{j}$ queries to $U_{j}$ for each $1\leq j\leq k$ , then $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\rangle[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,\lvert% \psi_{k}\rangle]$ can be implemented by using $T_{\mathcal{A}}+\mathsf{T}\lparen Q_{1},Q_{2},\dots,Q_{k};\delta\rparen$ two-qubit gates, where $T_{\mathcal{A}}$ is the number of two-qubit gates in $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ (excluding queries). Especially when $k=1$ , we write $\mathsf{T}\lparen x,y\rparen\coloneqq\mathsf{T}\lparen x;y\rparen$ for convenience.

Our algorithms for trace distance and fidelity estimation employ a $2$ -samplizer for pure states, which will be formally described in Section 7. Our definition of samplizer for pure states is inspired by the general samplizer defined in [43], where the latter simulates quantum query algorithms with query access to block-encoding oracles for quantum states. Here, the block-encoding oracle input model is standard in quantum algorithms, e.g., Hamiltonian simulation [15] and solving systems of linear equations [12]. It is worth noting that for pure states, the reflection oracle is computationally equivalent to the block-encoding oracle up to a constant factor (cf. [11, Lemma 5.5]). The relationship between the samplizer for pure states and the general samplizer is further discussed in [42, Appendix A].

6.2 An efficient approach

We provide an efficient approach to the multi-samplizer for pure states as follows.

Theorem 13.

There is a $k$ -samplizer for $n$ -qubit pure states, $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ , with sample complexity $\lparen\mathsf{S}_{1},\mathsf{S}_{2},\dots,\mathsf{S}_{k}\rparen$ , where

\mathsf{S}_{j}\lparen Q_{1},Q_{2},\dots,Q_{k};\delta\rparen=O\left\lparen\frac% {Q_{j}}{\delta}\cdot\sum_{i=1}^{k}Q_{i}\right\rparen.

(59)

Moreover, if a quantum query algorithm $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ uses $Q_{j}$ queries to $U_{j}$ for $1\leq j\leq k$ , then the (additional) time complexity (compared to the original $\mathcal{A}^{U_{1},U_{2},\dots,U_{k}}$ ) of $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\rangle$ is

\mathsf{T}\lparen Q_{1},Q_{2},\dots,Q_{k};\delta\rparen=O\left\lparen\frac{n}{% \delta}\left\lparen\sum_{j=1}^{k}Q_{j}\right\rparen^{2}\right\rparen.

(60)

Proof.

Let $Q\coloneqq\sum_{i=1}^{k}Q_{i}$ . For each $1\leq j\leq k$ , by Theorem 7 with $t\coloneqq\pi$ and $\delta\coloneqq\delta/Q$ , we can use $O\lparen Q/\delta\rparen$ samples of $\lvert\psi_{j}\rangle$ and $O\lparen nQ/\delta\rparen$ one- and two-qubit quantum gates to implement a quantum channel $\mathcal{E}_{j}$ that is $\lparen\delta/Q\rparen$ -close (in diamond norm) to (the controlled version of) the following unitary transformation

e^{i\lvert\psi_{j}\rangle\!\langle\psi_{j}\rvert\pi}=I-2\lvert\psi_{j}\rangle% \!\langle\psi_{j}\rvert=R_{\psi_{j}}.

(61)

That is,

\left\lVert\mathcal{E}_{j}-R_{\psi_{j}}\right\rVert_{\diamond}\leq\frac{\delta% }{Q}.

(62)

Suppose that the quantum circuit $\mathcal{A}^{R_{\psi_{1}},R_{\psi_{2}},\dots,R_{\psi_{k}}}$ using queries to $R_{\psi_{1}},R_{\psi_{2}},\dots,R_{\psi_{k}}$ is composed of a sequence of unitary operators:

\mathcal{A}^{R_{\psi_{1}},R_{\psi_{2}},\dots,R_{\psi_{k}}}=G_{Q}\circ\mathcal{% O}_{Q}\circ\dots\circ G_{2}\circ\mathcal{O}_{2}\circ G_{1}\circ\mathcal{O}_{1}% \circ G_{0},

(63)

where $G_{q}$ for each $1\leq q\leq Q$ can be implemented by one- and two-qubit quantum gates that do not depend on $R_{\psi_{1}},R_{\psi_{2}},\dots,R_{\psi_{k}}$ , and $\mathcal{O}_{q}$ for each $1\leq q\leq Q$ is (the controlled version of) $R_{\psi_{j_{q}}}$ for some $1\leq j_{q}\leq k$ . Then, we can implement $\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\big\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\big\rangle\big[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,% \lvert\psi_{k}\rangle\big]$ as follows

\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\big\langle\mathcal{A}^{U_{1},U_{2},% \dots,U_{k}}\big\rangle\big[\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\dots,% \lvert\psi_{k}\rangle\big]\coloneqq G_{Q}\circ\mathcal{E}_{j_{Q}}\circ\dots% \circ G_{2}\circ\mathcal{E}_{j_{2}}\circ G_{1}\circ\mathcal{E}_{j_{1}}\circ G_% {0}.

(64)

As $\lVert\mathcal{E}_{j_{q}}-R_{\psi_{j_{q}}}\rVert_{\diamond}\leq\delta/Q$ for each $1\leq q\leq Q$ , we conclude that

\left\lVert\mathsf{Samplize}^{\mathsf{pure}}_{\delta}\big\langle\mathcal{A}^{U% _{1},U_{2},\dots,U_{k}}\big\rangle\big[\lvert\psi_{1}\rangle,\lvert\psi_{2}% \rangle,\dots,\lvert\psi_{k}\rangle\big]-\mathcal{A}^{R_{\psi_{1}},R_{\psi_{2}% },\dots,R_{\psi_{k}}}\right\rVert_{\diamond}\leq\delta.

(65)

Therefore, the implementation given in Equation 64 is a valid $k$ -samplizer for pure states.

We analyze the complexity of this implementation as follows. Since there are $Q_{j}$ queries to $R_{\psi_{j}}$ among $\mathcal{O}_{1},\mathcal{O}_{2},\dots,\mathcal{O}_{Q}$ , the number of samples of $\lvert\psi_{j}\rangle$ used in the implementation defined by Equation 64 is

Q_{j}\cdot O\left\lparen\frac{Q}{\delta}\right\rparen=O\left\lparen\frac{Q_{j}% Q}{\delta}\right\rparen.

(66)

Moreover, the number of one- and two-qubit quantum gates used in this implementation in addition to (the implementation of) $G_{1},G_{2},\dots,G_{Q}$ is

\sum_{i=1}^{k}Q_{i}\cdot O\left\lparen\frac{nQ}{\delta}\right\rparen=O\left% \lparen\frac{nQ^{2}}{\delta}\right\rparen.

(67)

$\hfill\blacktriangleleft$

7 The Algorithm

In this section, we present a complete description of our quantum algorithm for pure-state trace distance and fidelity estimations in Algorithm 1, which combines the estimation algorithm using reflection oracles in Section 5 with the multi-samplizer for pure states in Section 6.

Algorithm 1 Quantum estimator for pure-state trace distance and fidelity estimations.

We state the result of our final algorithm in Theorem 14.

Theorem 14.

For $\varepsilon\in\lparen 0,1\rparen$ , we can estimate the trace distance and square root fidelity between $n$ -qubit pure states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ to within additive error $\varepsilon$ with probability at least $2/3$ by measuring the first $t$ qubits of

\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}}\big\langle\mathcal{A}^{U_{1},% U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]\big\lparen% \lvert 0\rangle\!\langle 0\rvert^{\otimes t}\otimes\lvert\varphi\rangle\!% \langle\varphi\rvert\big\rparen

(68)

in the computational basis (followed by proper classical postprocessing), where $\mathcal{A}^{U_{1},U_{2}}\coloneqq\mathsf{QPE}_{\frac{1}{10},\frac{\varepsilon% }{\pi}}^{U_{1}U_{2}}$ and $t=\Theta\lparen\log\lparen 1/\varepsilon\rparen\rparen$ . Here, the quantum channel $\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}}\big\langle\mathcal{A}^{U_{1},% U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]$ can be implemented by using $O\lparen 1/\varepsilon^{2}\rparen$ samples of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , and using $O\lparen n/\varepsilon^{2}\rparen$ two-qubit gates.

Proof.

The formal description of our algorithm is given in Algorithm 1. Now we will prove its correctness and analyze its complexity.

Correctness.

By Corollary 10, we know that the trace distance and square root fidelity between $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ can be obtained with success probability at least $\frac{9}{10}$ by measuring the first $t$ qubits of the state $\mathsf{QPE}^{R_{\varphi}R_{\psi}}_{\frac{1}{10},\frac{\varepsilon}{\pi}}% \lvert 0\rangle^{\otimes t}\lvert\varphi\rangle$ (followed by proper classical postprocessing). Thus we only have to show that the quantum state defined by Equation 68 is close to the pure quantum state $\mathsf{QPE}^{R_{\varphi}R_{\psi}}_{\frac{1}{10},\frac{\varepsilon}{\pi}}% \lvert 0\rangle^{\otimes t}\lvert\varphi\rangle$ . To this end, by Definition 12, we have

\left\lVert\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}}\big\langle\mathcal% {A}^{U_{1},U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]-% \mathsf{QPE}^{R_{\varphi}R_{\psi}}_{\frac{1}{10},\frac{\varepsilon}{\pi}}% \right\rVert_{\diamond}\leq\frac{1}{10}.

(69)

By applying each of them on the quantum state $\Psi\coloneqq\lvert 0\rangle\!\langle 0\rvert^{\otimes t}\otimes\lvert\varphi% \rangle\!\langle\varphi\rvert$ , we have

\mathrm{\mathsf{T}}\left\lparen\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}% }\big\langle\mathcal{A}^{U_{1},U_{2}}\big\rangle\big[\lvert\varphi\rangle,% \lvert\psi\rangle\big]\big\lparen\Psi\big\rparen,\mathsf{QPE}^{R_{\varphi}R_{% \psi}}_{\frac{1}{10},\frac{\varepsilon}{\pi}}\Psi\left\lparen\mathsf{QPE}^{R_{% \varphi}R_{\psi}}_{\frac{1}{10},\frac{\varepsilon}{\pi}}\right\rparen^{\dagger% }\right\rparen\leq\frac{1}{20}.

(70)

Therefore, the probability distribution of the outcomes from measuring (in the computational basis) the state $\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}}\big\langle\mathcal{A}^{U_{1},% U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]\big\lparen% \Psi\big\rparen$ is $\frac{1}{10}$ -close (in total variation distance) to that from measuring the state $\mathsf{QPE}^{R_{\varphi}R_{\psi}}_{\frac{1}{10},\frac{\varepsilon}{\pi}}% \lvert 0\rangle^{\otimes t}\lvert\varphi\rangle$ (in the computational basis). This implies that the success probability of Algorithm 1 is at least $\frac{9}{10}-\frac{1}{10}>\frac{2}{3}$ .

Complexity.

By Theorem 6 with $\varepsilon\coloneqq\frac{1}{10}$ and $\delta\coloneqq\frac{\varepsilon}{\pi}$ , the quantum query algorithm $\mathcal{A}^{U_{1},U_{2}}\coloneqq\mathsf{QPE}_{\frac{1}{10},\frac{\varepsilon% }{\pi}}^{U_{1}U_{2}}$ uses $O\lparen 1/\varepsilon\rparen$ queries to each of $U_{1}$ and $U_{2}$ , and uses $O\lparen\log\lparen 1/\varepsilon\rparen\log\log\lparen 1/\varepsilon\rparen\rparen$ two-qubit gates (due to the quantum Fourier transform). By the implementation of the multi-samplizer for pure states given in Theorem 13 with $\delta\coloneqq\frac{1}{10}$ and $Q_{1}=Q_{2}\coloneqq O\lparen 1/\varepsilon\rparen$ , we can implement the quantum channel $\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}}\big\langle\mathcal{A}^{U_{1},% U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]$ by using $O\lparen 1/\varepsilon^{2}\rparen$ samples of each of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ . In addition, we also use one sample of $\lvert\varphi\rangle$ as (part of) the input of the quantum channel $\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{10}}\big\langle\mathcal{A}^{U_{1},% U_{2}}\big\rangle\big[\lvert\varphi\rangle,\lvert\psi\rangle\big]$ . In total, we use $O\lparen 1/\varepsilon^{2}\rparen$ samples of $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ . Moreover, Algorithm 1 can be implemented by using

O\left\lparen\log\left\lparen\frac{1}{\varepsilon}\right\rparen\log\log\left% \lparen\frac{1}{\varepsilon}\right\rparen\right\rparen+O\left\lparen\frac{n}{% \varepsilon^{2}}\right\rparen=O\left\lparen\frac{n}{\varepsilon^{2}}\right\rparen

(71)

one- and two-qubit quantum gates, if $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ are $n$ -qubit pure quantum states. $\hfill\blacktriangleleft$

8 Optimality

In this section, we first mention the matching lower bounds for pure-state trace distance and fidelity estimations in Section 8.1, and then show a matching lower bound for the implementation of multi-samplizer for pure states in Section 8.2.

8.1 Lower bounds for pure-state trace distance and fidelity estimations

For completeness, we collect the sample complexity lower bounds for estimating pure-state trace distance and fidelity in the following theorem.

Theorem 15 (Sample complexity lower bounds for pure-state closeness estimation, adapted from [1, 39]).

Given sample access to two single-qubit pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , it is necessary to use $\Omega\lparen 1/\varepsilon^{2}\rparen$ samples of them to $\varepsilon$ -estimate

(1)

the trace distance $\mathrm{T}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ for $\varepsilon\in\lparen 0,1\rparen$ ,
(2)

the square root fidelity $\mathrm{F}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ for $\varepsilon\in\lparen 0,1/4\rparen$ .
(3)

the squared fidelity $\mathrm{F}^{2}\lparen\lvert\varphi\rangle,\lvert\psi\rangle\rparen$ for $\varepsilon\in\lparen 0,1/2\rparen$ ,

Proof.

Items 2 and 3 are directly implied by [1, Lemma 13 in the full version]. It remains to prove Item 1.

The sample complexity lower bound for pure-state trace distance estimation was already shown in [39, Theorem B.2] for $\varepsilon\in\lparen 0,1/2\rparen$ . Here, we strengthen the lower bound to encompass a more general case that $\varepsilon\in\lparen 0,1\rparen$ and both the states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ are single-qubit, with a simple proof. To this end, we denote

\lvert\psi_{x}\rangle=\sqrt{1-x^{2}}\lvert 0\rangle+x\lvert 1\rangle

(72)

for $x\in[0,1]$ . Let $\varepsilon\in\lparen 0,1\rparen$ . Consider the following quantum hypothesis testing problem:

$\blacksquare$

Given an unknown pure quantum state $\lvert\varphi\rangle$ , determine whether $\lvert\varphi\rangle$ is $\lvert\psi_{0}\rangle$ or $\lvert\psi_{\varepsilon}\rangle$ , under the promise that $\lvert\varphi\rangle$ is in either case with equal probability.

The trace distance between $\lvert\psi_{0}\rangle$ and $\lvert\psi_{\varepsilon}\rangle$ is

\mathrm{T}\left\lparen\lvert\psi_{0}\rangle,\lvert\psi_{\varepsilon}\rangle% \right\rparen=\sqrt{1-\left\lvert\langle\psi_{0}|\psi_{\varepsilon}\rangle% \right\rvert^{2}}=\varepsilon.

(73)

By the Holevo-Helstrom bound for quantum state discrimination [24, 23], we know that the above quantum hypothesis testing problem requires sample complexity $\Omega\lparen 1/\varepsilon^{2}\rparen$ . On the other hand, any estimator for pure-state trace distance with additive error $\varepsilon$ can be used to solve this task, thereby also requiring sample complexity $\Omega\lparen 1/\varepsilon^{2}\rparen$ . $\hfill\blacktriangleleft$

8.2 Lower bounds for (multi-)samplizers for pure states

It is trivial that for any $k\geq 1$ , any $\lparen k+1\rparen$ -samplizer for pure states can be used to implement a $k$ -samplizer for pure states with the same sample complexity (by discarding the last pure state). To show the optimality of the multi-samplizer for pure states given in Theorem 13, it is sufficient to show the optimality of the $1$ -samplizer, given as follows.

Theorem 16.

For sufficiently large $Q$ and every $\delta\in\lparen 0,1/9\rparen$ , any $1$ -samplizer for $n$ -qubit pure states requires sample complexity $\mathsf{S}\lparen Q,\delta\rparen=\Omega\lparen Q^{2}/\delta\rparen$ .

Although the lower bound given in Theorem 16 for the $1$ -samplizer for pure states is of the same order as the lower bound $\Omega\lparen Q^{2}/\delta\rparen$ for the general samplizer given in [43, Theorem III.4], we emphasize that prior lower bounds do not imply our lower bound in Theorem 16. We discuss related lower bounds as follows.

1.

The lower bound $\Omega\lparen Q^{2}/\delta\rparen$ for general samplizer given in [43, Theorem III.4] is by reducing from the sample-based Hamiltonian simulation [26] via the optimal quantum query algorithm for Hamiltonian simulation [15] for time $t=\Theta\lparen Q\rparen$ . The sample-based Hamiltonian simulation is a task for implementing $e^{-i\rho t}$ with precision $\delta$ using samples of $\rho$ . A lower bound $O\lparen t^{2}/\delta\rparen$ on the sample complexity of sample-based Hamiltonian simulation is given in [26, Theorem 2], which is further reduced from distinguishing two mixed quantum states $\rho\lparen\frac{1}{2}\rparen$ and $\rho\lparen\frac{1}{2}+\Theta\lparen\frac{1}{t}\rparen\rparen$ , where $\rho\lparen x\rparen=x\lvert 0\rangle\!\langle 0\rvert+\lparen 1-x\rparen% \lvert 1\rangle\!\langle 1\rvert$ . However, this reduction does not directly apply to the case of pure states.
2.

One may wonder what happens if we consider the sample-based Hamiltonian simulation for pure states. Note that the unitary operator $e^{-i\lvert\psi\rangle\!\langle\psi\rvert t}$ is periodic with respect to $t$ as $e^{-i\lvert\psi\rangle\!\langle\psi\rvert 2\pi}=I$ . So the above idea will result in a lower bound of $\mathsf{S}\lparen Q,\delta\rparen=\Omega\lparen 1/\delta\rparen$ for $1$ -samplizer by taking $Q=\Theta\lparen t\rparen=\Theta\lparen 1\rparen$ , due to the lower bound $\Omega\lparen 1/\delta\rparen$ given in [26, Theorem 4] for implementing $e^{-i\lvert\psi\rangle\!\langle\psi\rvert t}$ for constant $t$ with precision $\delta$ .

Interestingly, our proof of Theorem 16 is based on a reduction from the pure-state trace distance estimation (whose lower bounds are previously presented in Section 8.1) instead of the sample-based Hamiltonian simulation [26].

Proof of Theorem 16.

Let $\mathcal{A}^{U_{1},U_{2}}_{\varepsilon}\coloneqq\mathsf{QPE}_{\frac{1}{10},% \frac{\varepsilon}{\pi}}^{U_{1}U_{2}}$ . Then, by Corollary 10, measuring the quantum state $\mathcal{A}^{R_{\varphi},R_{\psi}}_{\varepsilon}\lvert 0\rangle^{\otimes t}% \lvert\varphi\rangle$ can estimate the trace distance between two pure quantum states $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ to within additive error $\varepsilon$ with query complexity $O\lparen 1/\varepsilon\rparen$ , where $R_{\varphi}$ and $R_{\psi}$ are the reflection oracles for $\lvert\varphi\rangle$ and $\lvert\psi\rangle$ , respectively. Consider the two pure quantum states $\lvert\psi_{0}\rangle\coloneqq\lvert 0\rangle$ and $\lvert\psi_{\varepsilon}\rangle\coloneqq\sqrt{1-\varepsilon^{2}}\lvert 0% \rangle+\varepsilon\lvert 1\rangle$ employed in Theorem 15, where $\varepsilon\in\lparen 0,1\rparen$ . Note that the reflection oracle $R_{\psi_{0}}=I-2\lvert 0\rangle\!\langle 0\rvert$ for $\lvert\psi_{0}\rangle$ is constant (with respect to $\varepsilon$ ). Then, measuring $\mathcal{A}^{R_{\psi_{0}},R_{\psi_{\varepsilon}}}_{\varepsilon}\lvert 0\rangle$ (note that $\lvert\psi_{0}\rangle=\lvert 0\rangle$ ) can estimate the trace distance between $\lvert\psi_{0}\rangle$ and $\lvert\psi_{\varepsilon}\rangle$ to within additive error $\varepsilon$ with probability at least $2/3$ , using $O\lparen 1/\varepsilon\rparen$ queries to $R_{\psi_{\varepsilon}}$ . Therefore, using the quantum query algorithm $\mathcal{A}^{U_{1},U_{2}}_{\varepsilon}$ for pure-state trace distance estimation, we can obtain a quantum query algorithm $\mathcal{T}^{U}$ for distinguishing the two reflection operators $R_{\psi_{0}}$ and $R_{\psi_{\varepsilon}}$ with probability at least $2/3$ , using $O\lparen 1/\varepsilon\rparen$ queries to $U$ , promised that either $U=R_{\psi_{0}}$ or $R_{\psi_{\varepsilon}}$ . Formally, the probability that $\mathcal{T}^{U}$ accepts is given by $\lVert\Pi\mathcal{T}^{U}\lvert 0\rangle\rVert^{2}$ , where $\Pi=\lvert 0\rangle\!\langle 0\rvert\otimes I$ measures the first qubits. Then,

$\blacksquare$

$\mathcal{T}^{R_{\psi_{0}}}$ accepts with probability at least $2/3$ ;
$\blacksquare$

$\mathcal{T}^{R_{\psi_{\varepsilon}}}$ accepts with probability at most $1/3$ .

Let $\mathsf{Samplize}^{\mathsf{pure}}_{*}\langle*\rangle$ be any $1$ -samplizer with sample complexity $\mathsf{S}\lparen Q,\delta\rparen$ . Then, $\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{9}}\langle\mathcal{T}^{U}\rangle$ is a quantum channel family with sample complexity $\mathsf{S}\lparen\Theta\lparen 1/\varepsilon\rparen,1/9\rparen$ such that

$\blacksquare$

$\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{9}}\big\langle\mathcal{T}^{U}\big% \rangle\big[\lvert\psi_{0}\rangle\big]\big\lparen\lvert 0\rangle\!\langle 0% \rvert\big\rparen$ accepts with probability

$\operatorname{tr}\left\lparen\Pi\cdot\mathsf{Samplize}^{\mathsf{pure}}_{\frac{% 1}{9}}\big\langle\mathcal{T}^{U}\big\rangle\big[\lvert\psi_{0}\rangle\big]\big% \lparen\lvert 0\rangle\!\langle 0\rvert\big\rparen\right\rparen\geq\frac{2}{3}% -\frac{1}{9}=\frac{5}{9},$ (74)
$\blacksquare$

$\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{9}}\big\langle\mathcal{T}^{U}\big% \rangle\big[\lvert\psi_{\varepsilon}\rangle\big]\big\lparen\lvert 0\rangle\!% \langle 0\rvert\big\rparen$ accepts with probability

$\operatorname{tr}\left\lparen\Pi\cdot\mathsf{Samplize}^{\mathsf{pure}}_{\frac{% 1}{9}}\big\langle\mathcal{T}^{U}\big\rangle\big[\lvert\psi_{\varepsilon}% \rangle\big]\big\lparen\lvert 0\rangle\!\langle 0\rvert\big\rparen\right% \rparen\leq\frac{1}{3}+\frac{1}{9}=\frac{4}{9}.$ (75)

Therefore, if $\lvert\varphi\rangle$ is promised to be either $\lvert\psi_{0}\rangle$ or $\lvert\psi_{\varepsilon}\rangle$ , then, by a constant number (say, $9$ ) of repetitions of $\mathsf{Samplize}^{\mathsf{pure}}_{\frac{1}{9}}\langle\mathcal{T}^{U}\rangle$ on input $\lvert\varphi\rangle$ , we can determine with probability at least $2/3$ which is the case (by majority voting). This means that we can distinguish $\lvert\psi_{0}\rangle$ and $\lvert\psi_{\varepsilon}\rangle$ with probability at least $2/3$ with sample complexity $9\cdot\mathsf{S}\lparen\Theta\lparen 1/\varepsilon\rparen,1/9\rparen$ . On the other hand, using the same arguments as in Theorem 15, we know that distinguishing $\lvert\psi_{0}\rangle$ and $\lvert\psi_{\varepsilon}\rangle$ requires sample complexity $\Omega\lparen 1/\varepsilon^{2}\rparen$ . These together imply that $9\cdot\mathsf{S}\lparen\Theta\lparen 1/\varepsilon\rparen,1/9\rparen\geq\Omega% \lparen 1/\varepsilon^{2}\rparen$ . Since the choice of $\varepsilon\in(0,1)$ is arbitrary, by letting $Q=\Theta\lparen 1/\varepsilon\rparen$ , we further have the relation

\mathsf{S}\left\lparen Q,\frac{1}{9}\right\rparen\geq c\cdot Q^{2}

(76)

for sufficiently large $Q$ , where $c>0$ is a universal constant. This is the desired inequality for the case of constant $\delta$ .

To show the inequality for arbitrarily small $\delta$ , we note that $\mathsf{S}\lparen Q,\delta\rparen$ satisfies:

\mathsf{S}\left\lparen Q_{1}+Q_{2},\delta_{1}+\delta_{2}\right\rparen\leq% \mathsf{S}\left\lparen Q_{1},\delta_{1}\right\rparen+\mathsf{S}\left\lparen Q_% {2},\delta_{2}\right\rparen

(77)

for any integers $Q_{1},Q_{2}\geq 0$ and real numbers $\delta_{0},\delta_{1}\in(0,1)$ . This is because: to samplize any quantum query algorithm with $Q_{1}+Q_{2}$ queries to precision $\delta_{1}+\delta_{2}$ , one can always first samplize the first part of $Q_{1}$ queries to precision $\delta_{1}$ and then the second part of $Q_{2}$ queries to precision $\delta_{2}$ . Consequently, we further have the following properties:

1.

$\mathsf{S}\lparen mQ,m\delta\rparen\leq m\cdot\mathsf{S}\lparen Q,\delta\rparen$ for any integers $m,Q\geq 1$ and real number $\delta>0$ .
2.

$\mathsf{S}\lparen Q,\delta_{1}\rparen\geq\mathsf{S}\lparen Q,\delta_{2}\rparen$ for any integer $Q\geq 1$ and real numbers $0<\delta_{1}<\delta_{2}$ .

For sufficiently large $Q$ and for every $0<\delta<1/9$ , by taking $m\coloneqq\left\lfloor\frac{1}{9\delta}\right\rfloor\geq 1$ (which gives $0<m\delta\leq 1/9$ ), we have

$\displaystyle\mathsf{S}\lparen Q,\delta\rparen$	$\displaystyle\geq\frac{1}{m}\cdot\mathsf{S}\left\lparen mQ,m\delta\right\rparen$	(78)
	$\displaystyle\geq\frac{1}{m}\cdot\mathsf{S}\left\lparen mQ,\frac{1}{9}\right\rparen$	(79)
	$\displaystyle\geq\frac{1}{m}\cdot c\cdot\left\lparen mQ\right\rparen^{2}$	(80)
	$\displaystyle=c\cdot\left\lfloor\frac{1}{9\delta}\right\rfloor\cdot Q^{2}$	(81)
	$\displaystyle\geq\Omega\left\lparen\frac{Q^{2}}{\delta}\right\rparen,$	(82)

where the first inequality is due to property 1, the second inequality is due to property 2, and the third inequality is by Equation 76.

To complete the proof for general $n\geq 2$ , the hard instance can be taken as $\lvert\Psi_{0}\rangle=\lvert\psi_{0}\rangle\otimes\lvert 0\rangle^{\otimes% \lparen n-1\rparen}$ and $\lvert\Psi_{\varepsilon}\rangle=\lvert\psi_{\varepsilon}\rangle\otimes\lvert 0% \rangle^{\otimes\lparen n-1\rparen}$ . $\hfill\blacktriangleleft$

As a corollary of Theorem 16, we have a matching sample lower bound for the implementation of $k$ -samplizer for pure states for constant $k$ .

Theorem 17.

For sufficient large $Q_{j}$ for each $1\leq j\leq k$ and every $\delta\in\lparen 0,1/9\rparen$ , any $k$ -samplizer for pure states requires sample complexity

\mathsf{S}_{j}\lparen Q_{1},Q_{2},\dots,Q_{k};\delta\rparen=\Omega\left\lparen% \frac{Q_{j}^{2}}{\delta}\right\rparen

(83)

for each $1\leq j\leq k$ .

9 Conclusion

In this paper, we proposed a quantum algorithm for estimating the trace distance and square root fidelity between pure quantum states with optimal sample complexity, quadratically improving the long-standing folklore approach, answering the question raised in [39], and thereby completing the complexity picture for pure-state closeness estimation. Technically, our quantum algorithm requires new observations (the properties of the product of Householder reflections) and tools (the samplizer for pure states).

We therefore raise the following questions for future research.

1.

Can we close the gap between the upper and lower bounds on the quantum query/sample complexities of estimating the quantities of mixed quantum states such as trace distance and fidelity?
2.

Can we find more applications of the samplizer for pure states?
3.

After the distributed quantum algorithm for pure-state squared fidelity estimation in [1], the trade-off between the sample complexity and quantum communication was recently settled in [2, 17]. A further question is: what is the sample complexity of estimating the square root fidelity and trace distance between pure states with limited quantum communication?
4.

Following Question 3, can we implement a samplizer (for pure states) with distributed quantum computation or with limited quantum communication?

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] Srinivasan Arunachalam and Louis Schatzki. Generalized inner product estimation with limited quantum communication. In Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, pages 11:1–11:17, 2025. doi:10.4230/LIPIcs.STACS.2025.11.
[3] Costin Bădescu, Ryan O’Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 503–514, 2019. doi:10.1145/3313276.3316344.
[4] Joonwoo Bae and Leong-Chuan Kwek. Quantum state discrimination and its applications. Journal of Physics A: Mathematical and Theoretical, 48(8):083001, 2015. doi:10.1088/1751-8113/48/8/083001.
[5] Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello. Stabilization of quantum computations by symmetrization. SIAM Journal on Computing, 26(5):1541–1557, 1997. doi:10.1137/S0097539796302452.
[6] Stephen M. Barnett and Sarah Croke. Quantum state discrimination. Advances in Optics and Photonics, 1(2):238–278, 2009. doi:10.1364/AOP.1.000238.
[7] 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.
[8] 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.
[9] 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.
[10] Anthony Chefles. Quantum state discrimination. Contemporary Physics, 41(6):401–424, 2000. doi:10.1080/00107510010002599.
[11] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states. IEEE Transactions on Information Theory, 2026. doi:10.1109/TIT.2026.3697790.
[12] Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3(4):040303, 2022. doi:10.1103/PRXQuantum.3.040303.
[13] 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.
[14] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation. ArXiv e-prints, 2022. arXiv:2203.15993.
[15] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366.
[16] Byeongseon Go, Hyukjoon Kwon, Siheon Park, Dhrumil Patel, and Mark M. Wilde. Density matrix exponentiation and sample-based Hamiltonian simulation: Non-asymptotic analysis of sample complexity. ArXiv e-prints, 2024. arXiv:2412.02134.
[17] Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. ArXiv e-prints, 2024. doi:10.48550/arXiv.2410.12712.
[18] David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. Quantum state tomography via compressed sensing. Physical Review Letters, 105(15):150401, 2010. doi:10.1103/PhysRevLett.105.150401.
[19] Otfried Gühne, Chao-Yang Lu, Wei-Bo Gao, and Jian-Wei Pan. Toolbox for entanglement detection and fidelity estimation. Physical Review A, 76(3):030305(R), 2007. doi:10.1103/PhysRevA.76.030305.
[20] Otfried Gühne and Géza Tóth. Entanglement detection. Physics Reports, 474(1–6):1–75, 2009. doi:10.1016/j.physrep.2009.02.004.
[21] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63(9):5628–5641, 2017. doi:10.1109/TIT.2017.2719044.
[22] Lisa Hales and Sean Hallgren. An improved quantum fourier transform algorithm and applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 515–525, 2000. doi:10.1109/SFCS.2000.892139.
[23] Carl W. Helstrom. Detection theory and quantum mechanics. Information and Control, 10(3):254–291, 1967. doi:10.1016/S0019-9958(67)90302-6.
[24] Alexander S. Holevo. Statistical decision theory for quantum systems. Journal of Multivariate Analysis, 3(4):337–394, 1973. doi:10.1016/0047-259X(73)90028-6.
[25] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. doi:10.1038/s41567-020-0932-7.
[26] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(1):1–7, 2017. doi:10.1038/s41534-017-0013-7.
[27] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv e-prints, 1995. arXiv:quant-ph/9511026.
[28] 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.
[29] François Le Gall, Yupan Liu, and Qisheng Wang. Space-bounded quantum state testing via space-efficient quantum singular value transformation. Computational Complexity, 2026. doi:10.1007/s00037-025-00284-5.
[30] Nana Liu, Qisheng Wang, Mark M. Wilde, and Zhicheng Zhang. Quantum algorithms for matrix geometric means. npj Quantum Information, 11:101, 2025. doi:10.1038/s41534-025-00973-7.
[31] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631–633, 2014. doi:10.1038/nphys3029.
[32] 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.
[33] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.
[34] Ryan O’Donnell and John Wright. Efficient quantum tomography. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 899–912, 2016. doi:10.1145/2897518.2897544.
[35] Ryan O’Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics, 387(1):1–75, 2021. doi:10.1007/s00220-021-04180-1.
[36] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. doi:10.1137/S0097539795293172.
[37] Yuuki Tokunaga, Takashi Yamamoto, Masato Koashi, and Nobuyuki Imoto. Fidelity estimation and entanglement verification for experimentally produced four-qubit cluster states. Physical Review A, 74(2):020301(R), 2006. doi:10.1103/PhysRevA.74.020301.
[38] Gregory Valiant and Paul Valiant. Estimating the unseen: improved estimators for entropy and other properties. Journal of the ACM, 64(6):37:1–37:41, 2017. doi:10.1145/3125643.
[39] 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.
[40] 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.
[41] 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.
[42] 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.
[43] Qisheng Wang and Zhicheng Zhang. Time-efficient quantum entropy estimator via samplizer. IEEE Transactions on Information Theory, 71(12):9569–9599, 2025. doi:10.1109/TIT.2025.3576137.
[44] 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.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] Srinivasan Arunachalam and Louis Schatzki. Generalized inner product estimation with limited quantum communication. In Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, pages 11:1–11:17, 2025. doi:10.4230/LIPIcs.STACS.2025.11.

[bib.bib3] [3] Costin Bădescu, Ryan O’Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 503–514, 2019. doi:10.1145/3313276.3316344.

[bib.bib4] [4] Joonwoo Bae and Leong-Chuan Kwek. Quantum state discrimination and its applications. Journal of Physics A: Mathematical and Theoretical, 48(8):083001, 2015. doi:10.1088/1751-8113/48/8/083001.

[bib.bib5] [5] Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello. Stabilization of quantum computations by symmetrization. SIAM Journal on Computing, 26(5):1541–1557, 1997. doi:10.1137/S0097539796302452.

[bib.bib6] [6] Stephen M. Barnett and Sarah Croke. Quantum state discrimination. Advances in Optics and Photonics, 1(2):238–278, 2009. doi:10.1364/AOP.1.000238.

[bib.bib7] [7] 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.bib8] [8] 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.bib9] [9] 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.bib10] [10] Anthony Chefles. Quantum state discrimination. Contemporary Physics, 41(6):401–424, 2000. doi:10.1080/00107510010002599.

[bib.bib11] [11] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states. IEEE Transactions on Information Theory, 2026. doi:10.1109/TIT.2026.3697790.

[bib.bib12] [12] Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3(4):040303, 2022. doi:10.1103/PRXQuantum.3.040303.

[bib.bib13] [13] 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.bib14] [14] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation. ArXiv e-prints, 2022. arXiv:2203.15993.

[bib.bib15] [15] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366.

[bib.bib16] [16] Byeongseon Go, Hyukjoon Kwon, Siheon Park, Dhrumil Patel, and Mark M. Wilde. Density matrix exponentiation and sample-based Hamiltonian simulation: Non-asymptotic analysis of sample complexity. ArXiv e-prints, 2024. arXiv:2412.02134.

[bib.bib17] [17] Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. ArXiv e-prints, 2024. doi:10.48550/arXiv.2410.12712.

[bib.bib18] [18] David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. Quantum state tomography via compressed sensing. Physical Review Letters, 105(15):150401, 2010. doi:10.1103/PhysRevLett.105.150401.

[bib.bib19] [19] Otfried Gühne, Chao-Yang Lu, Wei-Bo Gao, and Jian-Wei Pan. Toolbox for entanglement detection and fidelity estimation. Physical Review A, 76(3):030305(R), 2007. doi:10.1103/PhysRevA.76.030305.

[bib.bib20] [20] Otfried Gühne and Géza Tóth. Entanglement detection. Physics Reports, 474(1–6):1–75, 2009. doi:10.1016/j.physrep.2009.02.004.

[bib.bib21] [21] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63(9):5628–5641, 2017. doi:10.1109/TIT.2017.2719044.

[bib.bib22] [22] Lisa Hales and Sean Hallgren. An improved quantum fourier transform algorithm and applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 515–525, 2000. doi:10.1109/SFCS.2000.892139.

[bib.bib23] [23] Carl W. Helstrom. Detection theory and quantum mechanics. Information and Control, 10(3):254–291, 1967. doi:10.1016/S0019-9958(67)90302-6.

[bib.bib24] [24] Alexander S. Holevo. Statistical decision theory for quantum systems. Journal of Multivariate Analysis, 3(4):337–394, 1973. doi:10.1016/0047-259X(73)90028-6.

[bib.bib25] [25] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. doi:10.1038/s41567-020-0932-7.

[bib.bib26] [26] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(1):1–7, 2017. doi:10.1038/s41534-017-0013-7.

[bib.bib27] [27] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv e-prints, 1995. arXiv:quant-ph/9511026.

[bib.bib28] [28] 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.bib29] [29] François Le Gall, Yupan Liu, and Qisheng Wang. Space-bounded quantum state testing via space-efficient quantum singular value transformation. Computational Complexity, 2026. doi:10.1007/s00037-025-00284-5.

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

[bib.bib31] [31] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631–633, 2014. doi:10.1038/nphys3029.

[bib.bib32] [32] 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.bib33] [33] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.

[bib.bib34] [34] Ryan O’Donnell and John Wright. Efficient quantum tomography. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 899–912, 2016. doi:10.1145/2897518.2897544.

[bib.bib35] [35] Ryan O’Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics, 387(1):1–75, 2021. doi:10.1007/s00220-021-04180-1.

[bib.bib36] [36] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. doi:10.1137/S0097539795293172.

[bib.bib37] [37] Yuuki Tokunaga, Takashi Yamamoto, Masato Koashi, and Nobuyuki Imoto. Fidelity estimation and entanglement verification for experimentally produced four-qubit cluster states. Physical Review A, 74(2):020301(R), 2006. doi:10.1103/PhysRevA.74.020301.

[bib.bib38] [38] Gregory Valiant and Paul Valiant. Estimating the unseen: improved estimators for entropy and other properties. Journal of the ACM, 64(6):37:1–37:41, 2017. doi:10.1145/3125643.

[bib.bib39] [39] 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.bib40] [40] 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.bib41] [41] 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.bib42] [42] 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.bib43] [43] Qisheng Wang and Zhicheng Zhang. Time-efficient quantum entropy estimator via samplizer. IEEE Transactions on Information Theory, 71(12):9569–9599, 2025. doi:10.1109/TIT.2025.3576137.

[bib.bib44] [44] 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.

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Optimal quantum estimators for pure-state trace distance and square root fidelity, Theorem 14 restated).

Organization of this paper.

2 Techniques

2.1 Properties of the product of Householder reflections

2.2 Multi-samplizer for pure states

Definition 2 (Multi-samplizer for pure states, Definition 12 restated).

Theorem 3 (Implementation of multi-samplizer for pure states, Theorem 13 restated).

▶ Remark 4.

2.3 Optimality

Theorem 5 (Optimality of the samplizer for pure states, Theorem 17 restated).

Proof sketch.

3 Related Work

4 Preliminaries

4.1 Norms

4.1.1 Vector norms

4.1.2 Matrix norms

4.2 Diamond norm

4.3 Quantum phase estimation

Theorem 6 (Quantum phase estimation, [33, Section 5.2]).

4.4 Density matrix exponentiation

Theorem 7 ([26, Theorem 2]).

5 Estimation with Reflections

5.1 Product of Householder reflections

Lemma 8.

Proof.

5.2 A meta-algorithm

Lemma 9.

Proof.

Corollary 10.

6 Samplizer for Pure States

6.1 Definition

Definition 11 (Reflection oracle for pure states).

Definition 12 (Multi-samplizer for pure states).

6.2 An efficient approach

Theorem 13.

Proof.

7 The Algorithm

Theorem 14.

Proof.

Correctness.

Complexity.

8 Optimality

8.1 Lower bounds for pure-state trace distance and fidelity estimations

Theorem 15 (Sample complexity lower bounds for pure-state closeness estimation, adapted from [1, 39]).

Proof.

8.2 Lower bounds for (multi-)samplizers for pure states

Theorem 16.

Proof of Theorem 16.

Theorem 17.

9 Conclusion

References

$\blacktriangleright$ Remark 4.