# Quantum state testing beyond the polarizing regime and
quantum triangular discrimination

Yupan Liu Email<EMAIL_ADDRESS>Graduate School of
Mathematics, Nagoya University

###### Abstract

The complexity class Quantum Statistical Zero-Knowledge (QSZK) captures
computational difficulties of quantum state testing with respect to the trace
distance for efficiently preparable (mixed) quantum states (Quantum State
Distinguishability Problem, QSDP), as introduced by Watrous (FOCS 2002).
However, this class faces the same parameter issue as its classical
counterpart, because of error reduction for the QSDP (the polarization lemma),
as demonstrated by Sahai and Vadhan (JACM, 2003).

In this paper, we introduce quantum analogues of triangular discrimination,
which is a symmetric version of the $\chi^{2}$ divergence, and investigate the
quantum state testing problems for quantum triangular discrimination and
quantum Jensen-Shannon divergence (a symmetric version of the quantum relative
entropy). These new QSZK-complete problems allow us to improve the parameter
regime for testing quantum states in trace distance and examine the
limitations of existing approaches to polarization. Additionally, we prove
that the quantum state testing for trace distance with negligible errors is in
PP, while the same problem without error is in BQP. This result suggests that
achieving length-preserving polarization for QSDP seems implausible unless
QSZK is in PP.

##  1 Introduction

The quantum state testing is generally about telling whether one (mixed)
quantum state is close to the other, often referred to as the quantum property
testing on the equality of a pair of (mixed) quantum states. This problem is
the quantum generalization of the classical question on testing whether two
probability distributions are close, known as the distribution testing. These
problems typically focus on the number of samples (sample complexity) needed
to distinguish two (mixed) quantum states111See [MdW16] for a comprehensive
survey on the quantum property testing.. However, in this paper, we will
concentrate on understanding the computational complexity of these problems
when quantum states that has an efficient description.

The Quantum State Distinguishability problem (QSDP) with respect to the trace
distance, first introduced by Watrous [Wat02], is a well-known example in this
area of study. It is a crucial computational (promise) problem in both quantum
complexity theory and quantum cryptography, and is closely related to the
investigation of quantum statistical zero-knowldge (QSZK). The input to this
problem consists of the description of two efficient quantum circuits $Q_{0}$
and $Q_{1}$, which specify two corresponding (mixed) quantum states $\rho_{0}$
and $\rho_{1}$222In order to prepare these quantum states, we first apply
quantum circuits $Q_{0}$ and $Q_{1}$ on all-zero states, and then tracing out
the ancillary qubits. This will outputs quantum states $\rho_{0}$ and
$\rho_{1}$ respectively. . Yes instances are those in which the trace distance
between the two quantum states is at least $\alpha$, while no instances are
those in which the distance is at most $\beta$, where $0\leq\beta<\alpha\leq
1$. Any input quantum circuits that do not fit into either of these categories
are considered outside the promise. In this paper, we extend the parameters
$\alpha$ and $\beta$ to efficiently computable functions and denote this
parameterized version as $(\alpha,\beta)$-QSDP, which is the quantum analogue
for the Statistical Difference Problem introduced by Sahai and Vadhan [SV03].

In [SV03], error reduction for the QSDP, also known as the polarization lemma,
demonstrates how to polarize the statistical distance between two
distributions. Put it differently, for any constants $\alpha$ and $\beta$ such
that $\alpha^{2}>\beta$, the lemma constructs new distributions such that they
are either very far apart for yes instances or very close for no instances,
which reduces errors on both sides. The polarization lemma is used to
establish the SZK containment of $(\alpha,\beta)$-SDP provided
$\alpha^{2}>\beta$ [SV03], and an analogue of the direct product lemma for the
Hellinger affinity leads to error reduction for StoqMA on no instances
[Liu21]. Interestingly, this polarization lemma techniques works almost
straightforwardly on the trace distance as noted in [Wat02].

Sahai and Vadhan left an open problem of reducing error parameters $\alpha$
and $\beta$ that do not coincide with the requirements of the polarization
lemma technique. Specifically, the parameter regime $\alpha>\beta>\alpha^{2}$
which is referred to as the non-polarizing regime. This issue also arises in
the quantum counterpart QSDP. Recently, Berman, Degwekar, Rothblum, and
Vasudevan [BDRV19] made significant progress in addressing this problem by
examining the limitations of existing approaches to polarization. As a result,
they extended the SZK containment for SDP beyond the regime of constants
$\alpha$ and $\beta$ where $\alpha^{2}-\beta>0$ as originally stated in the
polarization lemma333By inspecting the polarization lemma in [SV03], SDP is in
SZK for $\alpha^{2}-\beta\geq 1/O(\log n)$ as elaborated in [BDRV19]. [SV03].

######  Theorem 1.1 (Informal version of [BDRV19]).

$(\alpha,\beta)$-SDP is in SZK for the following parameter regimes:

  * •

$\alpha^{2}-\beta\geq 1/\mathrm{poly}(n)$;

  * •

$(\alpha,\beta)$ in the non-polarizing regime $\alpha>\beta>\alpha^{2}$
satisfing $\alpha-\beta\geq 1/\mathrm{poly}(n)$ and certain criteria on
$\mathrm{SD}$ and $\mathrm{TD}$444To be specific, pairs of efficient Boolean
circuits $(C_{0},C_{1})$ and $(C^{\prime}_{0},C^{\prime}_{1})$ such pairs of
the corresponding distributions $(p_{0},p_{1})$ and
$(p^{\prime}_{0},p^{\prime}_{1})$ satisfy
$\mathrm{SD}(p_{0},p_{1})>\mathrm{SD}(p^{\prime}_{0},p^{\prime}_{1})>\mathrm{SD}^{2}(p_{0},p_{1})$
and $\mathrm{TD}(p_{0},p_{1})>\mathrm{TD}(p^{\prime}_{0},p^{\prime}_{1})$..

The proof of Theorem 1.1 entails a series of ingenious reductions to two
distribution testing problems, with respect to the Jensen-Shannon divergence
and the triangular discrimination, respectively. The prior works focus on
these two divergences since they captured the limitation of two known
approaches to polarization. In particular, the original polarization lemma
[SV03] focuses on reducing errors in yes-instances and no-instances
alternately, while the triangular discrimination directly admits the latter.
In addition, the entropy extraction approach [GV99] is essentially based on
the Jensen-Shannon divergence555This connection arises from the fact that the
Jensen-Shannon divergence can be interpreted as the (conditional) entropy
difference, as indicated implicitly in Vadhan’s PhD thesis [Vad99]. .

The focus of this work is to address an analogous issue in the quantum
scenario by examining the limitations of current techniques on demonstrating
QSZK containments, achieved through investigating quantum counterparts of
classical distances and divergences related to the problem.

###  1.1 Main results

#### Quantum state testing beyond the polarizing regime.

We introduce two quantum state testing problems, the Quantum Jensen-Shannon
Divergence Problem (QJSP) and the Measured Quantum Triangular Discrimination
Problem (measQTDP). QJSP corresponds to the quantum Jensen-Shannon divergence
defined in [MLP05], while measQTDP involves a quantum analogue of the
triangular discrimination that will be explained later. The QSZK containments
of these problems, as stated in Theorem 1.2, also result in the improved QSZK
containments for the Quantum State Distinguishability problem666The reader may
feel confused with Theorem 5.4 in [VW16] which builds upon the techniques in
[SV03]. However, it was claimed in [GV11] that the proof in [SV03] does extend
to the parameter regime of $\alpha^{2}-\beta\geq 1/\mathrm{poly}(n)$, but this
claim was later retracted, see [Gol19]..

######  Theorem 1.2 (Improved QSZK containments of QSDP – informal).

For quantum state testing problems with respect to the quantum Jensen-Shannon
divergence and the measured triangular discrimination problem, we know that

  1. (1)

$(\alpha,\beta)$-QJSP is in QSZK if $\alpha-\beta\geq 1/\mathrm{poly}(n)$.
Consequently, $(\alpha,\beta)$-QSDP is also in QSZK if
$\alpha^{2}-\sqrt{2\ln{2}}\beta\geq 1/\mathrm{poly}(n)$.

  2. (2)

$(\alpha,\beta)$-measQTDP is in QSZK if $\alpha-\beta\geq 1/O(\log{n})$. This
containment further implies that $(\alpha,\beta)$-QSDP is in QSZK for certain
instances 777In particular, the QSZK containment of QSDP via a reduction to
measQTDP holds for pairs of (mixed) quantum states $(\rho_{0},\rho_{1})$ and
$(\rho^{\prime}_{0},\rho^{\prime}_{1})$ satisfying the conditions
$\mathrm{td}(\rho_{0},\rho_{1})>\mathrm{td}(\rho^{\prime}_{0},\rho^{\prime}_{1})>\mathrm{td}^{2}(\rho_{0},\rho_{1})$
and $\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1})>\mathrm{QTD}^{\rm
meas}(\rho^{\prime}_{0},\rho^{\prime}_{1})$.  with
$\alpha^{2}\leq\beta\leq\alpha$ and $\alpha-\beta\geq 1/O(\log(n))$.

In fact, both QJSP and measQTDP are QSZK-complete. The measured quantum
triangular discrimination ($\mathrm{QTD}^{\rm meas}{}$) exposes the limitation
of the quantum polarization lemma technique [SV03, Wat02], and its QSZK
containment exhibits a natural inverse-logarithmic promise gap. Notably,
another quantum analogue QTD does not achieve a similar result. Likewise, the
quantum Jensen-Shannon divergence captures the limitation of the quantum
entropy extraction approach [BASTS10], but our implications on QSZK
containments are slightly weaker than the classical counterpart in Theorem
1.1, as quantum analogues of the triangular discrimination behave differently
from the classical equivalent.

#### Easy regimes for the class QSZK.

For the $(1-\epsilon,\epsilon)$-Statistical Difference Problem, if the error
parameter $\epsilon$ is negligible, then this problem falls into the class PP.
SDP instances within these parameter regimes are unlikely to be SZK-hard
because of the oracle separation between SZK and PP [BCH+19]. We show a
similar phenomenon on the $(1-\epsilon,\epsilon)$-Quantum State
Distinguishability problem, and these instances are even easier to solve if
there is no error, as stated in Theorem 1.3.

######  Theorem 1.3 (Easy regimes for QSZK – informal).

For a negligible error $\epsilon\leq 2^{-n/2-1}$,
$(1-\epsilon,\epsilon)$-$\overline{\mbox{{QSDP}}}$ is in PP. Moreover,
$(1,0)$-$\overline{\mbox{{QSDP}}}$ is in $\textnormal{{BQP}}_{1}$ if there is
no error.

We list our results and compare them with the counterpart results of SZK in
Table 1.

Parameter regimes |  $(1-\epsilon,\epsilon)$-$\overline{\mbox{{SDP}}}$ |  $(1-\epsilon,\epsilon)$-$\overline{\mbox{{QSDP}}}$
---|---|---
$\epsilon=0$ |  in NP Folklore |  in $\textnormal{{BQP}}_{1}$ This work (Section 5.1)
$\epsilon\leq 2^{-n/2-1}$ |  in PP Theorem 7.1 in [BCH+19] |  in PP This work (Theorem 5.1)
$\epsilon\geq 2^{-n^{1/2-\gamma}}$ for $\gamma\in(0,1/2)$ |  SZK-hard Implicitly stated in [SV03] |  QSZK-hard Implicitly stated in [Wat02]
Table 1: Easy and hard regimes for SZK and QSZK.

Here the improved SZK-hardness and QSZK-hardness follow from skillfully
applying the polarization lemma for the relevant distance to the original
proof, see Theorem 3.14 in [BDRV19]. We then observe that
$\frac{1}{2}\mathrm{HS}^{2}(\rho_{0},\rho_{1})=\frac{1}{2}(\mathrm{Tr}(\rho_{0}^{2})+\mathrm{Tr}(\rho_{1}^{2}))-\mathrm{Tr}(\rho_{0}\rho_{1})$.
Hence, the remaining results are mainly derived from a hybrid algorithm based
on the SWAP test [BCWdW01], namely tossing two random coins and performing the
SWAP test on the corresponding states.

In essence, the phenomenon that parameter regimes with negligible errors are
easier to solve is not unique to the class QSZK. Analogous phenomena can also
be observed in other quantum complexity classes, such as $\mathsf{QMA(2)}$
[KMY09] and $\mathsf{StoqMA}$ [AGL20]. Nevertheless, it is worth noting that
these similar results in other classes do not always necessitate the length-
preserving property888A polarization lemma for some (quantum) distance is
length-preserving if the output length of the pair of resulting (quantum)
circuits is as same as the output length of the original pair of (quantum)
circuits. . Considering that SZK is a subset of QSZK, Theorem 5.1 can be
interpreted as an indication that problems that can effectively distinguish
quantum states may not remain QSZK-hard when the acceptance probability
deviates negligibly from $0$ or $1$.

###  1.2 Proof techniques

The QSZK completeness of the aforementioned QJSP and measQTDP crucially relies
on the relationships between quantum analogues of common classical
$f$-divergences999An $f$-divergence is a function
$\mathrm{D}_{f}(p_{0}\|p_{1})$ that measures the difference between two
probability distributions $p_{0}$ and $p_{1}$, and this divergence is defined
as $\mathrm{D}_{f}(p_{0}\|p_{1}):=\mathbb{E}_{x\sim
p_{1}}f(p_{0}(x)/p_{1}(x))$. . We start by reviewing and defining these
quantum analogues. The most widely used quantum distances are the trace
distance ($\mathrm{td}$) with the Bures distance ($\mathrm{B}$, essentially
the fidelity), which are quantum counterparts of the statistical distance
($\mathrm{SD}$) and the (squared) Hellinger distance ($\mathrm{H}$),
respectively. Other commonly used $f$-divergences are the KL divergence (also
known as the relative entropy) and the $\chi^{2}$-divergence, which are
unbounded, so we instead focus on their symmetrized versions, the Jensen-
Shannon divergence ($\mathrm{JS}$) and the triangular discrimination
$(\mathrm{TD})$, respectively.

The relationship between two quantum analogues of the Jensen-Shannon
divergence constitutes a specific instance of the renowned Holevo’s bound,
namely the measured quantum Jensen-Shannon divergence is at most the quantum
Jensen-Shannon divergence ($\mathrm{QJS}$). To the best of our knowledge,
there is no known quantum analogue of triangular discrimination. We thus
initiate the definition of the quantum triangular discrimination (QTD) and the
measured quantum triangular discrimination $(\mathrm{QTD}^{\rm meas})$, based
on their connection to the quantum analogues of $\chi^{2}$-divergence
[TKR+10]. We further examine their relationship with other aforementioned
quantum distances and divergences, as stated in Theorem 1.4.

######  Theorem 1.4 (Inequalities on quantum analogues of the triangular
discrimination – informal).

For any quantum states $\rho_{0}$ and $\rho_{1}$, we know that

  1. (1)

$\mathrm{td}^{2}\\!(\rho_{0},\\!\rho_{1}\\!)\\!\leq\\!\\!\mathrm{QTD}^{\rm
meas}(\rho_{0},\\!\rho_{1}\\!)\\!\leq\\!\textnormal{{QTD}}(\rho_{0},\\!\rho_{1}\\!)\\!\leq\\!\mathrm{td}(\\!\rho_{0},\\!\rho_{1}\\!)$;

  2. (2)

$\frac{1}{2}\textnormal{{QTD}}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QJS}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})$;

  3. (3)

$\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\mathrm{B}^{2}(\rho_{0},\rho_{1})$ and
$\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{B}(\rho_{0},\rho_{1})$.

We summarize our new results and known inequalities in Table 2, as well as how
we utilize these inequalities in our proof. In addition, we highlight that the
quantum triangular discrimination behaves differently from its classical
counterpart since the triangular discrimination is a constant multiplicative
error approximation of the Jensen-Shannon divergence. This difference breaks
down the quantum equivalent of the ingenious reduction from TDP to JSP
presented in [BDRV19], leading to a slightly worse parameter in the improved
QSZK containment for the Quantum State Distinguishability problem.

