@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 {2391, title = {Simulating quantum circuits by classical circuits}, year = {2019}, month = {04/10/2019}, abstract = {

In a recent breakthrough, Bravyi, Gosset and K{\"o}nig (BGK) [Science, 2018] proved that \"simulating\" constant depth quantum circuits takes classical circuits Ω(logn) depth. In our paper, we first formalise their notion of simulation, which we call \"possibilistic simulation\". Then, from well-known results, we deduce that their circuits can be simulated in depth O(log2n). Separately, we construct explicit classical circuits that can simulate any depth-d quantum circuit with Clifford and t T-gates in depth O(d+t). Our classical circuits use {NOT, AND, OR} gates of fan-in \≤2.

}, url = {https://arxiv.org/abs/1904.05282}, author = {Daochen Wang} }