Pith. sign in

REVIEW 3 major objections 4 minor 65 references

Efficient Optimization Accelerator Framework for Multistate Ising Problems

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Binary-vector encoding of node colors makes probabilistic Ising machines competitive with Tabucol and GNN solvers on graph coloring, and a 1024-neuron FPGA version runs roughly 10000x faster than GPU Tabucol.

desk verdict Vectorized binary encoding with truth-table F is a real improvement for Ising solvers, but the 'eliminates invalid states' claim only holds for powers of two — for other q it's a soft penalty, and success counts may include illegal colorings. read the letter →

arxiv 2505.20250 v2 pith:LA5MMFZL submitted 2025-05-26 cs.AR cs.DCcs.ETcs.LGstat.CO

Chirag Garg , Sayeef Salahuddin This is my paper · ORCID
classification cs.ARcs.DCcs.ETcs.LGstat.CO
keywords graphcoloringIsingmachinesprobabilisticcomputingcombinatorialoptimizationvectorizedmappingQUBOFPGAacceleratorparalleltempering
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that the usual way of mapping multi-state optimization problems onto Ising machines---one-hot encoding plus a penalty term---is what makes those machines perform poorly on graph coloring. It proposes instead to encode each node's color as a $\lceil \log_2 q \rceil$-bit binary vector, so the search space shrinks from $2^{qN}$ to $2^{\lceil \log_2 q \rceil N}$ and the one-hot constraint term disappears from the energy function. With this vectorized mapping, probabilistic Ising solvers achieve accuracy competitive with Tabucol and physics-inspired graph neural networks on standard benchmark graphs, and they clearly beat one-hot QUBO-based Ising solvers and simulated bifurcation. Adding parallel tempering reduces the error by up to 50% on the hardest instances. The same mapping, expressed as a truth table and realized with higher-order multiplexers, supports a 1024-neuron all-to-all FPGA accelerator that reaches roughly 10000x time-to-solution speedup over GPU Tabucol while using 1.5-4x fewer physical neurons than one-hot Ising hardware.

What carries the argument

The central object is the vectorized mapping: replace each $q$-state variable by $n = \lceil \log_2 q \rceil$ binary spins and encode the interaction between two variables as a truth-table operator $F$, defined in Algorithm 1. In hardware, $F$ is implemented by higher-order multiplexers, so each spin's $\Delta H$ is computed as the difference between the multiplexer outputs for $s_{ik}=1$ and $s_{ik}=0$. This removes the one-hot penalty term $B \sum_i (1 - \sum_k s_{ik})^2$ and shrinks the explored state space from $2^{qN}$ to $2^{nN}$, which is what makes the mapping the load-bearing element of the claimed accuracy and speedup gains.

What would settle it

Run the vectorized mapping on a non-power-of-two instance, for example a 3-color queen problem, collect every final color assignment across many runs, and count how many use out-of-range codes, i.e. binary values $\ge q$. If such invalid-code solutions appear with nontrivial frequency or account for most incorrect edges, the central claim is falsified: the gains come from the penalty term, not from eliminating invalid state space.

Watch

Extended reading notes

Core claim

The paper's central claim is that mapping each multi-state variable to a binary vector, rather than to a one-hot vector, changes the energy landscape enough to make stochastic Ising machines competitive on graph coloring. For $q$ colors, node $S_i$ is represented by $\{s_{i0}, \dots, s_{i,n-1}\}$ with $n = \lceil \log_2 q \rceil$, and edge penalties are computed by a truth-table operator $F$ that returns 1 when two endpoints have equal color or an out-of-range code, and 0 otherwise. The resulting Hamiltonian is higher-order rather than quadratic, but each spin update needs only $\Delta H = H_{s_{ik}=1} - H_{s_{ik}=0}$, which hardware can evaluate directly with multiplexers. The paper reports that this encoding eliminates all invalid state space, that parallel tempering adds a further accuracy gain of up to 50% error reduction on hard instances, and that a 1024-neuron FPGA implementation reaches about 10000x time-to-solution speedup over GPU Tabucol while using 1.5-4x fewer physical neurons than one-hot Ising mappings.

Load-bearing premise