| Classical | Quantum |  Usages related to QSZK
---|---|---|---
$\mathrm{SD}\text{ vs. }\mathrm{H}^{2}$ |  $\mathrm{H}^{2}\leq\mathrm{SD}\leq\sqrt{2}\mathrm{H}$ [Kai67] |  $\frac{1}{2}\mathrm{B}^{2}\leq\mathrm{td}\leq\mathrm{B}$ [FvdG99] |  A polarization lemma for the trace distance [Wat02]
$\mathrm{SD}\text{ vs. }\mathrm{JS}$ |  $1-\mathrm{H_{2}}\left(\frac{1-\mathrm{SD}}{2}\right)\leq\mathrm{JS}_{2}\leq\mathrm{SD}$ [FvdG99, Top00] |  $1-\mathrm{H_{2}}\left(\frac{1-\mathrm{td}}{2}\right)\leq\mathrm{QJS}_{2}\leq\mathrm{td}$ [BH09, FvdG99] |  QJSP is QSZK-hard This work (Section 4.3)
$\mathrm{SD}\text{ vs. }\mathrm{TD}$ |  $\mathrm{SD}^{2}\leq\mathrm{TD}\leq\mathrm{SD}$ [Top00] |  $\mathrm{td}^{2}\leq\mathrm{QTD}^{\rm meas}\leq\textnormal{{QTD}}\leq\mathrm{td}$ This work (Theorem 3.1) |  measQTDP is QSZK-hard This work (Section 4.3)
$\mathrm{JS}\text{ vs. }\mathrm{TD}$ |  $\frac{1}{2}\mathrm{TD}\leq\mathrm{JS}\leq\ln{2}\cdot\mathrm{TD}$ [Top00] |  $\frac{1}{2}\textnormal{{QTD}}^{2}\leq\mathrm{QJS}\leq\textnormal{{QTD}}$ This work (Theorem 3.2) |  None
$\mathrm{TD}\text{ vs. }\mathrm{H}^{2}$ |  $\mathrm{H}^{2}\leq\mathrm{TD}\leq 2\mathrm{H}^{2}$ [LC86] |  $\frac{1}{2}\mathrm{B}^{2}\leq\mathrm{QTD}^{\rm meas}\leq\mathrm{B}^{2}$ $\frac{1}{2}\mathrm{B}^{2}\leq\textnormal{{QTD}}\leq\mathrm{B}$ This work (Theorem 3.3) |  A polarization lemma for the $\mathrm{QTD}^{\rm meas}$ This work (Section 4.2)
Table 2: A comparison between classical and quantum distances with usages
related to QSZK.

Leveraging inequalities in Table 2, we then proceed to prove that both QJSP
and measQTDP are QSZK-complete. The QSZK containment of measQTDP utilizes a
new polarization lemma for the measured quantum triangular discrimination, and
the QSZK containment of QJSP is demonstrated through a reduction to the
Quantum Entropy Difference problem [BASTS10] using a nice property of the
quantum conditional entropy on a classical-quantum state. We therefore explore
the limitations of current techniques for showing QSZK containments.
Additionally, the QSZK-hardness of these problems is straightforwardly
analogous to their classical counterparts [BDRV19] because of the
corresponding inequalities in Table 2.

###  1.3 Discussion and open problems

#### Improved inequalities on the quantum triangular discrimination.

We observe that Theorem 3.2 is not a tight bound. Numerical simulations
indicate that the tight bound is
$\textnormal{{QTD}}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QJS}_{2}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})$
for any quantum states $\rho_{0}$ and $\rho_{1}$, with improved constant
factors. This bound can be saturated by choosing quantum states $\rho_{0}$ and
$\rho_{1}$ with an orthogonal support, as these instances sufficient for
$\mathrm{QJS}(\rho_{0},\rho_{1})$ and $\textnormal{{QTD}}(\rho_{0},\rho_{1})$
equal to $1$101010In fact, this is a sufficient and necessary condition for
$\mathrm{QJS}$ as well as the trace distance. By Section 3.1, we apply this
condition to QTD.. Furthermore, numerical simulations also suggest that the
triangular inequality holds for the square root of QTD, namely
$\sqrt{\textnormal{{QTD}}(\rho_{0},\rho_{1})}+\sqrt{\textnormal{{QTD}}(\rho_{1},\rho_{2})}\geq\sqrt{\textnormal{{QTD}}(\rho_{0},\rho_{2})}$
for any quantum states $\rho_{0},\rho_{1}$ and $\rho_{2}$. This indicates that
the square root of quantum triangular discrimination is a metric, with the
same property also holding for triangular discrimination [LC86].

#### Applications of the quantum triangular discrimination.

Is there any other application of the (measured) quantum triangular
discrimination besides its use in QSZK as demonstrated in this paper? For
instance, Amir Yehudayoff [Yeh20] has utilized triangular discrimination to
obtain a sharper lower bound on the communication complexity of the point
chasing problem. Can we expect an analogous implication in the quantum world?

#### What is the computational complexity of low-rank variants of QJSP and
measQTDP?

Recent research has demonstrated that in the case of the Fidelity Estimation
problem, which concerns quantum state testing on fidelity and assumes one of
the (mixed) quantum states has low-rank, the problem becomes BQP-complete
[WZC+23, ARSW21, GP22]. Additionally, in the case of the Quantum State
Distinguishability problem, which concerns quantum state testing on trace
distance and assumes two quantum states have low-rank, the problem is also
BQP-complete [WZ23, ARSW21]. This leads to an intriguing question of whether
the low-rank counterparts of QJSP, measQTDP, and QTDP also have an efficient
quantum algorithm.

###  1.4 Paper organization

Section 2 introduces (quantum) distance and divergences for classical
probability distributions and mixed quantum states, as well as reviewing some
prior works for showing the QSZK containment and hardness. Section 3 is
devoted to quantum analogues of the triangular discrimination and proving
relavant inequalities. Section 4 provides two new QSZK-complete problems, viz.
the Quantum ensen-Shannon Divergence problem (QJSP) and the Measured Quantum
Triangular Discrimination problem (measQTDP). Section 5 presents easy regimes
for QSZK in terms of the Quantum State Distinguishability problem.

##  2 Preliminaries

###  2.1 Distances and divergences for quantum states

An introduction about classical distances and divergences for probability
distributions can be found in Appendix A. Now we will review relevant quantum
distances and divergences. Classical distances and divergences often have
corresponding quantum versions, and sometimes even multiple options. These
distances usually reduce to the classical counterpart when quantum states
$\rho_{0}=\mathrm{diag}(p_{0})$ and $\rho_{1}=\mathrm{diag}(p_{1})$ are
diagonal. We recommend Section 3.1 in [BOW19] for a nice survey.

For any classical $f$-divergence, we can define a quantum analogue through
either converting arithmetic operations in the classical divergence to their
matrix-theoretic counterparts, or by considering the probability distributions
induced by the same POVM, referred to as the measured quantum $f$-divergence.
For a comprehensive overview of other quantum analogues of $f$-divergence and
their relationships, we refer to [Hia21]. Consider a classical $f$-divergence
$\mathrm{d}_{f}(\cdot,\cdot)$, the measured quantum $f$-divergence
$\mathrm{D}_{f}(\cdot,\cdot)$ is defined as follows:

$\mathrm{D}_{f}(\rho_{0},\rho_{1})=\sup_{\mathrm{POVMs}\leavevmode\nobreak\
\mathcal{E}}\left\\{\mathrm{d}_{f}\left(p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})}\right)\right\\}\text{
where
}p_{z}^{(\mathcal{E})}:=\left(\mathrm{Tr}(\rho_{z}E_{1}),\cdots,\mathrm{Tr}(\rho_{z}E_{N})\right).$
(2.1)

Put it differently, the quantum divergence is the maximum classical divergence
achievable when the same POVM is applied to both quantum states. In this
section, we will encounter different flavors of quantum analogues of Jensen-
Shannon divergence. We further provide a review on quantum analogues of the
statistical distance and (squared) Hellinger distance in Section A.1.

#### Quantum analogues of Jensen-Shannon Divergence

The study on quantum analogues of Jensen-Shannon Divergence (a.k.a., Shannon
Distinguishability) could date back to the Holevo bound [Hol73]. We begin with
a definition in [MLP05], and notice that $\mathrm{QJS}$ is at most
$1$111111Whereas quantum relative entropy is unbounded, by properties of von
Neumann entropy (e.g., Theorem 11.8 in [NC02]), we know that
$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\mathrm{H_{2}}(1/2)=1$. Then the equality
holds if and only if $\rho_{0}$ and $\rho_{1}$ have support on orthogonal
subspaces..

[Quantum Jensen-Shannon Divergence, [MLP05]] The quantum Jensen-Shannon
divergence between two (mixed) quantum states $\rho_{0}$ and $\rho_{1}$ is
$\mathrm{QJS}(\rho_{0},\rho_{1}):=S\left(\frac{\rho_{0}+\rho_{1}}{2}\right)-\frac{S(\rho_{0})+S(\rho_{1})}{2}=\frac{1}{2}\left[\mathrm{D}\left(\rho_{0}\big{\|}\frac{\rho_{0}+\rho_{1}}{2}\right)+\mathrm{D}\left(\rho_{1}\big{\|}\frac{\rho_{0}+\rho_{1}}{2}\right)\right],$
where $S(\rho):=-{\rm Tr}(\rho\ln\rho)$ is the von Neumann entropy and
$\mathrm{D}(\cdot\|\cdot)$ is the quantum relative entropy.

In [FvdG99], the authors study a measured variant of Jensen-Shannon Divergence
(a.k.a., quantum Shannon distinguishability). It is worthwhile to mention that
there is no explicit formula for $\mathrm{QJS}^{\rm meas}$ since it is a
solution of some transcendental equation, as explained in [FC94]. We can
analogously define the Measured Quantum Jensen-Shannon Divergence
$\mathrm{QJS}^{\rm meas}(\rho_{0},\rho_{1})$ in terms of Equation 2.1. For
convenience, we define
$\mathrm{QJS}_{2}(\rho_{0},\rho_{1}):=\mathrm{QJS}(\rho_{0},\rho_{1})/\ln 2$
with respect to the base-$2$ (matrix) logarithmic function. Likewise,
$\mathrm{QJS}^{\rm meas}_{2}(\rho_{0},\rho_{1}):=\mathrm{QJS}^{\rm
meas}(\rho_{0},\rho_{1})/\ln 2$.

Interestingly, Quantum Jensen-Shannon Divergence ($\mathrm{QJS}$) is a special
case of the Holevo Information (e.g., Section 11.6.1 in [Wil13]). To be
precise, this coincides with the Holevo Information on size-$2$ ensembles with
a uniform distribution. Moreover, $\mathrm{QJS}$ is upper-bounded by the trace
distance as Section 2.1, and the proof is deferred to Appendix B.

[Adapted from [BH09]]lemmaQJSLeqTracrDist For any quantum states
$\rho_{0},\rho_{1}$,
$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\ln{2}\cdot\mathrm{td}(\rho_{0},\rho_{1}).$

Owing to the Holevo bound121212See also Exercise 11.9.1 in [Wil13] for a
precise statement. [Hol73], we know that the quantum Jensen-Shannon divergence
is at least its measured variant, and the proof is also deferred to Appendix
B.

[Quantum Jensen-Shannon Divergence is at least its measured
variant]propositionmeasQJSleqQJS For any quantum states $\rho_{0}$ and
$\rho_{1}$, $\mathrm{QJS}^{\rm
meas}(\rho_{0},\rho_{1})\leq\mathrm{QJS}(\rho_{0},\rho_{1})$.

Utilizing Section 2.1, we have derived a lower bound of $\mathrm{QJS}$ in
terms of the trace distance. And the proof is also deferred in Appendix B.

[Adapted from [FvdG99]]lemmatraceDistLeqQJS For any quantum states $\rho_{0}$
and $\rho_{1}$,

$\mathrm{QJS}_{2}(\rho_{0},\rho_{1})\geq\mathrm{QJS}^{\rm
meas}_{2}(\rho_{0},\rho_{1})\geq
1-\mathrm{H_{2}}\left(\tfrac{1-\mathrm{td}(\rho_{0},\rho_{1})}{2}\right)=\sum\nolimits_{v=1}^{\infty}\tfrac{\mathrm{td}(\rho_{0},\rho_{1})^{2v}}{\ln{2}\cdot
2v(2v-1)},$

where the binary entropy
$\mathrm{H_{2}}(p):=-p\log_{2}(p)-(1-p)\log_{2}(1-p)$.

###  2.2 Quantum state testing in the trace distance and beyond

We start with a formal definition of the Quantum State Distinguishability
problem.

[Quantum State Distinguishability problem, adapted from [Wat02]] Given quantum
circuits $Q_{0}$ and $Q_{1}$ acting on $n$ qubits and having $k$ specified
output qubits. Let $\rho_{i}$ denote the quantum state obtained by running
$Q_{i}$ on state $|0^{n}\rangle$ and tracing out the non-output qubits. Let
$\alpha$ and $\beta$ be polynomial-time computable functions. Then promise
that one of the following cases will occur:

  * •

Yes instances: A pair of quantum circuits $(Q_{0},Q_{1})$ such that
$\mathrm{td}(\rho_{0},\rho_{1})\geq\alpha(n)$;

  * •

No instances: A pair of quantum circuits $(Q_{0},Q_{1})$ such that
$\mathrm{td}(\rho_{0},\rho_{1})\leq\beta(n)$.

Analogously, we also define the Quantum Jensen-Shannon Divergence problem
(QJSP) and the Measured Quantum Triangular Discrimination problem (measQTDP)
on the corresponding distances.

In a similar manner to the celebrated polarization lemma for SZK [SV03],
Watrous shows that $(\alpha,\beta)$-$\mathrm{QSD}$ is in QSZK for
$0\leq\beta<\alpha^{2}\leq 1$. The proof essentially follows from an analogous
polarization lemma for the trace distance. In [Wat02], it states that
$\mathrm{QSD}(\alpha,\beta)$ with any constants $\alpha$ and $\beta$ in this
parameter regime is QSZK-complete131313Here, we do not distinguish QSZK from
the honest-verifier variant $\textnormal{{QSZK}}_{\sf HV}$ since these classes
are equivalent [Wat06].. Moreover, the polarization lemma for the statistical
distance in [SV03] can be used to derive an improved SZK-hardness for SDP, as
stated in Theorem 3.14 of [BDRV19]. We thus analogously deduce the counterpart
improved QSZK-hardness for QSDP (Footnote 13) and omit the detailed proof.
[Improved QSZK-hardness for QSDP]theoremimprovedQSZKhardQSD Let $\alpha(n)$
and $\beta(n)$ be efficiently computable functions that satisfy
$\alpha^{2}-\beta\geq 1/\mathrm{poly}(n)$. There exists a constant
$\epsilon\in(0,1/2)$ with $\beta(n)\geq 2^{-n^{1/2-\epsilon}}$ and
$\alpha(n)\leq 1-2^{-n^{1/2-\epsilon}}$ for every $n\in\mathbb{N}$ such that
$(\alpha,\beta)$-QSDP is QSZK-hard.

##  3 Quantum analogues of the triangular discrimination

In this section, we introduce two quantum analogues of the triangular
discrimination and demonstrate their relationships with several commonly used
distance, such as trace distance, Bures distance (which is closely related the
fidelity), and quantum Jensen-Shannon divergence.

To the best of our knowledge, there is no known quantum analogue of triangular
discrimination (also known as Vincent-Le Cam divergence). Since triangular
discrimination is a symmetrized version of $\chi^{2}$ divergence,
$\mathrm{TD}(p_{0},p_{1})=\chi^{2}(p_{0}\big{\|}\frac{p_{0}+p_{1}}{2})=\chi^{2}(p_{1}\big{\|}\frac{p_{0}+p_{1}}{2})$,
we present the first quantum analogue which is derived from the quantum
$\chi^{2}$ divergence in [TKR+10].

[Quantum Triangular Discrimination] The quantum triangular discrimination
between two (mixed) quantum states $\rho_{0}$ and $\rho_{1}$ is defined as

$\textnormal{{QTD}}(\rho_{0},\rho_{1}):=\frac{1}{2}\mathrm{Tr}\left((\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}\right).$

Furthermore, if $\rho_{0}+\rho_{1}$ is not full-rank, then the inverse is
defined only on its support.

