Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The Journal of Chemical Physics

Quantum path minimization: An efficient method for global optimization

Pu Liu, B. J. Berne

Published Feb 10, 2003• 33 citations
Publisher

Abstract

A new unbiased global optimization approach is proposed, based on quantum staging path integral Monte Carlo sampling and local minimization of individual imaginary time slices. This algorithm uses the quantum tunneling effect to speed up the crossing of energy barriers. This method differs in important ways from previous work on quantum annealing and is able to find all the global minima of Lennard-Jones clusters of size up to N=100, except for N=76, 77, and 98. The comparison between this new algorithm and several other classes of algorithms is presented.

DOI
10.1063/1.1527919

Related papers

A renormalization approach to quantum thermal annealing

Yong‐ Han Lee, B. J. Berne

The details of an efficient global optimization approach, quantum thermal annealing with renormalization (QTAR) (Y. H. Lee and B. J. Berne, J. Phys. Chem. A, in press (2000)) are presented in this paper. This method is based on the application of the Migdal-Kadanoff method for decimating Trotter time slices in the staging and primitive algorithms for sampling path integrals using Monte Carlo methods. In a nutshell, one starts in a strong quantum regime where the number of Trotter beads representing each quantum particle and the value of Planck's constant are large, thereby allowing for efficient tunneling through the barriers of a rough energy landscape typical in the folding of proteins, and anneals the system methodically to the classical limit where the values of the aforementioned quantities are 1 and 0, respectively. Global optimization of the system is achieved through the iterative use of such quantum-to-classical annealing cycles. The QTAR algorithm applied to a highly frustrated BLN model protein with 46 residues more efficiently locates the global energy minimum than established methods like simulated annealing.

Annalen der Physik•Oct 1, 2000•5 citations

Quantum Monte Carlo simulations of tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate quantum adiabatic optimization algorithms during a quantum tunneling process. Specifically we look at symmetric cost functions defined over $n$ bits with a single potential barrier that a successful quantum adiabatic optimization algorithm will have to tunnel through. The height and width of this barrier depend on $n$, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.

arXiv:1509.02562•Physical Review A•Mar 4, 2016•29 citations

Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model

Roman Martoňák, Giuseppe E. Santoro, Erio Tosatti

Quantum annealing was recently found experimentally in a disordered spin-$\frac{1}{2}$ magnet to be more effective than its classical, thermal counterpart. We use the random two-dimensional Ising model as a test example and perform on it both classical and quantum (path-integral) Monte Carlo annealing. A systematic study of the dependence of the final residual energy on the annealing Monte Carlo time quantitatively demonstrates the superiority of quantum relative to classical annealing in this system. In order to determine the parameter regime for optimal efficiency of the quantum annealing procedure we explore a range of values of Trotter slice number P and temperature T. This identifies two different regimes of freezing with respect to efficiency of the algorithm, and leads to useful guidelines for the optimal choice of quantum annealing parameters.

Physical review. B, Condensed matter•Sep 13, 2002•144 citations

A renormalization approach to quantum thermal annealing

Yong‐ Han Lee, B. J. Berne

Abstract The details of an efficient global optimization approach, quantum thermal annealing with renormalization (QTAR) (Y. H. Lee and B. J. Berne, J. Phys. Chem. A, in press (2000)) are presented in this paper. This method is based on the application of the Migdal‐Kadanoff method for decimating Trotter time slices in the staging and primitive algorithms for sampling path integrals using Monte Carlo methods. In a nutshell, one starts in a strong quantum regime where the number of Trotter beads representing each quantum particle and the value of Planck's constant are large, thereby allowing for efficient tunneling through the barriers of a rough energy landscape typical in the folding of proteins, and anneals the system methodically to the classical limit where the values of the aforementioned quantities are 1 and 0, respectively. Global optimization of the system is achieved through the iterative use of such quantum‐to‐classical annealing cycles. The QTAR algorithm applied to a highly frustrated BLN model protein with 46 residues more efficiently locates the global energy minimum than established methods like simulated annealing.

Annalen der Physik•Sep 25, 2000•1 citation

Quantum annealing: A new method for minimizing multidimensional functions

A B Finnila, M A Gomez, C. Sebenik +2 more

Abstract Quantum Monte Carlo has found a new application far afield from the solution of the Schrodinger equation for many-body problems. In this paper the authors report a method for solving multidimensional optimization problems that is superior, in many cases, to other methods such as conjugate gradient methods, the simplex method, direction-set methods, genetic methods, and classical simulated annealing. The new approach, aptly titled “quantum annealing,” is closely related to classical annealing, in which a physical system such as a metal cluster is slowly cooled and finds its lowest-energy configuration as the temperature drops to zero. In classical annealing the system follows classical-mechanical dynamics as the temperature drops. In quantum annealing a collection of configurations evolves in the the same way as walkers undergoing diffusion and multiplication in diffusion QMC with the added feature of a slowly dropping value for Planck’s constant h. Classical annealing allows the escape from local minima with the aid of thermal fluctuations. Quantum annealing allows such escape by delocalization and tunneling. Since a QMC walker can multiply in number on entering a low-energy region, a single walker can populate an entire region.

•Jun 18, 2007•23 citations

Quantum Tunneling Parameter in Global Optimization

Teturo Itami

