An Optimal Analysis of the Product Test

Abstract

Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property testing, unentangled quantum proof systems, and tensor optimization. Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined. In this work, we determine this curve exactly. Let $\omega$ be the maximum squared overlap of the input with a product state, and let ${\mathrm{PT}}_n(\omega )$ be the largest possible acceptance probability of the product test over all $n$-partite pure states with product overlap $\omega$, allowing arbitrary finite local dimensions. We prove that, for every $n\ge 2$ and every $\omega \in (0,1]$, $${\mathrm{PT}}_n(\omega )=\frac{1}{2}\left(1+m{\omega }^2+(1-m\omega {)}^2\right),$$ where $m=\lfloor 1/\omega \rfloor$. The formula recovers the previously known tight section of the curve for $\omega \ge 1/2$, resolves all low-overlap regimes $\omega <1/2$, and implies ${\mathrm{PT}}_n(\omega )\to 1/2$ as $\omega \to 0$ answering an open problem in [Soleimanifar and Wright, SODA 2022]. As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $\mathsf{QMA}(k)$ to $\mathsf{QMA}(2)$. Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.

arXiv comment20 pages, 3 figures. Comments welcome