It is noteworthy that a quantum analogue of triangular discrimination can be
also defined as
$\textnormal{{QTD}}_{\alpha}(\rho_{0},\rho_{1})=\chi^{2}_{\alpha}\left(\rho_{z}\big{\|}\frac{\rho_{0}+\rho_{1}}{2}\right)$
for $z\in\\{0,1\\}$, following the approach presented in [TKR+10]. However,
$\textnormal{{QTD}}_{\alpha}$ is only upper-bounded by the trace distance for
$\alpha=1/2$141414See Remark 3.4 for the details. , which implies that
$\textnormal{{QTD}}_{1/2}$ is at most $1$. Therefore, we use
$\textnormal{{QTD}}_{\alpha=1/2}(\rho_{0},\rho_{1})$ for defining QTD in this
paper. In addition, a quantum analogue of triangular discrimination can also
be established based on distributions induced by quantum measurements. Namely,
the Measured Quantum Triangular Discrimination $\mathrm{QTD}^{\rm meas}$ in
terms of Equation 2.1. Utilizing Lemma 5 in [TV15], we can derive an explicit
formula for the $\mathrm{QTD}^{\rm meas}$151515Given that
$\mathrm{TD}(p_{0},p_{1})=\chi^{2}(p_{z}\big{\|}\frac{p_{0}+p_{1}}{2})$ for
$z\in\\{0,1\\}$, an explicit formula for the $\mathrm{QTD}^{\rm meas}$ derives
from Lemma 5 in [TV15]: $\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})=\mathrm{Tr}\left(\frac{\rho_{0}-\rho_{1}}{2}\Omega_{\rho}\left(\frac{\rho_{0}-\rho_{1}}{2}\right)\right)$
where $\rho:=(\rho_{0}+\rho_{1})/2$ and the linear operator $\Omega_{\rho}$
satisfies that $\Omega_{\rho}^{-1}(A)=(\rho A+A\rho)/2$. . As is typical, the
quantum triangular discrimination is lower-bounded by its measured
counterpart, following from a data-processing inequality for the quantum
$\chi^{2}$-divergence (Proposition 6 in [TKR+10]). The detailed proof is
deferred to Appendix C.

propositionmeasQTDleqQTD For any quantum states $\rho_{0}$ and $\rho_{1}$,
$\textnormal{{QTD}}(\rho_{0},\rho_{1})\geq\textnormal{{QTD}}^{\rm
meas}(\rho_{0},\rho_{1})$.

We now present three theorems that examine the relationship between the
quantum triangular discrimination (QTD) and other commonly used quantum
distances and divergences. Theorem 3.1 compares QTD with the trace distance
($\mathrm{td}$), and is established by the combination of Section 3.1 and
Appendix C, with the latter relying on the trace distance being also a
measured version of the statistical distance.

######  Theorem 3.1 (QTD vs. trace distance).

For any quantum states $\rho_{0}$ and $\rho_{1}$,

$\mathrm{td}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1}).$

Theorem 3.2 demonstrates the relationship between QTD and the quantum Jensen-
Shannon divergence ($\mathrm{QJS}$), which is based on the combination of
Appendix C and Appendix C in Appendix C. The proof of these lemmas takes
advantage of inequalities on the trace distance, thereby linking the
$\mathrm{QJS}$ and QTD.

######  Theorem 3.2 (QTD vs. $\mathrm{QJS}$).

For any quantum states $\rho_{0}$ and $\rho_{1}$,

$\frac{1}{2}\textnormal{{QTD}}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QJS}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1}).$

Theorem 3.3 explores the relationship between the QTD and the Bures distance.
The bounds of $\mathrm{QTD}^{\rm meas}$ (Appendix C) utilize the fact that the
Bures distance is the measured version of the Hellinger distance, and the
bounds of QTD (Appendix C) also employ inequalities on the trace distance,
connecting the QTD and the Bures distance. The detailed proof can be found in
Appendix C.

######  Theorem 3.3 (QTD vs. Bures distance).

For any quantum states $\rho_{0}$ and $\rho_{1}$,

$\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\mathrm{B}^{2}(\rho_{0},\rho_{1})\text{ and
}\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{B}(\rho_{0},\rho_{1}).$

###  3.1 QTD vs. trace distance

We now establish that QTD is no greater than the trace distance. Although this
inequality is similar to the relationship between triangular discrimination
(TD) and statistical difference (SD), the equality condition differs greatly
from the classical scenarios.

[$\textnormal{{QTD}}\leq\mathrm{QSD}$]lemmaQTDleqQSD For any quantum states
$\rho_{0}$ and $\rho_{1}$,
$\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1}).$

Next, we clarify the equality condition for Section 3.1 and highlight that the
first item in Section 3.1 corresponds to the equality condition for its
classical counterpart161616Namely,
$(p_{0}(x)-p_{1}(x))^{2}=(p_{0}(x)+p_{1}(x))^{2}$ holds for any
$x\in\mathrm{supp}\left(p_{0}\right)\cup\mathrm{supp}\left(p_{1}\right)$..

[Equality condition for
$\textnormal{{QTD}}\leq\mathrm{QSD}$]propositioncondsQTDeqQSD For any quantum
states $\rho_{0}$ and $\rho_{1}$, the equality
$\textnormal{{QTD}}(\rho_{0},\rho_{1})=\mathrm{td}(\rho_{0},\rho_{1})$ if and
only if the following conditions hold:

  1. (1)

$(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1}(\rho_{0}-\rho_{1})=(\rho_{0}+\rho_{1})$;

  2. (2)

$(\rho_{0}-\rho_{1})^{\dagger}(\rho_{0}-\rho_{1})=\frac{\mathrm{Tr}\left[(\rho_{0}-\rho_{1})^{\dagger}(\rho_{0}-\rho_{1})\right]}{|\mathrm{supp}\left(\rho_{0}-\rho_{1}\right)|}I$;

  3. (3)

For any $k\in\mathrm{supp}\left(\rho_{0}-\rho_{1}\right)$,
$\mathrm{sgn}\lambda_{k}(\rho_{0}-\rho_{1})=\mathrm{sgn}\lambda_{k}\left((\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{1/2}\right)$
where $\lambda_{k}(A)$ is the $k$-th eigenvalue of the matrix $A$.

######  Remark 3.4 ($\textnormal{{QTD}}_{\alpha}\leq\mathrm{td}$ holds only
for $\alpha=1/2$).

As Proposition 7 in [TKR+10] infers that
$\textnormal{{QTD}}_{\alpha=1/2}\leq\textnormal{{QTD}}_{\alpha}$, we may
wonder whether Section 3.1 holds for any $\alpha\in[0,1]$. Here is a
counterexample: Consider two single-qubit pure states
$\rho^{*}_{0}=\tfrac{1}{2}\left(I+\tfrac{6}{7}\sigma_{X}+\tfrac{3}{7}\sigma_{Y}+\tfrac{2}{7}\sigma_{Z}\right)$
and
$\rho^{*}_{1}=\tfrac{1}{2}\left(I-\tfrac{3}{7}\sigma_{X}-\tfrac{2}{7}\sigma_{Y}+\tfrac{6}{7}\sigma_{Z}\right)$,
where $\sigma_{X}$, $\sigma_{Y}$ and $\sigma_{Z}$ are Pauli matrices. Then we
simply have
$\textnormal{{QTD}}_{\alpha=1/2}(\rho^{*}_{0},\rho^{*}_{1})=\mathrm{td}(\rho^{*}_{0},\rho^{*}_{1})<\textnormal{{QTD}}_{\alpha>1/2}(\rho^{*}_{0},\rho^{*}_{1})$.

We then proceed to sketch the proof of Section 3.1 while the full proof can be
found in Appendix C. Additionally, the proof of Section 3.1 is deferred in
Appendix C, which follows from a detailed analysis on the equality condition
of the matrix Hölder inequality in [Cio21].

###### Proof Sketch of Section 3.1.

Utilizing a matrix Hölder inequality (e.g., Corollary IV.2.6 in [Bha96]), we
obtain
$\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1})\cdot\|I-\rho^{-1/2}\rho_{1}\rho^{-1/2}\|_{\infty}$
where $\rho:=(\rho_{0}+\rho_{1})/2$. We complete the proof by upper-bounding
$\sigma_{\max}\left(I-\rho^{-1/2}\rho_{1}\rho^{-1/2}\right)$ using Weyl’s
inequalities (e.g., Corollary 4.3.12 in [HJ12]). ∎

##  4 Complete problems for QSZK on the quantum state testing

In this section, we present two new QSZK complete problems, the Quantum
Jensen-Shannon Divergence problem (QJSP) and the Measured Quantum Triangular
Discrimination problem (measQTDP). These results extend the classical
analogues in [BDRV19] to the realm of quantum computing.

######  Theorem 4.1 (QJSP is QSZK-complete).

For any $0\leq\beta(n)<\alpha(n)\leq 1$ such that $\alpha(n)-\beta(n)\geq
1/\mathrm{poly}(n)$, $(\alpha,\beta)$-QJSP is in QSZK. Moreover, provided that
$\alpha(n)\leq 1-2^{-n^{1/2-\epsilon}}$ and $\beta(n)\geq
2^{-n^{1/2-\epsilon}}$ for every $n\in\mathbb{N}$ and some constant
$\epsilon\in(0,1/2)$, $(\alpha,\beta)$-QJSP is also QSZK-hard.

######  Theorem 4.2 (measQTDP is QSZK-complete).

For any $0\leq\beta(n)<\alpha(n)\leq 1$ such that $\alpha(n)-\beta(n)\geq
O(1/\log(n))$, $(\alpha,\beta)$-measQTDP is in QSZK. Moreover, provided that
$\alpha(n)\leq 1-2^{-n^{1/2-\epsilon}}$ and $\beta(n)\geq
2^{-n^{1/2-\epsilon}}$ for every $n\in\mathbb{N}$ and some constant
$\epsilon\in(0,1/2)$, $(\alpha,\beta)$-measQTDP is also QSZK-hard.

Subsequently, we proceed to demonstrate the proof.

###  4.1 QSZK containment from the Quantum Entropy Difference Problem

Along the line of Berman et al. [BDRV19], we employ the Quantum Entropy
Difference Problem (QEDP), which is a QSZK-complete problem introduced by Ben-
Aroya, Schwartz, and Ta-Shma [BASTS10]. A concise overview on QEDP can be
found in Appendix D. Utilizing a reduction from QJSP to QEDP, we establish a
QSZK containment for QJSP with an inverse polynomial promise gap.

[QJSP is in QSZK]lemmaQJSPinQSZK For any $0\leq\beta(n)<\alpha(n)\leq 1$ such
that $\alpha(n)-\beta(n)\geq 1/p(n)$ where $p(n)$ is some polynomial of $n$,
we have $(\alpha,\beta)$-QJSP is in QSZK.

With inequalities between the trace distance and the $\mathrm{QJS}$, we
further derive a QSZK containment with a $1/\mathrm{poly}(n)$ promise gap for
QSDP on some parameter regime. The proof is deferred in Appendix E.
theoremQSDPinQSZKinversepoly For any
$0\leq\sqrt{2\ln{2}}\beta(n)<\alpha^{2}(n)\leq 1$ such that
$\alpha^{2}(n)-\sqrt{2\ln{2}}\beta(n)\geq 1/p(n)$ where $p(n)$ is some
polynomial of $n$, we know that $(\alpha^{2}(n),\sqrt{2\ln{2}}\beta(n))$-QSDP
is in QSZK.

It is worthwhile to mention that as shown in [BDRV19], $(\alpha,\beta)$-TDP is
in SZK for $\beta(n)-\alpha(n)$ is at least some inverse polynomial of $n$.
However, we unlikely have an analogous reduction from QTDP to QJSP.

######  Remark 4.3 (An obstacle on a reduction from QTDP to QJSP).

The SZK containment of TDP follows from a tailor-made (Karp) reduction from
TDP to JSP. The key observation is that $\mathrm{TD}(p_{0},p_{1})$ is a
constant multiplicative-error approximation of $\mathrm{JS}(p_{0},p_{1})$, and
specifically, the lower bound $\mathrm{TD}(p_{0},p_{1})/2$ is essentially the
first-order approximation of the series used in the upper bound
$\ln{2}\cdot\mathrm{TD}(p_{0},p_{1})$. Utilizing this fact, Lemma 4.5 in
[BDRV19] show that $\lambda^{2}\mathrm{TD}(p_{0},p_{1})$ is a
$1/\mathrm{poly}(n)$-additive error approximation of
$\mathrm{JS}(q_{0},q_{1})$ where $\lambda$ is some specific
$1/\mathrm{poly}(n)$ factor and $q_{0}$ (also $q_{1}$) are a convex
combination of $p_{0}$ and $p_{1}$ parameterized by $\lambda$. However,
$\textnormal{{QTD}}(\rho_{0},\rho_{1})$ is not a constant multiplicative error
approximation of $\mathrm{QJS}(\rho_{0},\rho_{1})$.

####  QJSP is in QSZK.

Adapting the classical proof171717To be specific, Proposition 4.1 and Lemma
4.2 in [BDRV19]. requires several modifications, since this proof utilizes a
conditional probability that conditions on distributions are supposed to be
distinguished, and meanwhile its quantum counterpart is not well-defined. We
circumvent this caveat by considering a conditional entropy of classical-
quantum states conditioned on a classical register that behaves analogously to
the classical analogue.

###### Proof Sketch of Section 4.1.

The proof reduces $(\alpha,\beta)$-QJSP to $g(n)$-QEDP for
$0\leq\beta(n)<\alpha(n)\leq 1$ such that $\alpha(n)-\beta(n)\geq
1/\mathrm{poly}(n)$ where $g(n):=\frac{1}{2}[\alpha(n-1)-\beta(n-1)]$. And the
full proof is deferred to Appendix E.

Given a QJSP instance $(Q_{0},Q_{1})$ which is a pair of quantum circuits.
Consider a classical-quantum state $\sigma=\frac{1}{2}|0\rangle\langle
0|\otimes\rho_{0}+\frac{1}{2}|1\rangle\langle 1|\otimes\rho_{1}$, where
$\rho_{i}$ is the state prepared by the circuit $Q_{i}$ and the classical
register is $B$. The reduction outputs classical-quantum states $\sigma$ and
$\sigma^{\prime}$ such that $\sigma^{\prime}=(p_{0}|0\rangle\langle
0|+p_{1}|1\rangle\langle 1|)\otimes(\frac{1}{2}\rho_{0}+\frac{1}{2}\rho_{1})$
and $B^{\prime}=(p_{0},p_{1})$ is an independent random bit with
$H(B^{\prime})=1-\frac{1}{2}[\alpha(n)+\beta(n)]$. Leveraging a nice equality
regarding the conditional entropy of a classical-quantum state conditioned on
the classical register (e.g., Theorem 11.2.2 in [Wil13]), we then have derived
that
$S(\sigma^{\prime})-S(\sigma)=\mathrm{QJS}(\rho_{0},\rho_{1})-\frac{1}{2}[\alpha(n)+\beta(n)]$.

Plugging this into the promise, we obtain that
$S(\sigma^{\prime})-S(\sigma)\geq\frac{1}{2}[\alpha(n)-\beta(n)]=g(n+1)$
provided that $\mathrm{QJS}(\rho_{0},\rho_{1})\geq\alpha(n)$ whereas
$S(\sigma^{\prime})-S(\sigma)\leq-\frac{1}{2}[\alpha(n)-\beta(n)]=g(n+1)$ if
$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\beta(n)$. Since $\sigma$ and
$\sigma^{\prime}$ are $(n+1)$-qubit states, the output length of the
corresponding new quantum circuits $\tilde{Q}_{0}$ and $\tilde{Q}_{1}$ is
$n+1$. Therefore, $(\rho_{0},\rho_{1})\mapsto(\sigma^{\prime},\sigma)$ is
indeed a polynomial-time reduction from $(\alpha,\beta)$-QJSP to $g$-QEDP. ∎

###  4.2 QSZK containment using the polarization lemma

Now we introduce a new polarization lemma for the measured quantum triangular
discrimination ($\mathrm{QTD}^{\rm meas}$), this will analogously lead to a
QSZK containment for measQTDP. Interestingly, this polarization lemma for
$\mathrm{QTD}^{\rm meas}$ only needs $\alpha>\beta$181818In fact, combined
with a conjectured triangle inequality for the square root of the quantum
triangular discrimination (QTD), we will result in a polarization lemma for
the QTD that also needs $\alpha^{2}>\beta$ since the inequalities on QTD
differ. Moreover, since the proof of Section 4.3 straightforwardly extends to
the QSZK-hardness of the Quantum Triangular Discrimination Problem (QTDP),
this polarization lemma for QTD will also indicate that QTDP is also QSZK-
complete. , whereas the equivalent of the trace distance requires
$\alpha^{2}>\beta$.

