An Optimal Analysis of the Product Test

• URL: http://arxiv.org/abs/2607.21477v1
• Date: Thu, 23 Jul 2026 16:17:44 GMT
• Title: An Optimal Analysis of the Product Test
• Abstract summary: Product testing decides whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition.<n>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.<n>As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $mathsfQMA(k)$ to $mathsfQMA(2)$.
• Score: 42.29010058743949
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $ω$ be the maximum squared overlap of the input with a product state, and let $\mathrm{PT}_n(ω)$ 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\ge 2 $ and every $ω\in(0,1] $, $$ \mathrm{PT}_n(ω)=\frac12\left(1+mω^2+(1-mω)^2\right), $$ where $m=\lfloor1/ω\rfloor $. The formula recovers the previously known tight section of the curve for $ω\ge 1/2 $, resolves all low-overlap regimes $ω<1/2 $, and implies $\mathrm{PT}_n(ω)\to 1/2 $ as $ω\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.

Related papers

• A Simple Algorithm for Best Separable State [5.5559749120901385]
  We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states.<n>In classical terms, the goal is to maximize $langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$.
  arXiv  Detail & Related papers  (2026-08-10T19:04:15Z)
• Optimal Quantum de Finetti Theorems via Argmax Rounding [42.55259086694773]
  We prove optimal finite quantum de Finetti upper bounds for bosonic states and arbitrary exchangeable states.<n>Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program.<n> spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance.
  arXiv  Detail & Related papers  (2026-08-03T17:57:15Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• OAM-Induced Lattice Rotation Reveals a Fractional Optimum in Fault-Tolerant GKP Quantum Sensing [0.0]
  We establish that orbital-angular-momentum encoding and Gottesman-Kitaev-Preskill (GKP) lattice geometry are structurally coupled.<n>Using an end-to-end differentiable Strawberry Fields--TensorFlow circuit, we jointly optimise $ell$, the lattice aspect ratio $r$, and the finite-energy envelope $$ to maximise quantum Fisher information.
  arXiv  Detail & Related papers  (2026-05-13T09:49:16Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• $φ^n$ trajectory bootstrap [1.8855270809505869]
  We show that the non-integer $n$ results for $langlephinrangle$ or $langle(iphi)nrangle$ are consistent with those from the wave function approach.<n>In the $mathcalPT$ invariant case, the existence of $langle(iphi)nrangle$ with non-integer $n$ allows us to bootstrap the non-Hermitian theories with non-integer powers.
  arXiv  Detail & Related papers  (2024-02-08T16:09:06Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit. We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
  arXiv  Detail & Related papers  (2023-11-22T20:27:05Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Testing matrix product states [5.225550006603552]
  We study the problem of testing whether an unknown state $|psirangle$ is a matrix product state (MPS) in the property testing model. MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems.
  arXiv  Detail & Related papers  (2022-01-05T21:10:50Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
  arXiv  Detail & Related papers  (2021-05-31T16:10:49Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.