2026-07-21T14:16:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18868 2024-03-06T11:02:47Z ddc:004 open_access

Classical Simulation of One-Query Quantum Distinguishers Bogdanov, Andrej Cheung, Tsun Ming Dinesh, Krishnamoorthy Lui, John C. S. Query complexity quantum algorithms hypothesis testing Grothendieck’s inequality 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 ε-distinguishable by a one-query quantum algorithm, but O(ε k/√n)-indistinguishable by any non-adaptive k-query classical algorithm. We show that every pair of distributions that is ε-distinguishable by a one-query quantum algorithm is distinguishable with k classical queries and (1) advantage min{Ω(ε√{k/n})), Ω(ε²k²/n)} non-adaptively (i.e., in one round), and (2) advantage Ω(ε²k/√{n log n}) in two rounds. As part of our analysis, we introduce a general method for converting unbiased estimators into distinguishers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrej Bogdanov and Tsun Ming Cheung and Krishnamoorthy Dinesh and John C. S. Lui 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.43 urn:nbn:de:0030-drops-188684 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode