Learning Sparse Quantum States

• URL: http://arxiv.org/abs/2609.12219v1
• Date: Thu, 10 Sep 2026 21:28:21 GMT
• Title: Learning Sparse Quantum States
• Abstract summary: We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states.<n>We obtain fidelity at least $1-varepsilon$ with high probability using $tildeO(k/varepsilon)$ copies of the state and $tildeO(kn/varepsilon)$ time.<n>As an implication, we also obtain an algorithm with near optimal $tildeO(kr/varepsilon)$ sample complexity for learning $k$-sparse rank-$r
• Score: 0.8122270502556375
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.

Related papers

• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  We study the sample complexity of learning an $$-optimal policy in the Shortest Path (SSP) problem.<n>We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.<n>Surprisingly, this implies that whenever $c_min = 0$ an SSP problem may not be learnable.
  arXiv  Detail & Related papers  (2026-04-17T14:47:52Z)
• Sample-optimal single-copy quantum state tomography via shallow depth measurements [0.42970700836450487]
  We make two contributions by employing circuits with depth $mathcalO!left(fracd3epsilon2right)$ on an $n$-qubit system.<n>First, QST for rank-$r$ $d$-dimensional state $$ can be achieved with sample complexity $mathcalO!left(tfracdr2 ln depsilon2right)$.<n>Second, for the general case of $r = d$, we can remove the $ln
  arXiv  Detail & Related papers  (2025-09-16T05:54:01Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
  arXiv  Detail & Related papers  (2024-07-04T11:03:48Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
  arXiv  Detail & Related papers  (2023-04-25T15:32:37Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states [0.9453554184019105]
  We show how to learn the coefficients of a Hamiltonian to error $varepsilon$ with sample complexity $S = O(log N/(betavarepsilon)2)$ and time linear in the sample size, $O(S N)$. In the appendix, we show virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e-it Hilon in a small $t regime with similar sample and time complexity.
  arXiv  Detail & Related papers  (2021-08-10T18:00:49Z)
• 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)
• 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)
• 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)

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.