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.
We study a restricted class of correlator product states (CPS) for a spin-half chain in which each spin is contained in just two overlapping plaquettes. This class is also a restriction upon matrix product states (MPS) with local dimension 2n (n being the size of the overlapping regions of plaquettes) equal to the bond dimension. We investigate the trade-off between gains in efficiency due to this restriction against losses in fidelity. The time-dependent variational principle formulated for these states is numerically very stable. Moreover, it shows significant gains in efficiency compared to the naively related matrix product states---the evolution or optimization scales as 23n for the correlator product states versus 24n for the unrestricted matrix product state. However, much of this advantage is offset by a significant reduction in fidelity. Correlator product states break the local Hilbert space symmetry by the explicit selection of a local basis. We investigate this dependence in detail and formulate the broad principles under which correlator product states may be a useful tool. In particular, we find that scaling with overlap/bond order may be more stable with correlator product states allowing a more efficient extraction of critical exponents---we present an example in which the use of correlator product states is several orders of magnitude quicker than matrix product states.