论文标题
通过灵敏度，魔术和连贯性的量子电路的复杂性
Complexity of quantum circuits via sensitivity, magic, and coherence
论文作者
论文摘要
量子电路复杂性 - 实现给定统一转换所需的最小门数的量度 - 是量子计算中的基本概念，其广泛应用程序从确定量子算法的运行时间到了解黑洞的物理。在这项工作中，我们使用灵敏度，平均灵敏度（也称为影响），魔术和连贯性的概念研究了量子回路的复杂性。我们以消失的灵敏度来表征一组单位，并表明它与对照门家族一致。由于匹配设备是可行的量子电路，因此我们证明了量子加速的灵敏度是必要的。由于魔术是量化量子优势的另一种措施，因此了解魔术与灵敏度之间的关系很有趣。我们通过引入傅立叶熵影响关系的量子版本来做到这一点。我们的结果是了解量子计算中灵敏度，魔术和连贯性的作用的关键。
Quantum circuit complexity-a measure of the minimum number of gates needed to implement a given unitary transformation-is a fundamental concept in quantum computation, with widespread applications ranging from determining the running time of quantum algorithms to understanding the physics of black holes. In this work, we study the complexity of quantum circuits using the notions of sensitivity, average sensitivity (also called influence), magic, and coherence. We characterize the set of unitaries with vanishing sensitivity and show that it coincides with the family of matchgates. Since matchgates are tractable quantum circuits, we have proved that sensitivity is necessary for a quantum speedup. As magic is another measure to quantify quantum advantage, it is interesting to understand the relation between magic and sensitivity. We do this by introducing a quantum version of the Fourier entropy-influence relation. Our results are pivotal for understanding the role of sensitivity, magic, and coherence in quantum computation.
