An Optimal Analysis of the Product Test

arXiv:2607.21477v1 Announce Type: new 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)=\frac12\left(1+m\omega^2+(1-m\omega)^2\right), $$ where $m=\lfloor1/\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.

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)=\frac12\left(1+m\omega^2+(1-m\omega)^2\right), $$ where $m=\lfloor1/\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.

20 pages, 3 figures. Comments welcome

arXiv:2607.21477 [quant-ph]

(or arXiv:2607.21477v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.21477 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

An Optimal Analysis of the Product Test

Related coverage