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.

Bio: Andrew Childs, co-director of QuICS, is a professor in the Department of Computer Science and the Institute for Advanced Computer Studies (UMIACS).

Childs's research interests are in the theory of quantum information processing, especially quantum algorithms.

He has explored the computational power of quantum walk, providing an example of exponential speedup, demonstrating computational universality, and constructing algorithms for problems including search and formula evaluation. Childs has also developed fast quantum algorithms for simulating Hamiltonian dynamics. His other areas of interest include quantum query complexity and quantum algorithms for algebraic problems.

Before coming to UMD, Childs was a DuBridge Postdoctoral Scholar at Caltech from 2004-2007 and a faculty member in Combinatorics & Optimization and the Institute for Quantum Computing at the University of Waterloo from 2007-2014. Childs received his doctorate in physics from MIT in 2004.