Lower bounds for learning quantum states with single-copy measurements

• URL: http://arxiv.org/abs/2207.14438v2
• Date: Mon, 1 Aug 2022 22:03:52 GMT
• Title: Lower bounds for learning quantum states with single-copy measurements
• Authors: Angus Lowe and Ashwin Nayak
• Abstract summary: We study the problems of quantum tomography and shadow tomography using measurements performed on individual copies of an unknown $d$-dimensional state. In particular, this rigorously establishes the optimality of the folklore Pauli tomography" algorithm in terms of its complexity.
• Score: 3.2590610391507444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown $d$-dimensional state. We first revisit a known lower bound due to Haah et al. (2017) on quantum tomography with accuracy $\epsilon$ in trace distance, when the measurements choices are independent of previously observed outcomes (i.e., they are nonadaptive). We give a succinct proof of this result. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes. In particular, this rigorously establishes the optimality of the folklore ``Pauli tomography" algorithm in terms of its sample complexity. We also derive novel bounds of $\Omega(r^2 d/\epsilon^2)$ and $\Omega(r^2 d^2/\epsilon^2)$ for learning rank $r$ states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of different measurements used by an algorithm. We extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of $\exp(O(d))$ measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.

Related papers

• Quantum state testing with restricted measurements [30.641152457827527]
  We develop an information-theoretic framework that yields unified copy complexity lower bounds for restricted families of non-adaptive measurements. We demonstrate a separation between these two schemes, showing the power of randomized measurement schemes over fixed ones.
  arXiv  Detail & Related papers  (2024-08-30T17:48:00Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  We prove an $mathcalO(t-1)$ lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation. To nearly achieve the desired fast rate, we design an entropic regularization scheme decreasing with the number of samples.
  arXiv  Detail & Related papers  (2024-05-23T11:46:03Z)
• 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)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing [87.17253904965372]
  We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. We show that these errors decrease exponentially with decay rates given by the measured relative entropies between the two states.
  arXiv  Detail & Related papers  (2021-04-30T00:52:48Z)
• Quantum data hiding with continuous variable systems [8.37609145576126]
  We investigate data hiding in the context of continuous variable quantum systems. We look at the case where $mathcalM=mathrmLOCC$, the set of measurements implementable with local operations and classical communication. We perform a rigorous quantitative analysis of the error introduced by the non-ideal Braunstein-Kimble quantum teleportation protocol.
  arXiv  Detail & Related papers  (2021-02-01T19:00:14Z)
• Efficient computation of the Nagaoka--Hayashi bound for multi-parameter estimation with separable measurements [16.53410208934304]
  We introduce a tighter bound for estimating multiple parameters simultaneously when performing separable measurements on finite copies of the probe. We show that this bound can be efficiently computed by casting it as a semidefinite program.
  arXiv  Detail & Related papers  (2020-08-06T12:43:31Z)
• 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)

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.