@conference {2599, title = {Symmetries, graph properties, and quantum speedups}, booktitle = {Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649{\textendash}660 (2020)}, year = {2020}, month = {6/23/2020}, abstract = {

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup?
In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups.
In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

}, doi = {https://doi.org/10.1109/FOCS46700.2020.00066}, url = {https://arxiv.org/abs/2006.12760}, author = {Shalev Ben-David and Andrew M. Childs and Andras Gilyen and William Kretschmer and Supartha Podder and Daochen Wang} } @article {2221, title = {Classical lower bounds from quantum upper bounds}, year = {2018}, abstract = {

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem.\ 
We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt{n}) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013.\ 
We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma_2 norm) of F: X x Y -\> {0,1} grows by a factor of Omega~(sqrt{n}) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov\&$\#$39;s celebrated Omega(sqrt{n}) lower bound on the quantum communication complexity of the disjointness problem.\ 
Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

}, url = {https://arxiv.org/abs/1807.06256}, author = {Shalev Ben-David and Adam Bouland and Ankit Garg and Robin Kothari} }