[A polarization lemma for the $\mathrm{QTD}^{\rm
meas}$]lemmameasQTDpolarization For quantum circuits $(Q_{0},Q_{1})$ that
specify quantum states $\rho_{0},\rho_{1}$ respectively, there is a
deterministic procedure on input $(Q_{0},Q_{1},1^{n},\alpha,\beta,l)$, where
$\alpha>\beta$, outputs a pair of quantum circuits
$\tilde{Q}_{0},\tilde{Q}_{1}$ specifies quantum states $\tilde{\rho}_{0}$ and
$\tilde{\rho}_{1}$ satisfying that $\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\geq\alpha\Rightarrow\mathrm{QTD}^{\rm
meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})\geq 1-2^{-l}$ and $\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\beta\Rightarrow\mathrm{QTD}^{\rm
meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})\leq 2^{-l}$. Here
$\tilde{\rho}_{0},\tilde{\rho}_{1}$ are $kl$-qubit states. And the time
complexity is a polynomial in the size of $Q_{0}$ and $Q_{1}$, as well as in
$l$ and $\exp\big{(}\frac{\beta\log(1/\alpha)}{\alpha-\beta}\big{)}$.

Analogous to the QSDP, Section 4.2 derives a QSZK containment for measQTDP by
a (Karp) reduction to the QSDP. A detailed analysis of Section 4.2 is provided
in Appendix E.

[measQTDP is in QSZK]lemmameasQTDPinQSZK For any efficiently computable
functions $\alpha(n)$ and $\beta(n)$ such that $0\leq\beta(n)<\alpha(n)\leq 1$
and $\alpha(n)-\beta(n)\geq O(1/\log(n))$, $(\alpha,\beta)$-measQTDP is in
QSZK.

#### A polarization lemma for measQTDP.

Now we provide this new polarization lemma for measQTDP, and this technique
utilizes one-sided error reduction for yes instances also no instances,
separately and alternatively. We begin with no-instances error reduction,
which is referred to as the XOR lemma in the context of the polarization lemma
of the SDP. It is noteworthy that the counterpart result of Section 4.2 holds
for the quantum triangular discrimination, as expressed by
$\textnormal{{QTD}}(\tilde{\rho}_{0},\tilde{\rho}_{1})=\textnormal{{QTD}}(\rho_{0},\rho_{1})^{l}$.

[No-instance error reduction for measQTDP] For quantum circuits
$(Q_{0},Q_{1})$ the specifies quantum states $\rho_{0}$ and $\rho_{1}$, there
exists a deterministic procedure on input $(Q_{0},Q_{1},1^{n},l)$ output new
quantum circuits $(\tilde{Q}_{0},\tilde{Q}_{1})$ specifying quantum states
$\tilde{\rho}_{0},\tilde{\rho}_{1}$ satisfying $\mathrm{QTD}^{\rm
meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})=\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})^{l}$, where
$\tilde{\rho}_{k}=2^{-l+1}\sum_{b_{1}\oplus\cdots\oplus
b_{l}=k}\rho_{b_{1}}\otimes\cdots\otimes\rho_{b_{l}}\text{ for
}k\in\\{0,1\\}$.

factmeasQTDnoErrorReduction For quantum states
$\rho_{0},\rho_{1},\rho^{\prime}_{0},\rho^{\prime}_{1}$, define
$\tilde{\rho}_{0}:=\frac{1}{2}(\rho^{\prime}_{0}\otimes\rho_{0}+\rho^{\prime}_{1}\otimes\rho_{1})$
and
$\tilde{\rho}_{1}:=\frac{1}{2}(\rho^{\prime}_{0}\otimes\rho_{1}+\rho^{\prime}_{1}\otimes\rho_{0})$,
then $\mathrm{QTD}^{\rm
meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})=\mathrm{QTD}^{\rm
meas}(\rho^{\prime}_{0},\rho^{\prime}_{1})\cdot\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})$.

###### Proof of Section 4.2.

It suffices to show Section 4.2, following from an effortless calculation (the
full proof is deferred to Appendix E). Then we complete the proof by
inductively applying Section 4.2 to $\mathrm{QTD}^{\rm
meas}\big{(}\tilde{\rho}^{(l)}_{0},\tilde{\rho}^{(l)}_{1}\big{)}$. ∎

We then proceed with yes-instance error reduction, which is referred to as the
direct product lemma in the context of the polarization lemma of the SDP. It
is noteworthy that the lower bound obtained through this approach exhibits a
quadratic improvement compared to the equivalent of the trace distance,
whereas the upper bound is slightly worse191919This difference follows from
the property of the trace distance and statistical distance being metrics,
whereas the triangular discrimination and probably its quantum counterpart are
merely squares of a metric. than the one presented in Lemma 9 of [Wat02].

[Yes-instance error reduction for measQTDP]lemmameasQTDyesErrorReduction For
quantum circuits $(Q_{0},Q_{1})$ that specify quantum states $\rho_{0}$ and
$\rho_{1}$, there is a deterministic procedure on input
$(Q_{0},Q_{1},1^{n},l)$ outputs new quantum circuits
$(\tilde{Q}_{0},\tilde{Q}_{1})$ specifying quantum states $\tilde{\rho}_{0}$
and $\tilde{\rho}_{1}$ satisfying

$1-\exp\big{(}-\tfrac{l}{2}\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\big{)}\leq\mathrm{QTD}^{\rm
meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})\leq 2l\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1}),$

where $\tilde{\rho}_{k}:=\rho_{k}^{\otimes l}\text{ for }k\in\\{0,1\\}.$

###### Proof Sketch.

Analogous to Lemma 4.10 in [BDRV19], we take advantage of that the Bures
distance between two tensor-product states $\rho_{0}^{\otimes l}$ and
$\rho_{1}^{\otimes l}$ is equally described by the Bures distance between
states $\rho_{0}$ and $\rho_{1}$. To be specific,
$\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0}^{\otimes l},\rho_{0}^{\otimes
l})=1-\left(1-\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\right)^{l}$. We
then finish the proof by plugging this equality into the relationship between
the Bures distance and the $\mathrm{QTD}^{\rm meas}$. The full proof is
deferred to Appendix E. ∎

Eventually, according to parameters selected in the polarization lemma of the
triangular discrimination (Lemma 4.9 in [BDRV19]), we are capable to prove
Section 4.2 by first applying no-instance error reduction (Section 4.2), then
using yes-instance error reduction (Section 4.2) to ensure that the soundness
parameter is at most $1/2$, and finally applying no-instance error reduction
(Section 4.2) again. The time complexity analysis is also similar to Lemma 38
of [CCKV08]. Detailed proof is deferred to Appendix E.

###  4.3 QSZK-hardness for QJSP and measQTDP

We begin by proving the QSZK-hardness for the Quantum Jensen-Shannon
Divergence problem (QJSP).

[QJSP is QSZK-hard]lemmaQJSPisQSZKhard Let $\alpha(n)$ and $\beta(n)$ be
efficiently computable functions such that there is a constant
$\epsilon\in(0,1/2)$ such that $\alpha(n)\leq 1-2^{-n^{1/2-\epsilon}}$ and
$\beta(n)\geq 2^{-n^{1/2-\epsilon}}$ for every $n\in\mathbb{N}$. Then
$(\alpha,\beta)$-QJSP is QSZK-hard.

In a manner similar to the demonstration of the SZK-hardness for the JSP
(Lemma 4.3 in [BDRV19], we utilize the relationship between the trace distance
and the $\mathrm{QJS}$ by combining Section 2.1 and Section 2.1, which is
identical to the inequalities between the statistical distance and the Jensen-
Shannon divergence [FvdG99, Top00]. The detailed proof can be found in
Appendix E. Next, we proceed to show the QSZK-hardness for the Measured
Quantum Triangular Discrimination problem (measQTDP).

[measQTDP is QSZK-hard]lemmameasQTDPisQSZKhard Let $\alpha(n)$ and $\beta(n)$
be efficiently computable functions such that there exists a constant
$\epsilon\in(0,1/2)$ such that $\alpha(n)\leq 1-2^{-n^{1/2-\epsilon}}$ and
$\beta(n)\geq 2^{-n^{1/2-\epsilon}}$ for every $n\in\mathbb{N}$. Then we have
QSZK-hardness for $(\alpha,\beta)$-measQTDP.

The proof follows a simialr approach to the demonstration of the SZK-hardness
for the TDP (Lemma 4.4 in [BDRV19]), employing the inequality between the
trace distance and the $\mathrm{QTD}^{\rm meas}$ presented in Theorem 3.1,
which is as same as the the inequalities between the counterpart classical
distances shown in [Top00]. The full proof of Section 4.3 is deferred to
Appendix E. Furthermore, we remark that the QSZK-hardness also holds for the
Quantum Triangular Discrimination problem defined analogously.

##  5 Easy regimes for the class QSZK

We begin with the main result in this section.

######  Theorem 5.1 ($\overline{\mbox{{QSDP}}}$ with negligible errors is in
PP).

For any efficiently computable functions $\alpha(n),\beta(n)$ such that
$1-2^{-n/2-1}\leq\alpha(n)\leq 1$ and $0\leq\beta(n)\leq 2^{-n/2-1}$,
$(\alpha,\beta)$-$\overline{\mbox{{QSDP}}}$ is in PP.

Theorem 5.1 is in line with a classical result, as depicted in Theorem 7.1 in
[BCH+19], that when errors in $\overline{\mathrm{SD}}$ are negligible, it is
in the class PP. It is important to note that $\overline{\mbox{{QSDP}}}$ is
also QSZK-complete since QSZK is closed under the complement [Wat02].
Furthermore, the implications of Theorem 5.1 suggest that achieving a length-
preserving polarization for the Quantum State Distinguishability problem
(QSDP) appears to be implausible. This is because if such a polarization were
possible, Theorem 5.1 would imply
$\textnormal{{QSZK}}\subseteq\textnormal{{PP}}$, which seems unlikely based on
the existing oracle separation [BCH+19].

###  5.1 $\overline{\mbox{{QSDP}}}$ without error is in
$\textnormal{{BQP}}_{1}$

As a prelude to Theorem 5.1, we first present an effortless observation.

[$\overline{\mbox{{QSDP}}}$ without error is in $\textnormal{{BQP}}_{1}$]
$(1,0)$-$\overline{\mbox{{QSDP}}}$ is in $\textnormal{{BQP}}_{1}$.

###### Proof.

For any quantum states $\rho_{0}$ and $\rho_{1}$, we notice the following
properties on $\mathrm{td}(\rho_{0},\rho_{1})$:

  1. (1)

$\mathrm{td}(\rho_{0},\rho_{1})=0$ if and only if $\rho_{0}=\rho_{1}$, due to
the trace distance being a metric;

  2. (2)

$\mathrm{td}(\rho_{0},\rho_{1})=1$ if and only if $\rho_{0}$ and $\rho_{1}$
have orthogonal supports, as per the triangular inequality:
$\mathrm{td}(\rho_{0},\rho_{1})\leq\frac{1}{2}\left(\mathrm{Tr}|\rho_{0}|+\mathrm{Tr}|\rho_{0}|\right)=1$.

When $\rho_{0}=\rho_{1}$, it is evident that
$\mathrm{Tr}(\rho_{0}\rho_{1})=1$. In the case where $\rho_{0}$ and $\rho_{1}$
have orthogonal supports, $\mathrm{Tr}(\rho_{0}\rho_{1})=0$. Therefore, we can
apply the SWAP test [BCWdW01] to quantum states $\rho_{0}$ and $\rho_{1}$
(e.g., Proposition 9 in [KMY09]). The acceptance probability is
$\frac{1}{2}\left(1+\mathrm{Tr}(\rho_{0}\rho_{1})\right)$, and this BQP
algorithm merely errs on no instances, which belongs to the class referred to
as coRQP or $\textnormal{{BQP}}_{1}$. ∎

Section 5.1 is unique in that it does not have a straightforward classical
analogue. We define the collision distance between $p_{0}$ and $p_{1}$ as
$\mathrm{Col}(p_{0},p_{1}):=\sum_{x}p_{0}(x)p_{1}(x)$. It follows that if
$\mathrm{SD}(p_{0},p_{1})=1$, then $\mathrm{Col}(p_{0},p_{1})=0$. Conversely,
if $\mathrm{SD}(p_{0},p_{1})=0$, then $\mathrm{Col}(p_{0},p_{1})\geq
1/|\mathrm{supp}\left(p_{0}\right)\cap\mathrm{supp}\left(p_{1}\right)|$ with
equality being achieved when $p_{0}$ and $p_{1}$ are uniform on
$\mathrm{supp}\left(p_{0}\right)\cap\mathrm{supp}\left(p_{1}\right)$. This
observation merely leads to an NP containment for
$(1,0)$-$\overline{\mathrm{SD}}$202020Note that there exists
$x\in\mathrm{supp}\left(p_{0}\right)\cup\mathrm{supp}\left(p_{1}\right)$ for
$\mathrm{SD}(p_{0},p_{1})=0$, then the prover could provide the corresponding
$w_{0}$ and $w_{1}$ as a witness such that $C_{0}(w_{0})=C_{1}(w_{1})=x$.
Additionally, such a witness does not exist for no instances, i.e.,
$\mathrm{SD}(p_{0},p_{1})=1$..

###  5.2 $\overline{\mbox{{QSDP}}}$ with a negligible error is in PP

The crucial insight for comprehending the PP containment of
$(1-\mathrm{negl},\mathrm{negl})$-$\overline{\mbox{{QSDP}}}$ is given by the
expression
$\frac{1}{2}\mathrm{HS}^{2}(\rho_{0},\rho_{1})=\frac{1}{2}\mathrm{Tr}(\rho_{0}-\rho_{1})^{2}=\frac{1}{2}\big{(}\mathrm{Tr}(\rho^{2}_{0})+\mathrm{Tr}(\rho^{2}_{1})\big{)}-\mathrm{Tr}(\rho_{0}\rho_{1})$.
It is noteworthy that by employing the SWAP test [BCWdW01] for mixed states
(e.g., Proposition 9 in [KMY09]), one can estimate the three terms involved:
$\mathrm{Tr}(\rho^{2}_{0})$, $\mathrm{Tr}(\rho^{2}_{1})$, and
$\mathrm{Tr}(\rho_{0}\rho_{1})$. This estimation enables the development of a
hybrid algorithm. Subsequently, we proceed to establish Theorem 5.1, which can
be viewed as the quantum counterpart of Theorem 7.1 in [BCH+19].

###### Proof of Theorem 5.1.

Consider two $n$-qubit quantum states, denoted as $\rho_{0}$ and $\rho_{1}$,
defined in a finite-dimensional Hilbert space $\mathcal{H}$ according to
Section 2.2. We begin with the inequality between the trace distance and the
Hilbert-Schmidt distance (e.g., Equation 9.176 in [Wil13]):

$\tfrac{1}{2}\mathrm{HS}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1})\leq\tfrac{\sqrt{\dim\mathcal{H}}}{2}\mathrm{HS}(\rho_{0},\rho_{1}).$
(5.1)

We present a hybrid classical-quantum algorithm $\mathcal{A}$ as follows.
First, we toss two random coins that the outcomes denoted as $r_{1}$ and
$r_{2}$. Subsequently, we apply the SWAP test on the corresponding states in
the following manner:

  * •

If the first coin lands on heads ($r_{1}=1$), we perform the SWAP test on
$\rho_{0}$ and $\rho_{0}$. We accept if the final measurement outcome is $0$.

  * •

If the first coin lands on tails ($r_{1}=0$), we perform the SWAP test on two
copies of $\rho_{r_{2}}$. We accept if the final measurement outcome is $1$.

Let $p^{(o)}_{\mathrm{SWAP}}(\rho_{0},\rho_{1})$ be the probability of the
SWAP test on $\rho_{0}$ and $\rho_{1}$ where the final measurement outcome
$o$. We then obtain the acceptance probability of our algorithm $\mathcal{A}$:

$p^{(0)}_{\mathrm{SWAP}}(\rho_{0},\rho_{1})+\\!\\!\sum_{i\in\\{0,1\\}}\\!\frac{p^{(1)}_{\mathrm{SWAP}}(\rho_{i},\rho_{i})}{2}=\frac{1+\mathrm{Tr}(\rho_{0}\rho_{1})}{2}+\\!\\!\sum_{i\in\\{0,1\\}}\\!\frac{1-\mathrm{Tr}(\rho^{2}_{i})}{4}=\frac{1}{2}-\frac{\mathrm{HS}^{2}(\rho_{0},\rho_{1})}{4}.$
(5.2)

