2020/01/27 by Shalev Ben-David, Ben-David, Shalev, Supartha Podder +1 · 2 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.2001.09642
18 pages
arxiv created 2020/01/27 · openalex publication_date 2020/01/27 · arxiv updated 2020/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose a Boolean function f is symmetric under a group action G acting on the n bits of the input. For which G does this mean f does not have an exponential quantum speedup? Is there a characterization of how rich G must be before the function f cannot have enough structure for quantum algorithms to exploit? In this work, we make several steps towards understanding the group actions G which are "quantum intolerant" in this way. We show that sufficiently transitive group actions do not allow a quantum speedup, and that a "well-shuffling" property of group actions -- which happens to be preserved by several natural transformations -- implies a lack of super-polynomial speedups for functions symmetric under the group action. Our techniques are motivated by a recent paper by Chailloux (2018), which deals with the case where G=Sn. Our main application is for graph symmetries: we show that any Boolean function f defined on the adjacency matrix of a graph (and symmetric under relabeling the vertices of the graph) has a power 6 relationship between its randomized and quantum query complexities, even if f is a partial function. In particular, this means no graph property testing problems can have super-polynomial quantum speedups, settling an open problem of Ambainis, Childs, and Liu (2011).