Symmetries, graph properties, and quantum speedups

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

arXiv comment46 pages. Subsumes arXiv:2001.09642 and arXiv:2001.10520; adds a characterization of permutation groups with speedup and an exponential speedup for adjacency-list graph property testing

References in corpus (5)

• Exponential algorithmic speedup by quantum walk
• Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
• The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
• Quantum property testing for bounded-degree graphs
• The Structure of Promises in Quantum Speedups

Cited by in corpus (4)

• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Information compression via hidden subgroup quantum autoencoders
• Exponential speedups for quantum walks in random hierarchical graphs
• Increasing extractable work in small qubit landscapes