Nearly tight bounds for testing tree tensor network states

• URL: http://arxiv.org/abs/2410.21417v1
• Date: Mon, 28 Oct 2024 18:13:38 GMT
• Title: Nearly tight bounds for testing tree tensor network states
• Authors: Benjamin Lovitz, Angus Lowe,
• Abstract summary: 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.
• Score: 0.0
• License:
• Abstract: 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 on $n$ qudits with bond dimension at most $r$, or is far in trace distance from any such state. We first establish that, independent of the physical dimensions, $O(nr^2)$ copies of the state suffice to acccomplish this task with one-sided error, as in the matrix product state (MPS) test of Soleimanifar and Wright. We then prove that $\Omega(n r^2/\log n)$ copies are necessary for any test with one-sided error whenever $r\geq 2 + \log n$. In particular, this closes a quadratic gap in the previous bounds for MPS testing in this setting, up to log factors. On the other hand, when $r=2$ we show that $\Theta(\sqrt{n})$ copies are both necessary and sufficient for the related task of testing whether a state is a product of $n$ bipartite states having Schmidt-rank at most $r$, for some choice of physical dimensions. We also study the performance of tests using measurements performed on a small number of copies at a time. In the setting of one-sided error, we prove that adaptive measurements offer no improvement over non-adaptive measurements for many properties, including TTNS. We then derive a closed-form solution for the acceptance probability of an $(r+1)$-copy rank test with rank parameter $r$. This leads to nearly tight bounds for testing rank, Schmidt-rank, and TTNS when the tester is restricted to making measurements on $r+1$ copies at a time. For example, when $r=2$ there is an MPS test with one-sided error which uses $O(n^2)$ copies and measurements performed on just three copies at a time.

Related papers

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known. Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Testing multipartite productness is easier than testing bipartite productness [0.0]
  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.
  arXiv  Detail & Related papers  (2024-06-24T17:36:57Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  The goal is to identify nodes where the null hypothesis $p_v = q_v$ should be rejected. We propose the non-parametric collaborative two-sample testing (CTST) framework that efficiently leverages the graph structure. Our methodology integrates elements from f-divergence estimation, Kernel Methods, and Multitask Learning.
  arXiv  Detail & Related papers  (2024-02-08T14:43:56Z)
• 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)
• 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)
• 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)
• Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
  We show that with independent measurements, $Omega(d4/3/epsilon2)$ is necessary, even if the measurements are chosen adaptively. We develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing.
  arXiv  Detail & Related papers  (2020-04-16T18:28:39Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.