DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.43

Classical Simulation of One-Query Quantum Distinguishers

Authors: Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, and John C. S. Lui

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract

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.

Cite as

Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, and John C. S. Lui. Classical Simulation of One-Query Quantum Distinguishers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.APPROX/RANDOM.2023.43,
  author =	{Bogdanov, Andrej and Cheung, Tsun Ming and Dinesh, Krishnamoorthy and Lui, John C. S.},
  title =	{{Classical Simulation of One-Query Quantum Distinguishers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.43},
  URN =		{urn:nbn:de:0030-drops-188684},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.43},
  annote =	{Keywords: Query complexity, quantum algorithms, hypothesis testing, Grothendieck’s inequality}
}

Search Results

Documents authored by Cheung, Tsun Ming

Classical Simulation of One-Query Quantum Distinguishers

Abstract

Cite as

Thanks for your feedback!

Could not send message