Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem
In this work, we experimentally demonstrate an integrated circuit (IC) of 30 relaxation oscillators with reconfigurable capacitive coupling to solve the NP-Hard maximum cut (Max-Cut) problem. We show that under the influence of an external second-harmonic injection signal, the oscillator phases exhi...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Journal on Exploratory Solid-State Computational Devices and Circuits |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9204635/ |
| _version_ | 1818370113326284800 |
|---|---|
| author | Mohammad Khairul Bashar Antik Mallick Daniel S. Truesdell Benton H. Calhoun Siddharth Joshi Nikhil Shukla |
| author_facet | Mohammad Khairul Bashar Antik Mallick Daniel S. Truesdell Benton H. Calhoun Siddharth Joshi Nikhil Shukla |
| author_sort | Mohammad Khairul Bashar |
| collection | DOAJ |
| description | In this work, we experimentally demonstrate an integrated circuit (IC) of 30 relaxation oscillators with reconfigurable capacitive coupling to solve the NP-Hard maximum cut (Max-Cut) problem. We show that under the influence of an external second-harmonic injection signal, the oscillator phases exhibit a bipartition that can be used to calculate a high-quality approximate Max-Cut solution. Leveraging the all-to-all reconfigurable coupling architecture, we experimentally evaluate the computational properties of the oscillators using randomly generated graph instances of varying size and edge density (η). Furthermore, comparing the Max-Cut solutions with the optimal values, we show that the oscillators (after simple postprocessing) produce a Max-Cut that is within 99% of the optimal value in 28 of the 36 measured graphs; importantly, the oscillators are particularly effective in dense graphs with the Max-Cut being optimal in seven out of nine measured graphs with η = 0.8. Our work marks a step toward creating an efficient, room-temperature-compatible non-Boolean hardware-based solver for hard combinatorial optimization problems. |
| first_indexed | 2024-12-13T23:34:34Z |
| format | Article |
| id | doaj.art-ebaf7f5bbf594e1686b3e7bdf38bd6a5 |
| institution | Directory Open Access Journal |
| issn | 2329-9231 |
| language | English |
| last_indexed | 2024-12-13T23:34:34Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Journal on Exploratory Solid-State Computational Devices and Circuits |
| spelling | doaj.art-ebaf7f5bbf594e1686b3e7bdf38bd6a52022-12-21T23:27:20ZengIEEEIEEE Journal on Exploratory Solid-State Computational Devices and Circuits2329-92312020-01-016211612110.1109/JXCDC.2020.30259949204635Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut ProblemMohammad Khairul Bashar0https://orcid.org/0000-0002-3668-0576Antik Mallick1https://orcid.org/0000-0002-5697-5742Daniel S. Truesdell2https://orcid.org/0000-0002-5723-0398Benton H. Calhoun3Siddharth Joshi4Nikhil Shukla5https://orcid.org/0000-0002-8899-5190Department of Electrical & Computer Engineering, University of Virginia, Charlottesville, VA, USADepartment of Electrical & Computer Engineering, University of Virginia, Charlottesville, VA, USADepartment of Electrical & Computer Engineering, University of Virginia, Charlottesville, VA, USADepartment of Electrical & Computer Engineering, University of Virginia, Charlottesville, VA, USADepartment of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN, USADepartment of Electrical & Computer Engineering, University of Virginia, Charlottesville, VA, USAIn this work, we experimentally demonstrate an integrated circuit (IC) of 30 relaxation oscillators with reconfigurable capacitive coupling to solve the NP-Hard maximum cut (Max-Cut) problem. We show that under the influence of an external second-harmonic injection signal, the oscillator phases exhibit a bipartition that can be used to calculate a high-quality approximate Max-Cut solution. Leveraging the all-to-all reconfigurable coupling architecture, we experimentally evaluate the computational properties of the oscillators using randomly generated graph instances of varying size and edge density (η). Furthermore, comparing the Max-Cut solutions with the optimal values, we show that the oscillators (after simple postprocessing) produce a Max-Cut that is within 99% of the optimal value in 28 of the 36 measured graphs; importantly, the oscillators are particularly effective in dense graphs with the Max-Cut being optimal in seven out of nine measured graphs with η = 0.8. Our work marks a step toward creating an efficient, room-temperature-compatible non-Boolean hardware-based solver for hard combinatorial optimization problems.https://ieeexplore.ieee.org/document/9204635/Analogcoupled oscillatorsintegrated circuit (IC)Ising machinesmaximum cut (Max-Cut) |
| spellingShingle | Mohammad Khairul Bashar Antik Mallick Daniel S. Truesdell Benton H. Calhoun Siddharth Joshi Nikhil Shukla Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem IEEE Journal on Exploratory Solid-State Computational Devices and Circuits Analog coupled oscillators integrated circuit (IC) Ising machines maximum cut (Max-Cut) |
| title | Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem |
| title_full | Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem |
| title_fullStr | Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem |
| title_full_unstemmed | Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem |
| title_short | Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem |
| title_sort | experimental demonstration of a reconfigurable coupled oscillator platform to solve the max cut problem |
| topic | Analog coupled oscillators integrated circuit (IC) Ising machines maximum cut (Max-Cut) |
| url | https://ieeexplore.ieee.org/document/9204635/ |
| work_keys_str_mv | AT mohammadkhairulbashar experimentaldemonstrationofareconfigurablecoupledoscillatorplatformtosolvethemaxcutproblem AT antikmallick experimentaldemonstrationofareconfigurablecoupledoscillatorplatformtosolvethemaxcutproblem AT danielstruesdell experimentaldemonstrationofareconfigurablecoupledoscillatorplatformtosolvethemaxcutproblem AT bentonhcalhoun experimentaldemonstrationofareconfigurablecoupledoscillatorplatformtosolvethemaxcutproblem AT siddharthjoshi experimentaldemonstrationofareconfigurablecoupledoscillatorplatformtosolvethemaxcutproblem AT nikhilshukla experimentaldemonstrationofareconfigurablecoupledoscillatorplatformtosolvethemaxcutproblem |