A Note on the Quantum Query Complexity of Permutation Symmetric Functions

Chailloux, André

doi:10.4230/LIPIcs.ITCS.2019.19

File

LIPIcs.ITCS.2019.19.pdf

Filesize: 394 kB
7 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ITCS.2019.19
URN: urn:nbn:de:0030-drops-101126

Author Details

André Chailloux

Inria de Paris, EPI SECRET, Paris, France

Cite AsGet BibTex

André Chailloux. A Note on the Quantum Query Complexity of Permutation Symmetric Functions. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 19:1-19:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.19

Abstract

It is known since the work of [Aaronson and Ambainis, 2014] that for any permutation symmetric function f, the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that R(f) = O~(Q^7(f)). In this paper, we improve this result and show that R(f) = O(Q^3(f)) for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zhandry, 2015].

Subject Classification

ACM Subject Classification

Theory of computation → Quantum query complexity

Keywords

quantum query complexity
permutation symmetric functions

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Scott Aaronson and Andris Ambainis. The Need for Structure in Quantum Speedups. Theory of Computing, 10(6):133-166, 2014. URL: http://dx.doi.org/10.4086/toc.2014.v010a006.
Scott Aaronson and Yaoyun Shi. Quantum Lower Bounds for the Collision and the Element Distinctness Problems. J. ACM, 51(4):595-605, July 2004. URL: http://dx.doi.org/10.1145/1008731.1008735.
A. Ambainis. Understanding Quantum Algorithms via Query Complexity. ArXiv e-prints, December 2017. URL: http://arxiv.org/abs/1712.06349.
Andris Ambainis. Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range. Theory of Computing, 1(3):37-46, 2005. URL: http://dx.doi.org/10.4086/toc.2005.v001a003.
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum Lower Bounds by Polynomials. J. ACM, 48(4):778-797, July 2001. URL: http://dx.doi.org/10.1145/502090.502097.
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and Weaknesses of Quantum Computing. SIAM Journal of Computing, 26(5):1510-1523, October 1997. URL: http://dx.doi.org/10.1137/S0097539796300933.
D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 439(1907):553-558, 1992. URL: http://dx.doi.org/10.1098/rspa.1992.0167.
Samuel Kutin. Quantum Lower Bound for the Collision Problem with Small Range. Theory of Computing, 1(2):29-36, 2005. URL: http://dx.doi.org/10.4086/toc.2005.v001a002.
Peter W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In IEEE Symposium on Foundations of Computer Science, pages 124-134, 1994. URL: https://citeseer.ist.psu.edu/14533.html.
Daniel R. Simon. On the Power of Quantum Cryptography. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 116-123, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365701.
Mark Zhandry. A Note on the Quantum Collision and Set Equality Problems. Quantum Info. Comput., 15(7-8):557-567, May 2015. URL: http://dl.acm.org/citation.cfm?id=2871411.2871413.
Mark Zhandry. How to Record Quantum Queries, and Applications to Quantum Indifferentiability. IACR Cryptology ePrint Archive, 2018:276, 2018. URL: https://eprint.iacr.org/2018/276.