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. https://resolver.caltech.edu/CaltechAUTHORS:20210630-171353593
![]() |
PDF
- Accepted Version
See Usage Policy. 635kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210630-171353593
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).
Item Type: | Book Section | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||
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 | ||||||||||||||||
Funders: |
| ||||||||||||||||
Subject Keywords: | quantum query complexity; graph properties; property testing | ||||||||||||||||
DOI: | 10.1109/focs46700.2020.00066 | ||||||||||||||||
Record Number: | CaltechAUTHORS:20210630-171353593 | ||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20210630-171353593 | ||||||||||||||||
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 | ||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||||
Deposited On: | 30 Jun 2021 22:51 | ||||||||||||||||
Last Modified: | 06 Jul 2021 22:00 |
Repository Staff Only: item control page