It suffices to show that the algorithm $\mathcal{A}$ is indeed a PP
containment distinguishing yes instances from no instances within an inverse-
exponential accuracy. Plugging Equation 5.1 and Equation 5.2, we then analyze
the acceptance probability: For yes instances, we obtain that
$p^{\sf(Y)}_{\mathcal{A}}(\rho_{0},\rho_{1})=1-\left(\frac{1}{2}\mathrm{HS}(\rho_{0},\rho_{1})\right)^{2}\leq\mathrm{td}(\rho_{0},\rho_{1})^{2}=2^{-n-2}$
because of $\mathrm{td}(\rho_{0},\rho_{1})\leq 2^{-n/2-1}$. For no instances,
notice that $\mathrm{td}(\rho_{0},\rho_{1})\geq 1-2^{-n/2-1}$, we have derived
that
$p^{\sf(N)}_{\mathcal{A}}(\rho_{0},\rho_{1})=1-\left(\frac{1}{2}\mathrm{HS}(\rho_{0},\rho_{1})\right)^{2}\leq
1-\frac{1}{\dim\mathcal{H}}\mathrm{td}(\rho_{0},\rho_{1})^{2}\leq
1-2^{-n}\cdot\big{(}1-2^{-\frac{n}{2}-1}\big{)}^{2}$.

Since $\textnormal{{PreciseBQP}}\subseteq\textnormal{{PP}}$ (e.g., Lemma 3.3
in [GSS+22]), we then complete the proof by showing that the gap
$p^{\sf(Y)}_{\mathcal{A}}(\rho_{0},\rho_{1})-p^{\sf(N)}_{\mathcal{A}}(\rho_{0},\rho_{1})$
is exponentially small as desired:

$p^{\sf(Y)}_{\mathcal{A}}(\rho_{0},\rho_{1})-p^{\sf(N)}_{\mathcal{A}}(\rho_{0},\rho_{1})=2^{-n}\cdot\left(\tfrac{3}{4}-2^{-n/2}\right)+\tfrac{1}{4}\cdot
2^{-2n}\geq\tfrac{1}{4}\cdot 2^{-2n},$

where the last inequality holds for $n\geq 1$. ∎

## Acknowledgments

The author expresses gratitude to François Le Gall for providing valuable
suggestions to improve the presentation and engaging in insightful
discussions. The author also thanks Qisheng Wang for helpful discussions,
particularly proposing the use of the SWAP test in Section 5.1. Moreover, the
author thanks anonymous reviewers for enlightening comments on the
polarization lemma, as well as useful suggestions on improving the
presentation. The author was partially supported by JSPS KAKENHI Grants No.
JP20H04139.

## References

  * [AGL20] Dorit Aharonov, Alex B Grilo, and Yupan Liu.  StoqMA vs. MA: the power of error reduction.  arXiv preprint arXiv:2010.02835, 2020.
  * [ARSW21] Rochisha Agarwal, Soorya Rethinasamy, Kunal Sharma, and Mark M Wilde.  Estimating distinguishability measures on quantum computers.  arXiv preprint arXiv:2108.08406, 2021.
  * [BASTS10] Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma.  Quantum expanders: Motivation and constructions.  Theory of Computing, 6:47–79, 2010.
  * [BCH+19] Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan.  On the power of statistical zero knowledge.  SIAM Journal on Computing, 49(4):FOCS17–1, 2019.
  * [BCWdW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87(16):167902, 2001.
  * [BDRV19] Itay Berman, Akshay Degwekar, Ron D Rothblum, and Prashant Nalini Vasudevan.  Statistical difference beyond the polarizing regime.  In Theory of Cryptography Conference, pages 311–332. Springer, 2019\.
  * [BGJ19] Rajendra Bhatia, Stephane Gaubert, and Tanvi Jain.  Matrix versions of the Hellinger distance.  Letters in Mathematical Physics, 109(8):1777–1804, 2019.
  * [BH09] Jop Briët and Peter Harremoës.  Properties of classical and quantum Jensen-Shannon divergence.  Physical review A, 79(5):052311, 2009.
  * [Bha96] Rajendra Bhatia.  Matrix Analysis, volume 169.  Springer Science & Business Media, 1996.
  * [BOW19] 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.
  * [CCKV08] André Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, and Salil Vadhan.  Interactive and noninteractive zero knowledge are equivalent in the help model.  In Theory of Cryptography Conference, pages 501–534. Springer, 2008\.
  * [Cio21] Krzysztof J Ciosmak.  Matrix Hölder’s inequality and divergence formulation of optimal transport of vector measures.  SIAM Journal on Mathematical Analysis, 53(6):6932–6958, 2021.
  * [CS20] Sam Cree and Jamie Sikora.  A fidelity measure for quantum states based on the matrix geometric mean.  arXiv preprint arXiv:2006.06918, 2020.
  * [FC94] Christopher A Fuchs and Carlton M Caves.  Ensemble-dependent bounds for accessible information in quantum mechanics.  Physical Review Letters, 73(23):3047, 1994.
  * [FvdG99] Christopher A Fuchs and Jeroen van de Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, 1999\.
  * [Gol19] Oded Goldreich.  Errata (3-Feb-2019).  http://www.wisdom.weizmann.ac.il/~/oded/entropy.html, 2019.
  * [GP22] András Gilyén and Alexander Poremba.  Improved quantum algorithms for fidelity estimation.  arXiv preprint arXiv:2203.15993, 2022.
  * [GSS+22] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka.  Quantum generalizations of the polynomial hierarchy with applications to $\mathsf{QMA(2)}$.  computational complexity, 31(2):1–52, 2022.
  * [GV99] Oded Goldreich and Salil Vadhan.  Comparing entropies in statistical zero knowledge with applications to the structure of SZK.  In Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference)(Cat. No. 99CB36317), pages 54–73. IEEE, 1999.
  * [GV11] Oded Goldreich and Salil P Vadhan.  On the complexity of computational problems regarding distributions.  Studies in Complexity and Cryptography, 6650:390–405, 2011.
  * [Hia21] Fumio Hiai.  Quantum f-divergences in von Neumann Algebras.  Springer, 2021.
  * [HJ12] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge University Press, 2012.
  * [Hol73] Alexander Semenovich Holevo.  Bounds for the quantity of information transmitted by a quantum communication channel.  Problemy Peredachi Informatsii, 9(3):3–11, 1973.
  * [Kai67] Thomas Kailath.  The divergence and bhattacharyya distance measures in signal selection.  IEEE transactions on communication technology, 15(1):52–60, 1967\.
  * [KMY09] 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.
  * [LC86] Lucien Le Cam.  Asymptotic methods in statistical decision theory.  Springer Science & Business Media, 1986.
  * [Liu21] Yupan Liu.  StoqMA meets distribution testing.  In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [MdW16] Ashley Montanaro and Ronald de Wolf.  A survey of quantum property testing.  Theory of Computing, pages 1–81, 2016.
  * [MLP05] Ana P Majtey, Pedro W Lamberti, and Domingo P Prato.  Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states.  Physical Review A, 72(5):052310, 2005.
  * [NC02] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.
  * [Pet07] Dénes Petz.  Quantum information theory and quantum statistics.  Springer Science & Business Media, 2007.
  * [RS90] Mary B Ruskai and Frank H Stillinger.  Convexity inequalities for estimating free energy and relative entropy.  Journal of Physics A: Mathematical and General, 23(12):2421, 1990\.
  * [SV03] Amit Sahai and Salil Vadhan.  A complete problem for statistical zero knowledge.  Journal of the ACM (JACM), 50(2):196–249, 2003.
  * [TKR+10] Kristan Temme, Michael James Kastoryano, Mary Beth Ruskai, Michael Marc Wolf, and Frank Verstraete.  The $\chi^{2}$-divergence and mixing times of quantum markov processes.  Journal of Mathematical Physics, 51(12):122201, 2010.
  * [Top00] Flemming Topsøe.  Some inequalities for information divergence and related measures of discrimination.  IEEE Transactions on information theory, 46(4):1602–1609, 2000\.
  * [TV15] Kristan Temme and Frank Verstraete.  Quantum chi-squared and goodness of fit testing.  Journal of Mathematical Physics, 56(1):012202, 2015.
  * [Vad99] Salil Pravin Vadhan.  A study of statistical zero-knowledge proofs.  PhD thesis, Massachusetts Institute of Technology, 1999.
  * [VW16] Thomas Vidick and John Watrous.  Quantum proofs.  Foundations and Trends® in Theoretical Computer Science, 11(1-2):1–215, 2016.
  * [Wat02] John Watrous.  Limits on the power of quantum statistical zero-knowledge.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 459–468. IEEE, 2002.
  * [Wat06] John Watrous.  Zero-knowledge against quantum attacks.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, pages 296–305, 2006.
  * [Wil13] Mark M Wilde.  Quantum information theory.  Cambridge University Press, 2013.
  * [WZ23] Qisheng Wang and Zhicheng Zhang.  Fast quantum algorithms for trace distance estimation.  arXiv preprint arXiv:2301.06783, 2023.
  * [WZC+23] 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.
  * [Yeh20] Amir Yehudayoff.  Pointer chasing via triangular discrimination.  Combinatorics, Probability and Computing, 29(4):485–494, 2020.

##  Appendix A Classical and quantum distances and divergences

In this section, we will review several commonly used classical distances and
divergences, as well as quantum analogues of the statistical distance and
Hellinger distance.

#### Distances and divergences for classical probability distributions.

We first begin by defining the statistical distance and the triangular
discrimination.

[Statistical Distance] The Statistical Distance between two distributions
$p_{0}$ and $p_{1}$ is
$\mathrm{SD}(p_{0},p_{1}):=\frac{1}{2}\|p_{0}-p_{1}\|_{1}=\frac{1}{2}\sum_{x\in\mathcal{X}}|p_{0}(x)-p_{1}(x)|$
where
$\mathcal{X}:=\mathrm{supp}\left(p_{0}\right)\cup\mathrm{supp}\left(p_{1}\right)$.

[Triangular Discrimination] The Triangular Discrimination (a.k.a., Le Cam
Divergence) between two distributions $p_{0}$ and $p_{1}$ is defined as
$\mathrm{TD}(p_{0},p_{1}):=\frac{1}{2}\sum_{x\in\mathcal{X}}\frac{(p_{0}(x)-p_{1}(x))^{2}}{p_{0}(x)+p_{1}(x)}$.
It is worthwhile to note that the $\mathrm{TD}$ is a symmetrized version of
the $\chi^{2}$ divergence, to be precise,
$\mathrm{TD}(p_{0},p_{1})=\chi^{2}\left(p_{z}\big{\|}\frac{p_{0}+p_{1}}{2}\right)$
for $z\in\\{0,1\\}$. We also know that
$\mathrm{SD}(p_{0},p_{1})^{2}\leq\mathrm{TD}(p_{0},p_{1})\leq\mathrm{SD}(p_{0},p_{1})$,
as presented in [Top00]. Then we proceed with defining the Jensen-Shannon
divergence ($\mathrm{JS}$).

[Jensen-Shannon Divergence] The Jensen-Shannon divergence between two
distributions $p_{0}$ and $p_{1}$ is
$\mathrm{JS}_{2}(p_{0},p_{1}):==\mathrm{H}\left(\frac{p_{0}+p_{1}}{2}\right)-\frac{1}{2}\left[H(p_{0})+H(p_{1})\right]$,
where $\mathrm{H}(p):=-\sum_{x}p(x)\log_{2}p(x)$.

The Jensen-Shannon divergence is a symmetrized version of the Kullback–Leibler
divergence (also known as the relative entropy), namely we have
$\mathrm{JS}_{2}(p,q)=\frac{1}{2}{\rm
KL}\left(p\big{\|}\frac{p+q}{2}\right)+\frac{1}{2}{\rm
KL}\left(q\big{\|}\frac{p+q}{2}\right)$ by a simple calculation.

[Adapted from [FvdG99, Top00]] For any distributions $p_{0}$ and $p_{1}$,

$\sum_{v=1}^{\infty}\frac{\mathrm{SD}(p_{0},p_{1})^{2v}}{\ln{2}\cdot
2v(2v-1)}=1-\mathrm{H_{2}}\left(\frac{1-\mathrm{SD}(p_{0},p_{1})}{2}\right)\leq\mathrm{JS}_{2}(p_{0},p_{1})\leq\mathrm{SD}(p_{0},p_{1}),$

where the binary entropy function
$\mathrm{H_{2}}(p):=-p\log_{2}p-(1-p)\log_{2}(1-p)$.

Finally, we define the Hellinger distance, and the inner product $\langle
P|Q\rangle$ between normalized non-negative vectors which is referred to as
Hellinger affinity (or Bhattacharyya coefficient). [Squared Hellinger
Distance] The square Hellinger distance between two distributions $p$ and $q$
on $\mathcal{X}$ is defined as
$\mathrm{H}^{2}(p,q):=\frac{1}{2}\sum_{x\in\mathcal{X}}(\sqrt{p(x)}-\sqrt{q(x)})^{2}=1-\left\langle
P|Q\right\rangle$, where $|P\rangle:=\sum_{x}\sqrt{p(x)}|x\rangle$ and
$|Q\rangle:=\sum_{x}\sqrt{p(x)}|x\rangle$.

Additionally, a simple observation (see Page 48 in [LC86]) indicates the
squared Hellinger distance is very close to the triangular discrimination.
Specifically, $\mathrm{H}^{2}(p,q)\leq\mathrm{TD}(p,q)\leq
2\mathrm{H}^{2}(p,q)$.

###  A.1 Quantum analogues of statistical distance and Hellinger distance

We continue with the trace distance, which is a metric. This distance has a
maximum value of $1$ occurring when $\rho_{0}$ and $\rho_{1}$ have orthogonal
supports. Moreover, the trace distance is a measured version of the
statistical distance in terms of Equation 2.1, e.g., Theorem 9.1 in [NC02].
[Trace distance] The trace distance between two mixed states $\rho_{0}$ and
$\rho_{1}$ is defined as
$\mathrm{td}(\rho_{0},\rho_{1})=\mathrm{Tr}|\rho_{0}-\rho_{1}|=\mathrm{Tr}(((\rho_{0}-\rho_{1})^{\dagger}(\rho_{0}-\rho_{1}))^{1/2}).$

Although the squared Hellinger distance is closely related to the inner
product, there are several quantum analogues because of the non-commuting
nature of matrices. Based on the (Uhlmann) fidelity, we proceed with the
Squared Bures distance, which is the first quantum analogue of Appendix A
since it is precisely the measured squared Hellingder distance [FC94].
[Squared Bures distance] The squared Bures distance between two mixed states
$\rho_{0}$ and $\rho_{1}$ is defined as
$\mathrm{B}^{2}(\rho_{0},\rho_{1}):=2(1-\mathrm{F}(\rho_{0},\rho_{1}))$ where
the fidelity
$\mathrm{F}(\rho_{0},\rho_{1}):=\mathrm{Tr}|\sqrt{\rho_{0}}\sqrt{\rho_{1}}|$.

We also provide a relationship between the trace distance and the Bures
distance. [Adapted from [FvdG99]] For mixed states $\rho_{0}$ and $\rho_{1}$,
$\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1})\leq\mathrm{B}(\rho_{0},\rho_{1}).$

Notice that matrices $(ABA)^{1/2}$ and $A^{1/2}B^{1/2}A^{1/2}$ are not
generally equal, this fact suggests that the Uhlmann fidelity differs from the
quantum Hellinger affinity
$\mathrm{Q}_{1/2}(\rho_{0},\rho_{1}):=\mathrm{Tr}(\rho_{0}\rho_{1})$. The
latter infers the second quantum analogue of Appendix A.

[Quantum Squared Hellinger Distance] For any mixed states $\rho_{0}$ and
$\rho_{1}$, quantum squared Hellinger distance is defined as
$\mathrm{QH^{2}}(\rho_{0},\rho_{1}):=\frac{1}{2}\mathrm{Tr}(\sqrt{\rho_{0}}-\sqrt{\rho_{1}})^{2}=1-\mathrm{Q}_{1/2}(\rho_{0},\rho_{1}).$
Furthermore, we know that
$\mathrm{F}(\rho_{0},\rho_{1})\geq\mathrm{Q}_{1/2}(\rho_{0},\rho_{1})$. We
further recommend two thorough reviews [CS20, BGJ19] for summarizing different
variants of the fidelity.

##  Appendix B Inequalities on the quantum Jensen-Shannon distance

This section is devoted to missing proofs in Section 2.1. We begin by proving
the relationship between the quantum Jensen-Shannon divergence and the
measured quantum Jensen-Shannon divergence.

*

###### Proof.

