Quantum state testing beyond the polarizing regime and quantum triangular discrimination

Abstract

The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$) captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether $\mathrm{T}({\rho }_0,{\rho }_1)$ is at least $\alpha$ or at most $\beta$, known as the Quantum State Distinguishability Problem ($\mathrm{QSDP}$) introduced by Watrous (FOCS 2002). However, $\mathrm{QSDP}[\alpha ,\beta ]$ is in $\mathsf{QSZK}$ only within the constant polarizing regime, where $\alpha$ and $\beta$ are constants satisfying ${\alpha }^2>\beta$ (rather than $\alpha >\beta$), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for $\mathrm{SDP}$). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the $\mathsf{SZK}$ containment of $\mathrm{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 $\mathsf{QSZK}$-complete problems improve $\mathsf{QSZK}$ containments of $\mathrm{QSDP}$ beyond the polarizing regime and establish a simple $\mathsf{QSZK}$-hardness for the quantum entropy difference problem ($\mathrm{QEDP}$) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that $\mathrm{QSDP}$ with some exponentially small errors is in $\mathsf{PP}$, while the same problem without error is in $\mathsf{NQP}$.

arXiv comment38 pages. v5: close to the published version, added a subsection on related works and recent developments. v4: added a polarization lemma for QTD, and minor changes. v3: added a simple QSZK-hardness proof for QEDP, updated a correct version of Theorem 5.1(2), and improved presentation. v2: minor changes

References in corpus (13)

• Quantum Amplitude Amplification and Estimation
• Quantum fingerprinting
• Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states
• Properties of Classical and Quantum Jensen-Shannon Divergence
• The ${\chi }^2$-divergence and Mixing times of quantum Markov processes
• The metric property of the quantum Jensen-Shannon divergence
• Matrix versions of the Hellinger distance
• Strong bound between trace distance and Hilbert-Schmidt distance for low-rank states
• Quantum Proofs
• Fast Quantum Algorithms for Trace Distance Estimation
• Quantum interactive proofs and the complexity of separability testing
• Quantum chi-squared tomography and mutual information testing
• Generalized Quantum Arthur-Merlin Games

Cited by in corpus (1)

• Quantum Lower Bounds by Sample-to-Query Lifting