论文标题
对称性，图形属性和量子加速
Symmetries, graph properties, and quantum speedups
论文作者
论文摘要
Aaronson和Ambainis（2009）和Chailloux（2018）表明，完全对称（部分）功能不接受指数量子查询加速。这提出了一个自然的问题：在函数无法表现出很大的量子加速之前，必须如何对称？ 在这项工作中，我们证明邻接矩阵模型中的超图对称性最多允许随机和量子查询复杂性之间的多项式分离。我们还表明，显着的，这些对称性构建的置换群本质上是唯一防止超多种量子加速的置换组。我们通过充分表征允许超级物质量子加速的原始置换组来证明这一点。 相比之下，在有界度图的邻接列表模型中（其中图对称性的表现不同），我们表现出一个属性测试问题，该问题显示了指数量子的速度。这些结果解决了由Ambainis，Childs和Liu（2010）以及Montanaro和De Wolf（2013）提出的开放问题。
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).
