Chakraborty Shantanav, Luh Kyle, Roland Jérémie
QuIC, Ecolé Polytechnique de Bruxelles, Université libre de Bruxelles, Brussels, Belgium.
Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA.
Phys Rev Lett. 2020 Feb 7;124(5):050501. doi: 10.1103/PhysRevLett.124.050501.
The fundamental problem of sampling from the limiting distribution of quantum walks on networks, known as mixing, finds widespread applications in several areas of quantum information and computation. Of particular interest in most of these applications is the minimum time beyond which the instantaneous probability distribution of the quantum walk remains close to this limiting distribution, known as the "quantum mixing time". However, this quantity is only known for a handful of specific networks. In this Letter, we prove an upper bound on the quantum mixing time for almost all networks, i.e., the fraction of networks for which our bound holds, goes to one in the asymptotic limit. To this end, using several results in random matrix theory, we find the quantum mixing time of Erdös-Renyi random networks: networks of n nodes where each edge exists with probability p independently. For example, for dense random networks, where p is a constant, we show that the quantum mixing time is O(n^{3/2+o(1)}). In addition to opening avenues for the analytical study of quantum dynamics on random networks, our work could find applications beyond quantum information processing. Owing to the universality of Wigner random matrices, our results on the spectral properties of random graphs hold for general classes of random matrices that are ubiquitous in several areas of physics. In particular, our results could lead to novel insights into the equilibration times of isolated quantum systems defined by random Hamiltonians, a foundational problem in quantum statistical mechanics.
从网络上量子行走的极限分布进行采样的基本问题，即混合问题，在量子信息和计算的多个领域有着广泛应用。在这些应用中的大多数情况下，特别令人感兴趣的是量子行走的瞬时概率分布保持接近此极限分布的最短时间，即所谓的“量子混合时间”。然而，这个量仅在少数特定网络中是已知的。在本信函中，我们证明了几乎所有网络的量子混合时间的一个上界，也就是说，我们的界所适用的网络比例在渐近极限中趋于1。为此，利用随机矩阵理论中的几个结果，我们求出了厄多斯 - 雷尼随机网络的量子混合时间：具有n个节点的网络，其中每条边以概率p独立存在。例如，对于p为常数的稠密随机网络，我们表明量子混合时间为O(n^{3/2 + o(1)})。除了为随机网络上量子动力学的分析研究开辟途径外，我们的工作还可能在量子信息处理之外找到应用。由于维格纳随机矩阵的普遍性，我们关于随机图谱性质的结果适用于在物理学多个领域中普遍存在的一般类随机矩阵。特别是，我们的结果可能会为随机哈密顿量定义的孤立量子系统的平衡时间带来新的见解，这是量子统计力学中的一个基础问题。
