betaFeedback

WorksComputer Science

HETRI: Heterogeneous Ising Multiprocessing

Abstract

Ising machines are effective solvers for complex combinatorial optimization problems. The idea is mapping the optimal solution(s) to a combinatorial optimization problem to the minimum energy state(s) of a physical system, which naturally converges to a minimum energy state upon perturbance. The underlying mathematical abstraction, the Ising model, can capture the dynamic behavior of different physical systems by mapping each problem variable to a spin which can interact with other spins. Ising model as a mathematical abstraction can be mapped to hardware using traditional devices. In this paper we instead focus on Ising machines which represent a network of physical spins directly implemented in hardware using, e.g., quantum bits or electronic oscillators. To eliminate the scalability bottleneck due to the mismatch in problem vs. Ising machine size and connectivity, in this paper we make the case for HETRI: Heterogeneous Ising Multiprocessing. HETRI organizes the maximum number of physical spins that the underlying technology supports in Ising cores; and multiple independent Ising cores, in Ising chips. Ising cores in a chip feature different inter-spin connectivity or spin counts to match the problem characteristics. We provide a detailed design space exploration and quantify the performance in terms of time or energy to solution and solution accuracy with respect to homogeneous alternatives under the very same hardware budget and considering the very same spin technology.

Introduction

Combinatorial optimization problems represent a broad class of real-world problems with numerous applications in machine learning, robotics, and bioinformatics. Many such problems are NP-complete or NP-hard, and the computational resources required to solve them on von Neumann machines grow rapidly with problem size. The Ising model represents a promising alternative, where the optimal solution(s) to a combinatorial optimization problem are mapped to the minimum-energy state(s) of a physical system—a network of discrete spins that naturally converges to equilibrium upon perturbation. In this mapping, problem variables correspond to spins, and variable interactions to physical spin-to-spin connections.

Ising machines differ from each other primarily by their inter-spin connectivity and the number of physical spins they support. Densely connected machines can directly express arbitrary variable interactions but support far fewer physical spins under the same hardware budget. Sparsely connected machines accommodate more physical spins but must chain several of them together to represent a single problem variable

when a problem needs connections the machine lacks, yielding a larger and often harder problem to solve. We analyze this tradeoff in detail in Section III-A.

As the connectivity graphs in Figure 1 show, combinatorial optimization problems of practical importance exhibit diverse interaction patterns that no single fixed machine connectivity realizes efficiently. Figure 1a shows a planar Maximum Independent Set (MIS) instance, where the goal is to find the largest subset of vertices with no edges between them, with interactions limited to nearest neighbors in a mesh. Figure 1b shows a 3SAT instance, where the goal is to find Boolean variable assignments that satisfy a given formula. Figure 1c shows a nonplanar MIS instance, where the same problem without the planarity constraint produces far denser interactions.

Figure 1. Representative problem connectivity graphs: (a) Planar MIS, (b) 3SAT, (c) Nonplanar MIS. Each dot corresponds to a spin, and each edge to a spin-to-spin coupling.

At the same time, physical constraints bound both the number of spins and the physical links between them for any given connectivity. These limits vary across technologies, but each admits a maximum physical spin count, NmaxN_{max}, that is unlikely to keep pace with growing problem sizes. When the required number of physical spins exceeds machine capacity, the problem must be decomposed into subproblems, which is itself complex because of the data dependencies between them (Section II).

Prior work has scaled Ising machines in three main ways: increasing connectivity toward all-to-all [1], [2], scaling spin count within a fixed topology on one chip or across many [3]–[7], or making a single chip reconfigurable [8]. All of these scale within a single connectivity model. Whether different connectivity classes should instead coexist on one chip is a different question, and it has not been answerable: comparing connectivities at a matched hardware budget would mean fabricating one chip per topology, and physics-accurate simulation cannot reach the scale a workload study requires. This paper introduces HETRI: Heterogeneous Ising Multiprocessing, which addresses this mismatch by integrating independent Ising cores of diverse connectivity on one chip and mapping each problem or decomposed subproblem to the core whose connectivity best matches its structure. Under an iso-area budget, this reduces workload completion time by 2.6× on geometric average, and by up to 19×, relative to the best homogeneous alternative for each workload.

In summary, this paper makes the following contributions:

  • We build the exploration flow that makes the question answerable: a synthesizable Ising emulator that exposes the physical cost of connectivity, and a solver study that establishes what can be run at workload scale.

  • We show that no single topology is best across mixed workloads, and that the favorable choice does not follow from a problem’s nominal parameters in any simple way.

  • We show that a single middle-ground topology does not resolve the mismatch either, which motivates independent cores of fundamentally different connectivity.

  • We propose two schedulers that make the problem–core assignment from information a system already has, before or after the Ising mapping, and show that the density-based one recovers essentially the same makespan as an oracle with per-instance knowledge.

Section II covers background on the Ising model and problem decomposition. Section III introduces the HETRI architecture, core independence, and scheduling policies. Section IV describes the emulation framework and evaluation methodology. Section V presents the quantitative analysis. Section VI discusses related work, and Section VII concludes.

Background

Ising Model [9, 10, 11, 12] models a system of pairwise-interacting spins. A Hamiltonian function captures the energy of an nn-spin system with s=[s1,s2,...,sn]\mathbf{s} = [s_1, s_2, ..., s_n] as:

H(s)=−∑⟨i≠j⟩Jijsisj−∑ihisiwhere i,j∈[1,2,...,n]H(\mathbf{s}) = - \sum_{\langle i\ne j\rangle} J_{ij}s_i s_j - \sum_i h_i s_i \quad\text{where } i,j \in[1,2,...,n]

sis_i can be either −1-1 or +1+1. hih_i denotes the local field at spin ii, and JijJ_{ij}, the interaction strength between spins ii and jj. hih_i and JijJ_{ij} are real-valued constants. The system evolves toward low-energy states that minimize H(s)H(\mathbf{s}) at equilibrium. Positive JijJ_{ij} favors aligned spins, while negative JijJ_{ij} favors anti-aligned spins. The Ising model is isomorphic to Quadratic Unconstrained Binary Optimization (QUBO), given by

H(x)=xTQxwhere xi=(si+1)/2H(\mathbf{x}) = \mathbf{x}^{T}Q\mathbf{x} \quad\text{where } x_i = (s_i+1)/2

for x=[x1,⋯ ,xn]T∈{0,1}n\mathbf{x} = [x_1,\cdots,x_n]^T \in\{0,1\}^n and Q∈Rn×nQ \in\mathbb{R}^{n\times n}.

We distinguish between logical spins, which correspond to variables in the Ising/QUBO formulation of a given problem, and physical spins, which correspond to the actual hardware implementation. Ideally, each logical spin maps to exactly one physical spin, but limited-connectivity machines may require multiple physical spins to represent a single logical spin (Section III-A).

Problem formulation maps problem variables to binary-valued spins; problem constraints, to pairwise interactions (JijJ_{ij}) and local fields (hih_i). Many important NP-complete/hard problems, including all of Karp’s 21 NP-complete problems, admit Ising formulations [13]. The goal is for the minimum-energy state(s) to encode the optimal solution(s), which an Ising-compliant physical system can reach through its convergence dynamics [14].

For a given optimization problem, multiple Ising or QUBO formulations may exist. Because these models primarily capture pairwise interactions, higher-order interactions must be reduced to pairwise ones, often by introducing ancillary variables. This, for instance, is the case for 3SAT, where a Boolean formula of mm clauses over nn variables must be satisfied. Because each clause is a three-way constraint, the QUBO formulation of [15] introduces one ancillary variable per clause, producing an (m+n)(m+n)-variable problem. The mapped problem is therefore larger than the original, and its structure depends on the ratio of clauses to variables.