The central load-bearing premise is that penalizing out-of-range binary codes is as good as forbidding them. For color counts that are not powers of two, the $\lceil \log_2 q \rceil$-bit encoding still contains invalid bit patterns; Algorithm 1 marks those with a penalty in the Hamiltonian, so the claimed elimination of invalid state space is a soft constraint, not a hard one, and the accuracy and speedup numbers depend on that approximation.

Editorial extensions

If this is right

  • Graph coloring benchmarks previously dominated by Tabucol and GNN solvers can now be solved to comparable accuracy by a probabilistic Ising machine, because the vectorized encoding removes the one-hot constraint from the energy function.
  • One-hot QUBO-based Ising solvers, including simulated bifurcation, are less accurate on these instances; the paper attributes that gap to exploration of invalid states, which the binary-vector encoding largely avoids.
  • A 1024-neuron all-to-all FPGA accelerator built from truth-table multiplexers supports graph coloring instances up to 256 nodes and 16 colors, delivering roughly 10000x time-to-solution speedup and about 5x power improvement over the GPU implementations.
  • Because the truth-table operator $F$ is problem-specific rather than quadratic-specific, the same construction can be written down for other multi-state problems; the paper demonstrates it on traveling salesman problems in the supplement.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the state-space reduction claim is exact only when $q$ is a power of two; for other color counts the method keeps a soft penalty for out-of-range codes, so an extension that truly excludes those patterns, or measures their frequency in the output, would settle how much of the gain is due to encoding versus penalty tuning.
  • Editorial inference: the ~10000x speedup over Tabucol is not purely algorithmic, because it compares a bit-parallel custom accelerator against a sequential heuristic on GPU; a fair algorithmic comparison would run both on the same hardware or count node-update operations.
  • Editorial inference: the higher-order truth-table interaction is a deliberate departure from standard QUBO hardware, so applying the same mapping to conventional Ising annealers would require expanding $F$ into quadratic terms, possibly reintroducing constraints or auxiliary variables; the paper does not explore that trade-off.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a 'vectorized mapping' for multi-state Ising problems, in which each node's color is encoded in a binary vector of length ceil(log2 Q) rather than a one-hot vector of length Q, and the pairwise interaction is defined by a truth-table operator F. The method is applied to graph coloring on COLOR benchmarks and to a small TSP example. The authors report that the vectorized mapping on GPU achieves errors comparable to Tabucol and PI-SAGE and substantially lower than one-hot probabilistic Ising and simulated bifurcation, and that adding parallel tempering reduces errors on hard instances. They also implement a 1024-neuron all-to-all FPGA accelerator supporting up to 256 nodes and 16 colors and report roughly 10,000x time-to-solution speedup over GPU-based Tabucol and about 5x power improvement over GPU-based vectorized mapping.

Significance. The core encoding idea is attractive and potentially useful: it reduces the physical neuron count from NQ to N ceil(log2 Q), a factor of about 1.5-4 for the color counts tested, and the truth-table formulation maps directly to multiplexer-based hardware. The FPGA demonstration is a concrete, measured result rather than a fitted prediction, and the state-space reduction from 2^{QN} to 2^{ceil(log2 Q) N} is a combinatorial fact. The per-instance distributions in the supplement and the explicit Algorithm 1 are helpful for reproducibility. However, the central claim that the mapping 'eliminates all invalid state space' is exact only when Q is a power of two; the benchmark claims for non-power-of-two Q rest on an unverified assumption about out-of-range binary codes. With that issue corrected or scoped, the contribution remains significant.

