This work designs quantum algorithms with complexities $\tilde{O}(1/\epsilon)$ and $\tilde{O}(\sqrt{m}/\epsilon)$ in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts.
Abstract
Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of $m$ ($m\geq 3$) distributions. This work focuses on quantum algorithms for testing whether $m$ distributions have similar means or are $\epsilon$-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities $\tilde{O}(1/\epsilon)$ (the $\tilde{O}$ notation hides poly-logarithmic factors) and $\tilde{O}(\sqrt{m}/\epsilon)$ in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of $\Omega\left(1/\epsilon\right)$ and $\Omega\rbra{m^{1/3}+\frac{m^{1/4}}{\epsilon}}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on $\epsilon$ up to logarithmic factors.
This work settles this conjecture for parallel quantum algorithms, showing that every $t-query $d-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries, suggesting that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and ex...
Guy Blanc, Jordan Docter, Carmen Strassle et al.· 2 citations· ⚡1
This work considers the property testing task of determining whether a function has Fourier dimension at most $k, or is $\epsilon$-far from being so, and shows that there is an $O(k/\sqrt{\epsilon})$-query quantum property tester for this problem, which is shown to be almost optimal.
Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we sho...
Keshav Bhateja, Mehdi Esmaili, A. Mantri· 0 citations
We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U...
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that $\widetilde{\Theta}(\sqrt{N})$ queries are necessary and sufficient for both these testing pro...
Chandrima Kayal, Sayantan Sen, Dániel Szabó· 0 citations
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation...
A. Ambainis, A. Gilyén, M. Kokainis· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.