Quantum state testing beyond the polarizing regime and quantum triangular discrimination

Quantum state testing beyond the polarizing regime and quantum triangular discrimination

연구 분야: Cryptography

학회: computational complexity

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 is at least or at most , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, is in QSZK only within the constant polarizing regime, where are constants satisfying (rather than ), 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.