In this work, we study the sample complexity of two variants of product testing when restricted to single-copy measurements. In particular, we consider both bipartite product testing (i.e., does there exist at least one non-trivial cut across which the state is product) and multipartite product testing (i.e., is the state fully product across every cut). For the first variant, we prove an exponential lower bound on the sample complexity of any algorithm for this task which utilizes only single-copy measurements. When comparing this with known efficient algorithms that utilize multi-copy measurements, this establishes an exponential separation for this and several related entanglement learning tasks. For the second variant, we prove another sample lower bound that establishes a separation between single- and multi-copy strategies. To obtain our results, we prove a crucial technical lemma that gives a lower bound on the overlap between tensor products of permutation operators acting on subsystems of states that themselves carry a tensor structure. Finally, we provide an algorithm for multipartite product testing using only single-copy, local measurements, and we highlight several interesting open questions arising from this work.
In this work, we study the sample complexity of two variants of product testing when restricted to single-copy measurements. In particular, we consider both bipartite product testing (i.e., does there exist at least one non-trivial cut across which the state is product) and multipartite product testing (i.e., is the state fully product across every cut). For the first variant, we prove an exponential lower bound on the sample complexity of any algorithm for this task which utilizes only single-copy measurements. When comparing this with known efficient algorithms that utilize multi-copy measurements, this establishes an exponential separation for this and several related entanglement learning tasks. For the second variant, we prove another sample lower bound that establishes a separation between single- and multi-copy strategies. To obtain our results, we prove a crucial technical lemma that gives a lower bound on the overlap between tensor products of permutation operators acting on subsystems of states that themselves carry a tensor structure. Finally, we provide an algorithm for multipartite product testing using only single-copy, local measurements, and we highlight several interesting open questions arising from this work.
Coherent measurements across multiple copies of an unknown quantum state can substantially reduce the number of samples required to learn its properties, but remain experimentally challenging. Current experiments typically prepare and measure one copy at a time, potentially adapting later measurements to earlier outcomes. A central challenge is adaptivity, which makes the space of possible measurement strategies difficult to characterize. The positive-partial-transpose (PPT) relaxation bypasses this complexity by considering a larger, mathematically tractable class of measurements, at the risk of weakening the resulting bounds. Here we show, surprisingly, that the relaxation loses nothing at the level of asymptotic sample complexity for two fundamental tasks: purity testing and product testing. In both cases, lower bounds against the full class of PPT measurements are matched by nonadaptive single-copy protocols. Moreover, our proof requires only basic symmetric subspace identities, providing a simple route to sharp lower bounds for adaptive single-copy measurements.
We prove a lower bound on the number of copies needed to test the property of a multipartite quantum state being product across some bipartition (i.e., not genuinely multipartite entangled), given the promise that the input state either has this property or is ϵ-far in trace distance from any state with this property. We show that Ω(n/log n) copies are required (for fixed ϵ≤12), complementing a previous result that O(n/ϵ2) copies are sufficient. Our proof technique proceeds by considering uniformly random ensembles over such states, and showing that the trace distance between these ensembles becomes arbitrarily small for sufficiently large n unless the number of copies is at least Ω(n/log n). We discuss implications for testing graph states and computing the generalized geometric measure of entanglement.
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.
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state ρ, test whether it matches some target state σ or is ε-far from it. For certifying d-dimensional states, Θ(d/ε2) copies of ρ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all O(d/ε2) copies of ρ. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on t copies at once, for some 1<t≪d/ε2. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements.
Our main result is a smooth copy complexity upper bound for state certification as a function of t, which achieves a near-optimal rate at t=d2. In the high-precision regime, i.e., for ε<d1, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at t=d2 as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take t≥Ω(d2) to achieve the optimal rate for certification.
We consider the problem of testing whether an unknown n-qubit quantum state is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(√n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.
We consider the problem of testing whether an unknown n-qubit quantum state ∣ψ⟩ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.