PIRSA:20120020

Symmetries, graph properties, and quantum speedups

Podder, S. (2020). Symmetries, graph properties, and quantum speedups. Perimeter Institute. https://pirsa.org/20120020

Podder, Supartha. Symmetries, graph properties, and quantum speedups. Perimeter Institute, Dec. 09, 2020, https://pirsa.org/20120020 

          @misc{ pirsa_PIRSA:20120020,
            doi = {10.48660/20120020},
            url = {https://pirsa.org/20120020},
            author = {Podder, Supartha},
            keywords = {Quantum Information},
            language = {en},
            title = {Symmetries, graph properties, and quantum speedups},
            publisher = {Perimeter Institute},
            year = {2020},
            month = {dec},
            note = {PIRSA:20120020 see, \url{https://pirsa.org}}
          }

Supartha Podder

University of Ottawa

Talk number
PIRSA:20120020
Collection
Talk Type
Subject
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). Based on: arxiv:2006.12760