On Estimating the Quantum ${\mathbf{\ell }}_{𝜶}$ Distance

We begin by stating our first main theorem, which provides a positive answer to Problem 1 when $\alpha$ lies in the range $1+\mathrm{\Omega }(1)\le \alpha \le O(1)$:

More precisely, for a given additive error $ϵ$, the explicit query complexity of Theorem 2 is $O(1/{ϵ}^{\alpha +1+\frac{1}{\alpha -1}})$ (see Theorem 14). In combination with the samplizer [74, 75], estimating ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ can be done using $\tilde{O}(1/{ϵ}^{3\alpha +2+\frac{2}{\alpha -1}})$ samples of ${\rho }_0$ and ${\rho }_1$ (see Theorem 16). Both upper bounds can be expressed as $\mathrm{poly}(1/ϵ)$ for the regime $1+\mathrm{\Omega }(1)\le \alpha \le O(1)$. In addition, if the state-preparation circuits of ${\rho }_0$ and ${\rho }_1$ have size $L(n)=\mathrm{poly}(n)$, then Theorem 2 implies a quantum algorithm with time complexity $\tilde{O}(L/{ϵ}^{\alpha +1+\frac{1}{\alpha -1}})$, or equivalently, $\mathrm{poly}(n,1/ϵ)$.

Previous quantum algorithms for estimating the quantum ${\mathrm{\ell }}_{\alpha }$ distance for constant $\alpha >1$ have all relied on its powered variant, specifically the powered quantum ${\mathrm{\ell }}_{\alpha }$ distance:

Thus, for , the estimates of ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ and ${\mathrm{\Lambda }}_{\alpha }({\rho }_0,{\rho }_1)$ are polynomially related.

When $\alpha >1$ is an even integer, estimating ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ follows from a folklore result via the Shift test [27], using $O(1/ϵ)$ queries or $O(1/{ϵ}^2)$ samples.³³3The sample complexity was noted in [62, Equations (83) and (84)]. However, for odd integer $\alpha >1$, no efficient quantum algorithm is known in general. Closeness testing of quantum states with respect to ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ for $\alpha =3$, with query complexity $O(1/{ϵ}^{3/2})$, has been noted only in [32]. For general non-integer constants $\alpha >1$, the quantum query complexity of estimating ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ was studied in [71], with polynomial dependence on the maximum rank $r$ of ${\rho }_0$ and ${\rho }_1$. A technical comparison of our approach with this result is provided in Section 1.2.

By combining our efficient quantum estimator for ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ in the regime $1+\mathrm{\Omega }(1)\le \alpha \le O(1)$ (Theorem 2) with our hardness results for QSD_$\alpha$ (Theorem 3), we identify a sharp phase transition between the case of $\alpha =1$ and constant $\alpha >1$, addressing Problem 1. For clarity, we summarize our main theorems and the quantitative bounds on quantum query and sample complexities, derived from both our results and prior work, in Table 1.

Finally, we present our second main theorem, which addresses the computational hardness of QSD_$\alpha$, as outlined in Theorem 3. In this context, PureQSD_$\alpha$ refers to a restricted variant of QSD_$\alpha$ (see also Definition 17), where the states of interest are pure.

At a high level, Quantum Singular Value Transformation (QSVT) [34] implies that the main challenge in designing a quantum algorithm based on a smooth function – e.g., Grover search [38] and the OR function, or the HHL algorithm [39] and the multiplicative inverse function (see [57] for more examples) – reduces to finding an efficiently computable polynomial approximation. Once such an approximation is obtained, the algorithm follows directly using techniques from [34], with its efficiency determined entirely by the polynomial’s properties.

Now we focus on quantum algorithms for estimating the powered quantum ${\mathrm{\ell }}_{\alpha }$ distance. We begin by reviewing [71] and then provide a high-level overview of our approach.

The quantum query complexity of estimating the quantum ${\mathrm{\ell }}_{\alpha }$ distance for non-integer $\alpha$ was first considered in [71, Theorem IV.1]. Their approach begins with the identity

