Symmetries, graph properties, and quantum speedups

作     者：Ben-David, Shalev Childs, Andrew M. Gilyén, András Kretschmer, William Podder, Supartha Wang, Daochen 

作者机构：Cheriton School of Computer Science University of Waterloo Canada Department of Computer Science Institute for Advanced Computer Studies University of Maryland United States Joint Center for Quantum Information and Computer Science University of Maryland United States Institute for Quantum Information and Matter California Institute of Technology United States Simons Institute for the Theory of Computing University of California Berkeley United States Department of Computer Science University of Texas Austin United States Department of Mathematics and Statistics University of Ottawa Canada Department of Mathematics University of Maryland United States 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2020年

核心收录：

主　　题：Group theory 

摘      要：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). Copyright © 2020, The Authors. All rights reserved.