Local Test for Unitarily Invariant Properties of Bipartite Quantum States

• URL: http://arxiv.org/abs/2404.04599v2
• Date: Mon, 29 Apr 2024 08:29:46 GMT
• Title: Local Test for Unitarily Invariant Properties of Bipartite Quantum States
• Authors: Kean Chen, Qisheng Wang, Zhicheng Zhang,
• Abstract summary: 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.
• Score: 12.29469360050918
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the power of local test for bipartite quantum states. Our central result is that, 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. This suggests a canonical local tester for entanglement spectra (i.e., Schmidt coefficients), and reveals that purified samples offer no advantage in property testing of mixed states. As applications, we show new sample lower bounds, e.g.: - The first general lower bound $\Omega(r/\epsilon^2)$ for testing whether the Schmidt rank of a bipartite state is at most $r$ or $\epsilon$-far, settling an open question raised in Montanaro and de Wolf (ToC 2016). - A lower bound $\Omega((\sqrt n+\sqrt r)\cdot\sqrt r/\epsilon^2)$ for testing whether an $n$-partite state is a matrix product state of bond dimension $r$ or $\epsilon$-far, improving the prior lower bound $\Omega(\sqrt n/\epsilon^2)$ by Soleimanifar and Wright (SODA 2022) and $\Omega(\sqrt r)$ by Aaronson et al. (ITCS 2024). Further, when perfect completeness is required, we provide a matching lower bound $\Omega(r^2/\epsilon^2)$ with respect to $r$ and $\epsilon$. - A matching lower bound $\Omega(d/\epsilon^2)$ for testing whether a $d$-dimensional bipartite state is maximally entangled or $\epsilon$-far, showing that the algorithm of O'Donnell and Wright (STOC 2015) is optimal for this task. Beyond sample complexity, we also contribute new query lower bounds: - A query lower bound $\tilde\Omega(\sqrt{d/\Delta})$ for the $d$-dimensional entanglement entropy problem with gap $\Delta$, improving the prior best $\Omega(\sqrt[4]{d})$ by She and Yuen (ITCS 2023) and $\tilde\Omega(1/\sqrt\Delta)$ by Wang and Zhang (2023) and Weggemans (2024). Further, our central result can be extended when the tested state is mixed: one-way LOCC is sufficient to realize the optimal tester.

Related papers

• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
  arXiv  Detail & Related papers  (2023-04-25T15:32:37Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  Unitarity estimation is a basic and important problem in quantum device certification and benchmarking. We provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms. We show that both the $d$-dependence and $epsilon$-dependence of our algorithms are optimal.
  arXiv  Detail & Related papers  (2022-12-19T09:36:33Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• 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.