where ${\nu }_{\pm }={\rho }_0\pm {\rho }_1$ and ${\mathrm{\Pi }}_{{\nu }_{+}}$ denotes the projector onto the support subspace of ${\nu }_{+}$. According to this identity, they aim to prepare a quantum state that is a block-encoding of (normalized) ${\left|{\nu }_{-}\right|}^{\alpha /2}{\mathrm{\Pi }}_{{\nu }_{+}}{\left|{\nu }_{-}\right|}^{\alpha /2}$.⁴⁴4See Definition 10 for the formal definition of block-encoding. To this end, they first prepare a quantum state that is a block-encoding of ${\mathrm{\Pi }}_{{\nu }_{+}}$, and then perform a unitary operator that is a block-encoding of ${\left|{\nu }_{-}\right|}^{\alpha /2}$ on it.⁵⁵5This is because of the evolution of subnormalized density operators [71, Lemma II.2]. Finally, the (unnormalized) powered quantum ${\mathrm{\ell }}_{\alpha }$ distance, ${\mathrm{\Lambda }}_{\alpha }({\rho }_0,{\rho }_1)$, can be obtained by estimating the trace of ${\left|{\nu }_{-}\right|}^{\alpha /2}{\mathrm{\Pi }}_{{\nu }_{+}}{\left|{\nu }_{-}\right|}^{\alpha /2}$ using quantum amplitude estimation [16]. After the error analysis, their approach was shown to have query complexity $\tilde{O}(r^{3+1/\{\alpha /2\}}/{ϵ}^{4+1/\{\alpha /2\}})=\mathrm{poly}(r,1/ϵ)$.⁶⁶6Here, $\{x\}≔x-\lfloor x\rfloor$ denotes the fractional part of $x$. The dependence on the rank is inherent in the approach of [71], as they have to prepare a rank-dependent quantum state that is a block-encoding of ${\mathrm{\Pi }}_{{\nu }_{+}}$, making the rank parameters unavoidable in the error analysis.

To overcome this technical issue, we utilize an identity different from theirs:

The idea is to estimate the terms $\mathrm{tr}({\rho }_j\cdot \mathrm{sgn}({\nu }_{-})\cdot {\left|{\nu }_{-}\right|}^{\alpha -1})$ for $j\in \{0,1\}$ individually, and then combine them to obtain an estimate of ${\mathrm{\Lambda }}_{\alpha }({\rho }_0,{\rho }_1)$. Our algorithm is sketched as follows:

1. 1.

   Find a good approximation polynomial for $\mathrm{sgn}(x)\cdot {|x|}^{\alpha -1}$.

2. 2.

   Implement a unitary block-encoding $U$ of $\mathrm{sgn}({\nu }_{-})\cdot {|{\nu }_{-}|}^{\alpha -1}$ using Quantum Singular Value Transformation (QSVT) [34] and Linear Combinations of Unitaries (LCU) [23, 15], given the state-preparation circuits of ${\rho }_0$ and ${\rho }_1$.

3. 3.

   Perform the Hadamard test [3] on $U$ and ${\rho }_j$ with outcome $b_j\in \{0,1\}$ for each $j\in \{0,1\}$.

4. 4.

   Estimate ${\mathrm{\Lambda }}_{\alpha }({\rho }_0,{\rho }_1)$ by computing the expected value of $b_0-b_1$.

Our algorithm is actually inspired by the trace distance estimation in [72], which corresponds to the case of $\alpha =1$. However, the approach in [72] still has a rank-dependent query complexity of $\tilde{O}(r/{ϵ}^2)$, compared to the $\tilde{O}(r^5/{ϵ}^6)$ in [71].⁷⁷7Some readers may wonder if our approach applies to trace distance estimation ($\alpha =1$) to remove the rank dependence in quantum query and sample complexities in [72]. However, the answer is generally no, as the rank dependence is intrinsic to trace distance estimation due to the polynomial dependence of the rank in the quantum query and sample complexities lower bounds (see [52, Section 2.2.2] in the full version). Nevertheless, we discover an approach for estimating the quantum ${\mathrm{\ell }}_{\alpha }$ distance with a rank-independent complexity as long as $\alpha$ is constantly greater than $1$. Specifically, we use the best uniform approximation polynomial $P_d(x)$ (of degree $d$) for the function $\mathrm{sgn}(x)\cdot {|x|}^q$, as given in [31, Theorem 8.1.1]:

Our use of the best uniform approximation by polynomials is inspired by the recent work [53] on estimating the $q$-Tsallis entropy of quantum states for non-integer $q$, where they used the best uniform approximation polynomial for $x^q$ in the non-negative range $[0,1]$ (given in [67]). The difference is that in our case, we have to further consider the sign of $x$, thereby requiring the polynomial approximation to behave well in the negative part. It turns out that the polynomial approximation given in [31] is suitable for our purpose. Having noticed this, we then use the now standard techniques (used in [48, 53]) such as Chebyshev truncations and the de La Vallée Poussin partial sum (cf. [65]) to construct efficiently computable asymptotically best approximation polynomials such that

Using this efficiently computable polynomial (with $q=\alpha -1$) and with further analysis, we can then estimate the quantum ${\mathrm{\ell }}_{\alpha }$ distance to within additive error $ϵ$ with the desired query upper bound in Theorem 2. Moreover, using the (multi-)samplizer [74, 75], a quantum query-to-sample simulation, we can also achieve the desired sample upper bound.

To establish the BQP- and QSZK-hardness results in Theorem 3, we reduce the promise problems QSD and PureQSD ($\alpha =1$) to the corresponding promise problems QSD_$\alpha$ and PureQSD_$\alpha$ for appropriate ranges of $\alpha$. The key technique underlying these reductions is the following rank-dependent inequalities that generalize the case of $\alpha =2$ from [24, 25]:

The proof of Theorem 4 follows from considering orthogonal positive semi-definite matrices ${\varsigma }_0$ and ${\varsigma }_1$ satisfying ${\rho }_0-{\rho }_1={\varsigma }_0-{\varsigma }_1$, and analyzing their properties carefully.

We then illuminate the hardness results in Theorem 3:

• $\mathrm{■}$

  For the easy regime, Equation 1 becomes an equality when both ${\rho }_0$ and ${\rho }_1$ are pure states. This equality implies the BQP-hardness of PureQSD_$\alpha$, along with the query and sample complexity lower bounds for all $1\le \alpha \le \mathrm{\infty }$, establishing Theorem 3(1).

• $\mathrm{■}$

  For the hard regime, Equation 1 is sensitive to $\alpha$. Particularly, for $\alpha =1+\frac{1}{n}$, if quantum states ${\rho }_0$ and ${\rho }_1$ are $\tau$-far, meaning $\mathrm{T}({\rho }_0,{\rho }_1)\ge \tau$, it follows only that ${\mathrm{T}}_{\alpha =1+\frac{1}{n}}({\rho }_0,{\rho }_1)\ge \tau /2$. However, when $\alpha \le 1+\frac{1}{n^{1+\delta }}$ for any arbitrarily small constant $\delta$, the same trace distance condition ensures that ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)\ge \tau$ as $n\to \mathrm{\infty }$, leading to the QSZK hardness result in Theorem 3(2) and distinct query complexity lower bounds in Table 1.

Lastly, we explain the QSZK containment in the hard regime. Simply combining Theorem 4 and the QSZK containment of QSD from [77, 78] does not work, as the resulting QSZK containment of $\text{QSD}\text{<sub class="ltx\_sub"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok name="alpha" role="UNKNOWN" font="italic">α</xmtok></xmath></sub>}[a,b]$ holds only for $a{(n)}^2/2-b(n)\ge 1/O(\log n)$, which is even weaker than the polarizing regime defined in Footnote 1. To address this, we establish a partial polarization lemma for ${\mathrm{T}}_{\alpha }$ (Lemma 25), which ensures that for quantum states ${\rho }_0$ and ${\rho }_1$ where $\mathrm{T}({\rho }_0,{\rho }_1)$ is either at least $a$ or at most $b$, we can construct new quantum states ${\tilde{\rho }}_0$ and ${\tilde{\rho }}_1$ such that ${\mathrm{T}}_{\alpha }({\tilde{\rho }}_0,{\tilde{\rho }}_1)$ is either at least $\frac{1}{2}-\frac{1}{2}{e}^{-k}$ or at most $1/16$, as long as the parameters $a$ and $b$ are in the polarizing regime. Theorem 3(2) follows by combining this partial polarization lemma for ${\mathrm{T}}_{\alpha }$ with the polarization lemma for $\mathrm{T}$ in [77].

