Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar
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 e...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2023-09-01
|
| Series: | Nature Communications |
| Online Access: | https://doi.org/10.1038/s41467-023-41647-2 |
| _version_ | 1797558523564916736 |
|---|---|
| author | Mingrui Jiang Keyi Shan Chengping He Can Li |
| author_facet | Mingrui Jiang Keyi Shan Chengping He Can Li |
| author_sort | Mingrui Jiang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T17:31:38Z |
| format | Article |
| id | doaj.art-6a47f4dfdd5d402fa64c47bf7a68f6d7 |
| institution | Directory Open Access Journal |
| issn | 2041-1723 |
| language | English |
| last_indexed | 2024-03-10T17:31:38Z |
| publishDate | 2023-09-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Nature Communications |
| spelling | doaj.art-6a47f4dfdd5d402fa64c47bf7a68f6d72023-11-20T09:59:45ZengNature PortfolioNature Communications2041-17232023-09-0114111110.1038/s41467-023-41647-2Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbarMingrui Jiang0Keyi Shan1Chengping He2Can Li3Department of Electrical and Electronic Engineering, The University of Hong KongDepartment of Electrical and Electronic Engineering, The University of Hong KongDepartment of Electrical and Electronic Engineering, The University of Hong KongDepartment of Electrical and Electronic Engineering, The University of Hong KongAbstract 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.https://doi.org/10.1038/s41467-023-41647-2 |
| spellingShingle | Mingrui Jiang Keyi Shan Chengping He Can Li Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar Nature Communications |
| title | Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar |
| title_full | Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar |
| title_fullStr | Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar |
| title_full_unstemmed | Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar |
| title_short | Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar |
| title_sort | efficient combinatorial optimization by quantum inspired parallel annealing in analogue memristor crossbar |
| url | https://doi.org/10.1038/s41467-023-41647-2 |
| work_keys_str_mv | AT mingruijiang efficientcombinatorialoptimizationbyquantuminspiredparallelannealinginanaloguememristorcrossbar AT keyishan efficientcombinatorialoptimizationbyquantuminspiredparallelannealinginanaloguememristorcrossbar AT chengpinghe efficientcombinatorialoptimizationbyquantuminspiredparallelannealinginanaloguememristorcrossbar AT canli efficientcombinatorialoptimizationbyquantuminspiredparallelannealinginanaloguememristorcrossbar |