Ising Model based solvers in software and hardware follow different approaches in implementing convergence dynamics. Exhaustive search over all spin assignments scales as 2n2^n and is infeasible for problems of practical size; even at an optimistic 10 GHz with one configuration evaluated per cycle, a 50-variable problem would require roughly a day of enumeration and a 60-variable problem several years. Solvers in software therefore rely on probabilistic pruning of the search space, typically using variants of simulated annealing [17], which probabilistically flips selected spin states at each step following predefined convergence criteria. Tabu search [18] is another general-purpose metaheuristic for QUBO/Ising problems, which iteratively flips spins while maintaining a list of recently visited states to avoid cycling. Solvers in hardware form two broad classes. One class [6, 19, 20, 21, 22, 23] implements these search procedures directly in hardware. The other directly implements Ising-model-compliant physical systems, spanning quantum [24, 25] and quantum-inspired designs [1, 2, 3, 26, 27, 28, 29]. In the second class the underlying physical system determines the time evolution of spin states, and the time allocated for convergence is the annealing time. We focus on this class, which we refer to as Ising machines. A prominent family builds each spin as an electronic oscillator, encoding the spin state in the oscillator’s phase and realizing JijJ_{ij} as a coupling between oscillator pairs; we refer to these as oscillator-based Ising machines (OIMs) [1, 2, 3]. Ising machines primarily differ from each other by their physical connectivity, which ranges from sparse nearest-neighbor graphs to all-to-all (Figure 2). Table I lists three fabricated examples spanning that range in the same 65nm process.

Figure 2. Representative Ising machine connectivity: (a) All-to-all (A2A), (b) Hybrid, (c) King’s Graph.

Problem decomposition partitions a large problem that exceeds the Ising machine capacity into smaller subproblems that fit within the machine. It becomes necessary as problem sizes grow beyond the spin count supported by a given topology. In the best case, the problem decomposes into independent subproblems that can be solved independently on separate Ising cores. This usually is not possible: subproblems typically depend on each other through shared variables, so the solution to one affects the other, prohibiting subproblem-level parallelism.

For each subproblem, the variables not included must still be accounted for. A common practical approach is clamping, which sets the corresponding spins in the Ising formulation to known values, typically taken from previously solved subproblems. If, for example, a subproblem covers spin sjs_j, but not sis_i, by setting sis_i to (−)1(-)1, the JijsisjJ_{ij}s_is_j term would reduce to (−)Jijsj(-)J_{ij}s_j, which we can account for, without breaking the Ising formulation, by updating the local field coefficient hjh_j to (−)Jij+hj(-)J_{ij}+h_j.

Ising solvers are probabilistic and typically iterate over multiple, possibly overlapping subproblems to cover all problem variables, solving each subproblem a preset number of times. The decomposition algorithm dictates how problem variables get picked in forming subproblems, which has a big impact on solver performance. Divide-and-conquer decomposition is common, with variants that either ignore [5] or consider problem connectivity [30].

The efficiency of an Ising machine depends on how well its connectivity matches the target problem. We first analyze the tradeoff between connectivity and capacity (Section III-A), then present the HETRI architecture (Section III-B) and its workload scheduling policy (Section III-C).

The Connectivity-Capacity Tradeoff

Implementing the interaction strength JijJ_{ij} requires a physical connection – a coupler – between spins ii and jj, and the number of couplers scales fundamentally differently across topologies. An all-to-all (A2A) machine requires N(N−1)/2N(N-1)/2 couplers for NN spins, scaling as O(N2)O(N^2). A King’s graph, where each spin connects to at most eight nearest neighbors, requires at most 4N4N couplers, scaling as O(N)O(N). Every coupler consumes chip area, wiring tracks, and power. In A2A each additional spin must connect to every existing spin, so the marginal cost of adding a spin grows with NN; in a King’s graph each additional spin connects to a fixed number of neighbors, so the marginal cost stays constant. Under a fixed area budget, NmaxN_{max} therefore scales as budget\sqrt{\textit{budget}} for A2A but linearly for King’s graph. Table 1 shows the consequence in silicon: 1968 spins for King’s graph versus 48 for A2A at comparable area in the same 65nm process. These are not a controlled comparison – the designs differ in spin and coupler implementation and in coefficient precision – but the direction is unambiguous: sparse connectivity buys far more spins under a comparable budget.

A2AHybridKing’s
Physical spins (NmaxN_{max})486001968
Area (mm²)1.84.02.1
Links per spin471118
Technology65nm CMOS65nm CMOS65nm CMOS
Reference[1][16][3]

Table 1. Machine connectivity vs. maximum spin count NmaxN_{max} of three representative Ising machines in the same technology.

Sparse topologies avoid the quadratic scaling of all-to-all connectivity, but introduce a different cost: embedding. A2A machines map arbitrary JijJ_{ij} values directly, since a physical link exists between every pair of spins, so embedding is an identity mapping with zero overhead. For any connectivity sparser than A2A, some logical spins require more connections than a single physical spin can support. The solution is to replicate the logical spin across several physical spins forming a strongly coupled chain, as illustrated in Figure 3. The strong coupling keeps chain members in the same state, while their combined connections serve the actual problem couplings. Finding a valid chain assignment – which logical spins to replicate, where to place each chain, and how to avoid conflicts between chains competing for the same physical spins – is a graph minor embedding problem, NP-complete/hard in general [31, 32].

Figure 3. Problem connectivity graph capturing problem variable interactions (a), and its embedding onto an Ising machine with limited connectivity (b). Each spin corresponds to a node; each edge in (b), to a physical link. In (b), logical spin s1s_1 requires more connections than a single physical spin can support, so it is replicated across four physical spins, forming a strongly coupled chain.

Beyond the cost of finding an embedding, the duplication carries a physical cost. Each replica consumes a physical spin that could otherwise represent a problem variable, the strong intra-chain coupling slows convergence [33], and chain coherence becomes harder to maintain as chains grow longer [34, 35]. As a representative example, a sparse machine with degree-6 connectivity and ~2000 physical spins can embed a fully connected problem of only ~65 logical variables [35], a physical-to-logical ratio exceeding 30:1. Increasing spin count by reducing connectivity therefore does not translate unconditionally into higher problem capacity. For dense problems, a King’s graph may need chains of tens of physical spins per logical spin, spending most of its budget on replication rather than on problem variables. For sparse problems, A2A spends its expensive coupler budget on links the problem never uses, while its limited spin capacity cannot hold even moderately sized instances. The effective capacity of an Ising machine is thus not a fixed property of the hardware, but a function of the problem it is given.

A middle-ground topology is the natural response. The Hybrid graph of [16], where spins form all-to-all connected tiles with sparse inter-tile links, scales linearly in couplers like a King’s graph but with a larger constant, and retains dense local connectivity. It also inherits limitations from both extremes. The intra-tile A2A couplers still limit spin count relative to a purely sparse machine, while the sparse inter-tile links still require embedding for problems whose connectivity spans multiple tiles. The tiled structure also introduces a convergence pathology: spins within an A2A tile synchronize rapidly and lock into a collective state that behaves as a single rigid spin, and the sparse inter-tile links lack the coupling strength to perturb these locked clusters, making it hard to escape local minima. As observed experimentally in [16], this yields fast convergence to a near-optimal solution but requires repeated perturbation to reach the true optimum. The remedy is therefore not a compromise inside one core, but independent cores of fundamentally different connectivity, each operating where it is most effective. This is the insight behind HETRI.

HETRI Architecture

HETRI is a heterogeneous multi-core Ising architecture: a single chip that places several independent Ising cores of different connectivity side by side, with a scheduler that routes each problem to the core whose connectivity best fits it. We refer to each network of Nmax⁡N_{\max} spins as an Ising core, where Nmax⁡N_{\max} is a function of the network topology (Section III-A). A HETRI chip features NcoreN_{\mathrm{core}} such cores, differing in connectivity. Figure 4 illustrates example 6-core designs built from A2A, Hybrid, and King’s-graph cores. Even with three topology types and six cores, the design space spans three homogeneous and twenty-five heterogeneous configurations, each trading aggregate spin capacity against embedding flexibility and workload coverage; we evaluate representative mixes from this space. As the number of topology types or cores grows, this space expands combinatorially.

