Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions

• URL: http://arxiv.org/abs/2304.12916v4
• Date: Tue, 25 Jun 2024 19:43:09 GMT
• Title: Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Authors: Jingquan Luo, Qisheng Wang, Lvzhou Li,
• Abstract summary: 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)
• Score: 2.3466828785520373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. Closeness testing is the problem of distinguishing whether two $n$-dimensional distributions are identical or at least $\varepsilon$-far in $\ell^1$- or $\ell^2$-distance. We show that the quantum query complexities for $\ell^1$- and $\ell^2$-closeness testing are $O(\sqrt{n}/\varepsilon)$ and $O(1/\varepsilon)$, respectively, both of which achieve optimal dependence on $\varepsilon$, improving the prior best results of Gily\'en and Li (2020). $k$-wise uniformity testing is the problem of distinguishing whether a distribution over $\{0, 1\}^n$ is uniform when restricted to any $k$ coordinates or $\varepsilon$-far from any such distributions. We propose the first quantum algorithm for this problem with query complexity $O(\sqrt{n^k}/\varepsilon)$, achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity $O(n^k/\varepsilon^2)$ by O'Donnell and Zhao (2018). Moreover, when $k = 2$ our quantum algorithm outperforms any classical one because of the classical lower bound $\Omega(n/\varepsilon^2)$. All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.

Related papers

• 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)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model. Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$. Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
  arXiv  Detail & Related papers  (2023-08-16T06:46:37Z)
• 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)
• Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
  We show that quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d. We also characterize the domains where quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
  arXiv  Detail & Related papers  (2022-12-05T19:10:32Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• 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)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)
• 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)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  We show that a quantum algorithm can be solved by making $2O(k)$ queries to the inputs. For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N2/3-varepsilon$ separation.
  arXiv  Detail & Related papers  (2019-12-29T01:42:31Z)

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.