Both reduction in computational load and setting parameters with ease are necessary in calculation of global optimization. For this we propose a new quantum mechanical method of the problem. Global optimization is achieved by a quantum particle with energy dissipation due to frictional force. Canonical quantization is applied to a system that consists of one mass point under friction proportional to its velocity. Realistic motion of a particle is abstracted from a resultant quantum system according to a causal interpretation. By simulation of the quantum particle motion under potential functions V(x) with local minima and one global minimum, it is clarified that the particle with its initial position at the local minimum at rest necessarily arrives at the global minimum. Only one particle is needed in the new algorithm. When we clarify mathematical structure of our algorithm, difficulties found in quantum annealing or conventional method for global optimization will thereby be solved in the new method.
Both reduction in computational load and setting parameters with ease are necessary in calculation of global optimization. For this we propose a new quantum mechanical method of the problem. Global optimization is achieved by a quantum particle with energy dissipation due to frictional force. Canonical quantization is applied to a system that consists of one mass point under friction proportional to its velocity. Realistic motion of a particle is abstracted from a resultant quantum system according to a causal interpretation. By simulation of the quantum particle motion under potential functions V(x) with local minima and one global minimum, it is clarified that the particle with its initial position at the local minimum at rest necessarily arrives at the global minimum. Only one particle is needed in the new algorithm. When we clarify mathematical structure of our algorithm, difficulties found in quantum annealing or conventional method for global optimization will thereby be solved in the new method.
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.
This work presents a quantum mechanical framework for analyzing quantization-based optimization algorithms. The sampling process of the quantization-based search is modeled as a gradient-flow dissipative system, leading to a Hamilton-Jacobi-Bellman (HJB) representation. Through a suitable transformation of the objective function, this formulation yields the Schroedinger equation, which reveals that quantum tunneling enables escape from local minima and guarantees access to the global optimum. By establishing the connection to the Fokker-Planck equation, the framework provides a thermodynamic interpretation of global convergence. Such an analysis between the thermodynamic and the quantum dynamic methodology unifies combinatorial and continuous optimization, and extends naturally to machine learning tasks such as image classification. Numerical experiments demonstrate that quantization-based optimization consistently outperforms conventional algorithms across both combinatorial problems and nonconvex continuous functions.
The protocol of quantum annealing is applied to an optimization problem with a one-dimensional continuous degree of freedom, a variant of the problem proposed by Shinomoto and Kabashima. The energy landscape has a number of local minima, and the classical approach of simulated annealing is predicted to have a logarithmically slow convergence to the global minimum. We show by extensive numerical analyses that quantum annealing yields a power-law convergence, thus an exponential improvement over simulated annealing. The power is larger, and thus the convergence is faster, than a prediction by an existing phenomenological theory for this problem. Performance of simulated annealing is shown to be enhanced by introducing quasiglobal searches across energy barriers, leading to a power-law convergence but with a smaller power than in the quantum case and thus a slower convergence classically even with quasiglobal search processes. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum by a meticulous choice of annealing schedule. This latter result explicitly contrasts the role of tunneling in quantum annealing against the classical counterpart of stochastic optimization by simulated annealing.
High Resolution Image Download MS PowerPoint Slide A new concept of the molecular structure optimization method based on quantum dynamics computations is presented. Nuclei are treated as quantum mechanical particles, as are electrons, and the many-body wave function of the system is optimized by the imaginary time evolution method. The numerical demonstrations with a two-dimensional H 2 + system and a H–C–N system exemplify two possible advantages of our proposed method: (1) the optimized nuclear positions can be specified with a small number of observations (quantum measurements) and (2) the global minimum structure of nuclei can be obtained without starting from any sophisticated initial structure and getting stuck in the local minima. This method is considered to be suitable for quantum computers, the development of which will realize its application as a powerful method.
In this work we present a novel method for global optimization, exploiting the mathematics of quantum mechanics, and in particular the tunnelling phenomenon. We consider a quantum mechanical system with a single particle in a potential specified by the cost function of our optimization problem. We assume the groundstate of the system is localised to the global minimum of the potential function, a condition which can be assured by choosing the particle mass sufficiently large. We then approximate this groundstate using a variational approach to optimise an expansion in terms of a truncated basis set of harmonic oscillator wavefunctions. We show how to encode integer factoring and travelling salesman problems in terms of finding the global minimum of a quartic polynomial cost function. We demonstrate our quantum algorithm on oneand two-dimensional toy problems, and apply it to factoring biprimes with 10 bits. Introduction The state of the art in global optimization for general problems is simulated annealing and its derivatives. The algorithm can be viewed in the physical context of a classical thermal system. This inspires the novel approach presented here, in which we draw upon intuition from non-classical physical systems which obey quantum mechanics (QM), and in particular exhibit the phenomenon of quantum tunnelling. In QM, a potential function V (x) describes the energy terrain experienced by a particle, which may contain multiple minima separated by barriers. Combined with a term describing the kinetic energy of the particle, it defines the Hamiltonian operator: Ĥ = − 2 2m ∇2 + V (1) QM captures all available information on the state of the particle in a (complex) wave function ψ(x). For instance, |ψ(x)|2 is the probability distribution over the position x of the particle. To obtain ψ(x) one solves the eigenvalue problem Ĥψ = Eψ (2) known as the Schroedinger equation, where E is the energy. The solution is a set of wave functions termed eigenstates, and a matching set of energies. The eigenstate with the lowest energy is the ground state, ψ. By choosing the particle’s mass sufficiently large, the probability density associated with the ground state wave function becomes localized to the global minimum of the potential. Hence, a given optimization problem involving the minimization of a cost function can be restated as the problem of finding the ground state of the QM system with a potential specified by that cost function. In particular, computationally ‘hard’ integer problems, including factoring [1] and the travelling salesman problem, can be cast as QM problems involving a quartic polynomial potential, [3]. However, solving the Schroedinger equation exactly for these potentials is generally an analytically intractable problem. In our approach we approximate the groundstate of such a system using a method based on perturbation theory.
Abstract We present a quantum algorithm for finding the minimum of a function based on multistep quantum computation, and apply the algorithm for solving optimization problems with continuous variables. We construct the state space of the problem by discretizing the variables of the problem, and divide the state space according to the function values of the vectors of the state space. By comparing the function values of the vectors with a series of threshold values in decreasing order, we construct a sequence of Hamiltonians where the search space of a Hamiltonian is nested in that of the previous one. By applying a multistep quantum computation process for finding the ground state of the last Hamiltonian, the optimal vector of the state space of the problem is located in a small search space and can be determined efficiently. One of the most difficult problems in optimization algorithms is that a trial vector is trapped in a deep local minimum while the global minimum is missed, this problem can be alleviated in our algorithm and the run time is proportional to the number of the steps of the algorithm, provided that the reduction rate of the search spaces is polynomial large. We discuss the implementation of the algorithm and test the algorithm for some test functions.