Figure 4. 6-core Ising multiprocessor design space with homogeneous baselines and heterogeneous HETRI core mixes. Figure 12 evaluates these same design points under different dispatch policies.

HETRI cores are independent by definition: there is no physical connection between them. Connecting cores would recreate a Hybrid-like topology at larger scale, reintroducing the problems of Section III-A. The coupling strength between cores cannot escape this. If it is weak, shared spins drift and the solution breaks; if it is strong enough to hold them together, the coupled cores lock into the same rigid clusters that slow a Hybrid core. Either way, coupling cores rebuilds the middle ground rather than avoiding it. Instead, HETRI embraces decomposition. A problem too large for a single core is decomposed into subproblems, each sized to fit one core. Each subproblem is then self-contained, carrying its own spin variables, interaction strengths, and local fields, with the variables it omits accounted for through clamping (Section II). This solve-and-clamp workflow is already standard practice for Ising machines that exceed single-core capacity [30, 36], and HETRI’s independent cores align with it naturally: each core solves its assigned subproblem without knowledge of the others. There is no shared memory, no inter-core synchronization, and no communication bus; the only coordination happens at the scheduler, which assigns subproblems to cores before computation begins.

The central design question is the composition of the core mix: for a given NcoreN_{\mathrm{core}}, how many cores of each connectivity type should the chip carry? Sparse problems tend to favor sparse cores that exploit their higher spin capacity, while denser problems favor more directly connected cores. If a workload consisted of a single problem type with known structure, the choice would be clear. In practice workloads are diverse, and different instances within the same family can exhibit substantially different interaction patterns. That diversity persists after decomposition, since neighborhood-based decomposers such as BFS traversal [30] preserve much of the original connectivity structure. Allocating too many cores of one topology wastes silicon when the workload shifts, while allocating too few forces problems onto mismatched cores. No single homogeneous design covers this spectrum, and among heterogeneous mixes the strongest span the connectivity extremes. We explore this design space quantitatively in § 7.

The core mix is further constrained by physical realities. Different topologies yield very different spin counts under the same budget, and the differences extend beyond coupler counts to area, power, routing congestion, and programming overhead. These costs are nonlinear, and a topology competitive at small spin counts may be impractical at larger ones. They are not captured by the Ising model and cannot be derived from the connectivity graph alone, which is why we introduce a synthesizable emulator in Section IV-A.

Workload Scheduling

A heterogeneous core mix is only useful if each problem can be routed to a core whose connectivity suits it. The cost of a mismatch is not a constant factor: a densely connected instance placed on a sparse core spends its spin budget replicating logical spins into chains rather than representing problem variables (Section III-A), so the penalty grows with the mismatch. A scheduler makes that routing decision, and the less it needs to know to make it, the more practical the architecture becomes. We evaluate three dispatch policies over a shared problem pool, each with access to less information than the one before it.

The oracle scheduler assigns every instance to its individually fastest core, using the true topology-specific TTS of each. It cannot be built, and it establishes whether routing problems to suitable cores is worth doing at all.

The history-based scheduler tests whether coarse information about the problem is enough. It operates before the Ising mapping, using only the problem as posed: its family and its generating parameter. For each such combination it records the median TTS measured on each topology in past runs and ranks the topologies accordingly. It fits no model; the table stores measured medians and nothing else, and is built once offline.

The density-based scheduler tests whether the problem needs to be identified at all. It operates after the mapping, computing the coupling density of the delivered QUBO, the fraction of nonzero pairwise couplings, and mapping the instance to a low-, medium-, or high-density regime, each carrying its own topology ranking. No model is fitted: the regime boundaries are read off the measured sweeps of § 7-B.

Both proposed policies produce a per-job topology ranking, and both feed the same dispatch loop. Jobs sit in a shared pool; whenever a core becomes free it takes the shortest available job for which its own topology ranks highest, where job length is the median already tabulated for that job’s class rather than a per-instance measurement, falling back to lower-ranked jobs if none remain. Homogeneous systems reduce to conventional load balancing, since every core has the same topology and all rankings are equal. Both tables are built from the same instance pool the workloads draw from, but hold only per-class medians, so no job’s own solve time affects its dispatch; the reported makespan uses true per-instance times the scheduler never sees.

Methodology

Evaluating HETRI requires knowing what Ising core topologies cost in hardware, and how well they solve problems of diverse structure. We address the first with a fully digital, synthesizable Ising-machine emulator (Section IV-A), and the second with an architectural simulation framework (Section IV-B), benchmark problems spanning diverse connectivity patterns (Section IV-C), HETRI configurations and fairness criteria (Section IV-D), and evaluation metrics (Section IV-E).

Digital Ising Emulator

Isolating the connectivity-capacity tradeoff requires many machines that differ only in connectivity, with spin and coupler resources held equal. Capturing these effects in analog Ising machines would require full-custom chip design for each topology, which does not lend itself to rapid architectural exploration [1, 2, 3]. Existing silicon does not close the gap either. Published machines in the same 65nm CMOS process [1], [3], [16]confirm that topology governs spin capacity under comparable area (Table I), but they differ in spin and coupler implementation and in coefficient precision, so their spin counts cannot be compared directly.

We therefore develop a fully digital, synthesizable Ising-machine emulator. It implements the dynamics of oscillator-based Ising machines (OIMs) and gives every spin and every coupling its own circuit. Unlike digital annealers, which hold coupling coefficients in memory and apply them with shared update logic [20], [37], no coupling here is stored or shared during annealing, so area and routing scale with the problem graph, while the fully digital design can be processed by an automated RTL-to-GDS flow. Holding the spin and coupler implementation, coefficient precision, and design flow constant while varying only the connectivity is what makes topologies comparable at a matched budget. It can be parameterized by connectivity type and spin count. Algorithm 1 and Figure 5 detail the emulator’s building blocks.

Figure 5. Digital Ising-machine emulator architecture. Each spin is implemented as a variable-delay element, while peer couplers monitor relative phases and adjust delays to drive spins toward the target coupling.

The emulator and an analog OIM implement the same model. Both follow the Kuramoto dynamics commonly used to describe OIMs [38], under which each spin’s phase evolves as

ϕ˙i=Ac∑jJijtanh⁡(ksin⁡(ϕi−ϕj))−Assin⁡(2ϕi)(1)\dot{\phi}_i = A_c \sum_j J_{ij}\tanh\left(k\sin(\phi_i-\phi_j)\right) - A_s\sin(2\phi_i) \tag*{(1)}

where ϕi\phi_i is the phase of spin ii, JijJ_{ij} is the coupling coefficient of § 2, AcA_c and AsA_s set the coupling and sub-harmonic injection locking (SHIL) strengths, and kk controls how sharply the coupling switches. In Eq. (1), the coupling term drives each spin toward or away from its neighbor by the sign of

Algorithm 1 Digital Ising Emulator Building Blocks

1: Spin stage (variable-delay element):
2: Q[0..4] ← 5-stage DFF shift register driven by in
3: safe ← (Q[2]=Q[3]) ∧ (Q[3]=Q[4])
4: If safe: tap ← delay[1:0]; out ← Q[2+tap] {0=fast, 1=normal, 2=slow}
5: Peer coupler (in₁, in₂, J, en → delay₁, delay₂):
6: chg₁ ← in₁ ⊕ in₁ᵖʳᵉᵛ; chg₂ ← in₂ ⊕ in₂ᵖʳᵉᵛ; diff ← in₁ ⊕ in₂
7: if chg₁ ∧ ¬chg₂ then
8:   delay₁ ← (J ⊕ diff) ? fast : slow
9: else if chg₂ ∧ ¬chg₁ then
10:   delay₂ ← (J ⊕ diff) ? fast : slow
11: else if chg₁ ∧ chg₂ then
12:   delay₁,₂ ← (J ⊕ diff) ? [normal, normal] : [slow, fast]
13: end if
14: N-oscillator A2A core (illustrated for N=3):
15: Load Jᵢⱼ and enable bits via scan chain
16: for each pair (i, j) ∈ {(0, 1), (0, 2), (1, 2)} do
17:   Coupler(i, j) observes spinᵢ[0], spinⱼ[0] → dᵢⱼ, dⱼᵢ
18: end for
19: Delay busᵢ = [nominal, dᵢ,¬ᵢ]; Oscillatorᵢ = spin-stage chain on busᵢ
20: osc_out[i] ← spinᵢ[3] ∧ enᵢ; Readout via scan chain

