Simulated quantum annealing (SQA) is a classical computational strategy that emulates a quantum annealing (QA) dynamics through a path-integral Monte Carlo whose parameters are changed during the simulation. Here we apply SQA to the one-dimensional transverse field Ising chain, where previous works have shown that, in the presence of disorder, a coherent QA provides a quadratic speedup with respect to classical simulated annealing, with a density of Kibble-Zurek defects decaying as ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}2}$ as opposed to ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}1}, \ensuremath{\tau}$ being the total annealing time, while for the ordered case both give the same power law ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\approx}{\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}1/2}$. We show that the dynamics of SQA, while correctly capturing the Kibble-Zurek scaling ${\ensuremath{\tau}}^{\ensuremath{-}1/2}$ for the ordered case, is unable to reproduce the QA dynamics in the disordered case at intermediate $\ensuremath{\tau}$. We analyze and discuss several issues related to the choice of the Monte Carlo moves (local or global in space), the time-continuum limit needed to eliminate the Trotter-discretization error, and the long autocorrelation times shown by a local-in-space Monte Carlo dynamics for large disordered samples.
Simulated annealing and quantum annealing are algorithms for combinatorial optimization problems. The former brings solutions using thermal fluctuations and through classical dynamics, while the latter does using quantum fluctuations and through quantum dynamics. In this paper, dynamics of these two algorithms are compared by means of the Kibble-Zurek argument, employing a one-dimensional random Ising model as an exercise for algorithms. We reveal that quantum annealing reduces residual errors faster than simulated annealing with decreasing annealing rate. The result implies the advantage of quantum annealing over simulated annealing.
The Kibble-Zurek mechanism (KZM) was originally proposed to describe the evolution and "freezing" of defects in the early universe, but later it was generalized to study other quantum and classical systems driven by a varying parameter. The basic idea behind the KZM is that, as long as the changing rate (velocity) of the parameter is below a certain critical velocity, 𝑣_crit, the system will remain adiabatic (for isolated quantum systems) or quasi-static (for classical systems with a heat bath). \nThe nonequilibrium finite-size scaling (FSS) method based on KZM has been exploited systematically. Through applying the scaling hypothesis, we can extract the critical exponents and study the dynamic properties of the system. \n \nIn the first few chapters of this dissertation, we discuss the applications of KZM in several classical systems: first, we study the dynamics of 2D and 3D Ising model under a varying temperature as well as a varying magnetic field. Secondly, we examine the classical ℤ₂ gauge model, in which we show that KZM also works for topological phase transitions. Moreover, we also investigate the dynamics of other models with topological ordering only at T=0, where KZM cannot be applied. Lastly, we explore the 2D Ising spin glass with bimodal and gaussian couplings. With bimodal couplings, we find dual time scales associated with the order parameter and the energy correspondingly, while in the gaussian case one unique time scale is involved. \n \nThe systems mentioned above are all classical and the dynamics are approached through simulated annealing (SA), in which thermal fluctuations drives systems to explore the energy landscape in finding the ground state. In the last chapter, we explore the efficiency of Quantum Annealing (QA) on a fully-connected spin glass (or Sherington-Kirkpatrick model) with a transverse field. QA is the counterpart of SA, where quantum fluctuations drive the system toward the ground state when the quantum terms are reduced. QA is currently widely explored as a paradigm for quantum computing to solve optimization problems. Here we compare the scaling of the dynamics (with system size) of the fully-connected spin glass through QA versus SA.
Kibble-Zurek theory (KZ) stands out as the most robust theory of defect generation in the dynamics of phase transitions. KZ utilizes the structure of equilibrium states away from the transition point to estimate the excitations due to the transition using adiabatic and impulse approximations. Here we show, the actual nonequilibrium dynamics lead to a qualitatively different scenario from KZ, as far correlations between the defects (rather than their densities) are concerned. For a quantum Ising chain, we show, this gives rise to a Gaussian spatial decay in the domain wall (kinks) correlations, while KZ would predict an exponential fall. We propose a simple but general framework on top of KZ, based on the ``quantum coarsening'' dynamics of local correlators in the supposed impulse regime. We outline how our picture extends to generic interacting situations.
We investigate defects in the two-dimensional transverse-field Ising ferromagnet on periodic
L×L lattices after quantum annealing from high to vanishing field. With exact numerical solutions for
L≤6, we observe the expected critical Kibble-Zurek (KZ) time scale
∝Lz+1/ν (with
z=1 and
1/ν≈1.59) at the quantum phase transition. We also observe KZ scaling of the ground-state fidelity at the end of the process. The excitations evolve by coarsening dynamics of confined defects, with a time scale
∝L2, and interface fluctuations of system-spanning defects, with life time
∝L3. We build on analogies with classical simulated annealing, where we characterize system-spanning defects in detail and find differences in the dynamic scales of domain walls with winding numbers
W=(1,0)/(0,1) (horizontal/vertical) and
W=(1,1) (diagonal). They decay on time scales
∝L3 (which applies also to system-spanning domains in systems with open boundaries) and
∝L3.4, respectively, when imposed in the ordered phase. As a consequence of
L3.4 exceeding the classical KZ scale
Lz+1/ν=L3.17 the probability of
W=(1,1) domains in SA scales with the KZ exponent even in the final
T=0 state. In QA, also the
W=(1,0)/(0,1) domains are controlled by the KZ time scale
L2.59. The
L3 scale can nevertheless be detected in the excited states, using a method that we develop that should also be applicable in QA experiments.
We present here our study of the adiabatic quantum dynamics of a random Ising chain across its quantum critical point. The model investigated is an Ising chain in a transverse field with disorder present both in the exchange coupling and in the transverse field. The transverse field term is proportional to a function $\ensuremath{\Gamma}(t)$ which, as in the Kibble-Zurek mechanism, is linearly reduced to zero in time with a rate ${\ensuremath{\tau}}^{\ensuremath{-}1}$, $\ensuremath{\Gamma}(t)=\ensuremath{-}t∕\ensuremath{\tau}$, starting at $t=\ensuremath{-}\ensuremath{\infty}$ from the quantum disordered phase $(\ensuremath{\Gamma}=\ensuremath{\infty})$ and ending at
t=0 in the classical ferromagnetic phase $(\ensuremath{\Gamma}=0)$. We first analyze the distribution of the gaps, occurring at the critical point ${\ensuremath{\Gamma}}_{c}=1$, which are relevant for breaking the adiabaticity of the dynamics. We then present extensive numerical simulations for the residual energy
Eres and density of defects ${\ensuremath{\rho}}_{k}$ at the end of the annealing, as a function of the annealing inverse rate $\ensuremath{\tau}$. Both the average ${E}_{\mathrm{res}}(\ensuremath{\tau})$ and ${\ensuremath{\rho}}_{k}(\ensuremath{\tau})$ are found to behave logarithmically for large $\ensuremath{\tau}$, but with different exponents, $[{E}_{\mathrm{res}}(\ensuremath{\tau})∕L{]}_{\mathrm{av}}\ensuremath{\sim}1∕{\mathrm{ln}}^{\ensuremath{\zeta}}(\ensuremath{\tau})$ with $\ensuremath{\zeta}\ensuremath{\approx}3.4$, and $[{\ensuremath{\rho}}_{k}(\ensuremath{\tau}){]}_{\mathrm{av}}\ensuremath{\sim}1∕{\mathrm{ln}}^{2}(\ensuremath{\tau})$. We propose a mechanism for $1∕{\mathrm{ln}}^{2}\ensuremath{\tau}$ behavior of $[{\ensuremath{\rho}}_{k}{]}_{\mathrm{av}}$ based on the Landau-Zener tunneling theory and on a Fisher's-type real-space renormalization group analysis of the relevant gaps. The model proposed shows therefore a paradigmatic example of how an adiabatic quantum computation can become very slow when disorder is at play, even in the absence of any source of frustration.