content_image/413764.jpg content_image/413763.jpg
## Abstract 

$^{a}$Department of Systems Science, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan 

$^{b}$Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan 

# Quantum Annealing with Jarzynski Equality 

Masayuki Ohzeki$^{a}$, Hidetoshi Nishimori b 

We show a practical application of an well-known nonequilibrium relation, the Jarzynski equality, in quantum com- putation. Its implementation may open a way to solve combinatorial optimization problems, minimization of a real single-valued function, cost function, with many arguments. It has been disclosed that the ordinary quantum com- putational algorithm to solve a kind of hard optimization problems, has a bottleneck that its computational time is restricted to be extremely slow without relevant errors. However, by our novel strategy shown in the present study, we might overcome such a di ffi culty. 

Keywords: Jarzynski equality, quantum annealing, optimization problem 

## 1. Introduction: Quantum Annealing 

To reduce power loss in electric circuits, we have to minimize the circuit length. This kind of problems are formulated into a more generic task to minimize or max- imize a real single-valued function of multivariables, cost function. This is called optimization problem [1]. To solve these problems is one of the most important tasks and has broad applications in science and engi- neering. Well-known examples with discrete variables are satisfiability problems, exact cover, maximum cut, Hamilton graph, and traveling salesman problem. 

Most of the above exemplified cases are mapped into a generic problem to find the ground state for a kind of systems seen in statistical physics, spin glasses. Its Hamiltonian is denoted as H$_{0}$ in the present study. One of the generic algorithms to solve optimization problems in reasonable time by exploiting resources in physics is quantum annealing (QA) [2, 3, 4]. In QA, we introduce artificial degrees of freedom of quantum na- ture, noncommutative operators in order to induce quan- tum fluctuations. 

where f ( t ) is assumed to be a monotonically increasing function satisfying f (0) = 0 and f ( τ ) = 1. The anneal- ing time is denoted by τ . The transeverse-field operator for spin glasses is often used as a quantum fluctuation, H$_{1}$ = − ∑ i σ x $_{i}$. The quantum annealing starts from the ground state of H$_{1}$ , a uniform linear combination of all 

Preprint submitted to Computer Physics Communications 

<img src='content_image/413764.jpg'>

spin configurations on the basis of σ z $_{i}$. The quantum system is driven by gradually decreasing the quantum fluctuation according to f ( t ). The adiabatic theorem guarantees that we can reach a nontrivial ground state of H$_{0}$ after su ffi ciently slow quantum sweep τ$_{c}$ ∼ 1 / Δ $^{2}$, where Δ is the energy gap of the instantaneous quantum system (1) [5]. If we consider the cases in which the quantum system as in Eq. (1) has a minimum energy gap vanishing as Δ ∼ $^{exp(}$− α N ) for increasing the sys- tem size N , QA does not work well in reasonable time [6, 7]. 

## 2. Jarzynski Equality 

To overcome the above di ffi culty in hard optimization problems, we propose a novel method in conjunction with a theoretical piece from non-equilibrium statisti- cal physics, the Jarzynski equality (JE), in the present study [8, 9]. The Jarzynski equality is written by an well-known expression as, 

where the angular brackets denote the average over all realizations in a predetermined process starting from an initial equilibrium state and W is the work done during the process. The partition functions for the initial and fi- nal Hamiltonians are written as Z$_{0}$ ( β ) and Z$_{τ}$ ( β ) with in- verse temperature β , respectively. We here shortly recall the formulation of JE for the classical system on a heat 

<img src='content_image/413763.jpg'>

November 18, 2018 