While the quantum ${\mathrm{\ell }}_{\alpha }$ distance ${\mathrm{T}}_{\alpha }(\cdot ,\cdot )$ and its powered version ${\mathrm{\Lambda }}_{\alpha }(\cdot ,\cdot )$ are almost computationally interchangeable for $1\le \alpha \le O(1)$, their behavior differs greatly when $\alpha =\mathrm{\infty }$:

• $\mathrm{■}$

  The quantity ${\mathrm{T}}_{\mathrm{\infty }}({\rho }_0,{\rho }_1)$ corresponds to the largest eigenvalue ${\lambda }_{\max }$ of $({\rho }_0-{\rho }_1)/2$. The associated promise problem ${\text{QSD}}_{\mathrm{\infty }}$ is BQP-hard and contains in QMA.⁸⁸8The verification circuit in the QMA containment simply follows from phase estimation [45], where a (normalized) eigenvector corresponding to ${\lambda }_{\max }$ serves as a witness state. However, establishing a BQP containment appears challenging, as $({\rho }_0-{\rho }_1)/2$ does not directly admit an efficiently computable basis – unlike its classical counterpart in [69], which does.

• $\mathrm{■}$

  The quantity ${\mathrm{\Lambda }}_{\mathrm{\infty }}({\rho }_0,{\rho }_1)$ takes values in $\{0,1/2,1\}$ for any states ${\rho }_0$ and ${\rho }_1$, and is nonzero if and only if the states are orthogonal, with at least one being pure. Thus, even the pure-state-restricted variant of the associated promise problem, $\text{PurePoweredQSD}\text{<sub class="ltx\_sub"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok meaning="infinity" name="infty" role="ID">∞</xmtok></xmath></sub>}[1,0]$, is ${𝖢}_{=}𝖯$-hard (see [52, Appendix A] in the full version). Here, ${𝖢}_{=}𝖯=\text{coNQP}$ [2, 80], a subclass of PP that provides a precise variant of BQP, ensuring acceptance for all yes instances.

This fundamental difference between these quantities raises an intriguing question on ${\text{QSD}}_{\mathrm{\infty }}$:

1. (a)

   What is the computational complexity of the promise problem ${\text{QSD}}_{\mathrm{\infty }}$, defined by ${\mathrm{T}}_{\mathrm{\infty }}(\cdot ,\cdot )$? Can we show that ${\text{QSD}}_{\mathrm{\infty }}$ is also in BQP, or is it inherently more difficult?

Another open problem concerns quantitative bounds for QSD_$\alpha$:

1. (b)

   Can the query and sample bounds in Table 1 be improved, particularly for the regime $1+\mathrm{\Omega }(1)\le \alpha \le O(1)$? Moreover, can tight bounds be established when the states have small support, analogous to the classical case in [69, Table 1]?

Schatten $p$-norm estimation $\mathrm{tr}({|A|}^p)$ of $O(\log n)$-local Hermitian $A$ on $n$ qubits to within additive error $2^{n-p}ϵ{\Vert A\Vert }^p$ for $ϵ(n)\le 1/\mathrm{poly}(n)$ and real $p(n)\le \mathrm{poly}(n)$ was shown to be $\mathrm{𝖣𝖰𝖢𝟣}$-complete in [19]. Given a unitary block-encoding of a matrix $A$, in [56], they presented a quantum algorithm that estimates the Schatten $p$-norm ${(\mathrm{tr}({|A|}^p))}^{1/p}$ to relative error $ϵ$ for integer $p$, where a condition number $\kappa$ satisfying $A\ge I/\kappa$ is required for the case of odd $p$.