major comments (3)
  1. [§2, Eq. (3), Algorithm 1] The statement that the vectorized mapping 'eliminates all invalid state space' is not correct for color counts that are not powers of two. For Q colors, the binary encoding uses n = ceil(log2 Q) bits, so the per-node code space has 2^n elements, of which 2^n - Q are invalid. Algorithm 1 handles out-of-range codes by setting F=1 and adding W_ij to the Hamiltonian; this is a soft penalty in the Gibbs sampler of Eq. (4), not a removal of those states from the explored space. The state space is therefore reduced from 2^{QN} to 2^{nN}, but not to Q^N as the text implies. Since Tables 1 and 2 report results for Q = 5, 7, 11, 12, and 13, this discrepancy affects the core accuracy claims.
  2. [§4, Fig. 4(b)-(c)] The success metric counts only incorrectly colored edges, i.e., edges whose two endpoints share the same color value. A final assignment that contains out-of-range binary codes but has no two nodes sharing the same invalid code will have zero incorrectly colored edges and will be counted as successful even though it is not a valid Q-coloring. The manuscript does not report how often final solutions contain out-of-range codes for non-power-of-two instances. Please (i) report the fraction of runs with invalid codes, (ii) recompute success probability and time-to-solution treating any out-of-range code as a failure, and (iii) either restrict the 'eliminates invalid state space' claim to Q=2^n or explicitly describe the penalty as an approximation. This verification is necessary to support the competitive accuracy claims for hard instances such as queen11_11 and queen13_13.
  3. [§5, Table 1] The FPGA accelerator is described as supporting up to 16 colors, which is a power of two, so the exact state-space elimination holds for the full-capacity hardware configuration. However, the FPGA column in Table 1 also reports results for non-power-of-two instances (Q = 5, 7, 11, 12, 13), and the text states that the FPGA achieves the same accuracy as the GPU vectorized mapping. The same invalid-code ambiguity therefore propagates to the hardware results. Please clarify whether the FPGA runs for such instances verify that the final colors are in [0, Q-1], or otherwise explain how out-of-range codes are treated in the reported accuracy.
minor comments (4)
  1. [Eq. (4)] Equation (4) defines the sigmoid as sigma(x) = 1/(1 + e^x), while Algorithm 2 defines sigmoid(x) = 1/(1 + e^{-x}). With the minus sign in the argument of Eq. (4), these two conventions give opposite flip probabilities. Please unify the notation and verify the sign convention against the standard Gibbs update.
  2. [Abstract and Discussion] The speedup numbers are stated inconsistently: the abstract reports '~10000x' versus GPU Tabucol, the introduction reports '100000x speed improvement' compared to its GPU-based implementation, and the Discussion reports '~10000x' versus Tabucol and '~100000x' versus vectorized mapping on GPU. Please clarify the baseline in each location.
  3. [Algorithm 1] The condition 'S_i, S_j /∈ [0, Q-1]' is ambiguous: it should state clearly whether the penalty is triggered when either node is out of range or only when both are out of range. The surrounding prose suggests 'either', but the pseudocode should be explicit.
  4. [Fig. 2b] The truth-table portion of Fig. 2b appears garbled in the manuscript text (e.g., the strings '00123467' and the F column). Please ensure the final figure renders the truth table legibly and that the table entries match Algorithm 1.

Circularity Check

0 steps flagged · score 2.0 of 10

No circularity: the vectorized mapping, accuracy comparisons, and FPGA speedups are constructed or measured rather than derived from fitted quantities; only minor non-load-bearing self-citations appear.

full rationale

The paper's central claims are not circular. The vectorized mapping reduces the state space from 2^{qN} to 2^{ceil(log2 q) N} by construction of the binary encoding, and this is a direct combinatorial fact rather than a fitted or predicted result. The Hamiltonian in Eq. 3 and Algorithm 1 define the F-operator directly from the graph-coloring validity condition, so the mapping is not derived from the benchmark outcomes. Accuracy tables and success probabilities are measured against external baselines (Tabucol, PI-SAGE, GNN, simulated bifurcation), and the FPGA time-to-solution and power figures are hardware measurements, not outputs of a fitted model. The parallel-tempering improvement is also an empirical result. The main self-citations (Refs. 9, 12, 26, and related p-bit hardware work) are used to motivate the probabilistic Ising hardware framework and the standard Gibbs-sampling update rule of Eq. 4; that update rule is independently standard Boltzmann-machine sampling, so these citations are not load-bearing in the derivation of the vectorized mapping or the speedup measurements. One validity concern, noted in the manuscript's own Algorithm 1, is that for non-power-of-two color counts the binary encoding does not actually eliminate invalid color codes: the algorithm sets F=1 for out-of-range colors, which is a soft penalty in the Hamiltonian rather than a hard removal of those states. This contradicts the paper's prose claim that the mapping 'eliminates all invalid state space.' However, this is a correctness/overclaim issue about the mapping, not a circularity: the claim is false or overstated, not entailed by the construction. It should be weighed as a correctness risk, not as evidence of circular reasoning. Overall, the derivation chain is self-contained and benchmarked externally, so the circularity score is low. Score 2 reflects the presence of minor self-citations in the hardware-framework background, not a load-bearing circular step.

