标题： 从干草堆里挑出：量子电路复杂性指数增长的显式例子 显示英文标题

标题： 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.