Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEntropic barriers as a reason for hardness in both classical and quantum algorithms
397
0
0.0
(
0
)
Added by
Federico Ricci-Tersenghi
Publication date
2021
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers. We study, both analytically and numerically, several optimization algorithms, finding that entropic barriers affect in a similar way classical local algorithms and quantum annealing. For the adiabatic algorithm, the difficulty we identify is distinct from that of tunnelling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.
rate research
Read More
Probing the out-of-equilibrium dynamics of quantum matter has gained renewed interest owing to immense experimental progress in artifcial quantum systems. Dynamical quantum measures such as the growth of entanglement entropy (EE) and out-of-time ordered correlators (OTOCs) have been shown, theoretically, to provide great insight by exposing subtle quantum features invisible to traditional measures such as mass transport. However, measuring them in experiments requires either identical copies of the system, an ancilla qubit coupled to the whole system, or many measurements on a single copy, thereby making scalability extremely complex and hence, severely limiting their potential. Here, we introduce an alternate quantity $-$ the out-of-time-ordered measurement (OTOM) $-$ which involves measuring a single observable on a single copy of the system, while retaining the distinctive features of the OTOCs. We show, theoretically, that OTOMs are closely related to OTOCs in a doubled system with the same quantum statistical properties as the original system. Using exact diagonalization, we numerically simulate classical mass transport, as well as quantum dynamics through computations of the OTOC, the OTOM, and the EE in quantum spin chain models in various interesting regimes (including chaotic and many-body localized systems). Our results demonstrate that an OTOM can successfully reveal subtle aspects of quantum dynamics hidden to classical measures, and crucially, provide experimental access to them.
Local entropic loss functions provide a versatile framework to define architecture-aware regularization procedures. Besides the possibility of being anisotropic in the synaptic space, the local entropic smoothening of the loss function can vary during training, thus yielding a tunable model complexity. A scoping protocol where the regularization is strong in the early-stage of the training and then fades progressively away constitutes an alternative to standard initialization procedures for deep convolutional neural networks, nonetheless, it has wider applicability. We analyze anisotropic, local entropic smoothenings in the language of statistical physics and information theory, providing insight into both their interpretation and workings. We comment some aspects related to the physics of renormalization and the spacetime structure of convolutional networks.
Restricted Boltzmann Machines (RBM) are bi-layer neural networks used for the unsupervised learning of model distributions from data. The bipartite architecture of RBM naturally defines an elegant sampling procedure, called Alternating Gibbs Sampling (AGS), where the configurations of the latent-variable layer are sampled conditional to the data-variable layer, and vice versa. We study here the performance of AGS on several analytically tractable models borrowed from statistical mechanics. We show that standard AGS is not more efficient than classical Metropolis-Hastings (MH) sampling of the effective energy landscape defined on the data layer. However, RBM can identify meaningful representations of training data in their latent space. Furthermore, using these representations and combining Gibbs sampling with the MH algorithm in the latent space can enhance the sampling performance of the RBM when the hidden units encode weakly dependent features of the data. We illustrate our findings on three datasets: Bars and Stripes and MNIST, well known in machine learning, and the so-called Lattice Proteins, introduced in theoretical biology to study the sequence-to-structure mapping in proteins.
In this work I will discuss some numerical results on the stability of the many-body localized phase to thermal inclusions. The work simplifies a recent proposal by Morningstar et al. [arXiv:2107.05642] and studies small disordered spin chains which are perturbatively coupled to a Markovian bath. The critical disorder for avalanche stability of the canonical disordered Heisenberg chain is shown to exceed W>20. In stark contrast to the Anderson insulator, the avalanche threshold drifts considerably with system size, with no evidence of saturation in the studied regime. I will argue that the results are most easily explained by the absence of a many-body localized phase.
Monitored quantum circuits can exhibit an entanglement transition as a function of the rate of measurements, stemming from the competition between scrambling unitary dynamics and disentangling projective measurements. We study how entanglement dynamics in non-unitary quantum circuits can be enriched in the presence of charge conservation, using a combination of exact numerics and a mapping onto a statistical mechanics model of constrained hard-core random walkers. We uncover a charge-sharpening transition that separates different scrambling phases with volume-law scaling of entanglement, distinguished by whether measurements can efficiently reveal the total charge of the system. We find that while Renyi entropies grow sub-ballistically as $sqrt{t}$ in the absence of measurement, for even an infinitesimal rate of measurements, all average Renyi entropies grow ballistically with time $sim t$. We study numerically the critical behavior of the charge-sharpening and entanglement transitions in U(1) circuits, and show that they exhibit emergent Lorentz invariance and can also be diagnosed using scalable local ancilla probes. Our statistical mechanical mapping technique readily generalizes to arbitrary Abelian groups, and offers a general framework for studying dissipatively-stabilized symmetry-breaking and topological orders.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