We begin with an equivalent characterization of the classical Jensen-Shannon
Divergence, which is a rudimentary property on this distance (e.g.,
Proposition 4.1 in [BDRV19]). [Mutual Information characterization of Jensen-
Shannon Divergence] For any distributions $p_{0}$ and $p_{1}$, let $T$ be a
binary indicator variable that chooses the value of $x$ according to $p_{0}$
if $T=i$ where $i\in\\{0,1\\}$, as well as let $X$ be a random variable
associated with a uniform mixture distribution between $p_{0}$ and $p_{1}$.
Then we obtain $\mathrm{JS}(p_{0},p_{1})=I(T;X)=H(T)-H(T|X)=1-H(T|X)$.

We then observe that $\mathrm{QJS}^{\rm meas}(\rho_{0},\rho_{1})$ is precisely
the accessible information $I_{\rm acc}(\mathfrak{E})$ (e.g., Section 10.8.2
in [Wil13]) on the ensemble $\mathfrak{E}=\\{1/2,\rho_{0};1/2,\rho_{1}\\}$.
Moreover, it is evident that $\mathrm{QJS}(\rho_{0},\rho_{1})$ is the Holevo
information $\chi(\mathfrak{E})$ on the same ensemble. The proof thus follows
from the Holevo bound, namely, $I_{\rm
acc}(\mathfrak{E})\leq\chi(\mathfrak{E})$. ∎

We subsequently proceed to demonstrate the proof of the relationship between
the quantum Jensen-Shannon divergence and the trace distance.

*

###### Proof of Section 2.1.

We first fix some POVM measurement $\mathcal{E}=\\{E_{x}\\}_{x\in\mathcal{U}}$
where
$\mathcal{U}=\mathrm{supp}\left(\rho_{0}\right)\cup\mathrm{supp}\left(\rho_{1}\right)$.
And let $p_{z}^{(\mathcal{E})}$ be the induced distribution with respect to
the POVM $\mathcal{E}$ of $\rho_{z}$ for $z\in\\{0,1\\}$. Equipped with the
left-hand side inequality in Appendix A, we deduce that

$\mathrm{QJS}^{\rm
meas}_{\mathcal{E}^{*}}(\rho_{0},\rho_{1})\geq\mathrm{QJS}^{\rm
meas}_{\mathcal{E}}(\rho_{0},\rho_{1})=\mathrm{JS}(p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})})\geq\sum_{v=1}^{\infty}\tfrac{\mathrm{SD}\big{(}p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})}\big{)}^{2v}}{2v(2v-1)},$
(B.1)

where $\mathcal{E}^{*}$ is an optimal measurement of $\mathrm{QJS}^{\rm
meas}(\rho_{0},\rho_{1})$. Let
$g(x):=\sum_{v=1}^{\infty}\frac{x^{2v}}{2v(2v-1)}$, then $g(x)$ is
monotonically increasing on $0\leq x\leq 1$. Since Equation B.1 holds for
arbitrary POVM $\mathcal{E}$, as well as the trace distance is the measured
statistical distance, we choose the one which maximizes
$\mathrm{td}(\rho_{0},\rho_{1})$. This completes the proof. ∎

*

It is noteworthy that the proof of Section 2.1 is essentially adapting the
demonstration of an analogous result on the counterpart classical distances
(e.g., Claim 4.4.2 in [Vad99]).

###### Proof of Section 2.1.

We begin with the construction in Theorem 14 of [BH09]. Consider a single
qutrit register $B$ with basis vectors $|0\rangle,|1\rangle,|2\rangle$. Define
$\tilde{\rho}_{0}$ and $\tilde{\rho}_{1}$ on $\mathcal{H}\otimes\mathcal{B}$
as below, where $\mathcal{B}=\mathbb{C}^{3}$ is the Hilbert space
corresponding to the register $B$:

$\displaystyle\tilde{\rho}_{0}:=$
$\displaystyle\tfrac{\rho_{0}+\rho_{1}-|\rho_{0}-\rho_{1}|}{2}\otimes\left|2\right\rangle\left\langle
2\right|+\tfrac{\rho_{0}-\rho_{1}+|\rho_{0}-\rho_{1}|}{2}\otimes|0\rangle\langle
0|:=$ $\displaystyle\sigma_{2}\otimes\left|2\right\rangle\left\langle
2\right|+\sigma_{0}\otimes|0\rangle\langle 0|,$
$\displaystyle\tilde{\rho}_{1}:=$
$\displaystyle\tfrac{\rho_{0}+\rho_{1}-|\rho_{0}-\rho_{1}|}{2}\otimes\left|2\right\rangle\left\langle
2\right|+\tfrac{\rho_{1}-\rho_{0}+|\rho_{0}-\rho_{1}|}{2}\otimes|1\rangle\langle
1|:=$ $\displaystyle\sigma_{2}\otimes\left|2\right\rangle\left\langle
2\right|+\sigma_{1}\otimes|1\rangle\langle 1|.$

Here $\sigma_{0}$ corresponds to the regime that $\rho_{0}$ is “larger than”
$\rho_{1}$ (where $\rho_{0}$ and $\rho_{1}$ are “distinguishable”) and so does
$\sigma_{1}$, whereas $\sigma_{2}$ corresponds to the regime that $\rho_{0}$
is “indistinguishable” from $\rho_{1}$. One can see this construction
generalizes the proof of the classical scenario (i.e., Claim 4.4.2 in [Vad99])
to quantum counterparts.

Then it is left to show
$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\mathrm{QJS}(\tilde{\rho}_{0},\tilde{\rho}_{1})=\mathrm{td}(\rho_{0},\rho_{1})$.
Utilizing the data-processing inequality of the quantum relative entropy
(e.g., Theorem 3.9 in [Pet07]), we have derived that

$\displaystyle\mathrm{QJS}(\rho_{0},\rho_{1})$
$\displaystyle=\mathrm{QJS}(\mathrm{Tr}_{B}(\tilde{\rho_{0}}),\mathrm{Tr}_{B}(\tilde{\rho_{1}}))$
(B.2) $\displaystyle\leq\mathrm{QJS}(\tilde{\rho}_{0},\tilde{\rho}_{1})$
$\displaystyle=-\mathrm{Tr}\left(\tfrac{\tilde{\rho}_{0}+\tilde{\rho}_{1}}{2}\ln\tfrac{\tilde{\rho}_{0}+\tilde{\rho}_{1}}{2}\right)+\tfrac{1}{2}\left(\mathrm{Tr}\left(\tilde{\rho}_{0}\ln\tilde{\rho}_{0}\right)+\mathrm{Tr}\left(\tilde{\rho}_{1}\ln\tilde{\rho}_{1}\right)\right),$

where the first line because of $\mathrm{Tr}_{B}(\tilde{\rho}_{k})=\rho_{k}$
for $k\in\\{0,1\\}$, and the third line due to
$\mathrm{QJS}(\rho,\sigma)=S(\frac{\rho+\sigma}{2})-\frac{1}{2}(S(\rho)+S(\sigma))$
for any mixed states $\rho$ and $\sigma$. Notice that $\sigma_{0},\sigma_{1}$,
and $\sigma_{2}$ are orthogonal to each other, and $\ln(A+B)=\ln(A)+\ln(B)$
provided that $A$ and $B$ are orthogonal (i.e., $AB=BA=0$), we obtain that

$\displaystyle\mathrm{Tr}\left(\tfrac{\tilde{\rho}_{0}+\tilde{\rho}_{1}}{2}\ln\tfrac{\tilde{\rho}_{0}+\tilde{\rho}_{1}}{2}\right)=$
$\displaystyle\mathrm{Tr}(\sigma_{2}\log\sigma_{2})+\sum_{k\in\\{0,1\\}}\mathrm{Tr}\left(\tfrac{\sigma_{0}}{2}\ln\tfrac{\sigma_{0}}{2}\right),$
(B.3) $\displaystyle\forall k\in\\{0,1\\},\leavevmode\nobreak\
\mathrm{Tr}\left(\tilde{\rho}_{k}\ln\tilde{\rho}_{k}\right)=$
$\displaystyle\mathrm{Tr}(\sigma_{2}\ln\sigma_{2})+\mathrm{Tr}(\sigma_{k}\log\sigma_{k}).$

Plugging Equation B.3 into Equation B.2, we finish the proof:

$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\mathrm{Tr}\left[\tfrac{\sigma_{0}}{2}\left(\ln\sigma_{0}-\ln\tfrac{\sigma_{0}}{2}\right)\right]+\mathrm{Tr}\left[\tfrac{\sigma_{1}}{2}\left(\ln\sigma_{1}-\ln\tfrac{\sigma_{1}}{2}\right)\right]=\tfrac{\ln{2}}{2}\cdot\mathrm{Tr}(\sigma_{0}+\sigma_{1})=\ln{2}\cdot\mathrm{td}(\rho_{0},\rho_{1}),$

where the third equality due to $\sigma_{0}+\sigma_{1}=|\rho_{0}-\rho_{1}|$. ∎

##  Appendix C Inequalities on the quantum triangular discrmination

We begin by demonstrating that the $\mathrm{QTD}^{\rm meas}$ is upper-bounded
by the QTD.

*

###### Proof of Section 3.

According to Proposition 6 in [TKR+10], a data-processing inequality for the
quantum $\chi^{2}_{\alpha=1/2}$-divergence, we have derived that: for any
mixed states $\rho_{0}$ and $\rho_{1}$,
$\textnormal{{QTD}}(\rho_{0},\rho_{1})=\chi^{2}_{\alpha=1/2}\left(\rho_{0}\big{\|}\tfrac{\rho_{0}+\rho_{1}}{2}\right)\geq\chi^{2}_{\alpha=1/2}\left(\mathcal{M}(\rho_{0})\big{\|}\mathcal{M}(\tfrac{\rho_{0}+\rho_{1}}{2})\right)=\tilde{\chi}^{2}_{\alpha=1/2}\left(\rho_{0}\big{\|}\tfrac{\rho_{0}+\rho_{1}}{2}\right)=\textnormal{{QTD}}^{\rm
meas}(\rho_{0},\rho_{1})$. Here we denote the measured $\chi^{2}$-divergence
as $\tilde{\chi}^{2}_{\alpha}(\cdot,\cdot)$, defining in terms of Equation
2.1. Additionally, we choose the quantum channel $\mathcal{M}$ that
corresponds to the optimal POVM in
$\tilde{\chi}^{2}_{\alpha}\left(\rho_{0}\big{\|}\tfrac{\rho_{0}+\rho_{1}}{2}\right)$.
∎

#### QTD vs. trace distance.

Now we provide detailed proof of Section 3.1.

*

###### Proof.

By a matrix Hölder inequality (e.g., Corollary IV.2.6 in [Bha96]), we obtain

$\displaystyle\textnormal{{QTD}}(\rho_{0},\rho_{1})$
$\displaystyle=\frac{1}{2}\mathrm{Tr}\left((\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}\right)$
(C.1)
$\displaystyle\leq\frac{1}{2}\|\rho_{0}-\rho_{1}\|_{1}\cdot\|(\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}\|_{\infty}$

It is sufficient to show that

$\|(\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}\|_{\infty}=\sigma_{\max}\left((\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}\right)\leq
1,$

where $\sigma_{\max}(A)$ is the largest singular value of $A$. Let
$\rho:=\frac{1}{2}(\rho_{0}+\rho_{1})$, then we have
$(\rho_{0}+\rho_{1})^{-1/2}(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1/2}=\rho^{-1/2}(\rho-\rho_{1})\rho^{-1/2}=I-\rho^{-1/2}\rho_{1}\rho^{-1/2}.$
Note that $\rho^{-1/2}\rho_{1}\rho^{-1/2}$ is positive semi-definite, and
$I-\rho^{-1/2}\rho_{1}\rho^{-1/2}$ thus is Hermitian. We then obtain that
$|I-\rho^{-1/2}\rho_{1}\rho^{-1/2}|\preceq I$212121It suffices to show that
$-I\preceq I-\rho^{-1/2}\rho_{1}\rho^{-1/2}\preceq I$. The right-hand side is
straightforward, while the left-hand side follows from
$\rho^{-1/2}\rho_{1}\rho^{-1/2}\preceq 2I$, which holds trivially by applying
$\Phi(\sigma):=\rho^{1/2}\sigma\rho^{1/2}$ on both sides.. With the help of
Corollary 4.3.12 in [HJ12], a corollary of Weyl’s inequalities, this implies
that

$\displaystyle\sigma_{\max}\left(I-\rho^{-1/2}\rho_{1}\rho^{-1/2}\right)$
$\displaystyle=\lambda_{\max}\left(I-\rho^{-1/2}\rho_{1}\rho^{-1/2}\right)$
(C.2)
$\displaystyle\leq\lambda_{\max}\left(\left(I-\rho^{-1/2}\rho_{1}\rho^{-1/2}\right)+\rho^{-1/2}\rho_{1}\rho^{-1/2}\right)$
$\displaystyle\leq 1.$

Here, the first line is derived from the fact that the singular values of a
Hermitian matrix are equal to the absolute values of the corresponding
eigenvalues of the same matrix, and the last line is due to
$\lambda_{\max}(I)=1$. ∎

The proof for the equality condition, stated in Section 3.1, is provided
below.

*

###### Proof.

We begin with the equality condition for the matrix Hölder inequality in
Theorem 2.11 of [Cio21]. Let $A=\frac{\rho_{0}-\rho_{1}}{2}$ and
$B=\left(\frac{\rho_{0}+\rho_{1}}{2}\right)^{-1/2}\left(\frac{\rho_{0}-\rho_{1}}{2}\right)\left(\frac{\rho_{0}+\rho_{1}}{2}\right)^{-1/2}$,
then

$\frac{A^{\dagger}B}{\mathrm{Tr}|A|\|B\|_{\infty}}=\frac{B^{\dagger}A}{\mathrm{Tr}|A|\|B\|_{\infty}}=\frac{|A|}{\mathrm{Tr}|A|}=\frac{|B|^{\infty}}{\mathrm{Tr}\left(|B|^{\infty}\right)}.$
(C.3)

Moreover, $B^{\dagger}A$ is supposed to be symmetric and positive semi-
definite. Note that $A$ and $B$ are Hermitian, we obtain $[A,B]=0$ utilizing
the first equality in Equation C.3. This implies that $B^{\dagger}A$ is indeed
symmetric, as well as the singular value decomposition
$A=\sum_{k}\sigma_{k}(A)|v_{k}\rangle\langle v_{k}|$ and
$B=\sum_{k}\sigma_{k}(B)|v_{k}\rangle\langle v_{k}|$. Then by Equation C.3, we
have derived that

$\displaystyle
B^{\dagger}A=\sum_{k}\sigma_{k}(B)\sigma_{k}(A)|v_{k}\rangle\langle v_{k}|$
$\displaystyle=\sigma_{\max}(B)\sum_{k}\sigma_{k}(A)|v_{k}\rangle\langle
v_{k}|=\|B\|_{\infty}|A|,$
$\displaystyle\tfrac{|A|}{\mathrm{Tr}|A|}=\sum_{k}\tfrac{\sigma_{k}(A)}{\sum_{i}\sigma_{i}(A)}|v_{i}\rangle\langle
v_{i}|$
$\displaystyle=\sum_{k}\tfrac{\sigma_{k}^{\infty}}{\sum_{j}\sigma_{k}^{\infty}(B)}|v_{k}\rangle\langle
v_{k}|=\tfrac{|B|^{\infty}}{\mathrm{Tr}\left(|B|^{\infty}\right)}.$

Notice that
$\\{|v_{i}\rangle\\}_{i\in\mathrm{supp}\left(\rho_{0}-\rho_{1}\right)}$ is an
orthonormal basis, by comparing the coefficients, we obtain

$\forall k:\leavevmode\nobreak\ \sigma_{k}(A)=\sigma_{\max}(A)\text{ and
}\sigma_{k}(B)=\sigma_{\max}(B)=1.$ (C.4)

Here, $\sigma_{\max}(B)=1$ due to Equation C.2 with the equality. Therefore,
we obtain that $B$ is an orthogonal matrix, which is equivalent to
$(\rho_{0}-\rho_{1})(\rho_{0}+\rho_{1})^{-1}(\rho_{0}-\rho_{1})=(\rho_{0}+\rho_{1})$.
Furthermore, note that $\mathrm{Tr}(A^{\dagger}A)=\sum_{k}\sigma^{2}_{k}(A)$,
this equality implies that
$A^{\dagger}A=\frac{\mathrm{Tr}\left(A^{\dagger}A\right)}{|\mathrm{supp}\left(\rho_{0}-\rho_{1}\right)|}I$
as desired. Finally, in order to make $B^{\dagger}A$ to be semi-positive, we
require that $\mathrm{sgn}\lambda_{k}(A)=\mathrm{sgn}\lambda_{k}(B)$ for any
$k\in\mathrm{supp}\left(\rho_{0}-\rho_{1}\right)$, which finishes the proof. ∎

