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. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    2. 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.
    3. 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.
    4. 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.
    5. Suhas Kumar & R. Stanley Williams & Ziwen Wang, 2020. "Third-order nanocircuit elements for neuromorphic engineering," Nature, Nature, vol. 585(7826), pages 518-523, September.
    6. 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.
    7. 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.
    8. 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.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    3. 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.
    4. 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).
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Lancia, Giuseppe & Vidoni, Paolo, 2020. "Finding the largest triangle in a graph in expected quadratic time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 458-467.
    11. Oya Ekin Karaşan & A. Ridha Mahjoub & Onur Özkök & Hande Yaman, 2014. "Survivability in Hierarchical Telecommunications Networks Under Dual Homing," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 1-15, February.
    12. Paredes-Belmar, Germán & Montero, Elizabeth & Lüer-Villagra, Armin & Marianov, Vladimir & Araya-Sassi, Claudio, 2022. "Vehicle routing for milk collection with gradual blending: A case arising in Chile," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1403-1416.
    13. Thanh Tan Doan & Nathalie Bostel & Minh Hoàng Hà & Vu Hoang Vuong Nguyen, 2023. "New mixed integer linear programming models and an iterated local search for the clustered traveling salesman problem with relaxed priority rule," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-27, August.
    14. Dong, Yujiao & Yang, Shuting & Liang, Yan & Wang, Guangyi, 2022. "Neuromorphic dynamics near the edge of chaos in memristive neurons," Chaos, Solitons & Fractals, Elsevier, vol. 160(C).
    15. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    16. Jean-Charles Créput & Amir Hajjam & Abderrafiaa Koukam & Olivier Kuhn, 2012. "Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 437-458, November.
    17. Jian Lin & Xiangfei Zeng & Jianxun Liu & Keqin Li, 2022. "Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 235-252, January.
    18. Leticia Vargas & Nicolas Jozefowiez & Sandra Ulrich Ngueveu, 2017. "A dynamic programming operator for tour location problems applied to the covering tour problem," Journal of Heuristics, Springer, vol. 23(1), pages 53-80, February.
    19. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    20. Marcel Turkensteen & Dmitry Malyshev & Boris Goldengorin & Panos M. Pardalos, 2017. "The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems," Journal of Global Optimization, Springer, vol. 68(3), pages 601-622, July.

    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.