their phase difference, which the emulator implements as its J⊕diffJ \oplus diff decision. The SHIL locking term forces each phase to one of two stable values ({0,π}\{0,\pi\}), which the emulator enforces through the spin’s bistable state. Together these mechanisms drive the coupled system toward minima of the Ising Hamiltonian of Section II. We verify this correspondence by simulating a cycle-accurate model of the RTL on random problem instances: the emulator reaches the same solutions as a continuous Kuramoto solver, Tabu search, and a fabricated Ising chip (Section IV-B).

We instantiate the emulator for A2A, Hybrid, and King’s-graph topologies across a range of spin counts using the Sky130 open process. The RTL-to-GDS flow is automated with LibreLane [39], while OpenROAD [40] performs placement, routing, and layout generation. For each topology and spin-count configuration, this flow produces a complete backend implementation from which we extract physical-design metrics including area, power, wire length, and cell count.

At equal spin count, the topologies occupy visibly different areas (Figure 6). We use the synthesized backend data to identify iso-area operating points across topologies and to define the fixed hardware configurations used in the evaluation, reported in Section V.

Synthesized Sky130 layouts for emulator-generated 60-spin Ising cores with A2A, Hybrid, and King’s-graph topologies

Figure 6. Synthesized Sky130 layouts for emulator-generated 60-spin Ising cores with A2A, Hybrid, and King’s-graph topologies.

Simulation Framework

While HETRI applies to any Ising machine technology, we ground our evaluation in oscillator-based Ising machines (OIMs), which represent a leading class of CMOS-compatible Ising hardware with multiple fabricated designs at different connectivity points [1, 3, 16]. Evaluating HETRI requires

solving thousands of QUBO instances across different problem sizes, densities, hardware topologies, and decomposition settings.

Two facts shape our choice of solver. The more of an Ising machine’s hardware a tool reproduces, the slower it runs; Figure 7 shows the resulting ordering across a physics-accurate simulator [41], our emulator, a continuous Kuramoto integrator, and Tabu search [18], all run on the same instances on the same machine. The physics-accurate simulator does not reach the reference solution beyond ten spins within a 100 s budget, and our emulator saturates at 45 spins. But solving an Ising problem does not require reproducing hardware at all. Tabu search models no Ising machine, reaches the same solutions as the others, and remains fast enough for thousands of instances, so we use it as the solver for the main study.

Figure 7. Time to first reach the reference solution, by problem size. Solver times are CPU wall clock on one machine; the chip figure is measured anneal time and is not comparable to them. Instances are random Ising problems spanning sizes and coupling densities.

The figure also includes a fabricated 28nm CMOS Ising chip, a reference point for what dedicated hardware achieves. It sweeps problem size but not design: one topology, 45 spins. Exploring the space would need a chip per point.

What the evaluation studies is the consequence of a hardware constraint rather than the behavior of a solver. Each subproblem is restricted to what one core can hold: its physical spin count, and its connectivity after embedding. A problem exceeding that is decomposed into subproblems that fit, and each round issues one such subproblem to one core and receives one solution back. Any engine that solves at core size can serve that call, which is what Figure 7 shows. Prior work has also shown that Tabu-search-based software workflows closely track the iteration-level behavior of fabricated oscillator-based Ising chips on the same problem instances [30]. The round count that Section IV-E converts into core time therefore reflects the mapping—embedding overhead, effective problem size increase due to spin replication inflation, and connectivity mismatch—rather than the engine that served the call.

For non-A2A cores, each problem is first embedded onto the target connectivity graph via graph minor embedding, inflating the problem by replicating logical spins across physical chains (Section III-A). The embedded problem is then solved by Tabu search, and the resulting number of solve-and-clamp rounds reflects the difficulty of the inflated problem on that topology. Tabu reaches these solutions within one to two milliseconds across the sizes evaluated, so each subproblem solve is allowed three milliseconds. A much longer 5000 ms run provides the reference energy against which all topologies are compared (Section IV-E).

For problem decomposition, we adapt the BFS-based decomposer from [30]. Starting from a random root node, the decomposer traverses the problem connectivity graph via BFS to form an ordered local neighborhood of variables. Variables outside the selected neighborhood are clamped to their best-known values, folding their contributions into the local field coefficients of the remaining variables (§ 2). The scheduling policy of Section III-C runs on top of this framework for both homogeneous and heterogeneous HETRI configurations.

Benchmarks

We evaluate HETRI using benchmark families that span a broad range of connectivity patterns and problem classes, including graph-based QUBO instances and SAT-derived QUBO instances. To enable controlled comparison across families, we normalize all constructed QUBO instances to 50 logical variables. This size balances two constraints. Validating solver behavior against physics-level models becomes impractical beyond a few tens of spins (Figure 7), while a 50-variable problem already expands to several hundred physical spins once embedded onto a sparse topology.

We consider three graph-based QUBO instance families. Erdős–Rényi (er) graphs [42] approximate homogeneous random interaction patterns [43, 44], and we sweep graph density from 0.01 to 0.64. Barabási–Albert (ba) graphs [42] model growing networks with preferential attachment [43, 45], and we sweep the attachment parameter mm from 1 to 32. Power-Law Cluster (pow) graphs [46] capture heavy-tailed connectivity with clustering [43, 47]; we fix the triad-formation probability to 0.5 and sweep mm from 1 to 16, with an additional dense point at m=32m = 32. For SAT-derived QUBO benchmarks (sat), we use the formulation from [15] and sweep the clause-to-variable ratio α\alpha from 0.5 to 5.0 in increments of 0.25. Across these families, we generate

several thousand random problem instances. Figure 8 shows representative adjacency matrices spanning this range.

Figure 8. Representative benchmark connectivity patterns, shown as adjacency matrices, one family per row: (a)–(c) Erdős–Rényi, (d)–(f) Barabási–Albert, (g)–(i) Power-Law Cluster, and (j)–(l) SAT-derived QUBO instances.

From these families we construct 15 workloads, one for every non-empty combination of the four families: the four single-family workloads, six pairs, four triples, and one containing all four. This lets us evaluate topology matching both within a single benchmark class and across mixed workloads, and later assess how effectively the scheduler exploits topology diversity.

Compared Configurations and Fairness Criteria

This paper is not about the design of a specific Ising core, but about an architectural principle that applies across Ising core implementations. Any design can serve as a component core of HETRI, provided it uses the same underlying technology while exposing substantially different connectivity. We base our evaluation on three representative oscillator-based organizations that satisfy these criteria: A2A, Hybrid, and King’s graph [1, 3, 16], each demonstrated in silicon (Table I). These three bound the tradeoff rather than sample it. A2A and King’s graph sit at opposite ends of the connectivity–capacity range, the densest practical connectivity and one of the sparsest, so they bracket the regime the design question lives in. Hybrid is included as a control rather than as a third design point: it tests whether a single compromise topology can achieve what HETRI achieves with independent cores, and Section V-B shows that it cannot.

Our primary fairness criterion is iso-area comparison. Rather than forcing all topologies to use the same spin count, we match them by hardware budget using the synthesized backend data from the emulator, so that performance differences reflect topology rather than unequal area allocation. We additionally check total power at the matched points, so that an area match does not conceal a power imbalance. The specific operating points and the resulting power spread are reported in Section V.

At the system level, we compare both homogeneous and heterogeneous HETRI organizations. This lets us evaluate not only which topology is favorable for a given problem regime, but also whether mixing complementary topologies improves coverage across diverse workloads.

Metrics

