All reports by Author John C.S. Lui:

__
TR23-108
| 21st July 2023
__

Andrej Bogdanov, TsunMing Cheung, Krishnamoorthy Dinesh, John C.S. Lui#### Classical simulation of one-query quantum distinguishers

Andrej Bogdanov, TsunMing Cheung, Krishnamoorthy Dinesh, John C.S. Lui

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 ... more >>>