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.
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 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.
Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states, through a parameter known as the bond dimension. This leads to succinct representations of quantum many-body systems with a tree-like entanglement structure. In this work, we study the task of testing whether an unknown pure state is a TTNS onnqudits with bond dimension at mostr, or is far in trace distance from any such state. We first establish that, independent of the dimension of the state,O(nr2) copies suffice to accomplish this task with onesided error. We then prove that Ω(nr2/ logn) copies are necessary for any test with one-sided error wheneverr≥ 2 + logn. In particular, this closes a roughly quadratic gap in the previous bounds for testing matrix product states in this setting. On the other hand, whenr= 2 we show that Θ(√n) copies are both necessary and sufficient for the related task of testing whether a state is a product ofnbipartite states having Schmidt-rank at mostr, for some choice of the qudit dimensions. We also study the performance of tests using measurements performed on a small number of copies at a time. Here, we obtain new bounds for testing rank, Schmidt-rank, and TTNS when the tester is restricted to making measurements onr+ 1 copies of the state.
There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity [1]–[6]. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent-but possibly adaptively chosen-measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a givend-dimensional quantum state is equal to orϵ-far in trace distance from the maximally mixed state. While it is known how to achieve optimalO(d/ϵ2)copy complexity using entangled measurements, we show that with independent measurements,Ω(d4/3/ϵ2)is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.
Genuine multipartite entanglement (GME) is considered a powerful form of entanglement since it corresponds to those states that are not biseparable, i.e. a mixture of partially separable states across different bipartitions of the parties. In this work we study this phenomenon in the multiple-copy regime, where many perfect copies of a given state can be produced and controlled. In this scenario the above definition leads to subtle intricacies as biseparable states can be GME-activatable, i.e. several copies of a biseparable state can display GME. We show that the set of GMEactivatable states admits a simple characterization: a state is GME-activatable if and only if it is not partially separable across one bipartition of the parties. This leads to the second question of whether there is a general upper bound in the number of copies that needs to be considered in order to observe the activation of GME, which we answer in the negative. In particular, by providing an explicit construction, we prove that for any number of parties and any number k 2 N there exist GME-activatable multipartite states of fixed (i.e. independent of k) local dimensions such that k copies of them remain biseparable.
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.
We consider the problem of learning N identical copies of an unknown n-qubit quantum graph state with product measurements. These graph states have corresponding graphs where every vertex has exactly d neighboring vertices. Here, we detail an explicit algorithm that uses product measurements on multiple identical copies of such graph states to learn them. When n ≫ d and N = O(d log(1/ϵ) + d2log n), this algorithm correctly learns the graph state with probability at least 1 – ϵ. From channel coding theory, we find that for arbitrary joint measurements on graph states, any learning algorithm achieving this accuracy requires at least Ω(log(1/ϵ) + d log n) copies when d=o(n). We also supply bounds on N when every graph state encounters identical and independent depolarizing errors on each qubit.