*Result*: Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar.
Title:
Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar.
Authors:
Jiang M; Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong SAR, China., Shan K; Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong SAR, China., He C; Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong SAR, China., Li C; Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong SAR, China. canl@hku.hk.
Source:
Nature communications [Nat Commun] 2023 Sep 22; Vol. 14 (1), pp. 5927. Date of Electronic Publication: 2023 Sep 22.
Publication Type:
Journal Article
Language:
English
Journal Info:
Publisher: Nature Pub. Group Country of Publication: England NLM ID: 101528555 Publication Model: Electronic Cited Medium: Internet ISSN: 2041-1723 (Electronic) Linking ISSN: 20411723 NLM ISO Abbreviation: Nat Commun Subsets: MEDLINE; PubMed not MEDLINE
Imprint Name(s):
Original Publication: [London] : Nature Pub. Group
References:
Korte, B. H., Vygen, J., Korte, B. & Vygen, J. Combinatorial Optimization (Springer, 2011).
Yu, G. Industrial Applications of Combinatorial Optimization (Springer Science & Business Media, 2013).
Paschos, V. T. Applications of Combinatorial Optimization (John Wiley & Sons, 2014).
Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).
Mohseni, N., Mcmahon, P. L. & Byrnes, T. Ising machines as hardware solvers of combinatorial optimization problems. Nat. Rev. Phys. 4, 363–379 (2022).
Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10, 218–224 (2014). (PMID: 10.1038/nphys2900)
King, A. D. et al. Coherent quantum annealing in a programmable 2000 qubit Ising chain. Nat. Phys. 18, 1324–1328 (2022).
Inagaki, T. et al. A coherent Ising machine for 2000-node optimization problems. Science 354, 603–606 (2016). (PMID: 10.1126/science.aah424327811271)
Mcmahon, P. L. et al. A fully programmable 100-spin coherent Ising machine with all-to-all connections. Science 354, 614–617 (2016). (PMID: 10.1126/science.aah517827811274)
Honjo, T. et al. 100,000-spin coherent Ising machine. Sci. Adv. 7, eabh0952 (2021). (PMID: 10.1126/sciadv.abh0952848091734586855)
Moy, W. et al. A 1968-node coupled ring oscillator circuit for combinatorial optimization problem solving. Nat. Electron. 5, 310–317 (2022). (PMID: 10.1038/s41928-022-00749-3)
Mallick, A., Bashar, M. K., Truesdell, D. S., Calhoun, B. H. & Shukla, N. Overcoming the accuracy vs. performance trade-off in oscillator ising machines. In 2021 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2021).
Dutta, S. et al. Experimental demonstration of phase transition nano-oscillator based ising machine. In 2019 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2019).
Dutta, S. et al. An Ising Hamiltonian solver based on coupled stochastic phase-transition nano-oscillators. Nat. Electron. 4, 502–512 (2021). (PMID: 10.1038/s41928-021-00616-7)
Kumar, S., Williams, R. S. & Wang, Z. Third-order nanocircuit elements for neuromorphic engineering. Nature 585, 518–523 (2020). (PMID: 10.1038/s41586-020-2735-532968256)
Cai, F. et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks. Nat. Electron. 3, 409–418 (2020). (PMID: 10.1038/s41928-020-0436-6)
Mahmoodi, M. R., Prezioso, M. & Strukov, D. B. Versatile stochastic dot product circuits based on nonvolatile memories for high performance neurocomputing and neurooptimization. Nat. Commun. 10, 5113 (2019). (PMID: 10.1038/s41467-019-13103-7684197831704925)
Yang, K. et al. Transiently chaotic simulated annealing based on intrinsic nonlinearity of memristors for efficient solution of optimization problems. Sci. Adv. 6, eaba9901 (2020). (PMID: 10.1126/sciadv.aba9901742834232851168)
Kumar, S., Strachan, J. P. & Williams, R. S. Chaotic dynamics in nanoscale NbO<sub>2</sub> Mott memristors for analogue computing. Nature 548, 318–321 (2017). (PMID: 10.1038/nature2330728792931)
Shin, J. H., Jeong, Y. J., Zidan, M. A., Wang, Q. & Lu, W. D. Hardware acceleration of simulated annealing of spin glass by RRAM crossbar array. In 2018 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2018).
Mahmoodi, M. R. et al. An analog neuro-optimizer with adaptable annealing based on 64×64 0T1R crossbar circuit. In 2019 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2019).
Hong, M.-C. et al. In-memory annealing unit (IMAU): energy-efficient (2000 TOPS/W) combinatorial optimizer for solving travelling salesman problem. In 2021 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2021).
Yan, X. et al. Reconfigurable Stochastic neurons based on tin oxide/MoS2 hetero-memristors for simulated annealing and the Boltzmann machine. Nat Commun 12, 5710 (2021). (PMID: 10.1038/s41467-021-26012-5848125634588444)
Kumar, S., Van Vaerenbergh, T. & Strachan, J. P. Classical adiabatic annealing in memristor hopfield neural networks for combinatorial optimization. In 2020 International Conference on Rebooting Computing (ICRC) (IEEE, 2020).
Jiang, M. et al. An efficient synchronous-updating memristor-based Ising solver for combinatorial optimization. In 2022 International Electron Devices Meeting (IEDM) (IEEE, 2022).
Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum computation by adiabatic evolution. Preprint at https://arxiv.org/abs/quant-ph/0001106 (2000).
Santoro, G. E. Theory of quantum annealing of an ising spin glass. Science 295, 2427–2430 (2002). (PMID: 10.1126/science.106877411923532)
McGeoch, C. C. Adiabatic quantum computation and quantum annealing: theory and practice. Synthesis Lectures on Quantum Computing 5, 1–93 (2014).
Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998). (PMID: 10.1103/PhysRevE.58.5355)
LeCun, Y., Bengio, Y. & Hinton, G. Deep learning. Nature 521, 436–444 (2015). (PMID: 10.1038/nature1453926017442)
Bengio, Y., Léonard, N. & Courville, A. Estimating or propagating gradients through stochastic neurons for conditional computation. Preprint at https://arxiv.org/abs/1308.3432 (2013).
Courbariaux, M., Bengio, Y. & David, J.-P. Binaryconnect: training deep neural networks with binary weights during propagations. In Advances in Neural Information Processing Systems 28 (2015).
Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R. & Bengio, Y. Binarized neural networks. In Advances in Neural Information Processing Systems 29 (2016).
Hamerly, R. et al. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Sci. Adv 5, eaau0823 (2019). (PMID: 10.1126/sciadv.aau0823653438931139743)
Hopfield, J. J. Neural networks and physical systems with emergent collective computational abilities. Proc. Natl Acad. Sci. USA 79, 2554–2558 (1982). (PMID: 10.1073/pnas.79.8.25543462386953413)
Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983). (PMID: 10.1126/science.220.4598.67117813860)
Granville, V., Krivanek, M. & Rasson, J.-P. Simulated annealing: a proof of convergence. IEEE Trans. Pattern Anal. Mach Intell. 16, 652–656 (1994). (PMID: 10.1109/34.295910)
Van Dam, W., Mosca, M. & Vazirani, U. How powerful is adiabatic quantum computation? In Proceedings 42nd IEEE Symposium on Foundations of Computer Science (IEEE, 2001).
Mao, R., Wen, B., Jiang, M., Chen, J. & Li, C. Experimentally-validated crossbar model for defect-aware training of neural networks. IEEE Trans. Circuits Syst. II Express Briefs 69, 2468–2472 (2022).
Rao, M. et al. Thousands of conductance levels in memristors integrated on CMOS. Nature 615, 823–829 (2023). (PMID: 10.1038/s41586-023-05759-536991190)
Goto, H. et al. High-performance combinatorial optimization based on classical mechanics. Sci. Adv. 7, eabe7953 (2021). (PMID: 10.1126/sciadv.abe795333536219)
Reinelt, G. TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3, 376–384 (1991). (PMID: 10.1287/ijoc.3.4.376)
Dan, A., Shimizu, R., Nishikawa, T., Bian, S. & Sato, T. Clustering approach for solving traveling salesman problems via ising model based solver. In 2020 57th ACM/IEEE Design Automation Conference (DAC) (IEEE, 2020).
Lu, A. et al. Scalable in-memory clustered annealer with temporal noise of FinFET for the travelling salesman problem. In 2022 International Electron Devices Meeting (IEDM) (IEEE, 2022).
Xue, C.-X. et al. 16.1 A 22 nm 4 Mb 8b-precision ReRAM computing-in-memory macro with 11.91 to 195.7TOPS/W for tiny AI edge devices. In 2021 IEEE International Solid-State Circuits Conference (ISSCC) (IEEE, 2021).
King, A. D., Bernoudy, W., King, J., Berkley, A. J. & Lanting, T. Emulating the coherent Ising machine with a mean-field algorithm. Preprint at https://arxiv.org/abs/1806.08422 (2018).
Tiunov, E. S., Ulanov, A. E. & Lvovsky, A. I. Annealing by simulating the coherent Ising machine. Opt. Express 27, 10288–10295 (2019). (PMID: 10.1364/OE.27.01028831045172)
Sun, Z. et al. Solving matrix equations in one step with cross-point resistive arrays. Proc. Natl Acad. Sci. USA 116, 4123–4128 (2019). (PMID: 10.1073/pnas.1815682116641082230782810)
Yao, P. et al. Fully hardware-implemented memristor convolutional neural network. Nature 577, 641–646 (2020). (PMID: 10.1038/s41586-020-1942-431996818)
Wan, W. et al. A compute-in-memory chip based on resistive random-access memory. Nature 608, 504–512 (2022). (PMID: 10.1038/s41586-022-04992-8938548235978128)
Sheng, X. et al. Low‐conductance and multilevel CMOS‐integrated nanoscale oxide memristors. Adv. Electron Mater. 5, 1800876 (2019).
Alizadeh, M., Fernández-Marqués, J., Lane, N. D. & Gal, Y. An empirical study of binary neural networks’ optimisation. In International Conference on Learning Representations (ICLR) (OpenReview.net, 2018).
Qian, N. On the momentum term in gradient descent learning algorithms. Neural Netw. 12, 145–151 (1999). (PMID: 10.1016/S0893-6080(98)00116-612662723)
Tao, M. et al. A Work-time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising model, with GPU implementation. In 2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (IEEE, 2020).
Yu, G. Industrial Applications of Combinatorial Optimization (Springer Science & Business Media, 2013).
Paschos, V. T. Applications of Combinatorial Optimization (John Wiley & Sons, 2014).
Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).
Mohseni, N., Mcmahon, P. L. & Byrnes, T. Ising machines as hardware solvers of combinatorial optimization problems. Nat. Rev. Phys. 4, 363–379 (2022).
Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10, 218–224 (2014). (PMID: 10.1038/nphys2900)
King, A. D. et al. Coherent quantum annealing in a programmable 2000 qubit Ising chain. Nat. Phys. 18, 1324–1328 (2022).
Inagaki, T. et al. A coherent Ising machine for 2000-node optimization problems. Science 354, 603–606 (2016). (PMID: 10.1126/science.aah424327811271)
Mcmahon, P. L. et al. A fully programmable 100-spin coherent Ising machine with all-to-all connections. Science 354, 614–617 (2016). (PMID: 10.1126/science.aah517827811274)
Honjo, T. et al. 100,000-spin coherent Ising machine. Sci. Adv. 7, eabh0952 (2021). (PMID: 10.1126/sciadv.abh0952848091734586855)
Moy, W. et al. A 1968-node coupled ring oscillator circuit for combinatorial optimization problem solving. Nat. Electron. 5, 310–317 (2022). (PMID: 10.1038/s41928-022-00749-3)
Mallick, A., Bashar, M. K., Truesdell, D. S., Calhoun, B. H. & Shukla, N. Overcoming the accuracy vs. performance trade-off in oscillator ising machines. In 2021 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2021).
Dutta, S. et al. Experimental demonstration of phase transition nano-oscillator based ising machine. In 2019 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2019).
Dutta, S. et al. An Ising Hamiltonian solver based on coupled stochastic phase-transition nano-oscillators. Nat. Electron. 4, 502–512 (2021). (PMID: 10.1038/s41928-021-00616-7)
Kumar, S., Williams, R. S. & Wang, Z. Third-order nanocircuit elements for neuromorphic engineering. Nature 585, 518–523 (2020). (PMID: 10.1038/s41586-020-2735-532968256)
Cai, F. et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks. Nat. Electron. 3, 409–418 (2020). (PMID: 10.1038/s41928-020-0436-6)
Mahmoodi, M. R., Prezioso, M. & Strukov, D. B. Versatile stochastic dot product circuits based on nonvolatile memories for high performance neurocomputing and neurooptimization. Nat. Commun. 10, 5113 (2019). (PMID: 10.1038/s41467-019-13103-7684197831704925)
Yang, K. et al. Transiently chaotic simulated annealing based on intrinsic nonlinearity of memristors for efficient solution of optimization problems. Sci. Adv. 6, eaba9901 (2020). (PMID: 10.1126/sciadv.aba9901742834232851168)
Kumar, S., Strachan, J. P. & Williams, R. S. Chaotic dynamics in nanoscale NbO<sub>2</sub> Mott memristors for analogue computing. Nature 548, 318–321 (2017). (PMID: 10.1038/nature2330728792931)
Shin, J. H., Jeong, Y. J., Zidan, M. A., Wang, Q. & Lu, W. D. Hardware acceleration of simulated annealing of spin glass by RRAM crossbar array. In 2018 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2018).
Mahmoodi, M. R. et al. An analog neuro-optimizer with adaptable annealing based on 64×64 0T1R crossbar circuit. In 2019 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2019).
Hong, M.-C. et al. In-memory annealing unit (IMAU): energy-efficient (2000 TOPS/W) combinatorial optimizer for solving travelling salesman problem. In 2021 IEEE International Electron Devices Meeting (IEDM) (IEEE, 2021).
Yan, X. et al. Reconfigurable Stochastic neurons based on tin oxide/MoS2 hetero-memristors for simulated annealing and the Boltzmann machine. Nat Commun 12, 5710 (2021). (PMID: 10.1038/s41467-021-26012-5848125634588444)
Kumar, S., Van Vaerenbergh, T. & Strachan, J. P. Classical adiabatic annealing in memristor hopfield neural networks for combinatorial optimization. In 2020 International Conference on Rebooting Computing (ICRC) (IEEE, 2020).
Jiang, M. et al. An efficient synchronous-updating memristor-based Ising solver for combinatorial optimization. In 2022 International Electron Devices Meeting (IEDM) (IEEE, 2022).
Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum computation by adiabatic evolution. Preprint at https://arxiv.org/abs/quant-ph/0001106 (2000).
Santoro, G. E. Theory of quantum annealing of an ising spin glass. Science 295, 2427–2430 (2002). (PMID: 10.1126/science.106877411923532)
McGeoch, C. C. Adiabatic quantum computation and quantum annealing: theory and practice. Synthesis Lectures on Quantum Computing 5, 1–93 (2014).
Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998). (PMID: 10.1103/PhysRevE.58.5355)
LeCun, Y., Bengio, Y. & Hinton, G. Deep learning. Nature 521, 436–444 (2015). (PMID: 10.1038/nature1453926017442)
Bengio, Y., Léonard, N. & Courville, A. Estimating or propagating gradients through stochastic neurons for conditional computation. Preprint at https://arxiv.org/abs/1308.3432 (2013).
Courbariaux, M., Bengio, Y. & David, J.-P. Binaryconnect: training deep neural networks with binary weights during propagations. In Advances in Neural Information Processing Systems 28 (2015).
Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R. & Bengio, Y. Binarized neural networks. In Advances in Neural Information Processing Systems 29 (2016).
Hamerly, R. et al. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Sci. Adv 5, eaau0823 (2019). (PMID: 10.1126/sciadv.aau0823653438931139743)
Hopfield, J. J. Neural networks and physical systems with emergent collective computational abilities. Proc. Natl Acad. Sci. USA 79, 2554–2558 (1982). (PMID: 10.1073/pnas.79.8.25543462386953413)
Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983). (PMID: 10.1126/science.220.4598.67117813860)
Granville, V., Krivanek, M. & Rasson, J.-P. Simulated annealing: a proof of convergence. IEEE Trans. Pattern Anal. Mach Intell. 16, 652–656 (1994). (PMID: 10.1109/34.295910)
Van Dam, W., Mosca, M. & Vazirani, U. How powerful is adiabatic quantum computation? In Proceedings 42nd IEEE Symposium on Foundations of Computer Science (IEEE, 2001).
Mao, R., Wen, B., Jiang, M., Chen, J. & Li, C. Experimentally-validated crossbar model for defect-aware training of neural networks. IEEE Trans. Circuits Syst. II Express Briefs 69, 2468–2472 (2022).
Rao, M. et al. Thousands of conductance levels in memristors integrated on CMOS. Nature 615, 823–829 (2023). (PMID: 10.1038/s41586-023-05759-536991190)
Goto, H. et al. High-performance combinatorial optimization based on classical mechanics. Sci. Adv. 7, eabe7953 (2021). (PMID: 10.1126/sciadv.abe795333536219)
Reinelt, G. TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3, 376–384 (1991). (PMID: 10.1287/ijoc.3.4.376)
Dan, A., Shimizu, R., Nishikawa, T., Bian, S. & Sato, T. Clustering approach for solving traveling salesman problems via ising model based solver. In 2020 57th ACM/IEEE Design Automation Conference (DAC) (IEEE, 2020).
Lu, A. et al. Scalable in-memory clustered annealer with temporal noise of FinFET for the travelling salesman problem. In 2022 International Electron Devices Meeting (IEDM) (IEEE, 2022).
Xue, C.-X. et al. 16.1 A 22 nm 4 Mb 8b-precision ReRAM computing-in-memory macro with 11.91 to 195.7TOPS/W for tiny AI edge devices. In 2021 IEEE International Solid-State Circuits Conference (ISSCC) (IEEE, 2021).
King, A. D., Bernoudy, W., King, J., Berkley, A. J. & Lanting, T. Emulating the coherent Ising machine with a mean-field algorithm. Preprint at https://arxiv.org/abs/1806.08422 (2018).
Tiunov, E. S., Ulanov, A. E. & Lvovsky, A. I. Annealing by simulating the coherent Ising machine. Opt. Express 27, 10288–10295 (2019). (PMID: 10.1364/OE.27.01028831045172)
Sun, Z. et al. Solving matrix equations in one step with cross-point resistive arrays. Proc. Natl Acad. Sci. USA 116, 4123–4128 (2019). (PMID: 10.1073/pnas.1815682116641082230782810)
Yao, P. et al. Fully hardware-implemented memristor convolutional neural network. Nature 577, 641–646 (2020). (PMID: 10.1038/s41586-020-1942-431996818)
Wan, W. et al. A compute-in-memory chip based on resistive random-access memory. Nature 608, 504–512 (2022). (PMID: 10.1038/s41586-022-04992-8938548235978128)
Sheng, X. et al. Low‐conductance and multilevel CMOS‐integrated nanoscale oxide memristors. Adv. Electron Mater. 5, 1800876 (2019).
Alizadeh, M., Fernández-Marqués, J., Lane, N. D. & Gal, Y. An empirical study of binary neural networks’ optimisation. In International Conference on Learning Representations (ICLR) (OpenReview.net, 2018).
Qian, N. On the momentum term in gradient descent learning algorithms. Neural Netw. 12, 145–151 (1999). (PMID: 10.1016/S0893-6080(98)00116-612662723)
Tao, M. et al. A Work-time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising model, with GPU implementation. In 2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (IEEE, 2020).
Grant Information:
T45-701/22-R Research Grants Council, University Grants Committee (RGC, UGC); 27210321 Research Grants Council, University Grants Committee (RGC, UGC); 62122005 National Natural Science Foundation of China (National Science Foundation of China); 23102360 Croucher Foundation
Entry Date(s):
Date Created: 20230922 Latest Revision: 20231115
Update Code:
20260130
PubMed Central ID:
PMC10516914
DOI:
10.1038/s41467-023-41647-2
PMID:
37739944
Database:
MEDLINE
*Further Information*
*Combinatorial optimization problems are prevalent in various fields, but obtaining exact solutions remains challenging due to the combinatorial explosion with increasing problem size. Special-purpose hardware such as Ising machines, particularly memristor-based analog Ising machines, have emerged as promising solutions. However, existing simulate-annealing-based implementations have not fully exploited the inherent parallelism and analog storage/processing features of memristor crossbar arrays. This work proposes a quantum-inspired parallel annealing method that enables full parallelism and improves solution quality, resulting in significant speed and energy improvement when implemented in analog memristor crossbars. We experimentally solved tasks, including unweighted and weighted Max-Cut and traveling salesman problem, using our integrated memristor chip. The quantum-inspired parallel annealing method implemented in memristor-based hardware has demonstrated significant improvements in time- and energy-efficiency compared to previously reported simulated annealing and Ising machine implemented on other technologies. This is because our approach effectively exploits the natural parallelism, analog conductance states, and all-to-all connection provided by memristor technology, promising its potential for solving complex optimization problems with greater efficiency.
(© 2023. Springer Nature Limited.)*