Optimal tradeoffs for estimating Pauli observables

• URL: http://arxiv.org/abs/2404.19105v1
• Date: Mon, 29 Apr 2024 20:57:05 GMT
• Title: Optimal tradeoffs for estimating Pauli observables
• Authors: Sitan Chen, Weiyuan Gong, Qi Ye,
• Abstract summary: 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
• Score: 13.070874080455862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of Pauli shadow tomography: given copies of an unknown $n$-qubit quantum state $\rho$, estimate $\text{tr}(P\rho)$ for some set of Pauli operators $P$ to within additive error $\epsilon$. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate $|\text{tr}(P\rho)|$ for all $P$ using $O(n/\epsilon^4)$ copies, but with $k\le n$ qubits of memory, $\Omega(2^{(n-k)/3})$ copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on $\epsilon$? What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions. For any subset $A$ of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to $\log |A|$ factors. We show any protocol that makes $\text{poly}(n)$-copy measurements must make $\Omega(1/\epsilon^4)$ measurements. For any protocol that makes $\text{poly}(n)$-copy measurements and only has $k < n$ qubits of memory, we show that $\widetilde{\Theta}(\min\{2^n/\epsilon^2, 2^{n-k}/\epsilon^4\})$ copies are necessary and sufficient. The protocols we propose can also estimate the actual values $\text{tr}(P\rho)$, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

Related papers

• Distributed inner product estimation with limited quantum communication [3.729242965449096]
  We consider the task of distributed inner product estimation when allowed limited quantum communication. We show that $k=Theta(sqrt2n-q)$ copies are essentially necessary and sufficient for this task. We also consider estimating $|langle psi|M|phirangle|2$, for arbitrary Hermitian $M$.
  arXiv  Detail & Related papers  (2024-10-16T15:46:59Z)
• Efficient Pauli channel estimation with logarithmic quantum memory [10.95781315121668]
  We show that a protocol can estimate the eigenvalues of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla qubits and $tildeO(n2/epsilon2)$ measurements. Our results imply, to our knowledge, the first quantum learning task where logarithmically many qubits of quantum memory suffice for an exponential statistical advantage.
  arXiv  Detail & Related papers  (2023-09-25T17:53:12Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  We give a new constant memory scheme that reduces the sample complexity to $(k/epsilon2)cdot textpolylog (1/epsilon)$. We conjecture that this is optimal up to $textpolylog (1/epsilon)$ factors.
  arXiv  Detail & Related papers  (2022-05-19T18:51:28Z)
• Quantum advantages for Pauli channel estimation [2.5496329090462626]
  entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation. We show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task.
  arXiv  Detail & Related papers  (2021-08-19T04:10:28Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)
• Sample efficient tomography via Pauli Measurements [11.98034899127065]
  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.
  arXiv  Detail & Related papers  (2020-09-10T00:04:44Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• 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)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.