With Section 3, we derive a lower bound for quantum analogues of triangular
discrimination based on the trace distance.
[$\mathrm{QSD}^{2}\leq\textnormal{{QTD}}$] For any mixed states $\rho_{0}$ and
$\rho_{1}$, we know that for any $\alpha\in[0,1]$,
$\mathrm{td}(\rho_{0},\rho_{1})^{2}\leq\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})$.

###### Proof.

Owing to Section 3, it suffices to show that $\textnormal{{QTD}}^{\rm
meas}(\rho_{0},\rho_{1})\geq\mathrm{td}(\rho_{0},\rho_{1})$. Analogous to the
approach presented in [Top00], we obtain the following for any POVM
$\mathcal{E}$:

$\displaystyle\textnormal{{QTD}}^{\rm meas}(\rho_{0},\rho_{1})$
$\displaystyle\geq\mathrm{TD}\left(p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})}\right)$
(C.5)
$\displaystyle=\frac{1}{2}\sum_{x}\tfrac{\left(p_{0}^{(\mathcal{E})}(x)-p_{1}^{(\mathcal{E})}(x)\right)^{2}}{p_{0}^{(\mathcal{E})}(x)+p_{1}^{(\mathcal{E})}(x)}$
$\displaystyle=\sum_{x}\tfrac{p_{0}^{(\mathcal{E})}(x)+p_{1}^{(\mathcal{E})}(x)}{2}\cdot\left(\tfrac{p_{0}^{(\mathcal{E})}(x)-p_{1}^{(\mathcal{E})}(x)}{p_{0}^{(\mathcal{E})}(x)+p_{1}^{(\mathcal{E})}(x)}\right)^{2}$
$\displaystyle\geq\Big{(}\sum_{x}\tfrac{p_{0}^{(\mathcal{E})}(x)+p_{1}^{(\mathcal{E})}(x)}{2}\cdot\tfrac{p_{0}^{(\mathcal{E})}(x)-p_{1}^{(\mathcal{E})}(x)}{p_{0}^{(\mathcal{E})}(x)+p_{1}^{(\mathcal{E})}(x)}\Big{)}^{2}$
$\displaystyle=\Big{(}\tfrac{1}{2}\sum_{x}|p_{0}^{(\mathcal{E})}(x)-p_{1}^{(\mathcal{E})}(x)|\Big{)}^{2},$

where the fourth line is because of $\mathbb{E}[X^{2}]\geq(\mathbb{E}[X])^{2}$
for any random variable $X$. We then complete the proof by choosing
$\mathcal{E}$ that maximizes the last line in Equation C.5. ∎

#### QTD vs. (squared) Bures distance.

As the measured quantum triangular discrimination plays a crucial role in the
polarization lemma for this distance (see Section 4.2), we are going to
provide the lower and upper bounds on it.

For any mixed states $\rho_{0}$ and $\rho_{1}$,
$\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\mathrm{B}^{2}(\rho_{0},\rho_{1})$.

###### Proof.

Let $\mathcal{E}^{*}$ be the optimized measurement for $\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})$. We first notice that

$\displaystyle\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})=\frac{1}{2}\sum_{x}\tfrac{\left(p_{0}^{(\mathcal{E}^{*})}(x)-p_{1}^{(\mathcal{E}^{*})}(x)\right)^{2}}{p_{0}^{(\mathcal{E}^{*})}(x)+p_{1}^{(\mathcal{E}^{*})}(x)}=\frac{1}{2}\sum_{x}\tfrac{\left(\sqrt{p_{0}^{(\mathcal{E}^{*})}(x)}-\sqrt{p_{1}^{(\mathcal{E}^{*})}(x)}\right)^{2}\left(\sqrt{p_{0}^{(\mathcal{E}^{*})}(x)}+\sqrt{p_{1}^{(\mathcal{E}^{*})}(x)}\right)^{2}}{p_{0}^{(\mathcal{E}^{*})}(x)+p_{1}^{(\mathcal{E}^{*})}(x)}.$

Note that $a^{2}+b^{2}\leq(a+b)^{2}\leq 2(a^{2}+b^{2})$ for $a,b\geq 0$, we
have derived that

$\frac{1}{2}\sum_{x}\left(\sqrt{p_{0}^{(\mathcal{E})}(x)}-\sqrt{p_{1}^{(\mathcal{E})}(x)}\right)^{2}\leq\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\sum_{x}\left(\sqrt{p_{0}^{(\mathcal{E}^{*})}(x)}-\sqrt{p_{1}^{(\mathcal{E}^{*})}(x)}\right)^{2}.$
(C.6)

Now notice that the Bures distance is the measured Hellinger distance [FC94],
we obtain: For the lower bound, since the first inequality in Equation C.6
holds for arbitrary POVM $\mathcal{E}$, we choose $\mathcal{E}^{\prime}$ that
maximizes the measured Hellinger distance, which indicates that
$\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\geq\frac{1}{2}\sum_{x}\left(\sqrt{p_{0}^{(\mathcal{E}^{\prime})}(x)}-\sqrt{p_{1}^{(\mathcal{E}^{\prime})}(x)}\right)^{2}=\sup_{{\rm
POVM}\leavevmode\nobreak\
\mathcal{E}}\mathrm{H}^{2}\left(p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})}\right)=\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1}).$
For the upper bound, let $\mathcal{E}^{\prime}$ be the POVM measurement that
maximizes the measured Hellinger distance. By the second inequality in
Equation C.6, we deduce that $\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\sum_{x}\left(\sqrt{p_{0}^{(\mathcal{E}^{\prime})}(x)}-\sqrt{p_{1}^{(\mathcal{E}^{\prime})}(x)}\right)^{2}=\sup_{{\rm
POVM}\leavevmode\nobreak\
\mathcal{E}}2\mathrm{H}^{2}\left(p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})}\right)=\mathrm{B}^{2}(\rho_{0},\rho_{1}).$
∎

In comparison, the upper bound of the quantum triangular discrimination is as
weak as the trace distance, stated as Appendix C.

For any mixed states $\rho_{0}$ and $\rho_{1}$,
$\frac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{B}(\rho_{0},\rho_{1})$.

###### Proof.

We can derive the left-hand side inequality from plugging Section 3 into the
Appendix C. And the right-hand side inequality because of combining Section
A.1 and Section 3.1. ∎

Moreover, it is important to note that Appendix C cannot be improved to
$\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq\mathrm{B}^{2}(\rho_{0},\rho_{1})$.

######  Remark C.1 ($\mathrm{QTD}^{\rm meas}$ vs. QTD).

The squared Bures distance is an example that separates between
$\mathrm{QTD}^{\rm meas}$ and QTD: Utilizing the counterexample $\rho_{0}^{*}$
and $\rho_{1}^{*}$ defined in Remark 3.4, we obtain: $\mathrm{QTD}^{\rm
meas}(\rho^{*}_{0},\rho^{*}_{1})\leq\mathrm{B}^{2}(\rho^{*}_{0},\rho^{*}_{1})<\textnormal{{QTD}}_{\alpha=1/2}(\rho^{*}_{0},\rho^{*}_{1})=\mathrm{td}(\rho^{*}_{0},\rho^{*}_{1})<\mathrm{B}(\rho^{*}_{0},\rho^{*}_{1}).$

#### QTD vs. quantum Jensen-Shannon divergence.

Finally, we link the quantum Jensen-Shannon divergence to the QTD, differing
from the established relationship of
$\frac{1}{2}\mathrm{TD}(p_{0},p_{1})\leq\mathrm{JS}(p_{0},p_{1})\leq\ln{2}\cdot\mathrm{TD}(p_{0},p_{1})$
presented in Theorem 2 of [Top00].

For any mixed states $\rho_{0}$ and $\rho_{1}$,
$\frac{1}{2}\textnormal{{QTD}}^{2}(\rho_{0},\rho_{1})\leq\mathrm{QJS}(\rho_{0},\rho_{1})$.

###### Proof.

Plugging Section 3.1 into Section 2.1, we obtain that: for any mixed states
$\rho_{0}$ and $\rho_{1}$,

$\mathrm{QJS}(\rho_{0},\rho_{1})\geq\sum_{v=1}^{\infty}\tfrac{\mathrm{td}{\rho_{0}}{\rho_{1}}^{2v}}{2v(2v-1)}\geq\sum_{v=1}^{\infty}\tfrac{\textnormal{{QTD}}(\rho_{0},\rho_{1})^{2v}}{2v(2v-1)}\geq\tfrac{1}{2}\textnormal{{QTD}}^{2}(\rho_{0},\rho_{1}),$

where the last inequality uses the first-order approximation. This completes
the proof. ∎

Appendix C follows an analogous proof to that of Theorem 8 in [TKR+10].

For any mixed states $\rho_{0}$ and $\rho_{1}$,
$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\ln{2}\cdot\textnormal{{QTD}}(\rho_{0},\rho_{1})$.

###### Proof.

We commence by noting that an upper bound for the quantum relative entropy in
[RS90]:

$\mathrm{D}(\rho_{0}\|\rho_{1})\leq\frac{1}{\gamma}\mathrm{Tr}\left(\rho_{0}^{1+\gamma}\rho_{1}^{-\gamma}-\rho_{0}\right)=\frac{1}{\gamma}\left[\mathrm{Tr}\left(\rho_{0}^{1+\gamma}\rho_{1}^{-\gamma}\right)-1\right]\text{
for }0<\gamma\leq 1.$ (C.7)

Since the quantum Jensen-Shannon divergence is a symmetrized version of the
quantum relative entropy, we deduce the following with Equation C.7 by
choosing $\gamma=1/2$:

$\displaystyle\mathrm{QJS}(\rho_{0},\rho_{1})$
$\displaystyle=\frac{1}{2}\sum_{z\in\\{0,1\\}}\mathrm{D}\left(\rho_{z}\big{\|}\tfrac{\rho_{0}+\rho_{1}}{2}\right)$
$\displaystyle\leq\sum_{z\in\\{0,1\\}}\left[\mathrm{Tr}\left(\rho_{z}^{3/2}\left(\tfrac{\rho_{0}+\rho_{1}}{2}\right)^{-1/2}\right)-1\right]$
$\displaystyle\leq\frac{1}{2}\sum_{z\in\\{0,1\\}}\left[\mathrm{Tr}\left(\rho_{z}\left(\tfrac{\rho_{0}+\rho_{1}}{2}\right)^{-1/2}\rho_{z}\left(\tfrac{\rho_{0}+\rho_{1}}{2}\right)^{-1/2}\right)-1\right]$
$\displaystyle=\textnormal{{QTD}}(\rho_{0},\rho_{1}),$

where the third line follows from
$\mathrm{Tr}\left[\left(\rho_{z}^{1/2}\rho^{-1/2}\rho_{z}^{1/2}-\rho_{z}^{1/2}\right)^{\dagger}\left(\rho_{z}^{1/2}\rho^{-1/2}\rho_{z}^{1/2}-\rho_{z}^{1/2}\right)\right]\geq
0$ since $\rho_{z}^{1/2}\rho^{-1/2}\rho_{z}^{1/2}$ is clearly positive semi-
definite and thus $\rho_{z}^{1/2}\rho^{-1/2}\rho_{z}^{1/2}-\rho_{z}^{1/2}$ is
Hermitian. ∎

##  Appendix D Quantum entropy difference problem

In this section, We will define the Quantum Entropy Difference problem (QEDP),
and provide an improved QSZK containment of QEDP which is implicitly shown in
[BASTS10].

[Quantum Entropy Difference Problem (QEDP), adapted from [BASTS10]] Given
quantum circuits $Q_{0}$ and $Q_{1}$ acting on $n$ qubits and having $k$
specified output qubits. Let $\rho_{i}$ be the state obtained by running
$Q_{i}$ in $|0^{n}\rangle$, and tracing out the non-output qubits. Let
$g:\mathbb{N}\rightarrow\mathbb{R}^{+}$ be a $\mathrm{poly}(n)$-time
computable function. Then promise that one of the following cases will occur:

  * •

Yes instance: A pair of quantum circuits $(Q_{0},Q_{1})$ such that
$S(\rho_{0})-S(\rho_{1})\geq g(n)$;

  * •

No instance: A pair of quantum circuits $(Q_{0},Q_{1})$ such that
$S(\rho_{1})-S(\rho_{0})\geq g(n)$.

######  Theorem D.1 (Implicitly in [BASTS10]).

For any efficiently computable function $g(n)$ which is an inverse-polynomial
of $n$, $g(n)$-QEDP is in QSZK.

###### Proof.

It suffices to show a promise gap amplification that reduces $g(n)$-QEDP to
$1/2$-QEDP. Consider new states $\tilde{\rho}_{0}$ and $\tilde{\rho}_{1}$
where $\tilde{\rho}_{k}=\rho_{k}^{\otimes p(n)}$ for $k\in\\{0,1\\}$ and
$p(n)$ is a polynomial such that $p(n)g(n)\geq 1/2$. Note that von Neumann
entropy are additive for independent systems, for yes instances, we obtain
that
$S\left(\tilde{\rho}_{0}\right)-S\left(\tilde{\rho}_{1}\right)=p(n)\cdot\left(S(\rho_{0})-S(\rho_{1})\right)\geq
p(n)g(n)\geq\frac{1}{2}$. Likewise, we deduce that
$S(\tilde{\rho}_{1})-S(\tilde{\rho}_{0})\geq 1/2$ for no instances, as
desired. ∎

##  Appendix E Missing proofs on new QSZK complete problems

In this section, we will provide missing proofs of the Quantum Jensen-Shannon
Divergence problem (QJSP) and the Measured Quantum Triangular Discrimination
problem (measQTDP).

####  QJSP is in QSZK.

We start by proving an improved QSZK containment of the Quantum State
Distinguishability problem (QSDP) via a reduction to QJSP. *

###### Proof.

The reduction from QSDP to QJSP straightforwardly follows from the
inequalities on the quantum Jensen-Shannon divergence: For yes instances,
$\mathrm{QJS}_{2}(\rho_{0},\rho_{1})\geq\alpha^{2}$ implies that
$\mathrm{td}(\rho_{0},\rho_{1})\geq\alpha^{2}$ owing to Section 2.1. For no
instances, $\mathrm{QJS}_{2}(\rho_{0},\rho_{1})\leq 2\ln{2}\cdot\beta^{2}$
infers that
$2\ln{2}\cdot\beta^{2}\geq\sum_{v=1}^{\infty}\frac{\mathrm{td}(\rho_{0},\rho_{1})^{2v}}{v(2v-1)}\geq\mathrm{td}(\rho_{0},\rho_{1})^{2}$
as desired, where the last inequality utilizes the first-order approximation.
∎

We next proceed with demonstrating the QSZK containment of QJSP.

*

###### Proof of Section 4.1.

The proof reduces $(\alpha,\beta)$-QJSP to $g(n)$-QEDP for
$0\leq\beta(n)<\alpha(n)\leq 1$ such that $\alpha(n)-\beta(n)$ is at least
some inverse polynomial of $n$, where
$g(n):=\frac{1}{2}[\alpha(n-1)-\beta(n-1)]$.

Given a pair of quantum circuits $(Q_{0},Q_{1})$ acting on $n$ qubits and
having $k$ specified output qubits. Consider a classical-quantum mixed state
on a classical register $B$ and a quantum register $Y$:
$\sigma=\frac{1}{2}|0\rangle\langle
0|\otimes\rho_{0}+\frac{1}{2}|1\rangle\langle 1|\otimes\rho_{1}$, where
$\rho_{i}$ ($i=0,1$) is the state obtained by running $Q_{i}$ in
$|0_{m}\rangle$, and tracing out the non-output qubits. The reduction outputs
classical-quantum mixed states $\sigma$ and $\sigma^{\prime}$ such that
$\sigma^{\prime}=(p_{0}|0\rangle\langle 0|+p_{1}|1\rangle\langle
1|)\otimes(\frac{1}{2}\rho_{0}+\frac{1}{2}\rho_{1})$ and
$B^{\prime}=(p_{0},p_{1})$ is an independent random bit with
$H(B^{\prime})=1-\frac{1}{2}[\alpha(n)+\beta(n)]$. We then obtain that