Assumptions & free parameters 6 free parameters · 6 assumptions · 0 invented entities

No new physical entities are postulated. The central claims rest on standard sampling assumptions, hand-chosen temperatures and parallel tempering parameters, and the truth-table encoding assumption that out-of-range binary codes can be softly penalized without restoring one-hot constraint difficulties.

free parameters (6)
  • Vectorized graph coloring temperature T = 0.2
    Chosen by hand for all graph coloring instances; controls acceptance probability in Eq. 4 and directly affects solution quality.
  • Parallel tempering settings = M=100 replicas, temperature range 0.01 to 40, swap every 15 steps
    Chosen without reported optimization; required for the hard-instance accuracy gains attributed to vectorized mapping plus parallel tempering.
  • Graph coloring Ising baseline weights A and B = Per-instance grid search in Supplementary Fig S1
    The one-hot baselines are tuned per problem; these parameters define the baseline the paper claims to outperform.
  • Success probability threshold = Error less than 2%, i.e. more than 98% correctly colored edges
    This threshold defines success probability and therefore the TTS comparison in Eq. 5 and Fig 4; changing it changes the reported speedup ratios.
  • TSP vectorized position-penalty weight wt = Optimized per TSP instance in Supplementary Fig S7
    The TSP extension results use a per-instance fitted weight, so part of the claimed generality is supported by fitting to the test instances.
  • TSP Ising baseline weights A and B = Optimized per instance via grid search in Supplementary Fig S6
    Used to construct the TSP Ising baseline Hamiltonian for comparison.
assumptions (6)
  • standard math Single-flip Gibbs sampling with sigmoid acceptance converges to a low-energy state of the Hamiltonian.
    Invoked in Eq. 4 and Algorithm 2; this is standard Boltzmann machine sampling, but convergence is not proven for the non-convex higher-order Hamiltonians used here.
  • domain assumption The truth-table F operator in Eq. 3 fully encodes the graph coloring objective.
    Algorithm 1 defines F and assumes that penalizing same-color and out-of-range pairs with edge weight W_ij guides sampling to valid colorings.
  • ad hoc to paper Out-of-range binary codes can be handled by a soft penalty without restoring one-hot constraint complications.
    For q not a power of 2, codes q through 2^n-1 are invalid; Algorithm 1 lines 11-13 penalize them, while the text claims invalid states are eliminated.
  • domain assumption Parallel tempering with 100 replicas and a geometric temperature schedule improves mixing without biasing the ground state.
    Used for all hard-instance results; no analysis of replica count or schedule bias is given.
  • domain assumption Multiplexer-based truth-table hardware reproduces GPU sampling accuracy at 8-bit precision.
    Table 1 reports equal accuracy for FPGA and GPU vectorized versions, but no bitstream or hardware measurement details are released for independent verification.
  • domain assumption The COLOR dataset and citation graphs are representative benchmarks for graph coloring solvers.
    Used to support the accuracy and speedup claims; standard datasets, but results on other graph distributions could differ.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Optimization Accelerator Framework for Multistate Ising Problems." pith.science (2026). https://pith.science/paper/LA5MMFZL

@misc{pith2026250520250,
  author       = {Pith},
  title        = {Pith review of: Efficient Optimization Accelerator Framework for Multistate Ising Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LA5MMFZL}},
  note         = {Machine review of arXiv:2505.20250}
}
read the original abstract

Ising Machines are emerging hardware architectures that efficiently solve NP-Hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ~10000x performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5-4x over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.

Figures

Figures reproduced from arXiv: 2505.20250 by the authors.