We evaluate HETRI using time-to-solution (TTS), which captures how quickly a hardware configuration reaches a target solution. Because the solver is stochastic, we evaluate each problem–hardware pair over 128 repeated trials and aggregate the outcomes.

Physical annealing time cannot be measured directly from the RTL, and how long an Ising machine must anneal to reach the reference solution is not predictable in advance, so we model core time with a topology-dependent proxy: each solve-and-clamp round is charged one traversal of the core’s oscillator chain. For each topology,

Titer=Nstages×Tclk,(2)T_{\mathrm{iter}} = N_{\mathrm{stages}} \times T_{\mathrm{clk}}, \tag*{(2)}

where NstagesN_{\mathrm{stages}} is the number of variable-delay elements forming a spin’s oscillator in the synthesized core and TclkT_{\mathrm{clk}} is the clock period, since a spin advances one stage per clock cycle. A spin needs one delay element per coupling it participates in, plus a nominal element (Algorithm 1), so NstagesN_{\mathrm{stages}} follows the topology’s degree rather than its spin count. All three cores are synthesized at a common period of Tclk=50T_{\mathrm{clk}} = 50 ns, which is the value used throughout. Coefficient programming and spin readout are handled by parallel scan chains of fixed depth, whose area and power cost is already carried by the synthesized designs; their latency is a constant independent of spin count and topology, so it does not enter the per-iteration model. Rounds are converted to core time as

Tcore=Nrounds×Titer.(3)T_{\mathrm{core}} = N_{\mathrm{rounds}} \times T_{\mathrm{iter}}. \tag*{(3)}

Because TclkT_{\mathrm{clk}} is common to all three topologies, it scales every configuration equally and the relative TTS rankings that drive our conclusions do not depend on its exact value.

Exhaustive enumeration of a 50-variable instance would take about a day (Section II), and we generate several thousand, so we define a reference target energy for each using the same Tabu engine with a much longer timeout of 5000 milliseconds. Topology-specific runs then use the 3 millisecond timeout of Section IV-B, and configurations are compared by how quickly they reach this common reference. All topologies are therefore measured against the same target, and differences reflect speed rather than solution quality.

Given a target success probability ptargetp_{\mathrm{target}}, we compute TTS in the standard form [48]

TTS⁡(t)=t⋅log⁡(1−ptarget)log⁡(1−p(t)),(4)\operatorname{TTS}(t) = t \cdot\frac{\log(1-p_{\mathrm{target}})}{\log(1-p(t))}, \tag*{(4)}

where t=Tcoret = T_{\mathrm{core}} is the core completion time of a trial and p(t)p(t) is the empirical probability of reaching the reference energy within time tt. We set ptarget=0.95p_{\mathrm{target}} = 0.95 and report the minimum of (4) over the observed completion times.

A workload is a set of problem instances dispatched across a configuration’s cores by the scheduler of Section III-C. Each instance occupies its assigned core for its TTS, and we report the workload makespan: the time at which the last instance completes. All HETRI results in Section V-C are makespans in this sense. Reported times are chip-time projections from Eqs. 2–4: host-side work, including embedding, decomposition, and scheduling, runs outside the cores and is not counted. That omission is not neutral, since only the non-A2A topologies embed at all, and we therefore compare cores rather than complete systems.

Evaluation

We evaluate HETRI along three dimensions, following the flow of Figure 9: hardware cost, topology matching, and scheduler-driven workload performance.

Figure 9. Evaluation flow. The emulator fixes each topology’s spin count at a matched area budget (Section IV-A); the scheduler assigns problems to cores (Section III-C); each problem is decomposed, embedded, and solved (Section IV-B).

Emulator-Based Hardware Analysis

Figure 10 shows how backend cost scales with spin count for the three topologies synthesized with the flow of Section IV-A. Cost tracks each topology’s coupler count: A2A area grows quadratically with spin count (∼N2\sim N^2), King’s graph near-linearly (∼N\sim N), and Hybrid in between, matching the tradeoff of Section III-A.

Core area and total power versus spin count

Figure 10. Synthesized backend scaling of emulator-generated Ising cores: (a) core area and (b) total power versus spin count. Each point is a distinct synthesized design produced by the same RTL-to-GDS flow.

Table II lists the iso-area operating points selected from these sweeps. At approximately the same core area, the three topologies expose markedly different spin capacities: 34 spins for A2A, 45 for Hybrid, and 144 for King’s graph. The matched points also lie within roughly 17% of one another in total power (39–46 mW), so the comparison is close to iso-power as well, and the workload differences that follow reflect topology rather than silicon or power allocation.

MetricA2AHybridKing’s
Spins3445144
Core area (mm2^2)1.251.261.23
Total power (mW)41.7939.3146.10
Wirelength (mm)163514771440
Total cells (k)70.771.668.8

Table II. Backend comparison of iso-area operating points across A2A, Hybrid, and King’s-graph Ising cores synthesized in Sky130.

These operating points also fix the per-iteration core-time proxy of Eq. (2). Because a spin needs one delay element per coupling, stage count follows degree rather than spin count: the 34-spin A2A design needs 34 stages and the 45-spin Hybrid 35, while the 144-spin King’s-graph design needs only 9. At the 50 ns clock period this yields per-iteration times of 1700 ns, 1750 ns, and 450 ns. The sparse core is therefore both larger in capacity and faster per iteration. At this spin count the Hybrid core’s tiles leave it denser relative to its size than a larger fabricated Hybrid would be, while still requiring embedding for couplings that span tiles. We use these values to convert round counts into core-level time-to-solution.

Problem Density and Topology Matching

Having fixed the hardware budget through Table II, we evaluate the three cores across sweeps spanning a broad range of connectivity regimes. The question is which topology is favorable for which class of problems under the same silicon budget, and whether any homogeneous design remains best across all of them.

Figure 11 shows that topology preference changes systematically with problem structure. Erdős–Rényi instances (a) strongly favor the King’s-graph core while the graph is sparse, with the advantage shifting to A2A as density rises; the crossover falls later here than for the other graph families. Barabási–Albert (b) and Power-Law Cluster (c) show the same one-way pattern, with the shift occurring once connectivity grows beyond the low-mm regime.

Topology-dependent core time-to-solution across benchmark density sweeps

Figure 11. Topology-dependent core time-to-solution across benchmark density sweeps for the iso-area A2A, Hybrid, and King’s-graph cores. Each box shows the distribution over repeated trials; annotations mark the topology with the lowest median TTS in each regime. (a) Erdős–Rényi. (b) Barabási–Albert. (c) Power-Law Cluster. (d) SAT-derived QUBO.

In these three families the homogeneous Hybrid core almost never attains the lowest median TTS. A middle-ground topology therefore does not resolve the connectivity tradeoff. Rather than combining the strengths of both extremes, Hybrid inherits A2A’s capacity limit and a sparse graph’s embedding burden. Capacity and embedding alone account for the result, without invoking the convergence pathology of Section III-A.

SAT-derived instances behave differently (Figure 11(d)). King’s graph is favorable in the sparse regime, A2A takes over across intermediate clause densities, and King’s graph becomes competitive again at high α\alpha. This reversal shows that topology preference is not set by the nominal sweep parameter, but by how the SAT-to-QUBO transformation shapes the resulting interaction graph.

The mapped QUBOs explain why. Characterizing the generated instances directly, the three graph families rise monotonically in QUBO interaction density across their range, reaching 0.64 for Erdős–Rényi and 0.43–0.44 for Barabási–Albert and Power-Law Cluster, matching their one-way crossover. SAT-derived QUBOs instead span a much narrower band and turn over: density rises from 0.08 at α=0.5\alpha= 0.5 to a peak of 0.14 near α=2.5\alpha= 2.5, then falls back to 0.13 by α=5\alpha= 5, while the maximum variable degree keeps climbing from 13 to 27. High-α\alpha instances therefore become degree-skewed rather than uniformly denser, and the point where King’s graph regains the lead coincides with that downturn.