Quantum tunneling that helps particles escape from local minima has been applied in “quantum annealing” method to global optimization of nonlinear functions. To control size of kinetic energy of quantum particles, we form a “quantum tunneling parameter” QT≡m/HR2, where HR corresponds to a physical constant h, Planck's constant divided by 2π, that determines the lowest eigenvalue of quantum particles with mass m. Assumptions on profiles of the function V(x) around its minimum point x0, harmonic oscillator type and square well type, make us possible to write down analytical formulae of the kinetic energy K in terms of QT. The formulae tell that we can make quantum expectation value of particle coordinates x approximate to the minimum point x0 in QT→∞. For systems where we have almost degenerate eigenvalues, examination working with our QT, that x→x0 in QT→∞, is analytically shown also efficient. Similar results that x→x0 under QT→∞ are also obtained when we utilize random-walk quantum Monte Carlo method to represent tunneling phenomena according to conventional quantum annealing.

Transactions of the Society of Instrument and Control Engineers•Jan 1, 2010•1 citation
A new unbiased global optimization approach is proposed, based on quantum staging path integral Monte Carlo sampling and local minimization of individual imaginary time slices. This algorithm uses the quantum tunneling effect to speed up the crossing of energy barriers. This method differs in important ways from previous work on quantum annealing and is able to find all the global minima of Lennard-Jones clusters of size up to N=100, except for N=76, 77, and 98. The comparison between this new algorithm and several other classes of algorithms is presented.
The details of an efficient global optimization approach, quantum thermal annealing with renormalization (QTAR) (Y. H. Lee and B. J. Berne, J. Phys. Chem. A, in press (2000)) are presented in this paper. This method is based on the application of the Migdal-Kadanoff method for decimating Trotter time slices in the staging and primitive algorithms for sampling path integrals using Monte Carlo methods. In a nutshell, one starts in a strong quantum regime where the number of Trotter beads representing each quantum particle and the value of Planck's constant are large, thereby allowing for efficient tunneling through the barriers of a rough energy landscape typical in the folding of proteins, and anneals the system methodically to the classical limit where the values of the aforementioned quantities are 1 and 0, respectively. Global optimization of the system is achieved through the iterative use of such quantum-to-classical annealing cycles. The QTAR algorithm applied to a highly frustrated BLN model protein with 46 residues more efficiently locates the global energy minimum than established methods like simulated annealing.
We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate quantum adiabatic optimization algorithms during a quantum tunneling process. Specifically we look at symmetric cost functions defined over nnn bits with a single potential barrier that a successful quantum adiabatic optimization algorithm will have to tunnel through. The height and width of this barrier depend on nnn, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.
Quantum annealing was recently found experimentally in a disordered spin-12\frac{1}{2}21​ magnet to be more effective than its classical, thermal counterpart. We use the random two-dimensional Ising model as a test example and perform on it both classical and quantum (path-integral) Monte Carlo annealing. A systematic study of the dependence of the final residual energy on the annealing Monte Carlo time quantitatively demonstrates the superiority of quantum relative to classical annealing in this system. In order to determine the parameter regime for optimal efficiency of the quantum annealing procedure we explore a range of values of Trotter slice number P and temperature T. This identifies two different regimes of freezing with respect to efficiency of the algorithm, and leads to useful guidelines for the optimal choice of quantum annealing parameters.
Abstract The details of an efficient global optimization approach, quantum thermal annealing with renormalization (QTAR) (Y. H. Lee and B. J. Berne, J. Phys. Chem. A, in press (2000)) are presented in this paper. This method is based on the application of the Migdal‐Kadanoff method for decimating Trotter time slices in the staging and primitive algorithms for sampling path integrals using Monte Carlo methods. In a nutshell, one starts in a strong quantum regime where the number of Trotter beads representing each quantum particle and the value of Planck's constant are large, thereby allowing for efficient tunneling through the barriers of a rough energy landscape typical in the folding of proteins, and anneals the system methodically to the classical limit where the values of the aforementioned quantities are 1 and 0, respectively. Global optimization of the system is achieved through the iterative use of such quantum‐to‐classical annealing cycles. The QTAR algorithm applied to a highly frustrated BLN model protein with 46 residues more efficiently locates the global energy minimum than established methods like simulated annealing.
Abstract Quantum Monte Carlo has found a new application far afield from the solution of the Schrodinger equation for many-body problems. In this paper the authors report a method for solving multidimensional optimization problems that is superior, in many cases, to other methods such as conjugate gradient methods, the simplex method, direction-set methods, genetic methods, and classical simulated annealing. The new approach, aptly titled “quantum annealing,” is closely related to classical annealing, in which a physical system such as a metal cluster is slowly cooled and finds its lowest-energy configuration as the temperature drops to zero. In classical annealing the system follows classical-mechanical dynamics as the temperature drops. In quantum annealing a collection of configurations evolves in the the same way as walkers undergoing diffusion and multiplication in diffusion QMC with the added feature of a slowly dropping value for Planck’s constant h. Classical annealing allows the escape from local minima with the aid of thermal fluctuations. Quantum annealing allows such escape by delocalization and tunneling. Since a QMC walker can multiply in number on entering a low-energy region, a single walker can populate an entire region.
Quantum tunneling that helps particles escape from local minima has been applied in “quantum annealing” method to global optimization of nonlinear functions. To control size of kinetic energy of quantum particles, we form a “quantum tunneling parameter” QT≡m/HR2, where HR corresponds to a physical constant h, Planck's constant divided by 2π, that determines the lowest eigenvalue of quantum particles with mass m. Assumptions on profiles of the function V(x) around its minimum point x0, harmonic oscillator type and square well type, make us possible to write down analytical formulae of the kinetic energy K in terms of QT. The formulae tell that we can make quantum expectation value of particle coordinates x approximate to the minimum point x0 in QT→∞. For systems where we have almost degenerate eigenvalues, examination working with our QT, that x→x0 in QT→∞, is analytically shown also efficient. Similar results that x→x0 under QT→∞ are also obtained when we utilize random-walk quantum Monte Carlo method to represent tunneling phenomena according to conventional quantum annealing.