Tight Bounds for Quantum State Certification with Incoherent Measurements

• URL: http://arxiv.org/abs/2204.07155v1
• Date: Thu, 14 Apr 2022 17:59:31 GMT
• Title: Tight Bounds for Quantum State Certification with Incoherent Measurements
• Authors: Sitan Chen, Brice Huang, Jerry Li, Allen Liu
• Abstract summary: 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.
• Score: 18.566266990940374
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of quantum state certification, where we are given the description of a mixed state $\sigma \in \mathbb{C}^{d \times d}$, $n$ copies of a mixed state $\rho \in \mathbb{C}^{d \times d}$, and $\varepsilon > 0$, and we are asked to determine whether $\rho = \sigma$ or whether $\| \rho - \sigma \|_1 > \varepsilon$. When $\sigma$ is the maximally mixed state $\frac{1}{d} 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. Unlike those that use entangled, multi-copy measurements, these can be implemented without persistent quantum memory and thus represent a large class of protocols that can be run on current or near-term devices. For mixedness testing, there is a folklore algorithm which uses incoherent measurements and only needs $O(d^{3/2} / \varepsilon^2)$ copies. The algorithm is non-adaptive, that is, its measurements are fixed ahead of time, and is known to be optimal for non-adaptive algorithms. However, when the algorithm can make arbitrary incoherent measurements, the best known lower bound is only $\Omega (d^{4/3} / \varepsilon^2)$ [Bubeck-Chen-Li '20], and it has been an outstanding open problem to close this polynomial gap. In this work, 1) we settle the copy complexity of mixedness testing with incoherent measurements and show that $\Omega (d^{3/2} / \varepsilon^2)$ copies are necessary, and 2) we show the instance-optimal bounds for state certification to general $\sigma$ first derived by [Chen-Li-O'Donnell '21] for non-adaptive measurements also hold for arbitrary incoherent measurements. Qualitatively, our results say that adaptivity does not help at all for these problems. Our results are based on new techniques that allow us to reduce the problem to understanding certain matrix martingales, which we believe may be of independent interest.

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)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• 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)
• Quantum Event Learning and Gentle Random Measurements [0.0]
  We prove the expected disturbance caused to a quantum system by a sequence of randomly ordered projective measurements is upper bounded by the square root of the probability that at least one measurement accepts. We also consider problems in which we are given sample access to an unknown state $rho$ and asked to estimate properties of the accepting probabilities.
  arXiv  Detail & Related papers  (2022-10-17T15:00:58Z)
• When Does Adaptivity Help for Quantum State Learning? [19.89243001385691]
  We show that any protocol using incoherent measurements requires $Omega(d3/epsilon2)$ copies, matching the best known upper bound. We give an adaptive algorithm that outputs a state which is $gamma$-close in infidelity to $rho$ using only $tildeO(d3/gamma)$ copies, which is optimal for incoherent measurements.
  arXiv  Detail & Related papers  (2022-06-10T17:59:16Z)
• 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)
• Toward Instance-Optimal State Certification With Incoherent Measurements [17.107198714549515]
  Given copies of unknown mixed state $rhoinmathbbCdtimes d$, decide whether $sigma = rho$ or $|sigma - rho|_mathsftr ge epsilon$. We show that the copy complexity for state certification using nonadaptive incoherent measurements is essentially given by the copy complexity for mixedness testing times the fidelity between $sigma$ and the maximally mixed state.
  arXiv  Detail & Related papers  (2021-02-25T18:59:11Z)
• 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)
• 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)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

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.