Naoya Onizawa

Synchronous update schemes in p-bit annealing offer a natural route to massive parallelism, but they can also induce period-2 oscillations that degrade optimization performance. In practical solvers, such oscillations matter only if they become observable within the finite runtime of the device or simulation. However, most existing analyses are formulated in terms of asymptotic stability and therefore do not directly address when oscillatory modes appear during finite-duration annealing. Here we develop a finite-time observability framework for synchronous tick-random p-bit dynamics. Starting from a linearized mean-field description, we derive a graph-dependent criterion that predicts whether unstable modes amplify sufficiently within a finite observation window to produce visible signatures in quantities such as the one-step autocorrelation and the energy trace. This shifts the analysis from asymptotic instability to practical detectability and yields a principled estimate of the reduction in synchrony required to suppress oscillations. We validate the framework on benchmark max-cut graph instances and illustrative graph families. The predicted thresholds capture both the graph dependence of oscillation onset and the finite-time conditions under which oscillations become observable. These results provide a graph-aware basis for selecting the update probability in synchronous p-bit annealers without relying on exhaustive instance-by-instance parameter sweeps.

Probabilistic bits (p-bits) offer an energy-efficient hardware abstraction for stochastic optimization; however, existing p-bit-based simulated annealing accelerators suffer from poor scalability and limited support for fully connected graphs due to fan-out and memory overhead. This paper presents an energy-efficient FPGA architecture for stochastic simulated quantum annealing (SSQA) that addresses these challenges. The proposed design combines a spin-serial and replica-parallel update schedule with a dual-BRAM delay-line architecture, enabling scalable support for fully connected Ising models while eliminating fan-out growth in logic resources. By exploiting SSQA, the architecture achieves fast convergence using only final replica states, significantly reducing memory requirements compared to conventional p-bit-based annealers. Implemented on a Xilinx ZC706 FPGA, the proposed system solves an 800-node MAX-CUT benchmark and achieves up to 50% reduction in energy consumption and over 90\% reduction in logic resources compared with prior FPGA-based p-bit annealing architectures. These results demonstrate the practicality of quantum-inspired, p-bit-based annealing hardware for large-scale combinatorial optimization under strict energy and resource constraints.

This paper introduces an analog-to-stochastic converter using a magnetic tunnel junction (MTJ) device for vision chips based on stochastic computation. Stochastic computation has been recently exploited for area-efficient hardware implementation, such as low-density parity-check (LDPC) decoders and image processors. However, power-and-area hungry two-step (analog-to-digital and digital-to-stochastic) converters are required for the analog to stochastic signal conversion. To realize a one-step conversion, an MTJ device is used as it inherently exhibits a probabilistic switching behavior between two resistance states. Exploiting the device-based probabilistic behavior, analog signals can be directly and area-efficiently converted to stochastic signals to mitigate the signal-conversion overhead. The analog-to-stochastic signal conversion is theoretically described and the conversion characteristic is evaluated using device and circuit parameters. In addition, the resistance variability of the MTJ device is considered in order to compensate the variability effect on the signal conversion. Based on the theoretical analysis, the analog-to-stochastic converter is designed in 90nm CMOS and 100nm MTJ technologies and is verified using a SPICE simulator (NS-SPICE) that handles both transistors and MTJ devices.

We propose an energy-efficient simulated annealing (SA) hardware design based on p-bits, an emerging class of probabilistic device models. Our approach adopts a spin-serial, replica-parallel architecture and integrates stochastic simulated quantum annealing (SSQA), which emulates quantum annealing behavior using classical hardware. This method accelerates convergence with fewer computational steps while supporting fully connected graphs and maintaining high energy efficiency. To enhance scalability, we introduce a dual-BRAM delay-line architecture that significantly outperforms previous shift-register-based designs. By eliminating the linear fan-out associated with weight propagation in shift-register architectures, our design maintains constant fan-out and on-chip logic usage regardless of the number of spins N. In contrast to conventional p-bit-based annealing hardware—which stores multiple intermediate spin states and selects the best one—SSQA achieves comparable annealing quality using only the final state, thereby reducing the BRAM footprint for replica states by over 90%. Implemented on a Xilinx ZC706 FPGA, the proposed hardware solves an 800-node benchmark while achieving a 50% energy reduction compared to conventional p-bit-based hardware, which only supports neighbor-connected graphs. It also reduces LUT usage by 97%, FF usage by 88%, and BRAM usage by 70%. These results demonstrate the practicality of p-bit-based annealing hardware for large-scale, fully connected combinatorial optimization problems, offering excellent efficiency in both energy consumption and hardware resource utilization.

Probabilistic computing using probabilistic bits (p-bits) presents an efficient alternative to traditional CMOS logic for complex problem-solving, including simulated annealing and machine learning. Realizing p-bits with emerging devices such as magnetic tunnel junctions introduces device variability, which was expected to negatively impact computational performance. However, this study reveals an unexpected finding: device variability can not only degrade but also enhance algorithm performance, particularly by leveraging timing variability. This paper introduces a GPU-accelerated, open-source simulated annealing framework based on p-bits that models key device variability factors-timing, intensity, and offset-to reflect real-world device behavior. Through CUDA-based simulations, our approach achieves a two-order magnitude speedup over CPU implementations on the MAX-CUT benchmark with problem sizes ranging from 800 to 20,000 nodes. By providing a scalable and accessible tool, this framework aims to advance research in probabilistic computing, enabling optimization applications in diverse fields.

Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.

This article critically investigates the limitations of the simulated annealing algorithm using probabilistic bits (pSA) in solving large-scale combinatorial optimization problems. The study begins with an in-depth analysis of the pSA process, focusing on the issues resulting from unexpected oscillations among p-bits. These oscillations hinder the energy reduction of the Ising model and thus obstruct the successful execution of pSA in complex tasks. Through detailed simulations, we unravel the root cause of this energy stagnation, identifying the feedback mechanism inherent to the pSA operation as the primary contributor to these disruptive oscillations. To address this challenge, we propose two novel algorithms, time average pSA (TApSA) and stalled pSA (SpSA). These algorithms are designed based on partial deactivation of p-bits and are thoroughly tested using Python simulations on maximum cut benchmarks that are typical combinatorial optimization problems. On the 16 benchmarks from 800 to 5000 nodes, the proposed methods improve the normalized cut value from 0.8 to 98.4% on average in comparison with the conventional pSA.