No single homogeneous topology therefore covers all families and density regimes. The favorable choice tracks the structure of the mapped interaction graph rather than the nominal sweep parameter, and that structure is visible in the delivered QUBO itself. § 7-C shows it can be turned into a dispatch rule.

Scheduler-Aware System Evaluation

We compare homogeneous and heterogeneous 6-core HETRI organizations under the three dispatch policies of Section III-C, shown in Figure 12. The question here is not how much benefit a scheduler can extract, but whether the assignment HETRI depends on can be made at all: the oracle establishes that core choice is worth making, and the two proposed schedulers establish that it can be made from information a system actually has.

Figure 12. Average workload makespan across homogeneous baselines and heterogeneous HETRI configurations drawn from the six-core design space of Figure 4, under three scheduling policies. In the legend, a, h, and k denote All-to-all, Hybrid, and King’s-graph cores; two-letter HETRI configurations use three cores of each listed topology, while HETRI (kha) uses two of each. Lower makespan is better.

Under all three policies and on every workload, the lowest makespan is achieved by a heterogeneous organization; no homogeneous A2A-, Hybrid-, or King’s-only system is ever the best of the evaluated configurations. Heterogeneity alone is not sufficient, however. The King’s+Hybrid mix (HETRI-kh) often trails the strongest configurations and at times only matches the homogeneous cores. The strongest configurations pair the connectivity extremes: HETRI-ka, spanning the sparse and dense ends of the range, is the best of the evaluated configurations on nearly all workloads.

Under the oracle (Figure 12(a)), HETRI-ka delivers the lowest makespan by a wide margin on er, ba, and pow: on er it reaches 7.60×10−57.60 \times10^{-5} s against 2.07×10−32.07 \times10^{-3} s for A2A-only and 1.24×10−31.24 \times10^{-3} s for King’s-only. The preferred mix can shift with workload composition: on the mixed er+sat workload the Hybrid+A2A configuration (HETRI-ha) is fastest at 7.64×10−47.64 \times10^{-4} s, ahead of HETRI-ka at 1.51×10−31.51 \times10^{-3} s. A Hybrid core is rarely the best topology alone, yet it can contribute to the best mix when paired with A2A on a workload containing both sparse and dense structure.

The history-based scheduler in Figure 12(b) achieves the same benefit using only the problem’s family and parameter, known before any Ising mapping takes place. Heterogeneous organizations again attain the lowest makespan on every workload, and HETRI-ka is best on all but pow, where HETRI-kha edges ahead with HETRI-ka close behind. The preference for one core over another is therefore already present at the problem level, and a lookup table built once from past runs is enough to exploit it.

The density-based scheduler in Figure 12(c) achieves it again with no family label and no history at all, partitioning the density range into preference zones that order the cores, with a narrow band between zones where the top two are nearly tied. Hybrid is the hardest core for a density rule to place and usually falls in that band, but this costs little, since Hybrid is rarely the optimal target and the zone boundaries sit around the King’s–A2A crossover where makespan is actually determined. Across all 15 workloads it beats every homogeneous baseline, by 2.6× on geometric average and up to 19×. Averaged over all workloads the oracle, history-based, and density-based policies reduce makespan relative to the best homogeneous baseline by 2.4×, 2.3×, and 2.6× respectively, all within roughly 10% of one another. The oracle is not makespan-optimal: it assigns each instance to its individually fastest core, which can leave that core’s queue imbalanced, so a load-balancing policy can occasionally finish sooner while knowing less. The signal that makes the assignment possible therefore survives the mapping to QUBO, and can be read from the coupling matrix of a problem whose origin is unknown.

The precondition HETRI depends on is therefore met at both ends of the problem pipeline. Problem-core matching can be exploited before the Ising mapping, from the problem as posed, and after it, from the delivered QUBO alone. Neither requires per-instance analysis or machinery beyond a load balancer, so HETRI’s advantage is reachable with simple dispatch. Extending these signals to previously unseen problem classes remains open.

Related Work

§ 2 divides Ising solvers in hardware into those that implement search procedures directly [37, 49, 50] and those that implement Ising-model-compliant physical systems. Only the second class exposes physical connectivity as a design variable, so only its members can serve as component HETRI cores; the first remains relevant as prior work on scaling, which we discuss below. The literature is broad and fast-moving; see [51] for a survey.

The closest prior efforts to HETRI scale a single connectivity type. Multi-chip Ising machines tile many instances of one topology to grow capacity. Tatsumura et al. [6] scale out simulated-bifurcation machines with full spin-to-spin connectivity across chips, and Kashimata et al. [4] extend this by overlapping in-chip computation with inter-chip communication to hide the resulting overhead. Others network sparse King’s-graph chips [7] or attach a multi-chip extension to a fully connected annealer [52]. A separate line keeps one chip but makes its connectivity reconfigurable, emulating denser coupling on sparse hardware [8]. All of these hold connectivity uniform across the workload: they grow how large a problem one topology can hold, whereas HETRI varies connectivity across cores to match how different problems are shaped. This is also why HETRI’s cores do not communicate. Coupling independent cores would reintroduce the embedding and convergence penalties of a Hybrid topology at chip scale (Section III-A), trading away the flexibility that heterogeneity provides. A heterogeneous chip can still be replicated and scaled out without coupling its cores, so these capacity-scaling techniques compose with HETRI, but none of them targets the workload-diversity question HETRI addresses.

One multi-chip design [5] also supports an independent mode, in which chips solve separate smaller problems rather than cooperating on one large problem. HETRI shares the independence but not the goal: those chips are identical, so independence buys only throughput, whereas HETRI’s cores differ in connectivity, and independence lets each problem run on the topology that fits it.

Several other efforts are orthogonal to HETRI and can be combined with it: more efficient problem decomposition [30, 53]; more compact problem formulation [54, 55, 56, 57, 58, 59]; models that natively support higher-order interactions [60, 61, 62, 63]; and hardware connectivity or precision optimization [1, 64, 65].

Conclusion

This paper makes the case for HETRI, a heterogeneous Ising multiprocessor in which independent cores of different connectivity share a chip, and a scheduler assigns each problem to the core whose connectivity fits it. The argument rests on three results. First, a single connectivity serves a diverse workload: the favorable topology moves with problem structure, set by the interaction graph that remains after a problem is mapped to the Ising model. Second, a middle-ground topology does not resolve this. A Hybrid core almost never attains the lowest time-to-solution, and among the configurations evaluated the strongest pair the connectivity extremes. Third, the assignment this depends on can be made from information a system actually has: we propose two schedulers, one keyed on the problem’s family and parameters before the Ising mapping and one on the coupling density of the delivered QUBO after it, and both realize the benefit without per-instance analysis.

To reach these results under a controlled hardware budget we built a fully digital, synthesizable Ising-machine emulator, which gives every spin and every coupling its own circuit and therefore exposes the area and routing cost of connectivity in a form that automated design flows can measure. It is the instrument that makes iso-area comparison across topologies possible without fabricating a chip per design point.

The key contribution is an architecture-level insight that applies across Ising core designs, so any such design can serve as a component core in this context. The capacities and speedups reported here are those of the modeled implementation and workload set; what carries beyond them is the architectural principle rather than the numbers. We focused on integrating cores of the same technology but diverse connectivity into a single chip; extending the same principle beyond chip boundaries, subject to hardware resource budgets, remains open.

References

