论文标题
对于大量子加速度，对称性太对称了？
How symmetric is too symmetric for large quantum speedups?
论文作者
论文摘要
假设Boolean函数$ f $是在集体操作$ g $下作用于输入的$ n $位的对称的。对于哪个$ g $，这意味着$ f $没有指数的量子加速？在函数$ f $无法具有足够的结构来利用该功能之前，是否有富裕$ g $的表征？ 在这项工作中，我们迈出了几个步骤，以理解以这种方式“量子不耐受”的团体操作$ g $。我们表明，足够的传递群体动作不允许量子加速，并且小组动作的“井井有条”的特性（恰好由几种自然变换保存）意味着在小组动作下缺乏对称功能的超级多项式加速。我们的技术是由Chailloux（2018）最近的一篇论文激励的，该论文涉及$ g = s_n $的情况。 我们的主要应用程序是图形对称性：我们证明，在图形的邻接矩阵上定义的任何布尔函数$ f $（在RelabeLing the图的顶点下的对称性）在其随机和量子查询复杂性之间具有$ 6 $的关系，即使$ f $是部分函数。特别是，这意味着没有图形属性测试问题可以具有超级多项式量子加速，这解决了Ambainis，Childs和Liu（2011）的开放问题。
Suppose a Boolean function $f$ is symmetric under a group action $G$ acting on the $n$ bits of the input. For which $G$ does this mean $f$ does not have an exponential quantum speedup? Is there a characterization of how rich $G$ must be before the function $f$ cannot have enough structure for quantum algorithms to exploit? In this work, we make several steps towards understanding the group actions $G$ which are "quantum intolerant" in this way. We show that sufficiently transitive group actions do not allow a quantum speedup, and that a "well-shuffling" property of group actions -- which happens to be preserved by several natural transformations -- implies a lack of super-polynomial speedups for functions symmetric under the group action. Our techniques are motivated by a recent paper by Chailloux (2018), which deals with the case where $G=S_n$. Our main application is for graph symmetries: we show that any Boolean function $f$ defined on the adjacency matrix of a graph (and symmetric under relabeling the vertices of the graph) has a power $6$ relationship between its randomized and quantum query complexities, even if $f$ is a partial function. In particular, this means no graph property testing problems can have super-polynomial quantum speedups, settling an open problem of Ambainis, Childs, and Liu (2011).
