English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We explore potential quantum speedups for the fundamental problem of testingthe properties of closeness and $k$-wise uniformity of probabilitydistributions.  \textit{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\rbra{\sqrt{n}/\varepsilon}$ and$O\rbra{1/\varepsilon}$, respectively, both of which achieve optimal dependenceon $\varepsilon$, improving the prior best results of\hyperlink{cite.gilyen2019distributional}{Gily{\'e}n and Li~(2019)}.  \textit{$k$-wise uniformity testing} is the problem of distinguishing whethera distribution over $\cbra{0, 1}^n$ is uniform when restricted to any $k$coordinates or $\varepsilon$-far from any such distributions. We propose thefirst quantum algorithm for this problem with query complexity$O\rbra{\sqrt{n^k}/\varepsilon}$, achieving a quadratic speedup over thestate-of-the-art classical algorithm with sample complexity$O\rbra{n^k/\varepsilon^2}$ by \hyperlink{cite.o2018closeness}{O'Donnell andZhao (2018)}. Moreover, when $k = 2$ our quantum algorithm outperforms anyclassical one because of the classical lower bound$\Omega\rbra{n/\varepsilon^2}$.  All our quantum algorithms are fairly simple and time-efficient, using onlybasic quantum subroutines such as amplitude estimation.

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