2026/07/23 by Jacob Beckey, Fernando Granha Jeronimo, Pei Wu
#quant-ph
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 ω be the maximum squared overlap of the input with a product state, and let PTn(ω) be the largest possible acceptance probability of the product test over all n-partite pure states with product overlap ω, allowing arbitrary finite local dimensions. We prove that, for every n≥ 2 and every ω∈(0,1] , PTn(ω)=\frac12(1+mω2+(1-mω)2), where m=\lfloor1/ω\rfloor . The formula recovers the previously known tight section of the curve for ω≥ 1/2 , resolves all low-overlap regimes ω<1/2 , and implies PTn(ω)→ 1/2 as ω→ 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 QMA(k) to QMA(2). Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.