Figure 1
Figure 1. Probabilistic Ising Machine Architecture and Optimization Problem Classifica￾tion a, Quadratic unconstrained binary optimization (QUBO) problems are represented as an Ising net￾work with nodes representing the states and edges depicting interactions between them. b, Prob￾abilistic Ising architecture based on the Boltzmann machine update rule to minimize the problem Hamiltonian and energy function. c, The State of th… view at source ↗
Figure 2
Figure 2. Comparison between Ising and Vectorized Mapping Approaches a, Existing Ising framework employs one-hot encoding to map N node q color graph coloring problem to Nq nodes. The encoding constraint is enforced by adding an extra term in the Hamil￾tonian, creating a complex optimization landscape that can result in suboptimal ground states. This mapping preserves QUBO Hamiltonian, therefore, the interactions are modeled … view at source ↗
Figure 3
Figure 3. Solution Exploration in Ising and Vectorized Mapping framework. a, Energy evolution for queen13_13 problem instance mapped and solved using Ising and Vec￾torized mapping implementation on GPU. (b) Distribution of number of incorrectly colored edges achieved for queen13_13 problem instance after running GPU-based Ising and Vectorized im￾plementation for 200 parallel runs. (c) Ising and Vectorized framework combined w… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Area, Solution Quality, Performance and Energy Efficiency Benchmarks a, Physical implementation nodes used in Ising and Vectorized mapping approach for dataset prob￾lem 40 . (b) Success Probability (> 98 % correctly colored edges) metric comparing vectorized map￾ping w…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 58 canonical work pages

  1. [1]

    In2022 International Joint Conference on Neural Networks (IJCNN), 1–8 (2022)

    Sevilla, J.et al.Compute trends across three eras of machine learning. In2022 International Joint Conference on Neural Networks (IJCNN), 1–8 (2022)

    work page 2022

  2. [2]

    Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing.Science 220, 671–680 (1983). https://www.science.org/doi/pdf/10.1126/science.220.4598.671

    doi:10.1126/science.220.4598.671 1983

  3. [3]

    Hochba, D. S. Approximation algorithms for np-hard problems.SIGACT News28, 40–52 (1997)

    work page 1997

  4. [4]

    https://onlinelibrary.wiley

    Colorni, A.et al.Heuristics from nature for hard combinatorial optimization problems.In- ternational Transactions in Operational Research3, 1–21 (1996). https://onlinelibrary.wiley. com/doi/pdf/10.1111/j.1475-3995.1996.tb00032.x

    work page arXiv 1996

  5. [5]

    J., Sanches, F., Ide, T., Kamiya, K

    Weinberg, S. J., Sanches, F., Ide, T., Kamiya, K. & Correll, R. Supply chain logistics with quantum and classical annealing algorithms.Scientific Reports13, 4770 (2023)

    work page 2023

  6. [6]

    & Han, J

    Tao, Q. & Han, J. Solving traveling salesman problems via a parallel fully connected ising machine. InProceedings of the 59th ACM/IEEE Design Automation Conference, DAC ’22, 1123–1128 (Association for Computing Machinery, New York, NY , USA, 2022)

    work page 2022

  7. [7]

    Y ., Di Felice, R., Rohs, R

    Li, R. Y ., Di Felice, R., Rohs, R. & Lidar, D. A. Quantum annealing versus classical machine learning applied to a simplified computational biology problem.npj Quantum Information4, 14 (2018)

    work page 2018

  8. [8]

    InProceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA ’24, 43 (Association for Computing Machinery, New York, NY , USA, 2024)

    Gerlach, T.et al.Fpga-placement via quantum annealing. InProceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA ’24, 43 (Association for Computing Machinery, New York, NY , USA, 2024)

    work page 2024

