论文标题
干草的干草：指数量子电路复杂性的明确示例
Hay from the haystack: explicit examples of exponential quantum circuit complexity
论文作者
论文摘要
绝大多数量子状态和单位型在量子数的数量中具有电路复杂性指数。同样，它们中的大多数也具有指数最小的描述长度，这使得很难确定指数复杂性的示例。在这项工作中，我们构建了恒定描述长度但指数电路复杂性的示例。我们提供无限的家族，使每个元素都需要从产品中精确地生成指数数的两倍大门，并且对于该家族中绝大多数元素的大约生成也是如此。结果基于一组较大的超越程度，并讨论了张量网络，对角线单位和最大相干状态。
The vast majority of quantum states and unitaries have circuit complexity exponential in the number of qubits. In a similar vein, most of them also have exponential minimum description length, which makes it difficult to pinpoint examples of exponential complexity. In this work, we construct examples of constant description length but exponential circuit complexity. We provide infinite families such that each element requires an exponential number of two-qubit gates to be generated exactly from a product and where the same is true for the approximate generation of the vast majority of elements in the family. The results are based on sets of large transcendence degree and discussed for tensor networks, diagonal unitaries, and maximally coherent states.
