Browsing by Subject "Quantum-Inspired"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Quantum-Inspired coupled oscillator computing in CMOS
    (2023-01) Moy, William
    Combinatorial optimization problems (COPs) occur in a variety of fields including logistics, resource allocation, communication network design, finance, drug discovery, and transportation systems. Digital computers based on a von Neumann architecture often struggle to solve COPs quickly and efficiently due to the need for exponential computational power. Several COPs can be solved using a formulation known as the quadratic unconstrained binary optimization (QUBO) problem. The QUBO formulation covers problems ranging from max-cut to graph coloring and has parallels in machine learning and neuromorphic computing. Software algorithms solve a QUBO problem by modeling it as the Ising spin glass model and updating the spin states in an iterative and probabilistic manner until a satisfactory ground state is found. The Ising model describes the behavior of ferromagnets and works on minimizing the energy level of coupled spins through a Hamiltonian cost function. Within the Ising model, si represents the spin value of node i with si ∈{+1,−1} and Jij represents the coupling between spins si and sj. Visualization of the Ising model is frequently represented by a mathematical graph structure with spins represented by nodes and coupling represented by edges. The solution to a QUBO problem is the combination of spins that minimizes the Ising Hamiltonian cost function: H(s) = ∑ Jijsisj. Although directly solving an Ising model can be inefficient with a digital computer, a physical representation of the Ising model can overcome these inefficiencies by simply letting a network of coupled oscillator circuits resolve to a low Hamiltonian state. The optimization problem, which can be defined by vertices (spins) and edge weights (that is, coupling) of a graph, is converted to a locally connected architecture compatible with the Ising hardware. Once the weights of the Ising hardware are programmed, the oscillator network naturally resolves to the ground state, with the oscillator phases representing the spin states. Simple error-correction and post-processing algorithms may be used to convert the phase information to the final solution of the original COP. Three hardware designs using coupled oscillators were created in CMOS. The first design was a 1,968 spin King’s graph architecture and expanded on previous works by increasing the connectivity, size, and coupling resolution. Connectivity was expanded from hexagonal to a King’s graph architecture. The number of oscillators per die was increased to a state-of-the-art 1,968 spins, and coupling resolution was increased to a first-of-its-kind 5-levels. Additionally, the first design revolutionized the coupling methodology of coupled oscillators through transmission gates. The design allowed for a compact multi-bit resolution that did not need a non-standard cell circuit layout. Our second coupled oscillator design expanded upon the coupling resolution of the first coupled oscillator design at the expense of spin count. The coupling was increased to 15 levels while the spin count was decreased to 1,024 spins. Additional coupling resolution increased circuit size, dramatically limiting spin count. The final third design combined high-resolution coupling with high connectivity through a 59 spin all-to-all coupled oscillator Ising machine. The design used a unique delay-based coupling circuit that significantly lowered static power compared to transmission gate couplings. Additionally, the all-to-all connectivity allowed all spins to interact, giving maximum problem-solving flexibility.