$\displaystyle S(\sigma^{\prime})-S(\sigma)$
$\displaystyle=S(B^{\prime},Y)_{\sigma^{\prime}}-S(B,Y)_{\sigma}$ (E.1)
$\displaystyle=[H(B^{\prime})+S(Y|B^{\prime})_{\sigma^{\prime}}]-[H(B)+S(Y|B)_{\sigma}]$
$\displaystyle=S(Y)_{\sigma^{\prime}}-S(Y|B)_{\sigma}+H(B^{\prime})-H(B)$
$\displaystyle=S(Y)_{\sigma^{\prime}}-S(Y|B)_{\sigma}-\frac{1}{2}[\alpha(n)+\beta(n)]$
$\displaystyle=S\left(\frac{1}{2}\rho_{0}+\frac{1}{2}\rho_{1}\right)-\frac{1}{2}(S(\rho_{0})+S(\rho_{1}))-\frac{1}{2}[\alpha(n)+\beta(n)]$
$\displaystyle=\mathrm{QJS}(\rho_{0},\rho_{1})-\frac{1}{2}[\alpha(n)+\beta(n)],$

where the second line is due to the definition of quantum condition entropy
and both $B$ and $B^{\prime}$ are classical registers, the third line owing to
the fact that $B^{\prime}$ is an independent random bit, the fifth line
follows from the entropy of a classical-quantum state conditioned on the
classical register (e.g., Theorem 11.2.2 in [Wil13]).

Plugging Equation E.1 into the promise of $(\alpha,\beta)$-QJSP, we then have
that: If $\mathrm{QJS}(\rho_{0},\rho_{1})\geq\alpha(n)$, then
$S(\sigma^{\prime})-S(\sigma)\geq\frac{1}{2}[\alpha(n)-\beta(n)]=g(n+1)$;
whereas if $\mathrm{QJS}(\rho_{0},\rho_{1})\leq\beta(n)$, then
$S(\sigma^{\prime})-S(\sigma)\leq-\frac{1}{2}[\alpha(n)-\beta(n)]=g(n+1)$. As
$\sigma$ and $\sigma^{\prime}$ are $(n+1)$-qubit states, the output length of
the corresponding quantum circuits $\tilde{Q}_{0}$ and $\tilde{Q}_{1}$ is
$n+1$. Therefore, $(\rho_{0},\rho_{1})\mapsto(\sigma^{\prime},\sigma)$ is a
polynomial-time reduction from $(\alpha,\beta)$-QJSP to $g$-QEDP. ∎

####  measQTDP is in QSZK.

We now continue with proving the QSZK containment of measQTDP.

*

###### Proof Sketch.

Utilizing Section 4.2, we begin with $(1-2^{-l(n)},2^{-l(n)})$-QTDP. Then we
will provide a reduction to QSDP: For yes instances, we have
$\mathrm{td}(\rho_{0},\rho_{1})\geq\textnormal{{QTD}}(\rho_{0},\rho_{1})\geq
1-2^{-l(n)}$; For no instances, we know that
$\mathrm{td}^{2}(\rho_{0},\rho_{1})\leq\textnormal{{QTD}}(\rho_{0},\rho_{1})\leq
2^{-l(n)}$, this deduces $\mathrm{td}(\rho_{0},\rho_{1})\leq 2^{-l(n)/2}$. We
conclude that the desired QSZK containment with the completeness $1-2^{-l(n)}$
and the soundness $1/2+2^{-l(n)/2}$ follows from Theorem 10 (as well as the
protocol in Figure 2) in [Wat02]. ∎

We next provide the proof of the key ingredient in no-instance error reduction
for measQTDP.

*

###### Proof of Section 4.2.

Resembling the approach of Proposition 4.12 in [BDRV19], we obtain that

$\displaystyle\mathrm{QTD}^{\rm meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})$
$\displaystyle=$ $\displaystyle\sup_{{\rm POVM}\leavevmode\nobreak\
\mathcal{E}}\mathrm{TD}\left(\tilde{p}_{0}^{(\mathcal{E})},\tilde{p}_{1}^{(\mathcal{E})}\right)$
$\displaystyle=$ $\displaystyle\sup_{{\rm POVM}\leavevmode\nobreak\
\mathcal{E}}\mathrm{TD}\left(p_{0}^{(\mathcal{E})},p_{1}^{(\mathcal{E})}\right)\cdot\mathrm{TD}\left({p^{\prime}_{0}}^{(\mathcal{E})},{p^{\prime}_{1}}^{(\mathcal{E})}\right)$
$\displaystyle=$ $\displaystyle\sup_{{\rm POVM}\leavevmode\nobreak\
\mathcal{E}_{1}\otimes\mathcal{E}_{2}}\mathrm{TD}\left(p_{0}^{(\mathcal{E}_{1})},p_{1}^{(\mathcal{E}_{1})}\right)\cdot\mathrm{TD}\left({p^{\prime}_{0}}^{(\mathcal{E}_{2})},{p^{\prime}_{1}}^{(\mathcal{E}_{2})}\right)$
$\displaystyle=$ $\displaystyle\sup_{{\rm POVM}\leavevmode\nobreak\
\mathcal{E}_{1}}\mathrm{TD}\left(p_{0}^{(\mathcal{E}_{1})},p_{1}^{(\mathcal{E}_{1})}\right)\cdot\sup_{{\rm
POVM}\leavevmode\nobreak\
\mathcal{E}_{2}}\mathrm{TD}\left({p^{\prime}_{0}}^{(\mathcal{E}_{2})},{p^{\prime}_{1}}^{(\mathcal{E}_{2})}\right)$
$\displaystyle=$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\cdot(\rho^{\prime}_{0},\rho^{\prime}_{1}),$

where the fourth line is since we are optimizing the measurement on tensor
product states. ∎

*

###### Proof of Section 4.2.

The proof is analogous to Lemma 4.10 in [BDRV19]. The key ingredient is the
Bures distance as it admits the following property on tensor-product states
$\rho_{0}^{\otimes l}$ and $\rho_{1}^{\otimes l}$:
$\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0}^{\otimes l},\rho_{0}^{\otimes
l})=1-\mathrm{Tr}\sqrt{\rho_{0}}^{\otimes l}\sqrt{\rho_{0}}^{\otimes
l}=1-\left(\mathrm{Tr}\sqrt{\rho_{0}}\sqrt{\rho_{0}}\right)^{l}=1-\left(1-\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\right)^{l}$.
Equipped with Appendix C, we obtain

$\displaystyle\mathrm{QTD}^{\rm meas}(\rho_{0}^{\otimes l},\rho_{1}^{\otimes
l})$ $\displaystyle\leq\mathrm{B}^{2}(\rho_{0}^{\otimes l},\rho_{1}^{\otimes
l})$
$\displaystyle=2\left(1-\left(1-\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\right)^{l}\right)$
$\displaystyle\leq l\mathrm{B}^{2}(\rho_{0},\rho_{1})$ $\displaystyle\leq
2l\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1}),$

where the second inequality is because $(1-x)^{k}\geq 1-kx$ for any $x$ and
integer $k$. Likewise, we also deduce that

$\displaystyle\mathrm{QTD}^{\rm meas}(\rho_{0}^{\otimes l},\rho_{1}^{\otimes
l})$ $\displaystyle\geq\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0}^{\otimes
l},\rho_{1}^{\otimes l})$
$\displaystyle=\left(1-\left(1-\tfrac{1}{2}\mathrm{B}^{2}(\rho_{0},\rho_{1})\right)^{l}\right)$
$\displaystyle\geq\left(1-\left(1-\tfrac{1}{2}\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\right)^{l}\right)$ $\displaystyle\geq
1-\exp\left(-\tfrac{l}{2}\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1})\right),$

where the last equality owing to $1-x\leq e^{-x}$ for any $x$. This finishes
the proof. ∎

Finally, we proceed with demonstrating the polarization lemma of the
$\mathrm{QTD}^{\rm meas}$.

*

###### Proof.

Let $\lambda=\min(\alpha/\beta,2)>1$, and let
$l=\lceil\log_{\lambda}8k\rceil$. Apply no-instance error reduction for
measQTDP (Section 4.2) to the input $(Q_{0},Q_{1},\rho_{0},\rho_{1},1^{l})$ to
produce $(Q^{\prime}_{0},Q^{\prime}_{1})$ with the corresponding
$(\rho^{\prime}_{0},\rho^{\prime}_{1})$ such that

$\displaystyle\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1})\geq\alpha$
$\displaystyle\Longrightarrow$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\rho^{\prime}_{0},\rho^{\prime}_{1})\geq\alpha^{l};$
$\displaystyle\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1})\leq\beta$
$\displaystyle\Longrightarrow$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\rho^{\prime}_{0},\rho^{\prime}_{1})\leq\beta^{l}.$

Let $m:=\lambda^{l}/(4\alpha^{l})\leq 1/(4\beta^{l})$. Also let
$\rho^{\prime\prime}_{0}:=(\rho^{\prime}_{0})^{\otimes m}$ and
$\rho^{\prime\prime}_{1}:=(\rho^{\prime}_{1})^{\otimes m}$, and so do the
corresponding $Q^{\prime\prime}_{0}$ and $Q^{\prime\prime}_{1}$. Then applying
yes-instance error reduction for measQTDP (Section 4.2) yields that

$\displaystyle\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1})\geq\alpha$
$\displaystyle\Longrightarrow$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\rho^{\prime\prime}_{0},\rho^{\prime\prime}_{1})$ $\displaystyle\geq
1-\exp(-\alpha^{l}m/2)\geq 1-e^{-k};$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\beta$ $\displaystyle\Longrightarrow$
$\displaystyle\mathrm{QTD}^{\rm
meas}(\rho^{\prime\prime}_{0},\rho^{\prime\prime}_{1})$ $\displaystyle\leq
2m\beta^{l}\leq 1/2.$

Finally, apply no-instance error reduction for measQTDP (Section 4.2) again to
the input
$(Q^{\prime\prime}_{0},Q^{\prime\prime}_{1},\rho^{\prime\prime}_{0},\rho^{\prime\prime}_{1},1^{k})$
to produce $(\tilde{Q}_{0},\tilde{Q}_{1})$ with the corresponding
$(\tilde{\rho}_{0},\tilde{\rho}_{1})$ such that

$\displaystyle\mathrm{QTD}^{\rm meas}(\rho_{0},\rho_{1})\geq\alpha$
$\displaystyle\Longrightarrow$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})$ $\displaystyle\geq(1-e^{-k})^{k}\geq
1-ke^{-k}\geq 1-2^{-k};$ $\displaystyle\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\beta$ $\displaystyle\Longrightarrow$
$\displaystyle\mathrm{QTD}^{\rm meas}(\tilde{\rho}_{0},\tilde{\rho}_{1})$
$\displaystyle\leq 2^{-k}.$

The last step holds for sufficiently large $k$, which we can achieve by
choosing the appropriate one at the beginning. The time complexity analysis is
analogous to Lemma 38 in [CCKV08]. Note that $\lambda\in(1,2]$, we obtain that
$\ln(\lambda)=\ln(1+(\lambda-1))\geq(\lambda-1)/2\geq\Omega\left(\frac{\alpha-\beta}{\beta}\right)$
where the first inequality due to $\ln(1+x)\geq x/2$ for all $x\in[0,1]$. Then
$l=O\left(\frac{\ln
k}{\ln\lambda}\right)=O\left(\frac{\beta\ln{k}}{\alpha-\beta}\right)$. Hence,
we derive that
$m\leq\frac{1}{4}\cdot\big{(}\frac{2}{\alpha}\big{)}^{l}=\exp\left(O\left(\frac{\beta\ln
k\ln(2/\alpha)}{\alpha-\beta}\right)\right)$. ∎

####  QSZK-hardness for QJSP and measQTDP.

We begin by proving that QJSP is QSZK-hard.

*

###### Proof.

Equipped with the improved QSZK-hardness for QSDP (i.e., Footnote 13), it
suffices to reduce $(1-2^{-n^{1/2-\epsilon/2}},2^{-n^{1/2-\epsilon/2}})$-QSDP
to $(\alpha,\beta)$-QJSP. Consider a pair of quantum circuits $(Q_{0},Q_{1})$
acting on $n$ qubits and having $k$ specified output qubits. Let $\rho_{0}$ be
the state obtained by performing $Q_{i}$ on $|0^{n}\rangle$, and tracing out
the non-output qubits. We then have the following.

  * •

If $\mathrm{td}(\rho_{0},\rho_{1})\geq 1-2^{-n^{1/2-\epsilon/2}}$, then
Section 2.1 yields that

$\mathrm{QJS}(\rho_{0},\rho_{1})\geq
1-\mathrm{H_{2}}\left(\tfrac{1-\mathrm{td}(\rho_{0},\rho_{1})}{2}\right)\geq
1-\mathrm{H_{2}}\left(2^{-n^{1/2-\epsilon/2}-1}\right)\geq 1-2\cdot
2^{-(n^{1/2-\epsilon/2}+1)/2}\geq\alpha(n),$

where the third inequality owing to $\mathrm{H_{2}}(x)\leq 2\sqrt{x}$ for all
$x\in[0,1]$. Then we set $n(\epsilon)$ such that the last inequality holds, to
be precise, there exists a constant $n(\epsilon)$ such that $1-2\cdot
2^{-(n^{1/2-\epsilon/2}+1)/2}\geq 1-2^{-n^{1/2-\epsilon}}$ for all $n\geq
n(\epsilon)$.

  * •

If $\mathrm{td}(\rho_{0},\rho_{1})\leq 2^{-n^{1/2-\epsilon/2}}$, then Section
2.1 indicates that
$\mathrm{QJS}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1})\leq
2^{-n^{1/2-\epsilon/2}}\leq\beta(n)$, where the last inequality holds for any
$n\geq n(\epsilon)$ since $\beta(n)\geq 2^{-n^{1/2-\epsilon/2}}$.

Therefore, this mapping $(Q_{0},Q_{1})\mapsto(Q_{0},Q_{1})$ is a reduction
from $\big{(}1-2^{-n^{1/2-\epsilon/2}},2^{-n^{1/2-\epsilon/2}}\big{)}$-QSDP to
$(\alpha,\beta)$-QJSP, as long as the output length of the given quantum
circuits is larger than $n(\epsilon)$. ∎

We then proceed with demonstrating the QSZK-hardness of measQTDP.

*

###### Proof.

Equipped with the improved QSZK-hardness for QSDP (i.e., Footnote 13 ), it
suffices to reduce $(1-2^{-n^{1/2-\epsilon/2}},2^{-n^{1/2-\epsilon/2}})$-QSDP
to $(\alpha,\beta)$-measQTDP. Consider a pair of quantum circuits
$(Q_{0},Q_{1})$ acting on $n$ qubits and having $k$ specified output qubits.
Let $\rho_{0}$ be the state obtained by performing $Q_{i}$ on $|0^{n}\rangle$,
and tracing out the non-output qubits. Now assume that $n\geq n(\epsilon)$,
where $n(\epsilon)$ is some constant that depends on $\epsilon$, and we will
determine $n(\epsilon)$ later. We then have derived the following.

  * •

If $\mathrm{td}(\rho_{0},\rho_{1})\geq 1-2^{-n^{1/2-\epsilon/2}}$, then
Appendix C yields that

$\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\geq\mathrm{td}(\rho_{0},\rho_{1})^{2}\geq\left(1-2^{-n^{1/2-\epsilon/2}}\right)^{2}\geq
1-2^{-n^{1/2-\epsilon/2}+1}\geq\alpha(n).$

We choose constant $n(\epsilon)$ such that $1-2^{-n^{1/2-\epsilon/2}+1}\geq
1-2^{-n^{1/2-\epsilon}}$ for all $n\geq n(\epsilon)$.

  * •

If $\mathrm{td}(\rho_{0},\rho_{1})\leq 2^{-n^{1/2-\epsilon/2}}$, then Section
3.1 and Section 3 indicate that $\mathrm{QTD}^{\rm
meas}(\rho_{0},\rho_{1})\leq\mathrm{td}(\rho_{0},\rho_{1})\leq
2^{-n^{1/2-\epsilon/2}}\leq\beta(n),$ where the last inequality holds for any
$n\geq n(\epsilon)$ since $\beta(n)\geq 2^{-n^{1/2-\epsilon/2}}$.

Hence, this mapping $(Q_{0},Q_{1})\mapsto(Q_{0},Q_{1})$ is a reduction from
$\big{(}1-2^{-n^{1/2-\epsilon/2}},2^{-n^{1/2-\epsilon/2}}\big{)}$-QSDP to
$(\alpha,\beta)$-measQTDP, as long as the output length of the given quantum
circuits is larger than $n(\epsilon)$. ∎