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

Jingquan Luo, Qisheng Wang, Lvzhou Li*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and k-wise uniformity of probability distributions: 1) Closeness testing is the problem of distinguishing whether two n-dimensional distributions are identical or at least ε -far in ℓ1 - or ℓ2 -distance. We show that the quantum query complexities for ℓ1 - and ℓ2 -closeness testing are O(n−−√/ε) and O(1/ε) , respectively, both of which achieve optimal dependence on ε , improving the prior best results of Gilyén and Li (2019) and 2) 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 ε -far from any such distribution. We propose the first quantum algorithm for this problem with query complexity O(nk−−√/ε) , achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity O(nk/ε2) by O’Donnell and Zhao (2018). Moreover, when k=2 our quantum algorithm outperforms any classical one because of the classical lower bound Ω(n/ε2) . All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.
Original languageEnglish
Article number10508394
Pages (from-to)1-12
Number of pages12
JournalIEEE Transactions on Information Theory
Volume70
Issue number7
DOIs
Publication statusPublished - 25 Apr 2024

Keywords / Materials (for Non-textual outputs)

  • quantum computing
  • quantum algorithm
  • property testing
  • probability distribution

Fingerprint

Dive into the research topics of 'Succinct quantum testers for closeness and k-wise uniformity of probability distributions'. Together they form a unique fingerprint.

Cite this