<p>The complexity class Quantum Statistical Zero-Knowledge <Emphasis FontCategory="SansSerif">(QSZK)</Emphasis> captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textrm{T}(\rho_0,\rho_1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>T</mtext> <mo stretchy="false">(</mo> <msub> <mi>ρ</mi> <mn>0</mn> </msub> <mo>,</mo> <msub> <mi>ρ</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\alpha$</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> or at most <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\beta$</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation>, known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textrm{QSDP}[\alpha,\beta]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>QSDP</mtext> <mo stretchy="false">[</mo> <mi>α</mi> <mo>,</mo> <mi>β</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> is in <Emphasis FontCategory="SansSerif">QSZK</Emphasis> only within the constant polarizing regime, where <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\alpha \, \textrm{and} \, \beta$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mspace width="0.166667em" /> <mtext>and</mtext> <mspace width="0.166667em" /> <mi>β</mi> </mrow> </math></EquationSource> </InlineEquation> are constants satisfying <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\alpha^2 > \beta$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>α</mi> <mn>2</mn> </msup> <mo>></mo> <mi>β</mi> </mrow> </math></EquationSource> </InlineEquation> (rather than <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\alpha > \beta$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>></mo> <mi>β</mi> </mrow> </math></EquationSource> </InlineEquation>), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the <Emphasis FontCategory="SansSerif">SZK</Emphasis> containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work introduces <i>proper</i> quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new <Emphasis FontCategory="SansSerif">QSZK</Emphasis>-complete problems improve <Emphasis FontCategory="SansSerif">QSZK</Emphasis> containments of QSDP beyond the polarizing regime and establish a simple <Emphasis FontCategory="SansSerif">QSZK</Emphasis>-hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in <Emphasis FontCategory="SansSerif">PP</Emphasis>, while the same problem without error is in <Emphasis FontCategory="SansSerif">NQP</Emphasis>. </p>

Quantum state testing beyond the polarizing regime and quantum triangular discrimination

期刊论文
出版模式：

开放获取
发表日期：

2025年9月17日

查看全文

Yupan Liu

摘要

The complexity class Quantum Statistical Zero-Knowledge (QSZK) captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether $\textrm{T}(\rho_0,\rho_1)$ $T (ρ_{0}, ρ_{1})$ is at least $\alpha$ $α$ or at most $\beta$ $β$ , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, $\textrm{QSDP}[\alpha,\beta]$ $QSDP [α, β]$ is in QSZK only within the constant polarizing regime, where $\alpha \, \textrm{and} \, \beta$ $α and β$ are constants satisfying $\alpha^2 > \beta$ $α^{2} > β$ (rather than $\alpha > \beta$ $α > β$ ), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the SZK containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new QSZK-complete problems improve QSZK containments of QSDP beyond the polarizing regime and establish a simple QSZK-hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in PP, while the same problem without error is in NQP.