Journal Home > Volume 25 , Issue 4
Tsinghua Science and Technology 2020, 25(4): 508-515 https://doi.org/10.26599/TST.2019.9010030
Open Access | Issue | Published: 13 January 2020

Optimization of Quantum Computing Models Inspired by D-Wave Quantum Annealing

Show Author's Information Baonan Wang,  Feng Hu,  Chao Wang( )
Key laboratory of Specialty Fiber Optics and Optical Access Networks, Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai Institute for Advanced Communication and Data Science, Shanghai University, Shanghai 200444, China
State Key Laboratory of Cryptology, Beijing 100878, China.
Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518000, China.
Keywords:
Quantum Annealing (QA), annealing schedule, quantum tunneling, optimization problem
Cite this article:
Wang B, Hu F, Wang C. Optimization of Quantum Computing Models Inspired by D-Wave Quantum Annealing. Tsinghua Science and Technology, 2020, 25(4): 508-515. https://doi.org/10.26599/TST.2019.9010030
Download citation
EndNote(RIS)
BibTeX

621

Views

59

Downloads

Citations

6

Crossref

N/A

WoS

8

Scopus

2

CSCD

Abstract Full text About this article

With the slow progress of universal quantum computers, studies on the feasibility of optimization by a dedicated and quantum-annealing-based annealer are important. The quantum principle is expected to utilize the quantum tunneling effects to find the optimal solutions for the exponential-level problems while classical annealing may be affected by the initializations. This study constructs a new Quantum-Inspired Annealing (QIA) framework to explore the potentials of quantum annealing for solving Ising model with comparisons to the classical one. Through various configurations of the 1D Ising model, the new framework can achieve ground state, corresponding to the optimum of classical problems, with higher probability up to 28% versus classical counterpart (22% in case). This condition not only reveals the potential of quantum annealing for solving the Ising-like Hamiltonian, but also contributes to an improved understanding and use of the quantum annealer for various applications in the future.


menu
Abstract
Full text
Outline
About this article

Optimization of Quantum Computing Models Inspired by D-Wave Quantum Annealing

Show Author's information Baonan Wang, Feng Hu, Chao Wang( )
Key laboratory of Specialty Fiber Optics and Optical Access Networks, Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai Institute for Advanced Communication and Data Science, Shanghai University, Shanghai 200444, China
State Key Laboratory of Cryptology, Beijing 100878, China.
Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518000, China.

Abstract

With the slow progress of universal quantum computers, studies on the feasibility of optimization by a dedicated and quantum-annealing-based annealer are important. The quantum principle is expected to utilize the quantum tunneling effects to find the optimal solutions for the exponential-level problems while classical annealing may be affected by the initializations. This study constructs a new Quantum-Inspired Annealing (QIA) framework to explore the potentials of quantum annealing for solving Ising model with comparisons to the classical one. Through various configurations of the 1D Ising model, the new framework can achieve ground state, corresponding to the optimum of classical problems, with higher probability up to 28% versus classical counterpart (22% in case). This condition not only reveals the potential of quantum annealing for solving the Ising-like Hamiltonian, but also contributes to an improved understanding and use of the quantum annealer for various applications in the future.

Keywords: Quantum Annealing (QA), annealing schedule, quantum tunneling, optimization problem

References(38)

