IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v14y2023i1d10.1038_s41467-023-41647-2.html
   My bibliography  Save this article

Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar

Author

Listed:
  • Mingrui Jiang

    (The University of Hong Kong)

  • Keyi Shan

    (The University of Hong Kong)

  • Chengping He

    (The University of Hong Kong)

  • Can Li

    (The University of Hong Kong)

Abstract

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.

Suggested Citation

  • Mingrui Jiang & Keyi Shan & Chengping He & Can Li, 2023. "Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar," Nature Communications, Nature, vol. 14(1), pages 1-11, December.
    • Handle: RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-41647-2
    DOI: 10.1038/s41467-023-41647-2
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/s41467-023-41647-2
    File Function: Abstract
    Download Restriction: no
    File URL: https://libkey.io/10.1038/s41467-023-41647-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Suhas Kumar & John Paul Strachan & R. Stanley Williams, 2017. "Chaotic dynamics in nanoscale NbO2 Mott memristors for analogue computing," Nature, Nature, vol. 548(7667), pages 318-321, August.
    2. Weier Wan & Rajkumar Kubendran & Clemens Schaefer & Sukru Burc Eryilmaz & Wenqiang Zhang & Dabin Wu & Stephen Deiss & Priyanka Raina & He Qian & Bin Gao & Siddharth Joshi & Huaqiang Wu & H.-S. Philip , 2022. "A compute-in-memory chip based on resistive random-access memory," Nature, Nature, vol. 608(7923), pages 504-512, August.
    3. Xiaodong Yan & Jiahui Ma & Tong Wu & Aoyang Zhang & Jiangbin Wu & Matthew Chin & Zhihan Zhang & Madan Dubey & Wei Wu & Mike Shuo-Wei Chen & Jing Guo & Han Wang, 2021. "Reconfigurable Stochastic neurons based on tin oxide/MoS2 hetero-memristors for simulated annealing and the Boltzmann machine," Nature Communications, Nature, vol. 12(1), pages 1-8, December.
    4. Suhas Kumar & R. Stanley Williams & Ziwen Wang, 2020. "Third-order nanocircuit elements for neuromorphic engineering," Nature, Nature, vol. 585(7826), pages 518-523, September.
    5. Peng Yao & Huaqiang Wu & Bin Gao & Jianshi Tang & Qingtian Zhang & Wenqiang Zhang & J. Joshua Yang & He Qian, 2020. "Fully hardware-implemented memristor convolutional neural network," Nature, Nature, vol. 577(7792), pages 641-646, January.
    6. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    7. M. R. Mahmoodi & M. Prezioso & D. B. Strukov, 2019. "Versatile stochastic dot product circuits based on nonvolatile memories for high performance neurocomputing and neurooptimization," Nature Communications, Nature, vol. 10(1), pages 1-10, December.
    8. Mingyi Rao & Hao Tang & Jiangbin Wu & Wenhao Song & Max Zhang & Wenbo Yin & Ye Zhuo & Fatemeh Kiani & Benjamin Chen & Xiangqi Jiang & Hefei Liu & Hung-Yu Chen & Rivu Midya & Fan Ye & Hao Jiang & Zhong, 2023. "Thousands of conductance levels in memristors integrated on CMOS," Nature, Nature, vol. 615(7954), pages 823-829, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tinish Bhattacharya & George H. Hutchinson & Giacomo Pedretti & Xia Sheng & Jim Ignowski & Thomas Vaerenbergh & Ray Beausoleil & John Paul Strachan & Dmitri B. Strukov, 2024. "Computing high-degree polynomial gradients in memory," Nature Communications, Nature, vol. 15(1), pages 1-11, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Peng Chen & Fenghao Liu & Peng Lin & Peihong Li & Yu Xiao & Bihua Zhang & Gang Pan, 2023. "Open-loop analog programmable electrochemical memory array," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    2. Kyung Seok Woo & Alan Zhang & Allison Arabelo & Timothy D. Brown & Minseong Park & A. Alec Talin & Elliot J. Fuller & Ravindra Singh Bisht & Xiaofeng Qian & Raymundo Arroyave & Shriram Ramanathan & Lu, 2024. "True random number generation using the spin crossover in LaCoO3," Nature Communications, Nature, vol. 15(1), pages 1-9, December.
    3. Pietro Belleri & Judith Pons i Tarrés & Iain McCulloch & Paul W. M. Blom & Zsolt M. Kovács-Vajna & Paschalis Gkoupidenis & Fabrizio Torricelli, 2024. "Unravelling the operation of organic artificial neurons for neuromorphic bioelectronics," Nature Communications, Nature, vol. 15(1), pages 1-16, December.
    4. William Cook & Sanjeeb Dash & Ricardo Fukasawa & Marcos Goycoolea, 2009. "Numerically Safe Gomory Mixed-Integer Cuts," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 641-649, November.
    5. Thiago Serra & Ryan J. O’Neil, 2020. "MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions," SN Operations Research Forum, Springer, vol. 1(3), pages 1-6, September.
    6. Barbato, Michele & Gouveia, Luís, 2024. "The Hamiltonian p-median problem: Polyhedral results and branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 316(2), pages 473-487.
    7. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    8. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    9. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    10. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    11. Ernst Althaus & Felix Rauterberg & Sarah Ziegler, 2020. "Computing Euclidean Steiner trees over segments," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 309-325, October.
    12. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.
    13. Martins, Francisco Leonardo Bezerra & do Nascimento, José Cláudio, 2022. "Power law dynamics in genealogical graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    14. Djohan Bonnet & Tifenn Hirtzlin & Atreya Majumdar & Thomas Dalgaty & Eduardo Esmanhotto & Valentina Meli & Niccolo Castellani & Simon Martin & Jean-François Nodin & Guillaume Bourgeois & Jean-Michel P, 2023. "Bringing uncertainty quantification to the extreme-edge with memristor-based Bayesian neural networks," Nature Communications, Nature, vol. 14(1), pages 1-13, December.
    15. Marjan Marzban & Qian-Ping Gu & Xiaohua Jia, 2016. "New analysis and computational study for the planar connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 198-225, July.
    16. Rohit Abraham John & Yiğit Demirağ & Yevhen Shynkarenko & Yuliia Berezovska & Natacha Ohannessian & Melika Payvand & Peng Zeng & Maryna I. Bodnarchuk & Frank Krumeich & Gökhan Kara & Ivan Shorubalko &, 2022. "Reconfigurable halide perovskite nanocrystal memristors for neuromorphic computing," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    17. Yulin Feng & Yizhou Zhang & Zheng Zhou & Peng Huang & Lifeng Liu & Xiaoyan Liu & Jinfeng Kang, 2024. "Memristor-based storage system with convolutional autoencoder-based image compression network," Nature Communications, Nature, vol. 15(1), pages 1-13, December.
    18. Ferrer, José M. & Martín-Campo, F. Javier & Ortuño, M. Teresa & Pedraza-Martínez, Alfonso J. & Tirado, Gregorio & Vitoriano, Begoña, 2018. "Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications," European Journal of Operational Research, Elsevier, vol. 269(2), pages 501-515.
    19. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    20. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-41647-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.