Lecture Notes in Physics Editorial Board R. Beig, Wien, Austria W. Beiglböck, Heidelberg, Germany W. Domcke, Garching, Germany B.
Frisch, Nice, France P. Hänggi, Augsburg, Germany G. Hasinger, Garching, Germany K. Hepp, Zürich, Switzerland W.
Hillebrandt, Garching, Germany D. Imboden, Zürich, Switzerland R. Jaffe, Cambridge, MA, USA R. Lipowsky, Golm, Germany H.
Löhneysen, Karlsruhe, Germany I. Ojima, Kyoto, Japan D. Sornette, Nice, France, and Los Angeles, CA, USA S. Theisen, Golm, Germany W.
Weise, Garching, Germany J. Wess, München, Germany J. Zittartz, Köln, Germany The Lecture Notes in Physics The series Lecture Notes in Physics (LNP), founded in 1969, reports new developments in physics research and teaching – quickly and informally, but with a high quality and the explicit aim to summarize and communicate current knowledge in an accessible way. Books published in this series are conceived as bridging material between advanced grad- uate textbooks and the forefront of research to serve the following purposes: • to be a compact and modern up-to-date source of reference on a well-defined topic; • to serve as an accessible introduction to the field to postgraduate students and nonspe- cialist researchers from related areas; • to be a source of advanced teaching material for specialized seminars, courses and schools.
Both monographs and multi-author volumes will be considered for publication. Edited volumes should, however, consist of a very limited number of contributions only. Pro- ceedings will not be considered for LNP. Volumes published in LNP are disseminated both in print and in electronic formats, the electronic archive is available at springerlink.
The series content is indexed, abstracted and referenced by many abstracting and information services, bibliographic networks, subscription agencies, library networks, and consortia. Proposals should be sent to a member of the Editorial Board, or directly to the managing editor at Springer: Dr. Christian Caron Springer Heidelberg Physics Editorial Department I Tiergartenstrasse 17 69121 Heidelberg/Germany christian.caron@springer-sbm.com Arnab Das Bikas K.) Quantum Annealing and Related Optimization Methods ABC www.com Editors Arnab Das Bikas K. Chakrabarti Saha Institute of Nuclear Physics Centre for Applied Mathematics and Computational Science Bidhannagar 1/AF 700064 Kolkata, India E-mail: arnab.in Arnab Das, Bikas K.
Chakrabarti, Quantum Annealing and Related Optimization Methods, Lect.1007/b135699 Library of Congress Control Number: 2005930442 ISSN 0075-8450 ISBN-10 3-540-27987-3 Springer Berlin Heidelberg New York ISBN-13 978-3-540-27987-7 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable for prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media springeronline.com c Springer-Verlag Berlin Heidelberg 2005 Printed in The Netherlands The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: by the author using a Springer LATEX macro package Printed on acid-free paper SPIN: 11526216 54/TechBooks 543210 www.com Preface Quantum annealing employs quantum fluctuations in frustrated systems or networks to anneal the system down to its ground state or to its minimum cost state, tuning the quantum fluctuation down to zero eventually. Often this can be more effective in multivariable optimization problems, over classical annealing performed utilizing tunable thermal fluctuations.
The effectiveness comes from the fact that unlike in classical annealing, where the system scales the individual barrier heights by utilizing thermal fluctuations, in quantum annealing, fluctuations can help tunneling through these (even infinite but narrow) barriers. Apart from the recent theoretical demonstrations, this has been demonstrated experimentally. In this book, we discuss the problems and the recent achievements in de- tail. This book grew out of an international workshop on quantum annealing, held in March 2004 in Kolkata under the auspices of the Centre for Applied Mathematics and Computational Science, Saha Institute of Nuclear Physics, India.
With contributions from all the leading scientists/groups involved in its development so far, this first ever book on quantum annealing is expected to become an invaluable primer and also a guidebook for all researchers in this important field. The book is divided into three parts. In the first part, tutorial materials are introduced. Das introduce the transverse Ising model and quantum Monte Carlo techniques, following which most of the theoretical studies on quantum annealing have been made so far.
The decomposition of exponential operators used for the Suzuki–Trotter classical mapping in quantum Monte Carlo techniques is discussed in detail by N. Latest quantum Monte Carlo and other numerical investigations and developments in quantum spin glasses are reviewed by H. The question of ergodicity and consequent replica symmetry restoration in quantum spin glasses and ferroelectric glasses, experimental indications included, is reviewed by J. Fisher reviewes the theory of quantum systems coupled to noisy condensed-phase environments and describes how to tailor response functions so as to optimize the coherent evolution of the system.com VI Preface In the next part, quantum annealing techniques are developed and em- ployed.
Rosenbaum describe the experimental realization where the ground state of a glassy sample can be reached faster by tun- ing the external field (inducing changes in the tunneling field) rather than by tuning the temperature. Tosatti discuss the effectiveness of quantum annealing algorithms in solving hard computational problems such as the traveling salesman problem or a satisfiability problem and also in solving some very simple illustrative problems for a basic comparative study with thermal annealing. Okada investigate the prospect of adiabatic quantum annealing us- ing real-time quantum evolution. Chakrabarti discuss the application of quantum annealing in a kinetically constrained system and in an infinite range quantum spin glass.
Inoue reviewes the applicability of quantum annealing techniques in restoring informations and images after transportation through corrupted channels. In the last part some of the classical optimization studies are reviewed and discussed. Rieger reviewes the classical algorithms for solving various combinatorial optimization problems. Das discuss classical annealing in the context of the ANNNI model and make a comparative study with quantum annealing in the same system.
Martin-Mayor reviewes the problem of annealing and relaxation in the context of classical glasses and supercooled liquids. With these firsthand and detailed reviews by the poineers in this field, this book on an analog version of quantum computation, we hope, will immediately inspire further research and development. We are extremely grateful to all the contributors for excellent support and cooperation. We are also grateful to J.
Zittartz for his encouragement regarding the publication of this lecture note volume. Kolkata Arnab Das May, 2005 Bikas K.com Contents Part I Tutorial: Introductory Material Transverse Ising Model, Glass and Quantum Annealing Bikas K. Chakrabarti, Arnab Das. 3 2 Transverse Ising Model (TIM).
4 3 Mean Field Theory (MFT). 5 4 Dynamic Mode-Softening Picture. 8 5 Suzuki-Trotter Formalism. 9 6 Classical Spin Glasses: A Summary.
12 7 Quantum Spin Glasses .2 Replica Symmetry in Quantum Spin Glasses .1 Multivariable Optimization and Simulated Annealing .2 Ergodicity of Quantum Spin Glasses and Quantum Annealing .3 Quantum Annealing in Kinetically Constrained Systems. 24 9 Summary and Discussions. 35 Finding Exponential Product Formulas of Higher Orders Naomichi Hatano, Masuo Suzuki. 37 2 Why Do We Need the Exponential Product Formula?.
38 3 Why is the Exponential Product Formula a Good Approximant? .1 Example: Spin Precession .2 Example: Symplectic Integrator .com VIII Contents 5 Time-Ordered Exponential. 47 6 Quantum Analysis – Towards the Construction of General Decompositions .1 Operator Differential .3 Differential of Exponential Operators .4 Example: Baker-Campbell-Hausdorff Formula .5 Example: Ruth’s Formula .6 Example: Perturbational Composition. 67 Quantum Spin Glasses Heiko Rieger. 69 2 Random Transverse Ising Models in Finite Dimensions .1 Random Transverse Ising Chain and the Infinite Randomness Fixed Point .2 Diluted Ising Ferromagnet in a Transverse Field .3 Higher Dimensional Random Bond Ferromagnets in a Transverse Field .4 Quantum Ising Spin Glass in a Transverse Field.
78 3 Mean-Field Theory for Quantum Ising Spin Glasses .1 Quantum Phase Transition. 86 4 Heisenberg Quantum Spin Glasses .2 Mean-Field Model. 97 Ergodicity, Replica Symmetry, Spin Glass and Quantum Phase Transition Jong-Jean Kim. 101 2 Overview of Spin Glass.
116 6 Quantum Phase Transition. 121 7 Quantum Spin Glass .com Contents IX Decoherence and Quantum Couplings in a Noisy Environment Andrew Fisher. 131 1 Qubits Coupled to a Bath .3 The Lindblad Equation .4 The Markovian Weak-Coupling Limit .5 Good Qubits – the Rotating Wave Approximation .6 The Quantum Optical Master Equation .7 Bad Qubits–Quantum Brownian Motion .8 Simplifications for a Harmonic Environment .9 Brownian Motion with Ohmic Dissipation .10 The Fluctuation-Dissipation Theorem and the Link Between Coherent and Incoherent Evolution .11 Irreducible Decoherence and Decoherence-Free Subspaces. 151 2 Scaling Transformations for Partially Coherent Dynamics .1 Scaling for Thermodynamic Properties .2 Scaling the Liouvillian.
152 3 Quantum Gates via Optical Excitation .1 Advantages of Localised States .2 The UCL Project. 154 Part II Quantum Annealing: Basics and Applications Experiments on Quantum Annealing Gabriel Aeppli, Thomas F. 159 2 System with a Complex Free Energy Surface and Tuneable Quantum Fluctuations. 160 3 Demonstration of Domain Wall Tunnelling as the Dominant Mechanism for Low Temperature Magnetic Relaxation.
163 4 Comparing Quantum and Thermal ‘Computations’. 169 Deterministic and Stochastic Quantum Annealing Approaches Demian Battaglia, Lorenzo Stella, Osvaldo Zagordi, Giuseppe E. Santoro and Erio Tosatti .com X Contents 2 Deterministic Approaches on the Continuum .1 The Simplest Barrier: A Double-Well Potential .2 Other Simple One-Dimensional Potentials with Many Minima. 181 3 Role of Disorder, and Landau-Zener Tunneling.
183 4 Path Integral Monte Carlo Quantum Annealing .1 Path Integral Monte Carlo: Introduction .2 PIMC-QA Applied to Combinatorial Optimization Problems .3 PIMC-QA and 3-SAT: Lessons from a Hard Case .4 PIMC-QA of a Double-Well: Lessons from a Simple Case. 199 5 Beyond Naive Local Search .1 Focusing in 3-SAT and GFMC Quantum Annealing .2 Message-Passing Optimization. 202 6 Summary and Conclusions. 204 Simulated Quantum Annealing by the Real-time Evolution Sei Suzuki, Masato Okada.
207 2 Formulation and Mechanism of Quantum Annealing .1 Formulation of Quantum Annealing .2 Adiabatic Evolution of Quantum States .1 Simulations for Small-Sized Problems. 229 4 A method of Simulation for Large-Sized Problems .1 Real-Time Evolution by Means of DMRG .2 Results of Simulation. 237 Quantum Annealing of a ±J Spin Glass and a Kinetically Constrained System Arnab Das, Bikas K. 239 2 Quantum Annealing of ±J Ising Spin Glass at Infinite Dimension .2 The Zero Temperature Quantum Monte Carlo Method Used .3 Results and Discussions.
247 3 Quantum Annealing in a Kinetically Constrained System .com Contents XI 3.2 Simulation and Results .3 Summary and Discussion. 256 Quantum Spin Glasses Quantum Annealing, and Probabilistic Information Processing Jun-Ichi Inoue. 259 2 Bayesian Statistics and Information Processing .1 General Definition of the Model System .2 MAP Estimation and Simulated Annealing .3 MPM Estimation and a Link to Statistical Mechanics .4 The Priors and Corresponding Spin Systems. 265 3 Quantum Version of the Model.
266 4 Analysis of the Infinite Range Model .2 Image Restoration at Finite Temperature .3 Image Restoration Driven by Pure Quantum Fluctuation .4 Error-Correcting Codes .5 Analysis for Finite p .6 Phase Diagrams for p → ∞ and Replica Symmetry Breaking. 284 5 Quantum Markov Chain Monte Carlo Simulation .1 Quantum Markov Chain Monte Carlo Method .2 Quantum Annealing and Simulated Annealing .3 Application to Image Restoration. 296 Part III Other Optimizations Combinatorial Optimization and the Physics of Disordered Systems Heiko Rieger. 301 2 Polymers in a Disordered Environment and Dijkstras Algorithm .