[1]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman and Company, 1979.
[2]
R. Martoňák, G. E. Santoro, and E. Tosatti, Quantum annealing of the traveling salesman problem, Physical Review E, vol. 70, no. 5, p. 057701, 2004.
DOI Google Scholar
[3]
G. Ausiello, M. Protasi, A. Marchetti-Spaccamela, G. Gambosi, P. Crescenzi, and V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Berlin Heidelberg, Germany: Springer-Verlag, 1999.
DOI
[4]
P. Brucker, On the complexity of clustering problems, Optimization and Operations Research. Berlin Heidelberg, Germany: Springer, 1978.
[5]
M. Troyer and U. J. Wiese, Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations, Physical Review Letters, vol. 94, no. 17, p. 170201, 2005.
DOI Google Scholar
[6]
A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chemical Physics Letters, vol. 219, nos. 5&6, pp. 343-348, 1994.
DOI Google Scholar
[7]
G. E. Santoro and E. Tosatti, Optimization using quantum mechanics: Quantum annealing through adiabatic evolution, Journal of Physics A: Mathematical and General, vol. 39, no. 36, p. R393, 2006.
DOI Google Scholar
[8]
S. V. Isakov, I. N. Zintchenko, T. F. Rønnow, and M. Troyer, Optimised simulated annealing for Ising spin glasses, Computer Physics Communications, vol. 192, pp. 265-271, 2015.
DOI Google Scholar
[9]
J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aeppli, Quantum annealing of a disordered magnet, Science, vol. 284, no. 5415, pp. 779-781, 1999.
DOI Google Scholar
[10]
T. Albash and D. A. Lidar, Adiabatic quantum computation, Reviews of Modern Physics, vol. 90, no. 1, p. 015002, 2018.
DOI Google Scholar
[11]
A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan, E. Andriyash, A. Berkley, M. Reis, T. Lanting, R. Harris, F. Altomare, et al., Observation of topological phenomena in a programmable lattice of 1800 qubits, Nature, vol. 560, no. 7719, p. 456, 2018.
DOI Google Scholar
[12]
F. Neukart, D. Von Dollen, G. Compostella, C. Seidel, S. Yarkoni, and B. Parney, Traffic flow optimization using a quantum annealer, Frontiers in ICT, vol. 4, p. 29, 2017.
DOI Google Scholar
[13]
R. Harris, Y. Sato, A. J. Berkley, M. Reis, F. Altomare, M. H. Amin, K. Boothby, P. Bunyk, C. Deng, C. Enderud, et al., Phase transitions in a programmable quantum spin glass simulator, Science, vol. 361, no. 6398, pp. 162-165, 2018.
DOI Google Scholar
[14]
C. Wang and H. G. Zhang, The impact of Canada’s commercial quantum computer on cryptography, (Chinese), China Information Security, vol. 2, pp. 31-32, 2012.
Google Scholar
[15]
W. C. Peng, B. N. Wang, F. Hu, Y. J. Wang, X. J. Fang, X. Y. Chen, and C. Wang, Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci. China-Phys. Mech. Astron, vol. 62, no. 6, p. 060311, 2019.
DOI Google Scholar
[16]
F. Hu, L. Lamata, M. Sanz, X. Chen, X. Y. Chen, C. Wang, and E. Solano, Quantum computing cryptography: Unveiling cryptographic boolean functions with quantum annealing, arXiv preprint arXiv: 1806.08706, 2018.
Google Scholar
[17]
R. Martoňák, G. E. Santoro, and E. Tosatti, Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model, Physical Review B, vol. 66, no. 9, p. 094203, 2002.
DOI Google Scholar
[18]
L. Stella and G. E. Santoro, Quantum annealing of an Ising spinglass by Green’s function Monte Carlo, Physical Review E, vol. 75, no. 3, p. 036703, 2007.
DOI Google Scholar
[19]
M. Sarjala, V. Petäjä, and M. Alava, Optimization in random field Ising models by quantum annealing, Journal of Statistical Mechanics: Theory and Experiment, vol. 2006, no. 1, p. P01008, 2006.
DOI Google Scholar
[20]
S. Shinomoto and Y. Kabashima, Finite time scaling of energy in simulated annealing, Journal of Physics A: Mathematical and General, vol. 24, no. 3, p. L141, 1991.
DOI Google Scholar
[21]
C. De Simone, M. Diehl, M. Juenger, P. Mutzel, and G. Reinelt, Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm, Journal of Statistical Physics, vol. 80, nos. 1&2, pp. 487-496, 1995.
DOI Google Scholar
[22]
G. Carleo and M. Troyer, Solving the quantum many-body problem with artificial neural networks, Science, vol. 355, no. 6325, pp. 602-606, 2017.
DOI Google Scholar
[23]
Z. Zhu, A. J. Ochoa, and H. G. Katzgraber, Efficient cluster algorithm for spin glasses in any space dimension, Physical Review Letters, vol. 115, no. 7, p. 077201, 2015.
DOI Google Scholar
[24]
S. M. Krause, P. Böttcher, and S. Bornholdt, Mean-field-like behavior of the generalized voter-model-class kinetic Ising model, Physical Review E, vol. 85, no. 3, p. 031126, 2012.
DOI Google Scholar
[25]
M. W. Johnson, P. Bunyk, F. Maibaum, E. Tolkacheva, A. J. Berkley, E. M. Chapple, R. Harris, J. Johansson, T. Lanting, I. Perminov, et al., A scalable control system for a superconducting adiabatic quantum optimization processor, Superconductor Science and Technology, vol. 23, no. 6, p. 065004, 2010.
DOI Google Scholar
[26]
D. A. Huse and D. S. Fisher, Residual energies after slow cooling of disordered systems, Physical Review Letters, vol. 57, no. 17, p. 2203, 1986.
DOI Google Scholar
[27]
S. Suzuki and M. Okada, Simulated quantum annealing by the real-time evolution, in Quantum Annealing and Other Optimization Methods. Berlin, Heidelberg, Germany: Springer, pp. 207-238, 2005.
DOI
[28]
G. E. Santoro, R Martoňák, E. Tosatti, and R. Car, Theory of quantum annealing of an Ising spin glass, Science, vol. 295, no. 5564, pp. 2427-2430, 2002.
DOI Google Scholar
[29]
M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al., Quantum annealing with manufactured spins, Nature, vol. 473, no. 7346, pp. 194-198, 2011.
DOI Google Scholar
[30]
C. Wang, Y. J. Wang, and F. Hu, Shaping the future of commercial quantum computer and the challenge for information security, (Chinese), Chinese Journal Network and Information Security, vol. 2, no. 3, pp. 17-27, 2016.
Google Scholar
[31]
G. Mazzola, V. N. Smelyanskiy, and M. Troyer, Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing, Physical Review B, vol. 96, no. 13, p. 134305, 2017.
DOI Google Scholar
[32]
S. V. Isakov, G. Mazzola, V. N. Smelyanskiy, Z. Jiang, S. Boixo, H. Neven, and M. Troyer, Understanding quantum tunneling through quantum Monte Carlo simulations, Physical Review Letters, vol. 117, no. 18, p. 180402, 2016.
DOI Google Scholar
[33]
T. Kadowaki and H. Nishimori, Quantum annealing in the transverse Ising model, Physical Review E, vol. 58, no. 5, p. 5355, 1998.
DOI Google Scholar
[34]
I. Hen, J. Job, T. Albash, T. F. Rønnow, M. Troyer, and D. A. Lidar, Probing for quantum speedup in spin-glass problems with planted solutions, Physical Review A, vol. 92, no. 4, p. 042325, 2015.
DOI Google Scholar
[35]
H. G. Katzgraber, F. Hamze, and R. S. Andrist, Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines, Physical Review X, vol. 4, no. 2, p. 021008, 2014.
DOI Google Scholar
[36]
T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Defining and detecting quantum speedup, Science, vol. 345, no. 6195, pp. 420-424, 2014.
DOI Google Scholar
[37]
S. Suzuki, H. Nishimori, and M. Suzuki, Quantum annealing of the random-field Ising model by transverse ferromagnetic interactions, Physical Review E, vol. 75, no. 5, p. 051112, 2007.
DOI Google Scholar
[38]
T. Albash and D. A. Lidar, Demonstration of a scaling advantage for a quantum annealer over simulated annealing, Physical Review X, vol. 8, no. 3, p. 031016, 2018.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 27 June 2019
Revised: 27 June 2019
Accepted: 17 July 2019
Published: 13 January 2020
Issue date: August 2020

Copyright

© The author(s) 2020

Acknowledgements

This study was supported by the Special Zone Project of National Defense Innovation, the National Natural Science Foundation of China (Nos. 61572304 and 61272096), the Key Program of the National Natural Science Foundation of China (No. 61332019), and Open Research Fund of State Key Laboratory of Cryptology.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return