LIPIcs.APPROX-RANDOM.2023.43.pdf
- Filesize: 0.71 MB
- 17 pages
Document
Classical Simulation of One-Query Quantum Distinguishers
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
Conference: International Conference on Randomization and Computation (RANDOM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-09-04
File
Document Identifiers
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.43
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Probabilistic computation
Keywords
- Query complexity
- quantum algorithms
- hypothesis testing
- Grothendieck’s inequality
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 307-316, 2015. URL: https://doi.org/10.1145/2746539.2746547.
- Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, and Cheung Tsun Ming. On quantum versus classical query complexity. Electron. Colloquium Comput. Complex., TR21-115, 2021. URL: https://arxiv.org/abs/TR21-115.
- Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, and Juris Smotrovs. Polynomials, quantum query complexity, and grothendieck’s inequality. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 25:1-25:19, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.25.
- Nikhil Bansal and Makrand Sinha. k-forrelation optimally separates quantum and classical query complexity. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1303-1316, 2021. URL: https://doi.org/10.1145/3406325.3451040.
- Sergey Bravyi, David Gosset, Daniel Grier, and Luke Schaeffer. Classical algorithms for Forrelation, 2021. URL: https://arxiv.org/abs/2102.06963.
- Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig. Quantum property testing. SIAM J. Comput., 37(5):1387-1400, 2008. URL: https://doi.org/10.1137/S0097539704442416.
- Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians, 2020. URL: https://arxiv.org/abs/1810.08693.
- Joseph Jaeger, Fang Song, and Stefano Tessaro. Quantum key-length extension. In Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part I, pages 209-239, Berlin, Heidelberg, 2021. Springer-Verlag. URL: https://doi.org/10.1007/978-3-030-90459-3_8.
- Gilles Pisier. Grothendieck’s theorem, past and present. Bulletin of the American Mathematical Society, 49(2):237-323, May 2012. URL: https://doi.org/10.1090/s0273-0979-2011-01348-9.
- Mark Rudelson and Roman Vershynin. Sampling from large matrices: an approach through geometric functional analysis, 2006. URL: https://arxiv.org/abs/math/0503442.
- Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu. An optimal separation of randomized and quantum query complexity. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1289-1302, 2021. URL: https://doi.org/10.1145/3406325.3451019.
- Joel A. Tropp. Column subset selection, matrix factorization, and eigenvalue optimization, 2008. URL: https://arxiv.org/abs/0806.4404.
- Joel A. Tropp. On the linear independence of spikes and sines. Journal of Fourier Analysis and Applications, 14(5-6):838-858, September 2008. URL: https://doi.org/10.1007/s00041-008-9042-0.
-
Henry Yuen. A quantum lower bound for distinguishing random functions from random permutations. Quantum Info. Comput., 14(13–14):1089-1097, October 2014.
- Mark Zhandry. How to construct quantum random functions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 679-687, 2012. URL: https://doi.org/10.1109/FOCS.2012.37.