Improved quantum data analysis

• URL: http://arxiv.org/abs/2011.10908v4
• Date: Fri, 15 Mar 2024 15:19:51 GMT
• Title: Improved quantum data analysis
• Authors: Costin Bădescu, Ryan O'Donnell,
• Abstract summary: 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.
• Score: 1.8416014644193066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only $O((\log^2 m)/\epsilon^2)$ samples of a $d$-dimensional state $\rho$. That is, given observables $0 \le A_1, A_2, ..., A_m \le 1$ such that $\mathrm{tr}(\rho A_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(\rho A_j) \ge 1/2-\epsilon$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{O}((\log^2 m)(\log d)/\epsilon^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $\epsilon$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $\tilde{O}((\log^3 m)/\epsilon^2)$ samples.

Related papers

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
  We show a quantum implementation of $k$-means++ that runs in time $tildeO(zeta2 k2)$. It can be shown through a robust approximation analysis of $k$-means++ that the quantum version preserves its $O(logk)$ approximation guarantee. This results in a fast quantum-inspired classical implementation of $k$-means++, which we call QI-$k$-means++, with a running time $O(Nd) + tildeO(zeta
  arXiv  Detail & Related papers  (2024-05-22T05:13:28Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  Estimating the entropy of a quantum state is a basic problem in quantum information. We introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(rho)$ and R'enyi entropy $S_alpha(rho)$ of an $N$-dimensional quantum state $rho.
  arXiv  Detail & Related papers  (2024-01-18T12:50:20Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• 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)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
  arXiv  Detail & Related papers  (2021-04-29T14:50:03Z)
• 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)
• 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.