Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-108 | 21st July 2023 06:40

Classical simulation of one-query quantum distinguishers



We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable by any non-adaptive $k$-query classical algorithm.

We show that every pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm is distinguishable with $k$ classical queries and
(1) advantage $\min\{\Omega(\epsilon\sqrt{k/n})), \Omega(\epsilon^2k^2/n)\}$ non-adaptively (i.e., in one round), and (2) advantage $\Omega(\epsilon^2k/\sqrt{n\log n})$ in two rounds.

As part of our analysis we introduce a general method for converting unbiased estimators into distinguishers.

ISSN 1433-8092 | Imprint