Show all 65 references
  1. [9]

    & Salahuddin, S

    Patel, S., Canoza, P. & Salahuddin, S. Logically synthesized and hardware-accelerated re- stricted Boltzmann machines for combinatorial optimization and integer factorization.Nature Electronics 2022 5:25, 92–101 (2022)

    2022

  2. [10]

    A.et al.Integer factorization using stochastic magnetic tunnel junctions.Nature 573, 390–393 (2019)

    Borders, W. A.et al.Integer factorization using stochastic magnetic tunnel junctions.Nature 573, 390–393 (2019)

    2019

  3. [11]

    A.et al.Massively parallel probabilistic computing with sparse ising machines

    Aadit, N. A.et al.Massively parallel probabilistic computing with sparse ising machines. Nature Electronics5, 460–468 (2022). 10

    2022

  4. [12]

    /abs/2409.10325

    Patel, S.et al.PASS: An Asynchronous Probabilistic Processor for Next Generation Intelli- gence.ArXiv(2024). /abs/2409.10325

    2024 arXiv

  5. [13]

    L.et al.A fully programmable 100-spin coherent ising machine with all-to-all connections.Science354, 614–617 (2016)

    McMahon, P. L.et al.A fully programmable 100-spin coherent ising machine with all-to-all connections.Science354, 614–617 (2016). https://www.science.org/doi/pdf/10.1126/science. aah5178

    2016 doi

  6. [14]

    Moy, W.et al.A 1,968-node coupled ring oscillator circuit for combinatorial optimization problem solving.Nature Electronics5, 310–317 (2022)

    2022

  7. [15]

    Chowdhury, S., Camsari, K. Y . & Datta, S. Accelerated quantum monte carlo with probabilis- tic computers.Communications Physics6, 1–7 (2023)

    2023

  8. [16]

    & Kim, C

    Lo, H., Moy, W., Yu, H., Sapatnekar, S. & Kim, C. H. An Ising solver chip based on coupled ring oscillators with a 48-node all-to-all connected array architecture.Nature Electronics6, 771–778 (2023)

    2023

  9. [17]

    & Boothby, K

    McGeoch, C., Farre, P. & Boothby, K. The D-Wave Advantage2 Prototype. Tech. Rep., D-Wave Systems Inc. (2023). Technical Report

    2023

  10. [18]

    Yue, W., Zhang, T., Jing, Z.et al.A scalable universal ising machine based on interaction- centric storage and compute-in-memory.Nature Electronics(2024)

    2024

  11. [19]

    & Huang, K.-P

    Chiang, H.-W., Nien, C.-F., Cheng, H.-Y . & Huang, K.-P. Reaim: A reram-based adaptive ising machine for solving combinatorial optimization problems. In2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA), 58–72 (2024)

    2024

  12. [20]

    https://www.science.org/doi/pdf/10.1126/science.aah4243

    Inagaki, T.et al.A coherent ising machine for 2000-node optimization problems.Science 354, 603–606 (2016). https://www.science.org/doi/pdf/10.1126/science.aah4243

    2016 doi

  13. [21]

    & Roychowdhury, J

    Wang, T. & Roychowdhury, J. Oim: Oscillator-based ising machines for solving combinatorial optimisation problems. In McQuillan, I. & Seki, S. (eds.)Unconventional Computation and Natural Computation, 232–256 (Springer International Publishing, Cham, 2019)

    2019

  14. [22]

    ArXiv(2024)

    Chen, Z.et al.ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers. ArXiv(2024). 2406.05224

    2024 arXiv

  15. [23]

    Niazi, S., Chowdhury, S., Aadit, N.et al.Training deep boltzmann networks with sparse ising machines.Nature Electronics7, 610–619 (2024)

    2024

  16. [24]

    C., Chern, K., Farré, P

    McGeoch, C. C., Chern, K., Farré, P. & King, A. K. A comment on comparing optimization on D-Wave and IBM quantum processors.ArXiv(2024). 2406.19351

    2024 arXiv

  17. [25]

    Y ., Faria, R., Sutton, B

    Camsari, K. Y ., Faria, R., Sutton, B. M. & Datta, S. Stochasticp-bits for invertible logic.Phys. Rev. X7, 031014 (2017)

    2017

  18. [26]

    & Salahuddin, S

    Patel, S., Chen, L., Canoza, P. & Salahuddin, S. Ising Model Optimization Problems on a FPGA Accelerated Restricted Boltzmann Machine (2020). 11

    2020

  19. [27]

    Ising formulations of many np problems.Frontiers in Physics2(2014)

    Lucas, A. Ising formulations of many np problems.Frontiers in Physics2(2014)

    2014

  20. [28]

    Silva, C., Aguiar, A., Lima, P.et al.Mapping graph coloring to quantum annealing.Quantum Machine Intelligence2, 16 (2020)

    2020

  21. [29]

    In2023 IEEE International Conference on Consumer Electronics (ICCE), 1–6 (2023)

    Kawakami, S.et al.A constrained graph coloring solver based on ising machines. In2023 IEEE International Conference on Consumer Electronics (ICCE), 1–6 (2023)

    2023

  22. [30]

    Inaba, K., Inagaki, T., Igarashi, K.et al.Potts model solver based on hybrid physical and digital architecture.Communications Physics5, 137 (2022)

    2022

  23. [31]

    Whitehead, W., Nelson, Z., Camsari, K.et al.Cmos-compatible ising and potts annealing using single-photon avalanche diodes.Nature Electronics6, 1009–1019 (2023)

    2023

  24. [32]

    & de Werra, D

    Hertz, A. & de Werra, D. Using tabu search techniques for graph coloring.Computing39, 345–351 (1987)

    1987

  25. [33]

    Schuetz, M. J. A., Brubaker, J. K., Zhu, Z. & Katzgraber, H. G. Graph coloring with physics- inspired graph neural networks.Phys. Rev. Res.4, 043131 (2022)

    2022

  26. [34]

    2208.06975

    Li, W.et al.Rethinking graph neural networks for the graph coloring problem.ArXiv(2022). 2208.06975

    2022 arXiv

  27. [35]

    Koopmans, T. C. & Beckmann, M. Assignment problems and the location of economic activ- ities.Econometrica25, 53–76 (1957). Accessed 29 Sept. 2024

    1957

  28. [36]

    B., Park, C.-H., Xu, X

    Kahng, A. B., Park, C.-H., Xu, X. & Yao, H. Layout decomposition approaches for double patterning lithography.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems29, 939–952 (2010)

    2010

  29. [37]

    D., Ramsey, N

    Smith, M. D., Ramsey, N. & Holloway, G. A generalized algorithm for graph-coloring register allocation. InProceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, 277–288 (Association for Computing Machinery, New York, NY , USA, 2004)

    2004

  30. [38]

    & Perkowski, M

    Ciesielski, M., Yang, S. & Perkowski, M. Multiple-valued boolean minimization based on graph coloring. InProceedings 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 262–265 (1989)

    1989

  31. [39]

    Earl, D. J. & Deem, M. W. Parallel tempering: theory, applications, and new perspectives. Physical Chemistry Chemical Physics7, 3910–3916 (2005)

    2005

  32. [40]

    COLOR Dataset (2002)

    Trick, M. COLOR Dataset (2002). Accessed: 2024-09-29

    2002

  33. [41]

    Lewis, R. M. R.Guide to Graph Colouring: Algorithms and Applications. Texts in Computer Science (Springer, Cham, 2021), 2nd edn. 12

    2021

  34. [42]

    A., Chowdhury, S

    Nikhar, S., Kannan, S., Aadit, N. A., Chowdhury, S. & Camsari, K. Y . All-to-all reconfigura- bility with sparse and higher-order ising machines.Nature Communications15, 8977 (2024)

    2024

  35. [43]

    & Dixon, A

    Goto, H., Tatsumura, K. & Dixon, A. R. Combinatorial optimization by simulating adiabatic bifurcations in nonlinear hamiltonian systems.Science Advances5, eaav2372 (2019). https: //www.science.org/doi/pdf/10.1126/sciadv.aav2372

    2019 doi

  36. [44]

    & Pugliese, L

    Ageron, R., Bouquet, T. & Pugliese, L. Simulated bifurcation (sb) algorithm for python. https://github.com/bqth29/simulated-bifurcation-algorithm (2023). Version 1.2.1, Nov. 2023

    2023

  37. [45]

    & Malucelli, F

    Gualandi, S. & Malucelli, F. Exact solution of graph coloring problems via constraint pro- gramming and column generation.INFORMS Journal on Computing24, 81–100 (2012). https://doi.org/10.1287/ijoc.1100.0436

    2012

  38. [46]

    Hamerly, R.et al.Experimental investigation of performance differences between coherent Ising machines and a quantum annealer.Science Advances5, eaau0823 (2019)

    2019

  39. [47]

    Tatsumura, K., Dixon, A. R. & Goto, H. Fpga-based simulated bifurcation machine. In2019 29th International Conference on Field Programmable Logic and Applications (FPL), 59–66 (2019)

    2019

  40. [48]

    & Salahuddin, S

    Garg, C. & Salahuddin, S. Optimization_integer_ising_data (2025). https://doi.org/10.5281/ zenodo.16945085

    2025

  41. [49]

    H., Hinton, G

    Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. A learning algorithm for boltzmann machines. Cognitive Science9, 147–169 (1985)

    1985

  42. [50]

    Gibbs fields and monte carlo simulation

    Brémaud, P. Gibbs fields and monte carlo simulation. InMarkov Chains, 253–322 (Springer New York, New York, NY , 1999)

    1999

  43. [51]

    Si, e. a. Energy-efficient superparamagnetic ising machine and its application to traveling salesman problems.Nature Communications15, 3016 (2024)

    2024

  44. [52]

    K., Nigam, K., Rennie, J

    McCallum, A. K., Nigam, K., Rennie, J. & Seymore, K. Automating the construction of internet portals with machine learning.Information Retrieval3, 127–163 (2000)

    2000

  45. [53]

    Sen, P.et al.Collective classification in network data.AI Magazine29, 93–106 (2008)

    2008

  46. [54]

    & Huang, B

    Namata, G., London, B., Getoor, L. & Huang, B. Query-driven active surveying for collective classification. InProceedings of the 10th International Workshop on Mining and Learning with Graphs, vol. 8, 249–256 (2012)

    2012

  47. [55]

    In2025 IEEE International Solid- State Circuits Conference (ISSCC), vol

    Li, M.-C.et al.12.2 p-circuits: Neither digital nor analog. In2025 IEEE International Solid- State Circuits Conference (ISSCC), vol. 68, 1–3 (2025)

    2025

  48. [56]

    Lawler, E. L. The traveling salesman problem: A guided tour of combinatorial optimization. Journal of the Operational Research Society37, 535–536 (1986). 13

    1986

  49. [57]

    A., Tang, H

    Pevzner, P. A., Tang, H. & Waterman, M. S. An eulerian path approach to dna fragment assembly.Proceedings of the National Academy of Sciences98, 9748–9753 (2001). https: //www.pnas.org/doi/pdf/10.1073/pnas.171285098

    2001 doi

  50. [58]

    & Sato, T

    Dan, A., Shimizu, R., Nishikawa, T., Bian, S. & Sato, T. Clustering approach for solving traveling salesman problems via ising model based solver. In2020 57th ACM/IEEE Design Automation Conference (DAC), 1–6 (2020)

    2020

  51. [59]

    Tsplib—a traveling salesman problem library.INFORMS Journal on Computing 3, 376–384 (1991)

    Reinelt, G. Tsplib—a traveling salesman problem library.INFORMS Journal on Computing 3, 376–384 (1991)

    1991

  52. [60]

    𝑠!𝑠"+ %𝑏!𝑠!!

    Lin, S. & Kernighan, B. W. An effective heuristic algorithm for the traveling salesman prob- lem.Operations Research21, 498–516 (1973). AcknowledgementsThis work is supported by the Office of Naval Research (ONR), Multidisciplinary University Research Initiative (MURI) grant N...

    1973

  53. [61]

    Probabilistic Ising Machines Probabilistic Ising machines follow the principle of the Boltzmann Machine binary neural network

  54. [62]

    Therefore, the probability distribution corresponding to a given statep(s) = 1 Z e−H(s)/T where Z= P s e−H(s)/T is the normalizing/partition function,srepresents the states, T denotes temper- ature coefficient andH(s)is Hamiltonian or energy function to be minimized. Ising Ham...

  55. [63]

    1 andBin Eq

    Hyperparameter optimization for graph coloring In order to make a fair comparison between Ising and vectorized mapping, a grid search-based parameter optimization is performed for the parametersAin Eq. 1 andBin Eq. 2 in the graph coloring Hamiltonian. If the connectivity weigh...

  56. [64]

    These problems are often used for graph-based benchmark experiments and have also been used for testing graph-coloring based algorithms 33, 34

    Vectorized Mapping Benchmark for Citation Graph Dataset To demonstrate the scalability of vectorized mapping approach, we benchmark the citation datasets (Cora 52, Citeseer 53, and Pubmed 54). These problems are often used for graph-based benchmark experiments and have also be...

  57. [65]

    Traveling Salesman Problem The Traveling Salesman Problem (TSP) is a classic NP-hard optimization problem that aims to de- termine the shortest possible route in which a given set of cities is visited exactly once. Owing to its computational complexity and broad applicability ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.