Related papers: Quantum chi-squared tomography and mutual information testing

Quantum chi-squared tomography and mutual information testing

URL: http://arxiv.org/abs/2305.18519v2
Date: Wed, 12 Jun 2024 19:45:27 GMT
Title: Quantum chi-squared tomography and mutual information testing
Authors: Steven T. Flammia, Ryan O'Donnell,
Abstract summary: For quantum state tomography on rank-$r$ dimension-$d$ states, we show that $widetildeO(r.5d1.5/epsilon) leq widetildeO(d3/epsilon)$ copies suffice for accuracy$epsilon$ with respect to (Bures) $chi2$-divergence. We also improve the best known sample complexity for the emphclassical version of mutual information testing to $widetildeO(d
Score: 1.8416014644193066
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: For quantum state tomography on rank-$r$ dimension-$d$ states, we show that $\widetilde{O}(r^{.5}d^{1.5}/\epsilon) \leq \widetilde{O}(d^2/\epsilon)$ copies suffice for accuracy~$\epsilon$ with respect to (Bures) $\chi^2$-divergence, and $\widetilde{O}(rd/\epsilon)$ copies suffice for accuracy~$\epsilon$ with respect to quantum relative entropy. The best previous bound was $\widetilde{O}(rd/\epsilon) \leq \widetilde{O}(d^2/\epsilon)$ with respect to infidelity; our results are an improvement since infidelity is bounded above by both the relative entropy and the $\chi^2$-divergence. For algorithms that are required to use single-copy measurements, we show that $\widetilde{O}(r^{1.5} d^{1.5}/\epsilon) \leq \widetilde{O}(d^3/\epsilon)$ copies suffice for $\chi^2$-divergence, and $\widetilde{O}(r^{2} d/\epsilon)$ suffice for relative entropy. Using this tomography algorithm, we show that $\widetilde{O}(d^{2.5}/\epsilon)$ copies of a $d\times d$-dimensional bipartite state suffice to test if it has quantum mutual information~$0$ or at least~$\epsilon$. As a corollary, we also improve the best known sample complexity for the \emph{classical} version of mutual information testing to $\widetilde{O}(d/\epsilon)$.

Related papers

$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
arXiv Detail & Related papers (2023-07-11T08:51:53Z)
$\boldsymbol{\alpha_{>}(\epsilon) = \alpha_{<}(\epsilon)}$ For The Margolus-Levitin Quantum Speed Limit Bound [0.0]
I show that $alpha_>(epsilon)$ is indeed equal to $alpha_(epsilon)$. I also point out a numerical stability issue in computing $alpha_>(epsilon)$.
arXiv Detail & Related papers (2023-05-17T10:07:31Z)
Sample optimal tomography of quantum Markov chains [23.427626096032803]
A state on a tripartite quantum system $mathcalH_Aotimes mathcalH_B$ forms a Markov chain, i.e., quantum conditional independence, if it can be reconstructed from its marginal on $mathcalH_Aotimes mathcalH_B$. A quantum operation from $mathcalH_B$ to $mathcalH_BotimesmathcalH_C$ via the
arXiv Detail & Related papers (2022-09-06T06:30:37Z)
Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
Given a quantum state $varrho$ and a quantifier $cal E(varrho), it is a hard task to determine $cal E(varrhootimes N)$. We show that the one shot distillable entanglement of certain spherically symmetric states can be quantitatively approximated by such an augmented additivity.
arXiv Detail & Related papers (2022-07-31T00:23:10Z)
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)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z)
Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
In this paper, we investigate the sample complexity of policy evaluation in offline reinforcement learning. Under the low distribution shift assumption, we show that there is an algorithm that needs at most $Oleft(maxleft fracleftVert thetapirightVert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$ samples to approximate the
arXiv Detail & Related papers (2021-03-17T18:18:57Z)
Improved quantum data analysis [1.8416014644193066]
We give a quantum "Threshold Search" algorithm that requires only $O(log2 m)/epsilon2)$ samples of a $d$-dimensional state. We also give an alternative Hypothesis Selection method using $tildeO((log3 m)/epsilon2)$ samples.
arXiv Detail & Related papers (2020-11-22T01:22:37Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
arXiv Detail & Related papers (2020-02-17T18:41:49Z)
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.