References

  1. [1]H. Lo, W. Moy, H. Yu, S. Sapatnekar, and C. H. Kim, “An Ising solver chip based on coupled ring oscillators with a 48-node all-to-all connected array architecture,” Nature Electronics, vol. 6, no. 10, pp. 771–778, Oct 2023. [Online]. Available: https://doi.org/10.1038/s41928-023-02021-y
  2. [2]H. Cilasun, W. Moy, Z. Zeng, T. Islam, H. Lo, A. Vanasse, M. Tan, M. Anees, R. S. A. Kumar, S. S. Sapatnekar, C. H. Kim, and U. R. Karpuzcu, “A coupled-oscillator-based Ising chip for combinatorial optimization,” Nature Electronics, vol. 8, no. 6, pp. 537–546, 2025.DOI
  3. [3]W. Moy, I. Ahmed, P.-w. Chiu, J. Moy, S. Sapatnekar, and C. H. Kim, “A 1,968-node coupled ring oscillator circuit for combinatorial optimization problem solving,” Nature Electronics, vol. 5, no. 5, pp. 310–317, 2022.DOI
  4. [4]T. Kashimata, M. Yamasaki, R. Hidaka, and K. Tatsumura, “Efficient and scalable architecture for multiple-chip implementation of simulated bifurcation machines,” IEEE Access, vol. 12, p. 36606–36621, 2024. [Online]. Available: http://dx.doi.org/10.1109/ACCESS.2024.3374089
  5. [5]A. Sharma, R. Akafwa, Z. Ignjatovic, and M. Huang, “Increasing ising machine capacity with multi-chip architectures,” in Proceedings of the 49th Annual International Symposium on Computer Architecture, 2022, pp. 508–521.DOI
  6. [6]K. Tatsumura, M. Yamasaki, and H. Goto, “Scaling out ising machines using a multi-chip architecture for simulated bifurcation,” Nature Electronics, vol. 4, no. 3, pp. 208–217, 2021.DOI
  7. [7]K. Takemoto, T. Takemoto, C. Yoshimura, M. Mashimo, and M. Yamaoka, “A 1.3-mbit annealing system composed of fully-synchronized 9-board x 9-chip x 16-kbit annealing processor chips for large-scale combinatorial optimization problems,” in 2021 IEEE Asian Solid-State Circuits Conference (A-SSCC), 2021, pp. 1–3.DOI
  8. [8]S. Nikhar, S. Kannan, N. A. Adit, S. Chowdhury, and K. Y. Camsari, “All-to-all reconfigurability with sparse and higher-order ising machines,” Nature Communications, vol. 15, no. 1, p. 8977, 2024.DOI
  9. [9]Y. Fu and P. W. Anderson, “Application of statistical mechanics to NP-complete problems in combinatorial optimisation,” Journal of Physics A: Mathematical and General, vol. 19, no. 9, jun 1986.DOI
  10. [10]F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt, “An application of combinatorial optimization to statistical physics and circuit layout design,” Oper. Res., vol. 36, no. 3, Jun. 1988.DOI
  11. [11]F. Barahona, “On the computational complexity of Ising spin glass models,” Journal of Physics A: Mathematical and General, vol. 15, no. 10, Oct. 1982.DOI
  12. [12]E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, “A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem,” Science, vol. 292, no. 5516, 2001.DOI
  13. [13]A. Lucas, “Ising formulations of many np problems,” Frontiers in Physics, vol. 2, 2014.DOI
  14. [14]Z. Bian, F. A. Chudak, W. G. Macready, and G. Rose, “The Ising model: teaching an old problem new tricks,” 2010, dWave Systems.
  15. [15]N. Chancellor, S. Zohren, P. A. Warburton, S. C. Benjamin, and S. Roberts, “A direct mapping of max k-sat and high order parity checks to a chimera graph,” Scientific Reports, vol. 6, no. 1, p. 37107, 2016.DOI
  16. [16]A. Mallick, M. Bashar, D. Trussell, B. Calhoun, and N. Shukla, “Overcoming the accuracy vs. performance trade-off in oscillator ising machines,” in 2021 IEEE International Electron Devices Meeting (IEDM). IEEE, 2021, pp. 40–2.DOI
  17. [17]S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
  18. [18]G. Galubickas, “Multistart tabu search strategies for the unconstrained binary quadratic optimization problem,” Annals of Operations Research, vol. 131, pp. 259–282, 2004.
  19. [19]T. Takemoto, M. Hayashi, C. Yoshimura, and M. Yamaoka, “2.6 a 2×30k-spin multichip scalable annealing processor based on a processing-in-memory approach for solving large-scale combinatorial optimization problems,” IEEE, pp. 52–54, 2019.DOI
  20. [20]K. Yamamoto, K. Kawamura, K. Ando, N. Mertig, T. Takemoto, M. Yamaoka, H. Teramoto, A. Sakai, S. Takamaeda-Yamazaki, and M. Motomura, “Statica: A 512-spin 0.25 m-weight annealing processor with an all-spin-updates-at-once architecture for combinatorial optimization with complete spin–spin interactions,” IEEE Journal of Solid-State Circuits, vol. 56, no. 1, pp. 165–178, 2020.DOI
  21. [21]M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H. G. Katzgraber, “Physics-inspired optimization for quadratic unconstrained problems using a digital annealer,” Frontiers in Physics, vol. 7, p. 48, 2019.DOI
  22. [22]H. Nakayama, J. Koyama, N. Yoneoka, and T. Miyazawa, “Description: third generation digital annealer technology,” Fujitsu Limited: Tokyo, Japan, 2021.
  23. [23]H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao, Y. Hamakawa, R. Hidaka, M. Yamasaki, and K. Tatsumura, “High-performance combinatorial optimization based on classical mechanics,” Science Advances, vol. 7, no. 6, p. eabe7953, 2021.DOI
  24. [24]M. Johnson, M. Amin, S. Gilders, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. Berkley, J. Johansson, P. Bunyk, E. Chapple, C. Enderud, J. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. Thom, E. Tolacheva, C. Truncik, S. Uchaikin, I. Wang, B. Wilson, and G. Rose, “Quantum annealing with manufactured spins,” Nature, vol. 473, no. 7346, May 2011.DOI
  25. [25]S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeg hini, A. Omran, J.-G. Liu, R. Samajdar et al., “Quantum optimization of maximum independent set using rydberg atom arrays,” Science, vol. 376, no. 6598, pp. 1209–1215, 2022.
  26. [26]S. Dutta, A. Khanna, A. Assoa, H. Paik, D. G. Schlom, Z. Toroczkai, A. Raychowdhury, and S. Datta, “An ising hamiltonian solver based on coupled stochastic phase-transition nano-oscillators,” Nature Electronics, vol. 4, no. 7, pp. 502–512, 2021.
  27. [27]T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Ume ki, K. E nbut su et al., “A coherent Ising machine for 2000-node optimization problems,” Science, vol. 354, no. 6312, pp. 603–606, 2016.pubmed.ncbi.nlm.nih.gov/27811271
  28. [28]W. R. Clements, J. E. Renema, Y. H. Wen, H. M. Chrzanowski, W. S. Kolthammer, and I. A. Walmsley, “Gaussian optical ising machines,” Physical Review A, vol. 96, no. 4, p. 043850, 2017.DOI
  29. [29]D. Pierangeli, G. Marcucci, and C. Conti, “Large-scale photonic ising machine by spatial light modulation,” Physical Review Letters, vol. 122, no. 21, p. 213902, 2019.
  30. [30]H. Cilasun, Z. Zeng, A. Kumar, H. Lo, W. Cho, W. Moy, C. H. Kim, U. R. Karpuzcu, and S. S. Sapatnekar, “3sat on an all-to-all-connected cmos ising solver chip,” Scientific Reports, vol. 14, no. 1, p. 10577, 2024.DOI
  31. [31]J. Su and L. He, “Fast embedding of constrained satisfaction problem to quantum annealer with minimization chain length,” in 54th ACM/EDAC/IEEE Design Automation Conference (DAC), 2017.DOI
  32. [32]J. Su, T. Tu, and L. He, “A quantum annealing approach for Boolean satisfiability problem,” in 53rd ACM/EDAC/IEEE Design Automation Conference (DAC), 2016.DOI
  33. [33]J. Cai, W. G. Macready, and A. Roy, “A practical heuristic for finding graph minors,” arXiv preprint arXiv:1406.2741, 2014.arxiv.org/abs/1406.2741
  34. [34]R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, K. Enbutsu, T. Umeki, R. Kasahara, S. Utsunomiya, S. Kako, K. Ichi Kawarab ayashi, R. L. Byer, M. M. Fejer, H. Mabuchi, D. Englund, E. Rieffel, H. Takesue, and Y. Yamamoto, “Experimental investigation of performance differences between coherent Ising machines and a quantum annealer,” Science Advances, vol. 5, no. 5, p. eaau0823, 2019.
  35. [35]M. S. Könz, W. Lechner, H. G. Katzgraber, and M. Troyer, “Embedding overhead scaling of optimization problems in quantum annealing,” PRX Quantum, vol. 2, p. 040322, 2021.DOI
  36. [36]M. Booth, S. P. Reinhardt, and A. Roy, “Partitioning optimization problems for hybrid classical/quantum execution,” 2017, d-Wave Technical Report 14-1006A-A.
  37. [37]S. R. S. Raman, L. K. John, and J. P. Kulkarni, “Sachi: A stationarity-aware, all-digital, near-memory, ising architecture,” in 2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 2024, pp. 719–731.DOI
  38. [38]T. Wang and J. Roychowdhury, “Oscillator-based ising machine,” arXiv preprint arXiv:1709.08102, 2017.arxiv.org/abs/1709.08102
  39. [39]M. Shand and T. Edwards, “Building OpenLANE: A 130nm OpenROAD-based tapeout-proven flow,” in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2020, pp. 1–6.
  40. [40]T. Ajayi, V. A. Chhabria, M. Fogaca, S. Hashemi, A. Hosny, A. B. Kahng, M. Kim, J. Lee, U. Mallappa, M. Neseem, G. Pradipta, S. Reda, M. Saligane, S. S. Sapatnekar, C. Sechen, M. Shalan, W. Swartz, L. Wang, Z. Wang, M. Woo, and B. Xu, “OpenROAD: Toward a self-driving, open-source digital layout implementation tool chain,” Government Microcircuit Applications and Critical Technology Conference (GOMACTech), 2019.
  41. [41]A. Kumar, R. S., C. H. Kim, U. R. Karpuzcu, and S. S. Sapatnekar, “DROID: discrete-time simulation for ring-oscillator-based Ising design,” Scientific Reports, vol. 15, p. 18643, 2025.arxiv.org/abs/2502.19399
  42. [42]M. Böther, O. Kißig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich, “What’s wrong with deep learning in tree search for combinatorial optimization,” in International Conference on Learning Representations, 2022.arxiv.org/abs/2201.10494
  43. [43]M. E. J. Newman, “The structure and function of complex networks,” SIAM Review, vol. 45, no. 2, pp. 167–256, 2003.DOI
  44. [44]P. Erdős and A. Rényi, “On Random Graphs I,” Publlications Mathematicae, vol. 6, pp. 290–297, 1959.
  45. [45]A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.
  46. [46]P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” Physical review E, vol. 65, no. 2, p. 026107, 2002.pubmed.ncbi.nlm.nih.gov/11863587
  47. [47]N. Eikmeier and D. F. Gleich, “Revisiting power-law distributions in spectra of real world networks,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2017, pp. 817–826.DOI
  48. [48]S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, “Evidence for quantum annealing with more than one hundred qubits,” Nature Physics, vol. 10, no. 3, p. 218–224, Feb. 2014. [Online]. Available: http://dx.doi.org/10.1038/nphys2900
  49. [49]G. Yang, S. Karimi, C. A. R. Ocampo, A. K. Coskun, and A. Joshi, “SOPHIE: A scalable recurrent ising machine using optically addressed phase change memory,” in 2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE, 2024.DOI
  50. [50]H.-W. Chiang, C.-F. Nien, H.-Y. Cheng, and K.-P. Huang, “Reaim: A reram-based adaptive ising machine for solving combinatorial optimization problems,” in 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA). IEEE, 2024, pp. 58–72.DOI
  51. [51]N. Mohseni, P. L. McMahon, and T. Byrnes, “Ising machines as hardware solvers of combinatorial optimization problems,” Nature Reviews Physics, vol. 4, no. 6, pp. 363–379, 2022.arxiv.org/abs/2204.00276
  52. [52]K. Kawamura, J. Yu, D. Okonogi, S. Jimbo, G. Inoue, A. Hyodo, Á. López García-Arias, K. Ando, B. H. Fukushima-Kimura, R. Yasudo, T. Yan Chu, and M. Motomura, “Amorphica: 4-replica 512 fully connected spin 336mhz metamorphic annealer with programmable optimization strategy and compressed-spin-transfer multi-chip extension,” in 2023 IEEE International Solid-State Circuits Conference (ISSCC). IEEE, 2023, pp. 42–44.
  53. [53]S. Tan, M. Yu, A. Python, Y. Shang, T. Li, L. Lu, and J. Yin, “HyqSat: A hybrid approach for 3-sat problems by integrating quantum annealer with cdcl,” in 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 2023, pp. 731–744.
  54. [54]S. Zielinski, J. Nüßlein, J. Stein, T. Gabor, C. Linnhoff-Popien, and S. Feld, “Pattern quboes: Algorithmic construction of 3sat-to-qubo transformations,” Electronics, vol. 12, no. 16, p. 3492, 2023.
  55. [55]J. Nüßlein, T. Gabor, C. Linnhoff-Popien, and S. Feld, “Algorithmic qubo formulations for k-sat and hamiltonian cycles,” in Proceedings of the genetic and evolutionary computation conference companion, 2022, pp. 2240–2246.
  56. [56]T. Packebusch and S. Mertens, “Low autocorrelation binary sequences,” Journal of Physics A: Mathematical and Theoretical, vol. 49, no. 16, p. 165001, Mar. 2016. [Online]. Available: http://dx.doi.org/10.1088/1751-8113/49/16/165001
  57. [57]A. K. Singh, K. Jamieson, P. L. McMahon, and D. Venturelli, “Ising machines’ dynamics and regularization for near-optimal mimo detection,” IEEE Transactions on Wireless Communications, vol. 21, no. 12, pp. 11 080–11 094, 2022.
  58. [58]Z. Chen and E. Mossel, “Influence maximization in ising models,” 2024. [Online]. Available: https://arxiv.org/abs/2309.05206
  59. [59]J. Puerto, F. Ricca, M. Rodríguez-Mañez, and A. Scozzari, “A combinatorial optimization approach to scenario filtering in portfolio selection,” Computers & Operations Research, vol. 142, p. 105701, 2022.arxiv.org/abs/2103.01123
  60. [60]A. W. Glaetzle, R. M. W. van Bijnen, P. Zoller, W. Lechner, H. P. Buchler, M. Dalmonte, and G. Pupillo, “A coherent quantum annealer with rydberg atoms,” Nature Communications, vol. 8, p. 15813, 2017. [Online]. Available: https://doi.org/10.1038/ncomms15813
  61. [61]M. K. Bashar and N. Shukla, “Designing ising machines with higher order spin interactions and their application in solving combinatorial optimization,” Scientific Reports, vol. 13, no. 1, p. 9558, 2023.DOI
  62. [62]C. Bybee, D. Kleyko, D. E. Nikonov, A. Khosrowshahi, B. A. Olshausen, and F. T. Sommer, “Efficient optimization with higher-order ising machines,” Nature Communications, vol. 14, no. 1, p. 6033, 2023.DOI
  63. [63]A. Sharma, M. Burns, A. Hahn, and M. Huang, “Augmenting an electronic ising machine to effectively solve boolean satisfiability,” Scientific Reports, vol. 13, no. 1, p. 22858, 2023.DOI
  64. [64]S. Puri, C. K. Andersen, A. L. Grimsmo, and A. Blais, “Quantum annealing with all-to-all connected nonlinear oscillators,” Nature communications, vol. 8, no. 1, p. 15785, 2017.DOI
  65. [65]S. Kumar, H. Zhang, and Y.-P. Huang, “Large-scale ising emulation with four body interaction and all-to-all connections,” Communications Physics, vol. 3, no. 1, p. 108, 2020.DOI

Paper details

vlnc:W_z4np44xf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents