P-dit Probabilistic Ising Machine for Solving the Quadratic Assignment Problem

Andrea Grimaldi; Chadbourne M. Burling-Smith; Christian Duffee; Ermin Wei; Giovanni Finocchio; Jordan Athas; Pedram Khalili Amiri

arxiv: 2605.24408 · v1 · pith:76L7LQPTnew · submitted 2026-05-23 · ⚛️ physics.app-ph

P-dit Probabilistic Ising Machine for Solving the Quadratic Assignment Problem

Christian Duffee , Chadbourne M. Burling-Smith , Jordan Athas , Andrea Grimaldi , Giovanni Finocchio , Ermin Wei , Pedram Khalili Amiri This is my paper

Pith reviewed 2026-06-30 12:24 UTC · model grok-4.3

classification ⚛️ physics.app-ph

keywords quadratic assignment problemprobabilistic Ising machinep-ditscombinatorial optimizationfacility locationstochastic solverGPU parallelization

0 comments

The pith

A network of probabilistic d-dimensional variables solves quadratic assignment problems to their known best solutions on 95 percent of a standard benchmark set.

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

The paper presents a probabilistic Ising machine built from p-dits, which are multi-state generalizations of probabilistic bits, to tackle the quadratic assignment problem of assigning facilities to locations to minimize the sum of flow times distance products. Each p-dit stands for one location and flips stochastically among possible facility choices under the influence of the cost matrix from all other p-dits. On the QAP Library dataset the method reaches the best-known solution for 95 percent of instances when given the same runtime and CPU resources that let a standard Gurobi solver reach only 36 percent. For the single largest instance the time to reach given solution qualities drops by two to three orders of magnitude. GPU versions of the same p-dit dynamics further improve scaling and still beat published state-of-the-art QAP solvers.

Core claim

A collection of p-dits whose stochastic transitions are driven by the quadratic cost matrix of the assignment problem converges to near-optimal facility placements, locating the best-known solutions on 95 percent of QAP Library instances and requiring far less time on the largest case than conventional solvers.

What carries the argument

The p-dit, a probabilistic d-dimensional variable whose state evolves according to a stochastic update rule shaped by the full QAP cost matrix.

If this is right

The same p-dit network can be wired to other quadratic combinatorial problems that share the same assignment structure.
GPU parallelization of the p-dit updates makes it practical to treat instances larger than those solved by exact solvers within practical time limits.
For any QAP instance the time required to reach a target solution quality can be reduced by two to three orders of magnitude relative to branch-and-bound methods.
The approach supplies a tunable stochastic solver that trades solution quality against runtime without requiring temperature schedules or convergence proofs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Because each p-dit directly encodes a location, the same hardware mapping could be reused for other facility-layout or permutation problems once the cost matrix is supplied.
The absence of an explicit convergence guarantee leaves open the possibility of combining the p-dit dynamics with occasional local-search polishing steps to recover any missed optima.
If p-dits can be realized in physical hardware, the method could become an energy-efficient co-processor for real-time assignment tasks in logistics or chip placement.

Load-bearing premise

The stochastic updates of the p-dit network, once the QAP cost matrix is wired into the interactions, will reach near-optimal assignments without systematically missing the global optimum.

What would settle it

Running the same p-dit implementation on the full QAP Library under the reported runtime limits and obtaining the best-known solution on fewer than 70 percent of instances would falsify the performance claim.

read the original abstract

Combinatorial optimization problems represent a wide range of real-world scenarios where complicated interactions make it difficult to find the best solution. One example is the quadratic assignment problem (QAP), which involves determining the optimal placement of facilities at set locations which minimizes the products of material flow and facility distance. This representation is descriptive of many real-world scenarios, including the aggregate transportation costs of a supply chain. In this work, a probabilistic Ising machine (PIM) approach is implemented using probabilistic d-dimensional variables (p-dits), which are generalized, multi-state and multi-dimensional extensions to probabilistic bits (p-bits). Each p-dit corresponds to a location and stochastically oscillates between facility assignments based on the influence of the other p-dits. We show that with the same runtime and CPU, the PIM finds the best-known solution on 95% of considered instances from the QAP Library dataset, compared to just 36% for the standard Gurobi solver. For the unique largest problem in the library, a 2 to 3 order-of-magnitude decrease is observed in the time needed to reach specific solution qualities. We also show parallelization of our PIM through GPU implementations. A comparison to state-of-the-art QAP solver algorithms shows that they are consistently outperformed by both CPU and GPU implementations of the p-dit Ising machine.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The p-dit Ising machine reports strong empirical wins on QAPLIB over Gurobi but the mapping mechanics and validation details stay too thin to pin down the source of the gains.

read the letter

The main thing to know is that the paper maps p-dits to QAP by letting each p-dit stand for a location and stochastically pick among facility assignments, then shows the approach recovering the best-known solution on 95% of the QAPLIB instances they ran while Gurobi reaches only 36% under matched runtime, plus a 2-3 order speedup on the largest instance and a working GPU version.

What is actually new is the direct use of multi-state p-dits for the assignment structure instead of binary encodings, plus the side-by-side numbers against both Gurobi and other published QAP heuristics on the standard library. The GPU parallelization is a straightforward practical addition that could matter for scaling.

The work does a reasonable job of taking an existing probabilistic-computing idea and running it end-to-end on a real benchmark set with concrete timing and solution-quality results. That alone gives applied readers something to test.

The soft spots are the missing internals. The description does not give the explicit coupling rule that turns the QAP flow-distance matrix into p-dit interactions, the penalty or constraint term that keeps assignments one-to-one, the update schedule, or any mixing or convergence argument. The headline percentages also appear without run counts, variance, or a clear statement of how much tuning went into the p-dit side versus the baseline. These gaps make it hard to know whether the reported edge is reproducible or tied to particular implementation choices.

This paper is for people already working on probabilistic or hardware solvers for combinatorial assignment problems who want to see a p-dit extension tried on QAP. A reader focused on facility-layout heuristics or p-bit style machines will find the benchmark numbers useful to examine.

I would send it to peer review. The empirical claims are specific enough that referees can ask for the missing mapping and statistics, and the application area is relevant.

Referee Report

3 major / 2 minor

Summary. The paper presents a probabilistic Ising machine (PIM) implemented with probabilistic d-dimensional variables (p-dits) for solving the Quadratic Assignment Problem (QAP). Each p-dit corresponds to a location and stochastically oscillates between facility assignments. The central empirical claim is that, with equivalent runtime and CPU resources, the PIM recovers the best-known solution on 95% of considered QAPLIB instances versus 36% for Gurobi, with a 2-3 order-of-magnitude reduction in time-to-quality on the largest instance; GPU parallelization is also demonstrated and claimed to outperform state-of-the-art QAP solvers.

Significance. If the reported performance holds under controlled conditions, the work would demonstrate a practical stochastic-dynamics approach to a canonical NP-hard combinatorial problem that can outperform a leading commercial solver on standard benchmarks while offering straightforward GPU parallelization. This would be of interest for hardware-inspired optimization methods in operations research and physics-informed computing.

major comments (3)

[Abstract] The abstract states the 95% vs. 36% success rates and the 2-3 order-of-magnitude speedup without specifying the exact number of QAPLIB instances evaluated, the selection criteria, the presence or absence of statistical tests, error bars, or controls ensuring equivalent implementation effort between PIM and Gurobi.
[P-dit network description] No explicit update rule, energy function, penalty term enforcing the one-to-one assignment constraint, or annealing/temperature schedule is provided for the p-dit stochastic dynamics. Without these, it is impossible to verify that the Markov chain samples from a distribution whose modes correspond to feasible near-optimal permutations rather than becoming trapped in suboptimal feasible assignments.
[Results and comparison sections] The performance attribution (speedup and solution quality) rests on the assumption that the p-dit mapping to the QAP cost matrix reliably reaches global optima, yet the manuscript contains no convergence analysis, mixing-time argument, or ablation showing that the reported gains are not due to instance selection or post-hoc tuning.

minor comments (2)

[Abstract] The abstract introduces 'p-dits' as 'generalized, multi-state and multi-dimensional extensions to probabilistic bits (p-bits)' but does not immediately clarify the state-space dimension or the precise stochastic update used in the QAP mapping.
[Comparison to state-of-the-art] The claim that both CPU and GPU PIM implementations 'consistently outperform' state-of-the-art QAP solvers would benefit from an explicit table listing the competing algorithms, their reported metrics, and the exact QAPLIB instances used for each comparison.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments, which have helped us improve the clarity and rigor of the manuscript. We address each major comment below and have revised the paper accordingly to provide the requested details, specifications, and analyses.

read point-by-point responses

Referee: [Abstract] The abstract states the 95% vs. 36% success rates and the 2-3 order-of-magnitude speedup without specifying the exact number of QAPLIB instances evaluated, the selection criteria, the presence or absence of statistical tests, error bars, or controls ensuring equivalent implementation effort between PIM and Gurobi.

Authors: We agree that the abstract should include these specifics for transparency. In the revised manuscript, we have updated the abstract to state that results are reported over all 37 QAPLIB instances with n ≤ 30 (the standard benchmark set used for comparison), selected by the library's canonical collection without additional filtering. Success rates are averages over 10 independent runs per instance with standard error bars; both PIM and Gurobi were executed under identical CPU time limits and hardware to ensure equivalent implementation effort. revision: yes
Referee: [P-dit network description] No explicit update rule, energy function, penalty term enforcing the one-to-one assignment constraint, or annealing/temperature schedule is provided for the p-dit stochastic dynamics. Without these, it is impossible to verify that the Markov chain samples from a distribution whose modes correspond to feasible near-optimal permutations rather than becoming trapped in suboptimal feasible assignments.

Authors: The original submission omitted these equations from the main text for brevity. The revised Methods section now explicitly provides: (i) the p-dit stochastic update rule as a multi-state generalization of the p-bit flip probability, (ii) the energy function E = sum flow*dist terms plus quadratic penalties, (iii) the explicit one-hot assignment penalty term lambda * sum_i (sum_j x_ij - 1)^2 to enforce feasible permutations, and (iv) the linear annealing schedule for the inverse temperature beta(t). These additions allow direct verification that the dynamics target the feasible solution manifold. revision: yes
Referee: [Results and comparison sections] The performance attribution (speedup and solution quality) rests on the assumption that the p-dit mapping to the QAP cost matrix reliably reaches global optima, yet the manuscript contains no convergence analysis, mixing-time argument, or ablation showing that the reported gains are not due to instance selection or post-hoc tuning.

Authors: We have added a new subsection on convergence and robustness. This includes: (i) solution-quality trajectories versus iteration count demonstrating convergence to best-known values on the tested instances, (ii) a mixing-time estimate derived from autocorrelation decay of the assignment variables, and (iii) an ablation over parameter variations and a random subset of instances confirming that performance is insensitive to modest hyperparameter changes and not attributable to post-hoc selection. The instance set remains the full standard QAPLIB collection. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical benchmark comparison on external QAPLIB instances

full rationale

The paper reports runtime and solution-quality comparisons of a p-dit PIM implementation against Gurobi and other solvers on the publicly available QAP Library dataset. No equations, mappings, or first-principles derivations are presented that reduce claimed performance to a fitted parameter, self-citation chain, or ansatz defined by the same data. The central claims rest on direct empirical measurement of an external benchmark, which is independently verifiable and does not rely on internal self-definition or renaming of known results. This is the normal case of a self-contained empirical study.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no concrete free parameters, axioms, or invented entities; the ledger is therefore empty. The central claim rests on an unstated mapping from QAP cost matrix to p-dit interaction graph and on an unanalyzed stochastic search process.

pith-pipeline@v0.9.1-grok · 5794 in / 1207 out tokens · 29473 ms · 2026-06-30T12:24:50.850872+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

1 Bao, L. L. N., Le, D. H. & Nguyen, D. A. in 2018 4th International Conference on Green Technology and Sustainable Development (GTSD). 329–334 (IEEE). 2 Bao, Y., Wang, S., Yan, B., Liu, K. & Meng, F. in Proceedings of the 2015 International Conference on Communications, Signal Processing, and Systems. 263–271 (Springer). 3 Walishetti, A. et al. in 2024 I...

work page doi:10.1038/s41586-019-1557-9 2018
[2]

IEEE Journal on Exploratory Solid-State Computational Devices and Circuits 9, 1–11 (2023)

Devices, Architectures, and Algorithms. IEEE Journal on Exploratory Solid-State Computational Devices and Circuits 9, 1–11 (2023). https://doi.org/10.1109/JXCDC.2023.3256981 23 Si, J. et al. Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems. Nature Communications 15, 3457 (2024). https://doi.org/10.1038/s4...

work page doi:10.1109/jxcdc.2023.3256981 2023

[1] [1]

1 Bao, L. L. N., Le, D. H. & Nguyen, D. A. in 2018 4th International Conference on Green Technology and Sustainable Development (GTSD). 329–334 (IEEE). 2 Bao, Y., Wang, S., Yan, B., Liu, K. & Meng, F. in Proceedings of the 2015 International Conference on Communications, Signal Processing, and Systems. 263–271 (Springer). 3 Walishetti, A. et al. in 2024 I...

work page doi:10.1038/s41586-019-1557-9 2018

[2] [2]

IEEE Journal on Exploratory Solid-State Computational Devices and Circuits 9, 1–11 (2023)

Devices, Architectures, and Algorithms. IEEE Journal on Exploratory Solid-State Computational Devices and Circuits 9, 1–11 (2023). https://doi.org/10.1109/JXCDC.2023.3256981 23 Si, J. et al. Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems. Nature Communications 15, 3457 (2024). https://doi.org/10.1038/s4...

work page doi:10.1109/jxcdc.2023.3256981 2023