Linear Growth of Circuit Complexity from Brownian Dynamics

• URL: http://arxiv.org/abs/2206.14205v1
• Date: Tue, 28 Jun 2022 18:00:00 GMT
• Title: Linear Growth of Circuit Complexity from Brownian Dynamics
• Authors: Shao-Kai Jian, Gregory Bentsen, Brian Swingle
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We calculate the frame potential for Brownian clusters of $N$ spins or fermions with time-dependent all-to-all interactions. In both cases the problem can be mapped to an effective statistical mechanics problem which we study using a path integral approach. We argue that the $k$th frame potential comes within $\epsilon$ of the Haar value after a time of order $t \sim k N + k \log k + \log \epsilon^{-1}$. Using a bound on the diamond norm, this implies that such circuits are capable of coming very close to a unitary $k$-design after a time of order $t \sim k N$. 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 provided the underlying Hamiltonian is quantum chaotic. These models provide explicit examples of linear complexity growth that are also analytically tractable.

Related papers

• New random compiler for Hamiltonians via Markov Chains [0.08192907805418585]
  Many quantum algorithms, such as adiabatic algorithms, require simulating Hamiltonian evolution. We develop a new compiler, similar to the first order randomized Trotter, but with an arguably simpler framework. It is more versatile as it supports a large class of randomisation schemes and as well as time-dependent weights.
  arXiv  Detail & Related papers  (2024-11-10T14:57:25Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known. Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Complexity is not Enough for Randomness [0.0]
  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.
  arXiv  Detail & Related papers  (2024-05-27T18:00:00Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  This nearly establishes a conjecture ofciteSaundersonCPW12, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
  arXiv  Detail & Related papers  (2022-12-21T17:48:01Z)
• Unbiased random circuit compiler for time-dependent Hamiltonian simulation [8.694056486825318]
  Time-dependent Hamiltonian simulation is a critical task in quantum computing. We develop an unbiased random compiler for TDHS. We perform numerical simulations for a spin model under the interaction picture and the adiabatic ground state preparation for molecular systems.
  arXiv  Detail & Related papers  (2022-12-19T13:40:05Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• A real expectation value of the time-dependent non-Hermitian Hamiltonians [0.0]
  We solve the time-dependent Schr"odinger equation associated to a time-dependent non-Hermitian Hamiltonian. The expectation value of the non-Hermitian Hamiltonian in the $mathcalC(tmathcal)PT$ normed states is guaranteed to be real.
  arXiv  Detail & Related papers  (2021-12-27T06:27:33Z)
• Boundary time crystals in collective $d$-level systems [64.76138964691705]
  Boundary time crystals are non-equilibrium phases of matter occurring in quantum systems in contact to an environment. We study BTC's in collective $d$-level systems, focusing in the cases with $d=2$, $3$ and $4$.
  arXiv  Detail & Related papers  (2021-02-05T19:00:45Z)
• Spectral statistics in constrained many-body quantum chaotic systems [0.0]
  We study the spectral statistics of spatially-extended many-body quantum systems with on-site Abelian symmetries or local constraints. In particular, we analytically argue that in a system of length $L$ that conserves the $mth$ multipole moment, $t_mathrmTh$ scales subdiffusively as $L2(m+1)$.
  arXiv  Detail & Related papers  (2020-09-24T17:59:57Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

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.