Simulated quantum annealing based on the path-integral Monte Carlo is one of the most common tools to simulate quantum annealing on classical hardware. Nevertheless, it is in principle highly nontrivial whether or not this classical algorithm can correctly reproduce the quantum dynamics of quantum annealing, particularly in the diabatic regime. We study this problem numerically through the generalized Kibble-Zurek mechanism of defect distribution in the simplest ferromagnetic one-dimensional transverse-field Ising model with and without coupling to the environment. We find that, in the absence of coupling to the environment, simulated quantum annealing correctly describes the annealing-time dependence of the average number of defects, but a detailed analysis of the defect distribution shows clear deviations from the theoretical prediction. When the system is open (coupled to the environment), the average number of defects does not follow the theoretical prediction but is qualitatively compatible with the numerical result by the infinite-time-evolving block decimation combined with the quasiadiabatic propagator path integral, which is valid in a very-short-time region. The distribution of defects in the open system turns out to be not far from the theoretical prediction. It is surprising that the classical stochastic dynamics of simulated quantum annealing ostensibly reproduces some aspects of the quantum dynamics. However, a serious problem is that it is hard to predict for which physical quantities in which system it is reliable. Those results suggest the necessity to exert a good amount of caution in using simulated quantum annealing to study the detailed quantitative aspects of the dynamics of quantum annealing.
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.
We study quantum annealing in the quantum Ising model coupled to a thermal environment. When the speed of quantum annealing is sufficiently slow, the system evolves following the instantaneous thermal equilibrium. This quasistatic and isothermal evolution, however, fails near the end of annealing because the relaxation time grows infinitely, therefore yielding excess energy from the thermal equilibrium. We develop a phenomenological theory based on this picture and derive a scaling relation of the excess energy after annealing. The theoretical results are numerically confirmed using a novel non-Markovian method that we recently proposed based on a path-integral representation of the reduced density matrix and the infinite time evolving block decimation. In addition, we discuss crossovers from weak to strong coupling as well as from the adiabatic to quasistatic regime, and propose experiments on the D-Wave quantum annealer.
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.
The quantum dynamics of many-qubit systems is an outstanding problem that has recently driven significant advances in both numerical methods and programmable quantum processing units. In this work, we employ a comprehensive toolbox of state-of-the-art numerical approaches to classically simulate the dynamics of the two-dimensional transverse field Ising model. Our methods include three different tensor network techniques -- matrix product states, tree-tensor networks, and two-dimensional tensor-networks under the belief propagation approximation -- as well as time-dependent variational Monte Carlo with Neural Quantum States. We focus on two paradigmatic dynamical protocols: (i) quantum annealing through a critical point and (ii) post-quench dynamics. Our extensive results show the quantitative predictions of various state-of-the-art numerical methods providing a benchmark for future numerical investigations and experimental studies with the aim to push the limitations on classical and QPUs. In particular, our work connects classical simulability to different regimes associated with quantum dynamics in Rydberg arrays - namely, quasi-adiabatic dynamics, the Kibble-Zurek mechanism, and quantum quenches.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
We study the statistics of the kink number generated by quantum annealing in a one-dimensional transverse Ising model coupled to a bosonic thermal bath. Using the freezing ansatz for quantum annealing in the thermal environment, we show the relation between the ratio of the second to the first cumulant of the kink number distribution and the average kink density. The theoretical result is confirmed thoroughly by numerical simulation using the non-Markovian infinite time-evolving block decimation which we proposed recently. The simulation using D-Wave's quantum annealer is also discussed. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.