The query complexity of $N$-dimensional quantum state certification (i.e., determine whether two quantum states are identical or $ϵ$-far) with respect to trace distance was shown to be $O(N/ϵ)$ in [32]. The query complexity of trace distance estimation was shown to be $\tilde{O}(r^5/{ϵ}^6)$ in [71] and later improved to $\tilde{O}(r/{ϵ}^2)$ in [72], where $r$ is the rank of the quantum states, confirming a conjecture in [25] that low-rank trace distance estimation is in BQP. Both Low-rank trace distance and fidelity estimations are known to be BQP-complete [1, 72]. Based on the approach of [72], space-bounded quantum state discrimination with respect to trace distance was shown to be $\mathrm{𝖡𝖰𝖫}$-complete in [48]. In addition to trace distance, fidelity is another important measure of the closeness between quantum states. The query complexity of fidelity estimation was shown to be $\tilde{O}(r^{12.5}/{ϵ}^{13.5})$ in [76] and later improved to $\tilde{O}(r^{5.5}/{ϵ}^{6.5})$ in [71] and to $\tilde{O}(r^{2.5}/{ϵ}^5)$ in [33]. Recently, the query complexity of pure-state trace distance and fidelity estimations was shown to be $\mathrm{\Theta }(1/ϵ)$ in [70] and was recently extended in [29] to estimating fidelity of a mixed state to a pure state.

In addition to the query complexity, the sample complexity has also been studied in the literature. In [7], the sample complexity of $N$-dimensional quantum state certification was shown to be $\mathrm{\Theta }(N/{ϵ}^2)$ with respect to trace distance and $\mathrm{\Theta }(N/ϵ)$ with respect to fidelity. The sample complexity of trace distance estimation is known to be $\tilde{O}(r^2/{ϵ}^5)$ in [72] and that of fidelity estimation is known to be $\tilde{O}(r^{5.5}/{ϵ}^{12})$, where $r$ is the rank of quantum states. The sample complexity of pure-state squared fidelity estimation is known to be $\mathrm{\Theta }(1/{ϵ}^2)$ via the SWAP test [17], where the matching lower bound was given in [4]. Recently, the sample complexity of pure-state trace distance and fidelity estimations was shown to be $\mathrm{\Theta }(1/{ϵ}^2)$ in [73], which was achieved by using the samplizer in [75].

We start by defining the trace distance and providing useful properties of this distance:

Notably, the trace distance is a distance metric (e.g., [79, Lemma 9.1.8]).

Next, we define the quantum ${\mathrm{\ell }}_{\alpha }$ distance and its powered version, which generalize the trace distance ($\alpha =1$) using the Schatten norm. Notably, the quantum ${\mathrm{\ell }}_{\alpha }$ distance coincides with the Hilbert-Schmidt distance when $\alpha =2$:

By the monotonicity of the Schatten norm, e.g., [6, Equation (1.31)], it holds that:

As a corollary of the Davis convexity theorem [26], the quantum ${\mathrm{\ell }}_{\alpha }$ distance ${\mathrm{T}}_{\alpha }(\cdot ,\cdot )$ also serves as a distance metric, whereas its powered version ${\mathrm{\Lambda }}_{\alpha }(\cdot ,\cdot )$ does not. Further inequalities for the trace distance and the quantum ${\mathrm{\ell }}_{\alpha }$ distance are given in the full version, particularly in [52, Section 2.1].

Lastly, we require the following relationship for additive error estimation between the quantum ${\mathrm{\ell }}_{\alpha }$ distance and its powered version. The proof is provided in the full version, specifically in [52, Proposition 2.5].

We begin by defining the closeness testing of quantum states with respect to the trace distance, denoted as QSD$[a,b]$,⁹⁹9While Definition 8 aligns with the classical counterpart of QSD defined in [66, Section 2.2], it is slightly less general than the definition in [77, Section 3.3]. Specifically, Definition 8 assumes that the input length $m$ and the output length $n$ are polynomially equivalent, whereas [77, Section 3.3] allows for cases where the output length (e.g., a single qubit) is much smaller than the input length. and two variants of this problem:

In this work, we consider the purified quantum access input model, as defined in [77], in both white-box and black-box scenarios:

