Quantum Annealing Algorithm
Jump to navigation
Jump to search
A Quantum Annealing Algorithm is a numerical optimization algorithm that uses quantum fluctuations.
- …
- Counter-Example(s):
- See: Global Minimum, Objective Function, Combinatorial Optimization, Local Minimum, Ground State, Spin Glass, Schrödinger Equation, Ising Model.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/quantum_annealing Retrieved:2015-2-1.
- Quantum annealing (QA) is a general method for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. It was formulated in its present form in [1] though a preliminary proposal in a different form had appeared in [2] . Quantum annealing is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground state of a spin glass employing quantum tunneling [3] (across the barriers separating the global minimum from the local minima or spin configurations). Quantum annealing starts from a quantum-mechanical superposition of all possible states (candidate states) with equal weights. Then the system evolves following the time-dependent Schrödinger equation, a natural quantum-mechanical evolution of physical systems. The amplitudes of all candidate states keep changing, realizing a quantum parallelism, according to the time-dependent strength of the transverse field, which causes quantum tunneling between states. If the rate of change of the transverse-field is slow enough, the system stays close to the ground state of the instantaneous Hamiltonian, i.e., adiabatic quantum computation. [4] The transverse field is finally switched off, and the system is expected to have reached the ground state of the classical Ising model that corresponds to the solution to the original optimization problem. An experimental demonstration of the success of quantum annealing for random magnets was reported immediately after the initial theoretical proposal. [5]
- ↑ T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model" Phys. Rev. E 58, 5355 (1998)
- ↑ A. B. Finilla, M. A. Gomez, C. Sebenik and D. J. Doll, "Quantum annealing: A new method for minimizing multidimensional functions" Chem. Phys. Lett. 219, 343 (1994)
- ↑ P. Ray, B. K. Chakrabarti and A. Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations", Phys. Rev. B 39 11828 (1989)
- ↑ E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Ludgren and D. Preda, "A Quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem" Science 292, 472 (2001)
- ↑ J. Brooke, D. Bitko, T. F. Rosenbaum and G. Aeppli, "Quantum annealing of a disordered magnet", Science 284 779 (1999)