Sample efficient tomography via Pauli Measurements

• URL: http://arxiv.org/abs/2009.04610v2
• Date: Sun, 13 Sep 2020 13:36:11 GMT
• Title: Sample efficient tomography via Pauli Measurements
• Authors: Nengkun Yu
• Abstract summary: We explore the power of Pauli measurements in the state tomography related problems. We show that the textitquantum state tomography problem of $n$-qubit system can be accomplished with $mathcalO(frac10nepsilon2)$ copies of the unknown state using Pauli measurements.
• Score: 11.98034899127065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli measurements in the state tomography related problems. Firstly, we show that the \textit{quantum state tomography} problem of $n$-qubit system can be accomplished with ${\mathcal{O}}(\frac{10^n}{\epsilon^2})$ copies of the unknown state using Pauli measurements. As a direct application, we studied the \textit{quantum overlapping tomography} problem introduced by Cotler and Wilczek in Ref. \cite{Cotler_2020}. We show that the sample complexity is $\mathcal{O}(\frac{10^k\cdot\log({{n}\choose{k}}/\delta))}{\epsilon^{2}})$ for quantum overlapping tomography of $k$-qubit reduced density matrices among $n$ is quantum system, where $1-\delta$ is the confidential level, and $\epsilon$ is the trace distance error. This can be achieved using Pauli measurements. Moreover, we prove that $\Omega(\frac{\log(n/\delta)}{\epsilon^{2}})$ copies are needed. In other words, for constant $k$, joint, highly entangled, measurements are not asymptotically more efficient than Pauli measurements.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Optimal tradeoffs for estimating Pauli observables [13.070874080455862]
  We revisit the problem of Pauli shadow tomography: given copies of an unknown $n$-qubit quantum state $rho$, estimate $texttr(Prho)$ for some set of Pauli operators $P$ to within additive error $epsilon$. We show any protocol that makes $textpoly(n)$-copy measurements must make $Omega (1/epsilon4)$ measurements. The protocols we propose can also estimate the actual values $texttr(Prho)$, rather than just their absolute values
  arXiv  Detail & Related papers  (2024-04-29T20:57:05Z)
• 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)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
  arXiv  Detail & Related papers  (2023-07-02T05:03:38Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• 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)
• Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
  Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems. We develop an online shadow tomography procedure that solves this problem with high success probability.
  arXiv  Detail & Related papers  (2022-09-07T09:08: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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks [40.489350374378645]
  We prove that $widetildemathcalO(e1/delta2+sqrtn)$ neurons and $widetildemathcalO(fracddelta+n)$ weights are sufficient. We also prove new lower bounds by connecting in neural networks to the purely geometric problem of separating $n$ points on a sphere using hyperplanes.
  arXiv  Detail & Related papers  (2021-06-14T19:42:32Z)
• Compressed Sensing Tomography for qudits in Hilbert spaces of non-power-of-two dimensions [0.0]
  The techniques of low-rank matrix recovery were adapted for Quantum State Tomography (QST) We propose an alternative strategy, in which the quantum information is swapped into the subspace of a power-two system using only $textrmpoly(log(d)2)$ gates at most.
  arXiv  Detail & Related papers  (2020-06-02T17:37: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.