Complexity is not Enough for Randomness

• URL: http://arxiv.org/abs/2405.17546v2
• Date: Sun, 06 Oct 2024 16:10:15 GMT
• Title: Complexity is not Enough for Randomness
• Authors: Shiyong Guo, Martin Sasieta, Brian Swingle,
• Abstract summary: We study the dynamical generation of randomness in Brownian systems as a function of the degree of locality of the Hamiltonian. We find that the generation of randomness persists for exponentially long times in the system size, even for systems governed by highly non-local time-dependent Hamiltonians.
• Score: 0.0
• License:
• 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.

Related papers

• MindFlayer: Efficient Asynchronous Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
  We study the problem of minimizing the expectation of smooth non functions with the help of several parallel workers. We propose a new asynchronous SGD method, Mindlayer SGD, in which the noise is heavy tailed. Our theory empirical results demonstrate the superiority of Mindlayer SGD in cases when the noise is heavy tailed.
  arXiv  Detail & Related papers  (2024-10-05T21:11:32Z)
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians [0.0]
  We investigate circuit complexity of unitaries generated by time evolution of randomly chosen strongly interacting Hamiltonians in finite dimensional Hilbert spaces. We prove that the complexity of $exp(-it H)$ exhibits a surprising behaviour -- with high probability it reaches the maximal allowed value on the same time scale as needed to escape the neighborhood of the identity consisting of unitaries with trivial (zero) complexity.
  arXiv  Detail & Related papers  (2023-03-30T17:05:06Z)
• Linear Growth of Circuit Complexity from Brownian Dynamics [0.0]
  We calculate the frame potential for Brownian clusters of $N$ spins or fermions with time-dependent all-to-all interactions. We also consider the same question for systems with a time-independent Hamiltonian and argue that a small amount of time-dependent randomness is sufficient to generate a $k$-design in linear time.
  arXiv  Detail & Related papers  (2022-06-28T18:00:00Z)
• Simulation Complexity of Many-Body Localized Systems [0.0]
  We demonstrate a transition in the classical complexity of simulating such systems as a function of evolution time. We also show that the quantum circuit complexity for MBL systems is sublinear in evolution time.
  arXiv  Detail & Related papers  (2022-05-25T18:00:00Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T19:38:01Z)
• The connection between time-local and time-nonlocal perturbation expansions [0.0]
  We show that a series for the kernel $mathcalK$ to be translated directly into a corresponding series for the more complicated generator $mathcalG$. We illustrate this for leading and next-to-leading order calculations of $mathcalK$ and $mathcalG$ for the single impurity Anderson model.
  arXiv  Detail & Related papers  (2021-07-19T15:05:29Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  We consider causal discovery in continuous-time for the study of dynamical systems. We propose a causal discovery algorithm based on penalized Neural ODEs.
  arXiv  Detail & Related papers  (2021-05-06T08:48:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion [6.338178373376447]
  We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians. We demonstrate that the cost of the algorithm is independent of the Hamiltonian's frequencies.
  arXiv  Detail & Related papers  (2021-03-29T05:02:02Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.