Quantum annealing
This article may be too technical for most readers to understand.(January 2022) |
Quantum annealing (QA) is an optimization process for finding the
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 or essentially tunneling through peaks. If the rate of change of the transverse field is slow enough, the system stays close to the ground state of the instantaneous Hamiltonian (also see adiabatic quantum computation).[6] If the rate of change of the transverse field is accelerated, the system may leave the ground state temporarily but produce a higher likelihood of concluding in the ground state of the final problem Hamiltonian, i.e., diabatic quantum computation.[7][8] 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.[9] Quantum annealing has also been proven to provide a fast Grover oracle for the square-root speedup in solving many NP-complete problems.[10]
Comparison to Simulated Annealing
Quantum annealing can be compared to simulated annealing, whose "temperature" parameter plays a similar role to QA's tunneling field strength. In simulated annealing, the temperature determines the probability of moving to a state of higher "energy" from a single current state. In quantum annealing, the strength of transverse field determines the quantum-mechanical probability to change the amplitudes of all states in parallel. Analytical[11] and numerical[12] evidence suggests that quantum annealing outperforms simulated annealing under certain conditions (see[13] for a careful analysis, and,[14] for a fully solvable model of quantum annealing to arbitrary target Hamiltonian and comparison of different computation approaches).
Quantum mechanics: analogy and advantage
The tunneling field is basically a kinetic energy term that does not commute with the classical potential energy part of the original glass. The whole process can be simulated in a computer using quantum Monte Carlo (or other stochastic technique), and thus obtain a heuristic algorithm for finding the ground state of the classical glass.
In the case of annealing a purely mathematical objective function, one may consider the variables in the problem to be classical degrees of freedom, and the cost functions to be the potential energy function (classical Hamiltonian). Then a suitable term consisting of non-commuting variable(s) (i.e. variables that have non-zero commutator with the variables of the original mathematical problem) has to be introduced artificially in the Hamiltonian to play the role of the tunneling field (kinetic part). Then one may carry out the simulation with the quantum Hamiltonian thus constructed (the original function + non-commuting part) just as described above. Here, there is a choice in selecting the non-commuting term and the efficiency of annealing may depend on that.
It has been demonstrated experimentally as well as theoretically, that quantum annealing can indeed outperform thermal annealing (simulated annealing) in certain cases, especially where the potential energy (cost) landscape consists of very high but thin barriers surrounding shallow local minima.[15] Since thermal transition probabilities (proportional to , with the temperature and the Boltzmann constant) depend only on the height of the barriers, for very high barriers, it is extremely difficult for thermal fluctuations to get the system out from such local minima. However, as argued earlier in 1989 by Ray, Chakrabarti & Chakrabarti,[1] the quantum tunneling probability through the same barrier (considered in isolation) depends not only on the height of the barrier, but also on its width and is approximately given by , where is the tunneling field.[16] This additional handle through the width , in presence of quantum tunneling, can be of major help: If the barriers are thin enough (i.e. ), quantum fluctuations can surely bring the system out of the shallow local minima. For an -spin glass, the barrier height becomes of order . For constant value of one gets proportional to for the annealing time (instead of proportional to for thermal annealing), while can even become -independent for cases where decreases as .[17][18]
It is speculated that in a
Timeline of ideas related to quantum annealing in Ising spin glasses:
- 1989 Idea was presented that quantum fluctuations could help explore rugged energy landscapes of the classical Ising spin glasses by escaping from local minima (having tall but thin barriers) using tunneling;[1]
- 1998 Formulation of quantum annealing and numerical test demonstrating its advantages in Ising glass systems;[4]
- 1999 First experimental demonstration of quantum annealing in LiHoYF Ising glass magnets;[21]
- 2011 Superconducting-circuit quantum annealing machine built and marketed by D-Wave Systems.[22]
D-Wave implementations
In 2011, D-Wave Systems announced the first commercial quantum annealer on the market by the name D-Wave One and published a paper in Nature on its performance.[22] The company claims this system uses a 128 qubit processor chipset.[23] On May 25, 2011, D-Wave announced that Lockheed Martin Corporation entered into an agreement to purchase a D-Wave One system.[24] On October 28, 2011 USC's Information Sciences Institute took delivery of Lockheed's D-Wave One.
In May 2013 it was announced that a consortium of
In June 2014, D-Wave announced a new quantum applications ecosystem with computational finance firm
With demonstrations of entanglement published,
There are many open questions regarding quantum speedup. The ETH reference in the previous section is just for one class of benchmark problems. Potentially there may be other classes of problems where quantum speedup might occur. Researchers at Google, LANL, USC, Texas A&M, and D-Wave are working to find such problem classes.[34]
In December 2015, Google announced that the
D-Wave's architecture differs from traditional quantum computers. It is not known to be polynomially equivalent to a
"A cross-disciplinary introduction to quantum annealing-based algorithms" [37] presents an introduction to combinatorial optimization (NP-hard) problems, the general structure of quantum annealing-based algorithms and two examples of this kind of algorithms for solving instances of the max-SAT and Minimum Multicut problems, together with an overview of the quantum annealing systems manufactured by D-Wave Systems. Hybrid quantum-classic algorithms for large-scale discrete-continuous optimization problems were reported to illustrate the quantum advantage.[38][39]
References
- ^ PMID 9948016.
- ^ Apolloni, Bruno; Cesa-Bianchi, Nicolo; De Falco, Diego (July 1988). "A numerical implementation of quantum annealing". Stochastic Processes, Physics and Geometry, Proceedings of the Ascona-Locarno Conference.
- .
- ^ S2CID 36114913. Archived from the originalon 2013-08-11.
- S2CID 97302385.
- S2CID 10132718.
- ].
- arXiv:1505.01249 [quant-ph].
- S2CID 37564720.
- S2CID 258236417.
- S2CID 13992889.
- S2CID 116931586.
- PMID 25765071.
- S2CID 248389790.
- ^ "Local Maxima and Minima, and, Absolute Maxima and Minima". Mathonline.
- S2CID 16466621. Archived from the originalon 2014-01-13.
- S2CID 118525494.
- S2CID 14255125.
- S2CID 53594139.
- S2CID 248389790.
- S2CID 37564720.
- ^ S2CID 205224761.
- ^ "Learning to program the D-Wave One". D-Wave Systems blog. Archived from the original on July 23, 2011. Retrieved 11 May 2011.
- ^ "D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation". D-Wave. 2011-05-25. Archived from the original on July 23, 2011. Retrieved 2011-05-30.
- S2CID 57405432.
- ].
- S2CID 8031023.
- ^ "D-Wave Systems Building Quantum Application Ecosystem, Announces Partnerships with DNA-SEQ Alliance and 1QBit". D-Wave Systems. Archived from the original on 31 December 2019. Retrieved 22 June 2014.
- ^ "1QBit Research". 1QBit. Archived from the original on 19 June 2014. Retrieved 22 June 2014.
- S2CID 19235104.
- ^ Helmut Katzgraber, quoted in (Cho 2014).
- PMID 24948715.
- S2CID 66770023.
- S2CID 57916974.
- ^ "When can Quantum Annealing win?". Research Blog. 8 December 2015. Retrieved 2016-01-21.
- ^ D-Wave Systems (2021-10-05). "D-Wave's Next-Generation Roadmap: Bringing Clarity to Practical Quantum Computing". Medium. Retrieved 2021-11-12.
- S2CID 118974781.
- ISSN 0098-1354.
- S2CID 257236235.
Further reading
- Bapst, V.; Foini, L.; Krzakala, F.; Semerjian, G.; Zamponi, F. (2013). "The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective". Physics Reports. 523 (3): 127–205. S2CID 19019744.
- Chandra, Anjan K.; Das, Arnab & ISBN 978-3-64211-469-4.
- Das, Arnab & Chakrabarti, Bikas K., eds. (2005). Quantum Annealing and Related Optimization Methods. Lecture Note in Physics. Vol. 679. Heidelberg: Springer. ISBN 978-3-54027-987-7.
- Dutta, A.; Aeppli, G.; Chakrabarti, B. K.; Divakaran, U.; Rosenbaum, T.F. & Sen, D. (2015). Quantum Phase Transitions in Transverse Field Spin Models: From Statistical Physics to Quantum Information. Cambridge & Delhi: Cambridge University Press. ISBN 978-1-10706-879-7.
- Li, Fuxiang; Chernyak, V. Y.; Sinitsyn, N. A. (2013). "Quantum Annealing and Computation: A Brief Documentary Note". Science and Culture. 79: 485–500. Bibcode:2013arXiv1310.1339G..
- Suzuki, S.; Inoue, J.-I. & Chakrabarti, B. K. (2013). "Chapter 8 on Quantum Annealing". Quantum Ising Phases & Transitions in Transverse Ising Models (2nd ed.). Heidelberg: Springer. ISBN 978-3-64233-038-4.
- Tanaka, S.; Tamura, R. & Chakrabarti, B. K. (2017). Quantum Spin Glasses, Annealing & Computation. Cambridge & Delhi: Cambridge University Press. ISBN 978-1-10711-319-0.
- "Quantum Annealing & Computation: Challenges & Perspectives". Philosophical Transactions A. 381. Royal Society, London. January 2023.