|Title||Symmetries, graph properties, and quantum speedups|
|Publication Type||Journal Article|
|Year of Publication||2020|
|Authors||Ben-David, S, Childs, AM, Gilyen, A, Kretschmer, W, Podder, S, Wang, D|
|Journal||To appear in Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS 2020)|
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?