• $\mathrm{■}$

  White-box input model: The input of the problem QSD consists of descriptions of polynomial-size quantum circuits $Q_0$ and $Q_1$. Specifically, for $b\in \{0,1\}$, the description of $Q_b$ includes a sequence of polynomially many $1$- and $2$-qubit gates.

• $\mathrm{■}$

  Black-box input model: In this model, instead of providing the descriptions of the quantum circuits $Q_0$ and $Q_1$, only query access to $Q_b$ is allowed, denoted as $O_b$ for $b\in \{0,1\}$. For convenience, we also allow query access to $Q_b^{†}$ and controlled-$Q_b$, denoted by $O_b^{†}$ and controlled-$O_b$, respectively.

In addition to query complexity, defined within the black-box input model, sample complexity refers to the number of copies of quantum states ${\rho }_0$ and ${\rho }_1$ needed to accomplish a specific closeness testing task. Useful lemmas on computational hardness and quantitative lower bounds for query and sample complexities are available in the full version, specifically in [52, Section 2.2].

We now present useful tools on best uniform polynomial approximations. In addition, definitions and lemmas on Chebyshev expansion and truncations can be found in the full version, particularly in [52, Section 2.3.2].

Let $f(x)$ be a continuous function defined on the interval $[-1,1]$ that we aim to approximate using a polynomial of degree at most $d$. We define $P_d^{\ast }$ as a best uniform approximation on $[-1,1]$ to $f$ of degree $d$ if, for any degree-$d$ polynomial approximation $P_d$ of $f$, it holds that ${\max }_{x\in [-1,1]}\left|f(x)-P_d^{\ast }(x)\right|\le {\max }_{x\in [-1,1]}\left|f(x)-P_d(x)\right|$.

The best uniform (polynomial) approximation of positive (constant) powers ${|x|}^{\alpha }$ was first established by Serge Bernstein [14, 13]. However, the focus here is on the best uniform approximation of signed positive powers $\mathrm{sgn}(x){|x|}^{\alpha }$, as stated in Lemma 9. This result is often attributed to Bernstein’s work (see, e.g., [68, Equation (10.2)]), and a proof of a more general version can be found in [31, Theorem 8.1.1].

In this subsection, we recap the quantum singular value transformation. Additional quantum algorithmic tools, including useful quantum algorithmic subroutines and the quantum samplizer can be found in the full version, specifically in [52, Sections 2.4.2 and 2.4.3].

Using the averaged Chebyshev truncation specified in [52, Section 2.3.2] in the full version, we provide an efficiently computable uniform polynomial approximation of signed positive constant powers (see also [52, Lemma 3.1]):

More specifically, the degree-$d$ uniform approximation of signed positive powers (see Lemma 9) ensures that the degree-$(2d-1)$ averaged Chebyshev truncation (given in [52, Equation 2.3]) achieves almost the same approximation error bound, with efficiently computable Chebyshev coefficients. The complete proof is available in the full version, specifically in [52, Section 3.1].

We generalize the rank-dependent inequalities between the (squared) Hilbert-Schmidt distance and the trace distance, as demonstrated in [24, Appendix G] and [25, Theorem 1] for the case of $\alpha =2$, to all $1\le \alpha \le \mathrm{\infty }$:

It is worth noting that Item 1 and Item 2 in Theorem 18 are consistent, specifically

Additionally, the inequalities in Theorem 18 sharpen the inequalities between the trace norm and the Schatten norm (see, e.g., [6, Equation (1.31)]):

By considering the maximum rank of ${\rho }_0$ and ${\rho }_1$, we can derive a simplified form of Theorem 18 for convenience:

Moreover, for pure quantum states, Theorem 18 yields the following equality:

The proof of Theorem 18 (see also [52, Theorem 4.2] in the full version) relies on the positive semi-definite matrices ${\varsigma }_0$ and ${\varsigma }_1$, defined for each $b\in \{0,1\}$ as ${\varsigma }_b≔\frac{1}{2}\left({(-1)}^b({\rho }_0-{\rho }_1)+\left|{\rho }_0-{\rho }_1\right|\right)$. These matrices are orthogonal and satisfy the relation ${\rho }_0-{\rho }_1={\varsigma }_0-{\varsigma }_1$. The complete proof is provided in [52, Section 4.1].