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
- 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) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
We show, for any $ngeq 2k-1$, how to achieve sample complexity and run-time complexity $(1/zeta)O(k)$.
We also extend the known lower bound of $eOmega(k)$ to match our upper bound across a broad range of $zeta$.
arXiv Detail & Related papers (2023-09-25T09:50:15Z) - 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) - Tight Bounds for Quantum State Certification with Incoherent
Measurements [18.566266990940374]
When $sigma$ is the maximally mixed state $frac1d I_d$, this is known as mixedness testing.
We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $rho$ at a time.
arXiv Detail & Related papers (2022-04-14T17:59:31Z) - 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) - Distributed quantum inner product estimation [14.222887950206658]
A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers.
No quantum communication can be performed between the two physical platforms due to hardware constraints.
We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
arXiv Detail & Related papers (2021-11-05T05:35:03Z) - 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) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms.
We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling"
We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
arXiv Detail & Related papers (2020-06-02T16:38:36Z) - 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.