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.
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], $$
\mathrm{PT}_n(ω)=\frac12\left(1+mω^2+(1-mω)^2\right), $$ where m=⌊1/ω⌋. 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.
Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ1, …, k has rank r for each k ∊ {1, …, n}. When r = 1, this corresponds to the set of product states, i.e. states of the form |ψ1〉 ⊗ ⃛ ⊗ |ψn), which possess no entanglement. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state |ψ〉 is an MPS in the property testing model. In this model, one is given m identical copies of |ψ〉, and the goal is to determine whether |ψ〉 is an MPS of bond dimension r or whether |ψ〉 is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro [17], and a key ingredient in their proof that QMA(2) = QMA(k) for k ≥ 2. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in [17] and [23]. For the case of r ≥ 2, we give an efficient algorithm for testing whether |ψ〉 is an MPS of bond dimension r using m = O(nr2) copies, independent of the dimensions of the qudits, and we show that Ω(n1/2) copies are necessary for this task. This lower bound shows that a dependence on the number of qudits n is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.
We address the problem of testing whether an unknown n-qudit state ρ is a-close to a product state or b-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an n-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of [n] into q parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor O(1/q) larger. This reduces the problem to tolerant testing of q parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural k-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester.
We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in O((nd)2)2O(1/ε8) copies of the unknown state and produces an ε-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
In quantum information theory, the state space of a multipartite quantum system is modeled by a tensor product. In the tensor-product space $\C^{d_1}\otimes\cdots\otimes\C^{d_p}$, a nonzero vector is a \emph{product state} if it can be written as ∣φ1⟩⊗⋯⊗∣φp⟩ with $\ket{\varphi_j}\in\C^{d_j}\setminus\{0\}$. An \emph{unextendible product basis} (UPB) is a finite family of pairwise orthogonal product states such that no nonzero product state is orthogonal to all of them. UPBs play a key role in investigating quantum entanglement and nonlocal phenomena. Finding a smallest UPB is a natural extremal problem: it asks how few pairwise orthogonal product states suffice to prevent any further product state from being added. The general minimum-size problem for UPBs has been studied for over two decades since the seminal work of Alon and Lovász.
Let fm(d1,…,dp) be the minimum cardinality of a UPB in the space, and let fLB(d1,…,dp)=1+∑j=1p(dj−1) be the natural lower bound. Alon and Lovász determined exactly when fm attains the lower bound fLB, but the obstructed multipartite cases remained open in general.
We prove a stabilization theorem: for every non-all-qubit system with p≥3, whenever the natural lower bound fLB is unattainable, the true minimum is exactly fLB+1. Precisely, if the number of even local dimensions di is positive and even, and at least one local dimension is greater than two, then fm(d1,…,dp)=fLB(d1,…,dp)+1. The proof is built on a unified graph-theoretic framework. Our result, together with earlier work, settles the minimum size problem for UPBs in all finite quantum systems.
We study the power of local test for bipartite quantum states. Our central result is that, for properties of bipartite pure states, unitary invariance on one part implies anoptimal(over all global testers) local tester acting only on the other part. As an application, we demonstrate • Purified samples offer no advantage in property testing of mixed states. • A matching lower bound Ω(r2/ε2) for testing the Schmidt rank of bipartite states with perfect completeness, settling an open question raised in the survey of Montanaro and de Wolf (ToC 2016). • A lower bound Ω(( √n+ √r)· √r/ε2) for testing whether ann-partite state is a matrix product state of bond dimensionror ε-far, improving the prior lower bounds Ω( √n/ε2) by Soleimanifar and Wright (SODA 2022) and Ω( √r) by Aaronson et al. (ITCS 2024). • A matching lower bound Ω(d/ε2) for testing whether ad-dimensional bipartite state is maximally entangled or ε-far, showing that the algorithm of O’Donnell and Wright (STOC 2015) is optimal for this task. • A query lower bound Ω(d/ √ Δ) for thed-dimensional entanglement entropy problem with gap Δ, improving the prior lower bounds Ω(4√d) by She and Yuen (ITCS 2023) and Ω(1/ √ Δ) by Wang and Zhang (SICOMP 2025) and Weggemans (Quantum 2025). Moreover, we extend our central result to a robust version where the tested states are subject to noise and are not guaranteed to be pure: in this case, one-way LOCC is sufficient to realize the optimal tester.
In quantum physics, multiparticle systems are described by quantum states acting on tensor products of Hilbert spaces. This product structure leads to the distinction between product states and entangled states; moreover, one can quantify entanglement by considering the distance of a quantum state to the set of product states. The underlying optimization problem occurs frequently in physics and beyond, for instance in the computation of the injective tensor norm in multilinear algebra. Here, we introduce a method to determine the maximal overlap of a pure multiparticle quantum state with product states based on considering several copies of the pure state. This leads to three types of hierarchical approximations to the problem, all of which we prove to converge to the actual value. Besides allowing for the computation of the geometric measure of entanglement, our results can be used to tackle optimizations over stochastic local transformations, to find entanglement witnesses for weakly entangled bipartite states, and to design strong separability tests for mixed multiparticle states. Finally, our approach sheds light on the complexity of separability tests.
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including:
1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr(ρ2) and the inner product tr(ρσ).
2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr(ρk).
3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal.
4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state.
5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states.
6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal.
To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.