标题： 复杂性不足以证明随机性 显示英文标题

标题： Complexity is not Enough for Randomness

摘要： 我们研究布朗系统中随机性的动态生成作为哈密顿量局域程度的函数。 我们首先将这些系统的迹距离到一个单位设计表示为有效平衡热分区函数的形式，并提供一组保证设计时间线性增长的条件。 我们将迹距离到设计与时间演化算子的谱性质相关联。 我们将这些考虑应用于布朗$p$-SYK 模型作为局域程度$p$的函数。 我们证明设计时间是线性的，斜率与$1/p$成正比。 我们证实当$p$与系统大小同阶时，这再现了随机矩阵完全非局域布朗模型的行为。 对于随机矩阵模型，我们从单位流形中的经典布朗运动的角度重新解释这些结果。 因此，我们发现随机性的生成通常在系统大小的指数时间内持续存在，即使对于由高度非局域时间依赖哈密顿量支配的系统也是如此。 我们猜想这是普遍性质：除非时间依赖哈密顿量集合中存在大量微调，否则没有高效的方法可以动态生成近似哈耳随机酉变换。 我们将随机性的缓慢生成与时间演化算子的量子复杂度增长进行对比。 利用单位设计的电路复杂度已知界限，我们得到一个下界，确定复杂度至少随时间线性增长。 我们认为这些电路复杂度的界限远未紧密，并且复杂度的增长速度要快得多，至少对于非局域系统而言是这样。 显示英文摘要

摘要： We study the dynamical generation of randomness in Brownian systems as a function of the degree of locality of the Hamiltonian. We first express the trace distance to a unitary design for these systems in terms of an effective equilibrium thermal partition function, and provide a set of conditions that guarantee a linear time to design. We relate the trace distance to design to spectral properties of the time-evolution operator. We apply these considerations to the Brownian $p$-SYK model as a function of the degree of locality $p$. We show that the time to design is linear, with a slope proportional to $1/p$. We corroborate that when $p$ is of order the system size this reproduces the behavior of a completely non-local Brownian model of random matrices. For the random matrix model, we reinterpret these results from the point of view of classical Brownian motion in the unitary manifold. Therefore, we find that the generation of randomness typically persists for exponentially long times in the system size, even for systems governed by highly non-local time-dependent Hamiltonians. We conjecture this to be a general property: there is no efficient way to generate approximate Haar random unitaries dynamically, unless a large degree of fine-tuning is present in the ensemble of time-dependent Hamiltonians. We contrast the slow generation of randomness to the growth of quantum complexity of the time-evolution operator. Using known bounds on circuit complexity for unitary designs, we obtain a lower bound determining that complexity grows at least linearly in time for Brownian systems. We argue that these bounds on circuit complexity are far from tight and that complexity grows at a much faster rate, at least for non-local systems.