SciPost Submission Page
Complexity is not Enough for Randomness
by Shiyong Guo, Martin Sasieta, Brian Swingle
This is not the latest submitted version.
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Martin Sasieta |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/2405.17546v1 (pdf) |
| Date submitted: | 2024-06-10 21:49 |
| Submitted by: | Sasieta, Martin |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approach: | Theoretical |
Abstract
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.
Author indications on fulfilling journal expectations
- Provide a novel and synergetic link between different research areas.
- Open a new pathway in an existing or a new research direction, with clear potential for multi-pronged follow-up work
- Detail a groundbreaking theoretical/experimental/computational discovery
- Present a breakthrough on a previously-identified and long-standing research stumbling block
Current status:
Reports on this Submission
Report #2 by Anonymous (Referee 2) on 2024-8-26 (Contributed Report)
- Cite as: Anonymous, Report on arXiv:2405.17546v1, delivered 2024-08-26, doi: 10.21468/SciPost.Report.9653
Report
In this work, the authors study Haar randomness in Brownian systems. They show that the time to become a k-design is linear both for a general setup satisfying certain assumptions as well as for Brownian SYK and random matrix models.
The introduction provides the necessary motivation and background. The technical sections are clear and present calculations to an appropriate level of detail. The appendices provide relevant additional details.
Given the novelty and significance of this work, I recommend this paper for publication with a few minor changes listed below.
Requested changes
1. On page 12, the authors have some general comments about when $\text{V}_k = \text{GS}_k$ pertaining to the lack of clusters and global symmetries. This is a fairly important point and it would be helpful to explain the intuition behind this claim in greater detail.
2. On page 17, below (3.7) the authors should define $Q^r$.
3. On page 35, (4.44) $\varepsilon^{-1}$ should be changed to $\log \varepsilon^{-1}$.
4. On page 44, below (C.6) the authors assume that $H_0$ lacks degeneracies and rational relations. If this assumption is violated, I would expect $\text{dim GS}_k$ to be larger. This would still imply that $\mathcal{E}_t$ never becomes a $k$-design. Some clarification to this end would be helpful.
Recommendation
Ask for minor revision
Report #1 by Anonymous (Referee 1) on 2024-7-24 (Invited Report)
- Cite as: Anonymous, Report on arXiv:2405.17546v1, delivered 2024-07-24, doi: 10.21468/SciPost.Report.9457
Report
The paper asks a very interesting question: how hard is it to generate truly Haar-random dynamics
in a Hamiltonian system? The authors propose that it is indeed hard: the time it would take scales
exponentially with a system size. To corroborate this statement they present several universal arguments in the Introduction and also study several physical systems: the Brownian Sachdev--Ye--Kitaev (SYK) model, Brownian random
matrix and a diffusion on the unitary group.
The paper is very-well written, the physical question it addresses is important and I generally agree with the conclusion, so I highly recommend the paper for the publication. However, I would like the authors to address a few questions.
The main one is related to the design time. Eqns. (3.37), (4.29) for the design time contain 1/J factor.
Suppose that my sole goal is to generate a Haar random matrix using the SYK model. Would it be a legit thing to do
to make J very large (exponential in the system size) in order to achieve Haar randomness at times of order 1?
Also do I understand correctly that the authors would call such scaling unphysical because the two-point function
would decay on a time-scale of order inverse exponential system size?
Also I have a few less important questions:
I agree with most of the arguments from the Introduction about atypicality of $H_{Haar}$.
However, I am confused by the following statement on p.4: "On the other hand, the Hamiltonian H_{Haar} has approximately uniform spectrum on an interval". I thought that the eigenphases of a Haar random matrix do
exhibit repulsion - e.g. eq. (2.35) from the paper.
p.7: "...the growth in circuit complexity is expected to
generally be hyperfast in non-local systems. "
Does "hyperfast" mean that the complexity is saturated at times of order 1?
In this paper \epsilon-approximate k-design is defined through Schatten 1-norm of the corresponding
superoperator - eq. (2.5) . What is the motivation for using this norm? Schatten 1-norm is very useful for bounding
the correlation functions via the Holder inequality,
but as the authors point out in Appendix B, the diamond norm is generally smaller.
I am wondering if the design times will be significantly affected by the choice of the norm.
Finally, I noticed one typo:
Bottom of p.5: "non-trivial part the becomes to".
Recommendation
Ask for minor revision