A Caltech Library Service

Symmetries, Graph Properties, and Quantum Speedups

Ben-David, Shalev and Childs, Andrew M. and Gilyén, András and Kretschmer, William and Podder, Supartha and Wang, Daochen (2020) Symmetries, Graph Properties, and Quantum Speedups. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 649-660. ISBN 9781728196213.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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).

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2020 IEEE. We thank Scott Aaronson and Carl Miller for many helpful discussions. SP also thanks Zak Webb for many related discussions. Part of this work was done while visiting the Simons Institute for the Theory of Computing; we gratefully acknowledge its hospitality. AMC and DW acknowledge support from the Army Research Office (grant W911NF-20-1-0015); the Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams and Accelerated Research in Quantum Computing programs; and the National Science Foundation (grant CCF-1813814). AG acknowledges funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”. Additional support was provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). WK acknowledges support from a Vannevar Bush Fellowship from the US Department of Defense.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-20-1-0015
Department of Energy (DOE)UNSPECIFIED
Samsung ElectronicsUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Vannevar Bush FellowshipUNSPECIFIED
Subject Keywords:quantum query complexity; graph properties; property testing
Record Number:CaltechAUTHORS:20210630-171353593
Persistent URL:
Official Citation:S. Ben-David, A. M. Childs, A. Gilyén, W. Kretschmer, S. Podder and D. Wang, "Symmetries, Graph Properties, and Quantum Speedups," 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, pp. 649-660, doi: 10.1109/FOCS46700.2020.00066
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109674
Deposited By: Tony Diaz
Deposited On:30 Jun 2021 22:51
Last Modified:06 Jul 2021 22:00

Repository Staff Only: item control page