Testing multipartite productness is easier than testing bipartite productness

• URL: http://arxiv.org/abs/2406.16827v1
• Date: Mon, 24 Jun 2024 17:36:57 GMT
• Title: Testing multipartite productness is easier than testing bipartite productness
• Authors: Benjamin D. M. Jones, Ashley Montanaro,
• Abstract summary: We show that $Omega(n / log n)$ copies are required (for fixed $epsilon leq frac12$) We discuss implications for testing graph states and computing the generalised geometric measure of entanglement.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\epsilon$-far in trace distance from any state with this property. We show that $\Omega(n / \log n)$ copies are required (for fixed $\epsilon \leq \frac{1}{2}$), complementing a previous result that $O(n / \epsilon^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 $\Omega (n / \log n)$. We discuss implications for testing graph states and computing the generalised geometric measure of entanglement.

Related papers

• Nearly tight bounds for testing tree tensor network states [0.0]
  Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states. We study the task of testing whether an unknown pure state is a TTNS on $n$ qudits with bond dimension at most $r$. We also study the performance of tests using measurements performed on a small number of copies at a time.
  arXiv  Detail & Related papers  (2024-10-28T18:13:38Z)
• Testing Support Size More Efficiently Than Learning Histograms [0.18416014644193066]
  We show that testing can be done more efficiently than learning the histogram of the distribution $p$. The proof relies on an analysis of Chebyshev approximations outside the range where they are designed to be good approximations.
  arXiv  Detail & Related papers  (2024-10-24T17:05:34Z)
• Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
  We consider the problems of learning junta distributions, their quantum counter-part, quantum junta states, and QAC$0$ circuits. We show that they can be learned with error $varepsilon$ in total variation distance. We also prove a lower bound of $Omega(4k+log (n)/varepsilon2)$ copies.
  arXiv  Detail & Related papers  (2024-10-21T09:39:20Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Local Test for Unitarily Invariant Properties of Bipartite Quantum States [12.29469360050918]
  We study the power of local test for bipartite quantum states. For properties of bipartite pure states, unitary invariance on one part implies an optimal (over all global testers) local tester acting only on the other part. purified samples offer no advantage in property testing of mixed states.
  arXiv  Detail & Related papers  (2024-04-06T11:57:20Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
  arXiv  Detail & Related papers  (2023-12-23T15:52:46Z)
• Monogamy of entanglement between cones [68.8204255655161]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones. Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.