Skip to Main content Skip to Navigation
Conference papers

A note on the quantum query complexity of permutation symmetric functions

Abstract : It is known since the work of [AA14] 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) = \widetilde{O}\left(Q^7(f)\right)$. In this paper, we improve this result and show that $R(f) = {O}\left(Q^3(f)\right)$ 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 [Zha15].
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01950650
Contributor : André Chailloux <>
Submitted on : Tuesday, December 11, 2018 - 1:46:40 AM
Last modification on : Monday, January 6, 2020 - 11:32:32 AM
Long-term archiving on: : Tuesday, March 12, 2019 - 12:47:28 PM

File

1810.01790.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

André Chailloux. A note on the quantum query complexity of permutation symmetric functions. ITCS 2019 - 10th Annual Innovations in Theoretical Computer Science, Jan 2019, San Diego, United States. ⟨10.4230/LIPIcs.ITCS.2019.19⟩. ⟨hal-01950650⟩

Share

Metrics

Record views

85

Files downloads

80