Probabilistic greedy algorithm solver using magnetic tunneling junctions for traveling salesman problem

Domain: physics
Published: 2025-12-04
Editorial outcome: major_revision

Abstract
Combinatorial optimization underpins applications in artificial intelligence, logistics, and network design, yet classical techniques such as greedy search and dynamic programming struggle to balance efficiency and solution quality at scale. We present a probabilistic framework that embeds true random number generators based on spin-transfer-torque magnetic tunnel junctions into a greedy solver. Intrinsic stochastic switching enables configurable random number distributions, which we use to inject controlled randomness via a temperature parameter that interpolates between deterministic and stochastic choices, balancing exploration and exploitation. Applied to the traveling salesman problem, the framework yields high-quality tours and outperforms simulated annealing and genetic algorithms in solution quality and convergence speed. In larger instances with up to 70 cities, it maintains its advantage, reaching near-optimal solutions with fewer iterations and reduced computational cost. These results show that hardware true randomness with tunable statistics can improve heuristic search and motivate integrated, energy-efficient probabilistic hardware for scalable optimization.

Introduction
Combinatorial optimization is a cornerstone of modern computational science, playing a pivotal role in domains ranging from artificial intelligence and machine learning1,2 to logistics3–5 and operations research6. The objective is to identify an optimal configuration from a finite but exponentially large set of possibilities, where even modest increases in problem size can render classical methods impractical due to the exponential growth of computational complexity7. While deterministic algorithms such as dynamic programming8 and branch-and-bound9 have proven effective for small-scale problems, they often fail to scale efficiently to larger scenarios or escape local optima when confronted with the complex landscapes of combinatorial spaces10.

In recent years, there has been a paradigm shift towards incorporating randomness into optimization algorithms11–13, leading to an emerging class of techniques termed stochastic or probabilistic optimization14–20. Methods such as simulated annealing, genetic algorithms, and Monte Carlo simulations have demonstrated the potential of randomness to diversify search strategies, enabling algorithms to explore solution spaces more comprehensively and escape local minima. However, the efficacy of these methods is highly dependent on the quality and configurability of the random number generators (RNGs) employed13,21,22. Traditional RNGs, whether pseudo-random or hardware-based, often lack the flexibility required to dynamically adjust their distribution characteristics, limiting their adaptability to different optimization scenarios.

A promising development in this field is the utilization of magnetic tunneling junctions (MTJs) as a source of true random numbers, enabling true random number generators (TRNGs), which exploit inherent physical randomness rather than deterministic algorithmic processes23,24. MTJs, typically used in non-volatile memory technologies25–28, exhibit probabilistic switching behavior that can be finely tuned by external control parameters such as voltage or magnetic field strength. This inherent stochasticity—referred to as hardware randomness due to its direct physical origin—makes MTJ-based TRNGs uniquely suited for probabilistic computing29–33, where the randomness can be directly mapped onto computational processes. The ability to configure the probability distribution of an MTJ-based TRNG—effectively creating probabilistic bits (p-bits), binary units defined by probabilistic rather than deterministic states—enables an alternative approach to algorithm design, where the degree of randomness can be adjusted in real time to influence decision-making processes34,35.

Prior conceptual and simulation-level frameworks, such as the SPINBIS spintronics-based Bayesian inference engine built on MTJ stochastic bit-stream generators36, and spin-orbit-torque-based Bayesian reasoning hardware37, have demonstrated the feasibility of MTJ-based probabilistic inference in data-fusion and inference tasks. Distinctively, our work goes beyond these precedents by experimentally embedding MTJ-based, probability-distribution-configurable TRNGs into a probabilistic greedy algorithm for TSP optimization. This hybrid hardware-algorithm co-design is, to our knowledge, a representative fully experimental demonstration of Bayesian-PDF-matched probabilistic optimization for combinatorial problems.

In this study, we propose an advanced optimization framework that leverages MTJ-based TRNGs to solve complex combinatorial problems. Specifically, we introduce a probabilistic greedy algorithm for the traveling salesman problem (TSP)22,38–41–a canonical example in combinatorial optimization – to showcase the potential of this approach. The TSP challenges a solver to find the shortest possible route that visits a given set of cities and returns to the starting point, and it is well known for its non-deterministic polynomial-hardness (NP-Hardness). By incorporating MTJ-based TRNGs into the decision-making process, we can modulate the selection strategy for the next city, transitioning smoothly between deterministic greedy choices and purely random selection. This dynamic adaptability enables the algorithm to effectively balance exploration and exploitation, thereby improving its ability to find high-quality solutions efficiently.

Results
Figure 1 presents a detailed characterization of the MTJ-based TRNG employed in this study. The resulting R-H hysteresis loops, shown in Fig. 1b, reveals a clear and sharp switching between high and low resistance states, confirming the stability and reproducibility of the MTJ’s magnetic switching behavior. The MTJ has a high tunnel magnetoresistance (TMR) ratio ~175%, which is essential for ensuring reliable and distinct resistance states. The MTJ’s resistance switching behavior under current pulses is illustrated in Fig. 1c.

By applying a series of current pulses, we observed stochastic switching of the free layer’s magnetization, resulting in resistance changes. This stochastic behavior serves as the basis for the MTJ-based TRNG. To further analyze the switching probability, Fig. 1d plots the probability of switching as a function of the applied write voltage. The experimental data (green circles) show a gradual increase in switching probability (Psw) with increasing voltage (V), which is accurately captured by the fitted sigmoidal curve (black solid line). The fitting parameters b and c indicate the sharpness and offset of the curve.

Psw = 1 / (1 + e^(b(V+c)))

This relationship Psw(V) is crucial, as it enables precise control over the probability distribution of generated random numbers. Figure 1e demonstrates the results of continuous resistance measurements at three fixed voltages: 0.275V, 0.282V, and 0.288V, corresponding to Psw of 25%, 48%, and 81%, respectively. These measurements confirm that the device can achieve consistent and repeatable switching behavior, with well-defined probability at each voltage level. The ability to finely tune the switching probability by adjusting the voltage is a key advantage of MTJ-based TRNGs, allowing for the generation of random numbers with specific statistical properties tailored to various probabilistic algorithms. While achieving fine-grained control over switching probabilities typically requires highly precise voltage tuning, we adopt a hybrid control scheme previously validated in ref. 42, where switching probability is regulated via pulse-width modulation rather than analog amplitude adjustment. This digital control method ensures consistent sigmoidal switching behavior across devices, even when target probabilities are closely spaced. Moreover, the use of a self-stabilizing feedback mechanism compensates for device variation and drift, allowing robust and scalable probability distribution generation without relying on high-resolution voltage sources.

Figure 2 showcases the versatility of the MTJ-based TRNG in generating random numbers with configurable probability distributions. The schematic diagram in Fig. 2a illustrates the experimental setup, where multiple MTJs are connected to the NI PXIe system through a probe card and adapter board (Supplement I). This configuration enables the simultaneous measurement of multiple MTJs, allowing for efficient data collection and parallel testing of different devices.

Figure 2b displays the random numbers generated by the MTJ-based TRNGs. The generated values align closely with the expected Gaussian distribution, as evidenced by the smooth bell-shaped curve. This Gaussian-distributed randomness is achieved by carefully adjusting the write voltage of the MTJs, demonstrating the flexibility of the TRNG in producing specific distributions. The transformation from binary Bernoulli TRNGs into a probability-distribution-function-configurable TRNG modeled as a Bayesian network can be found in Supplement II in details.

To quantitatively evaluate the accuracy of the generated distributions, Fig. 2c presents the error analysis, where the left axis represents the Kullback-Leibler (KL) divergence and the right axis represents the mean squared error (MSE). The KL divergence measures the difference between the experimentally generated distribution and the theoretical Gaussian distribution, while the MSE quantifies the average deviation of the generated values from the expected mean and variance. Both metrics indicate minimal errors, confirming the high fidelity of the MTJ-based TRNG in replicating desired distributions.

The neighbor correlation of the generated random numbers is analyzed in Fig. 2d, where the color intensity represents the sample point density. The nearly uniform distribution of points and the presence of concentric circles indicate negligibly weak neighboring correlation, signifying that the generated random numbers are statistically independent. Our STT-MTJs are not low-barrier ones and each random number is generated by a reset-sampling circle, therefore correlevance between neighboring random numbers no longer an issue here. This property is essential for ensuring that the TRNG can produce high-quality random numbers suitable for applications requiring true randomness, such as probabilistic algorithms and cryptographic operations.

Figure 2e–g demonstrate the capability of the TRNG to generate random numbers following various probability distributions. Figure 2e presents a uniform distribution, where each value has an equal probability of being sampled. Figure 2f shows an exponential decay distribution, characterized by a high probability for smaller values and a rapidly decreasing probability for larger values. Finally, Fig. 2g illustrates a user-defined arbitrary distribution, highlighting the flexibility of the TRNG in generating custom probability profiles. This configurability is critical for integrating the TRNG into a wider range of applications, from stochastic optimization to artificial intelligence, where diverse probability distributions are needed to guide decision-making processes. The probabilistic nature of the algorithm inherently mitigates the influence of occasional transient faults or soft errors in random number generation. Additionally, the embedded self-calibration and stabilization routines further ensure robustness by identifying and correcting persistent anomalous switching behaviors at the hardware level. It is important to note that the experimentally demonstrated capability of generating random numbers with configurable and dynamically tunable probability distributions (Fig. 2) directly supports the probabilistic selection mechanism required by our greedy algorithm in solving the TSP (Fig. 3). At each iterative step of the algorithm, the MTJ-based TRNG efficiently provides random samples precisely matching the dynamically updated probability distribution defined by Eq. (1). This intrinsic alignment between the MTJ-based TRNG capabilities and the probabilistic selection mechanism greatly enhances both the solution quality and computational efficiency, clearly distinguishing our approach from traditional algorithms that rely on fixed or less-flexible random number generators.

Maintaining precise switching probability control in large-scale or on-chip implementations is crucial. In our recent work 42, we demonstrated a scalable hybrid control approach in which pulse-width modulation (PWM) replaces the need for high-resolution analog voltage tuning. By adjusting the duration of fixed-amplitude pulses using simple digital logic, the system effectively maintains the desired probability distribution across devices, even under thermal drift and process variation. This strategy significantly reduces the requirement for high-resolution DACs or ADCs, making the architecture well-suited for scalable on-chip integration.

Compared to pseudo-random number generators (PRNGs), MTJ-based TRNGs offer significant advantages in probabilistic computing applications, particularly through their ability to directly generate and dynamically tune probability distributions in real time. Unlike deterministic PRNGs, which typically require additional computational overhead for mapping uniform random outputs into desired distributions, MTJ-based TRNGs inherently produce physically-generated randomness with precisely controllable statistics via simple external parameters (e.g., applied voltage or pulse width). This feature significantly reduces complexity and latency, while also offering enhanced parallelism and power efficiency in hardware implementations.

While this work primarily focuses on distribution configurability, we emphasize that the random bit streams generated by our MTJs have been rigorously validated 42. In that study, we conducted comprehensive statistical evaluations using the NIST SP800-22 test suite, confirming that the TRNG outputs exhibit high entropy and pass all standard randomness tests without requiring post-processing. The same device architecture and control protocols were employed in this work, ensuring that the TRNGs used for TSP solving maintain equivalent statistical quality. Additional statistical evaluation of the TRNG-generated bit streams is provided in Supplement I, II, III. The current bit-stream generation rate in our experimental setup is limited by the speed of the NI PXIe data acquisition system, operating at approximately 500 kHz per MTJ. However, the intrinsic switching times of STT-MTJs allow for much faster operation. With high-speed peripheral circuits and optimized on-chip integration, generation rates approaching the GHz range are feasible, as reported in recent high-speed TRNG demonstrations 43. This positions our MTJ-based TRNGs as suitable candidates for future high-throughput probabilistic computing applications.

Figure 3 presents the probabilistic greedy algorithm’s mechanism for selecting the next city in the traveling salesman problem (TSP) under varying temperature conditions. The algorithm utilizes the MTJ-based TRNG to generate random numbers that influence the city selection process, allowing for a probabilistic adjustment of the greedy strategy. The selection probability Pi+1(Ni) of the next city Ni is a function of the distance dij between the current city N and Ni as well as a temperature parameter kBT as shown in Eq. (1).

Pi+1(Ni) = (1-bi)exp(-dij/kBT) / Z
Z = sum((1-bi)exp(-dij/kBT))

Here bi indicates the accessibility of the ith city and bi=1 once the ith city has been visited or else bi=0 if it is to be visited. Thus, the final probability of choosing a specific route P=∏Pi+1(Ni)∝exp[-(∑dij)/kBT] and, straightforwardly, the shortest route S=(∑dij)min has the highest probability to be experimentally sampled. This feature assures the convergence of this probabilistic greedy algorithm. More details can be found in the Supplement V.

It is worth noting that the decision of choosing the next city relies on a probabilistic sampling operation according to the series of probabilities Pi+1(Ni) with Ni being the city indices to be visited. This probability-distribution-function (PDF) defined by Pi+1(Ni) changes dynamically step by step, which calls for a random number generator that can output random numbers according to the time-variant PDFs. Fortunately, our TRNGs with configurable PDFs match this requirement well.

When kBT approaches zero, the algorithm operates as a deterministic greedy algorithm, always selecting the closest city to the current one. In this regime, the probability of choosing the closest city is nearly 100%, leading to rapid but potentially suboptimal solutions due to the algorithm’s inability to escape local minima.

Conversely, when kBT is extremely high, the selection probability for each remaining city becomes nearly uniform, leading to a selection process similar to a random walk. This behavior encourages exploration of the solution space but at the cost of reduced efficiency in converging to high-quality solutions. The optimal performance is observed at intermediate kBT-values, where the algorithm effectively balances exploration (randomness) and exploitation (favoring shorter distances), allowing it to escape local optima and discover near-optimal solutions with high probability. Practical considerations regarding frequent adjustments of MTJ-based TRNG distributions have shown minimal overhead. This is primarily because reconfigurations involve only modest voltage adjustments via a small set of parameters. Furthermore, implementing parallel and pipeline operations effectively reduces latency, ensuring these hardware-level adjustments do not significantly affect the overall algorithm performance.

It is important to acknowledge existing epsilon-greedy methods commonly used in reinforcement learning and optimization tasks 44, which similarly balance exploration (randomness) and exploitation (optimal choice). However, our proposed MTJ-based probabilistic greedy algorithm significantly diverges from traditional epsilon-greedy methods in several critical aspects. Unlike epsilon-greedy algorithms, which typically employ a fixed probability (ε) to introduce uniformly random choices, our algorithm continuously and dynamically updates a probability distribution for city selection at every step, based on distances and the adjustable temperature parameter kBT (Eq. (1)). This dynamic adjustment provides a more nuanced and context-sensitive trade-off between exploration and exploitation. Moreover, the direct hardware-based randomness offered by MTJ-based TRNGs facilitates immediate, real-time, and computationally efficient generation of precisely tuned probability distributions, eliminating the computational overhead associated with transforming uniformly distributed pseudo-random numbers into desired distributions. Consequently, our method achieves superior encoding efficiency, algorithmic flexibility, and scalability, representing a substantial advancement beyond traditional epsilon-greedy approaches.

Figure 4 provides experimental results demonstrating the application of the MTJ-based TRNGs in solving the TSP using the probabilistic greedy algorithm. Figure 4a depicts the map of the Burma14 problem (n=14, where n denotes the problem size), where the solid line indicates the known optimal solution, and the dashed line represents the best solution obtained using a classic greedy algorithm. The probabilistic greedy algorithm, driven by the MTJ-based TRNG, consistently identifies paths that are closer to the optimal solution, as shown by the reduced total distance metrics. Figure 4b illustrates the variation in total distance across a range of kBT values from 1 to 400. The orange dashed line marks the known optimal solution, while the green, orange, and red solid lines connect the maximum, minimum, and average total distances, respectively, obtained at each kBT value. The results indicate that the algorithm achieves optimal or near-optimal solutions when kBT is within the range of 40 to 60, highlighting the significance of selecting an appropriate temperature parameter to balance the probabilistic selection strategy.

Figure 4c further investigates the distribution of solution distances at six selected kBT values, showing improved performance and reaching the optimal solution when kBT is between 40 and 60. This analysis underscores the robustness of the probabilistic greedy algorithm in finding high-quality solutions when driven by suitably tuned randomness. Figure 4d examines the relationship between the best path distance and the number of iterations (where one iteration is defined as a single complete solution route, visiting each city exactly once) for four selected kBT values. When kBT=60, the optimal solution is achieved within 1000 iterations, demonstrating the efficiency of the algorithm in converging to high-quality solutions. Figure 4e presents a scatter plot of the best solutions obtained across the kBT range and density distribution plots of solutions within 0, 50 and 100 kilometers of the known optimal solution, further validating the algorithm’s effectiveness. For visibility, the density of the 0 kilometer is scaled by a factor of 50. The appearance of a clear peak shape in the distribution plots indicates the existence of an optimal kBT, highlighting the algorithm’s sensitivity to temperature parameters in achieving high-quality solutions.

The solver still works well when the city number is increased significantly. Figure 5 illustrates the simulated results obtained with the st70 problem, offering a comprehensive comparison of our algorithm against other established methods. In the map shown for the st70 problem, the optimal solution is indicated by a solid line, serving as a benchmark for evaluating the performance of different algorithms. The st70 problem, with its 70 cities, presents a considerable computational challenge, making it an ideal test case for demonstrating the efficacy of both heuristic and exact algorithms. The comparison of time and space complexity among the algorithms—Brute Force, Dynamic Programming, Genetic Algorithm, Simulated Annealing (SA), Greedy Algorithm, and Probabilistic Greedy Algorithm—clearly highlights the benefits of heuristic methods. While exhaustive approaches like Brute Force and Dynamic Programming struggle with scalability as n increases, heuristic algorithms, particularly the Probabilistic Greedy and Genetic algorithms, strike a balance between computational efficiency and solution quality. This contrast is evident from the results where n=70 is used, showcasing the advantage of these more advanced approaches when tackling larger problems. As the number of iterations grows, the quality of the solution improves, particularly when varying the thermal fluctuation parameter kBT. Across different values (kBT=0.1, 1.3, 2.0, and 3.0), the results indicate that the algorithm’s performance is highly sensitive to this parameter, with intermediate values (e.g., 1.3) leading to a more optimal convergence rate. The gradual improvement in path quality with increasing iterations underscore the algorithm’s ability to refine its solution over time. When comparing different heuristic approaches—Genetic Algorithm, Simulated Annealing (SA), Greedy Algorithm, and Probabilistic Greedy Algorithm—the results reveal that incorporating stochastic elements, as seen in the Probabilistic Greedy Algorithm, significantly enhances performance. It is worth noting that while the SA can only evaluate the situation of exchanging two cities at a sample, the Probabilistic Greedy Algorithm can take all the remaining cities into account for a single sampling owing to the arbitrary PDF configurability of our MTJ-TRNGs. Thus, the latter can deal with a higher entanglement degree, which accounts for its faster convergence speed. By avoiding local optima, the probabilistic variant consistently outperforms the classic Greedy Algorithm, especially in later iterations, demonstrating its potential for yielding superior solutions. Moreover, our MTJ-based probabilistic framework can also benefit advanced metaheuristics such as Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO). By integrating hardware-level randomness, these metaheuristics can systematically enhance their exploration strategies, potentially leading to improved solution quality and faster convergence due to more effective escape from local optima.

We note that the parameter kBT, which governs the shape of the exponential probability distribution, is currently selected empirically for each problem instance. While effective in practice, developing a more systematic or adaptive strategy for temperature tuning—analogous to annealing schedules or meta-optimization—remains an important avenue for future work, particularly to enhance scalability and generalizability.

Finally, the schematic in Fig. 5e illustrates the core design of a TSP solver based on an MTJ array. This hardware-based solver taps into the inherent randomness of the MTJ array, which can be efficiently reused to generate random numbers of any required length. This modularity and scalability make the MTJ array particularly well-suited for probabilistic algorithms like Simulated Annealing and Probabilistic Greedy Algorithm, enhancing the solver’s adaptability for larger and more complex TSP instances. The ability to expand the random number generation capability of the MTJ array according to an arbitrarily customized PDF without sacrificing performance is a crucial innovation, positioning this design as a versatile and efficient solution for hardware-accelerated optimization tasks.

To provide a transparent system-level comparison, we summarize key performance metrics of our prototype platform versus projected FPGA/ASIC implementations in Table 1. The prototype, implemented with 100nm STT-MTJs controlled by NI-PXIe instrumentation, operates at ~0.5MHz and requires ~20ms per 14-city TSP solution, with energy dominated by instrumentation overhead. In contrast, projections based on published MTJ switching speeds (≤10ns) 45 and intrinsic switching energies (fJ–pJ per event) 35 indicate that a dedicated FPGA or ASIC could achieve sub-millisecond or even sub-0.1ms solution times with microjoule-level energy consumption. This analysis highlights the large performance headroom available for integrated spintronic probabilistic solvers.

Furthermore, we note that the step-by-step probabilistic decision-making process in our algorithm bears strong resemblance to the autoregressive sampling mechanism employed in large language models (LLMs), where each token is sampled based on a dynamically updated softmax distribution. This conceptual alignment suggests a future direction for integrating MTJ-based probabilistic hardware with AI inference and generation tasks that involves structured randomness.

This paper presents a distinct probabilistic greedy algorithm that utilizes the stochastic properties of MTJ-based TRNGs to solve complex combinatorial optimization problems. By integrating MTJ-based TRNGs with the PDF reconfigurability into the optimization framework, we can dynamically adjust the degree of randomness in the decision-making process, allowing the algorithm to strike an optimal balance between exploration and exploitation. This capability is achieved through the control of a temperature parameter, which modulates the randomness level and enables the algorithm to adapt its strategy based on the problem state.

The effectiveness of the proposed approach is demonstrated through extensive experimentation on the traveling salesman problem. Our results show that the probabilistic greedy algorithm consistently achieves superior performance compared to classical methods such as simulated annealing and genetic algorithms, both in terms of solution quality and convergence speed. When applied to larger problem instances in simulation, the algorithm exhibits excellent scalability and robustness, maintaining a competitive edge even as the number of cities increases to 70. For significantly larger-scale problems involving hundreds or thousands of nodes, practical implementations may require adaptive parameter tuning strategies, parallelization techniques, or decomposition of the problem into manageable subproblems. Nonetheless, there are no fundamental limitations preventing the scalability of our proposed method. The key advantage of this approach lies in its ability to dynamically modulate randomness through the MTJ-based TRNG, which enhances the algorithm’s capacity to escape local optima and discover near-optimal solutions efficiently.

In the current implementation, the temperature-like parameter kBT, which governs the exploration-exploitation trade-off, is determined empirically for each problem instance. While this heuristic approach is effective in practice, developing a systematic or adaptive tuning strategy remains an important direction for future work. Additionally, although we demonstrate hardware results on medium-scale TSP instances (e.g., Burma14), the results for larger problems (e.g., st70) are obtained through algorithm-level simulations. These simulations validate the algorithmic scalability of our approach, while the underlying hardware design—requiring only log N MTJs for encoding an N-choice distribution—offers intrinsic architectural advantages for future large-scale implementations. It is worth noting that, besides the logarithmic scaling of MTJ count (O(log N)), our probabilistic greedy algorithm requires only O(N) auxiliary memory for conditional probability parameters, which remains significantly more favorable than the O(N2) parameter storage required in Boltzmann or Ising machines.

The integration of MTJ-based TRNGs offers a promising direction for developing hardware-accelerated optimization frameworks, with potential applications extending beyond TSP to other NP-hard problems. This framework can be readily generalized to other combinatorial optimization problems, such as graph coloring or scheduling tasks, by simply redefining the specific cost function and adjusting the temperature parameter accordingly. A concrete adaptation of the probabilistic greedy framework to the graph coloring problem is presented in Supplement VI. Future work will explore the integration of these TRNGs into parallel and distributed computing architectures, as well as their combination with advanced machine learning models to further expand the capabilities of probabilistic optimization methods. This research establishes a solid foundation for leveraging hardware-level stochasticity in computational algorithms, offering additional possibilities for tackling complex optimization challenges with greater efficiency and effectiveness.

Methods
The stack structure of the employed STT-MTJ devices 46–48, as depicted in Fig. 1a, is from top to bottom capping/CoFeB/Mo/CoFeB/MgO/CoFeB/Mo/[Co/Pt]n-based synthetic anti-ferromagnetic structure/Seed/SiO2. The multilayer films were deposited by magnetron sputtering on a thermally oxidized silicon substrate under a vacuum environment of 10^-6 Pa. Following deposition, the films were annealed at high temperature in an external magnetic field perpendicular to the film plane. The devices were then patterned into cylindrical STT-MTJs using standard lithography and etching processes. Magneto-transport measurements of the fabricated devices were conducted using an Hprobe H3DM tester. The samples were subsequently connected to a Keysight B1500A semiconductor analyzer and a NI PXIe system through a probe card and adapter board, enabling comprehensive experimental control and data acquisition through a Python-based interface. This setup facilitated precise electrical measurements and switching probability characterization of the STT-MTJs, providing a reliable platform for evaluating their performance as TRNGs. To ensure stable operation and mitigate the impact of device-to-device variations and long-term drift, we previously developed self-stabilizing techniques and pulse-width modulation strategies for MTJ-based TRNGs. These methods allow each MTJ to autonomously correct its switching probabilities, ensuring consistent random number generation across large-scale device arrays without frequent manual calibration 42,49. Specifically, for the TSP solver implementation reported herein (e.g., Burma14 problem), four MTJs were utilized to generate the required configurable random distributions. All MTJ devices used exhibited consistent sigmoid-shaped switching probability curves with stable and reproducible behavior, as characterized and verified prior to algorithmic integration.

Peer review rounds
[{"round": 1, "reviewer_comments": {"reviewer_1": "Yes, I can install and run the code well.", "reviewer_2": "The authors of “Probabilistic Greedy Algorithm Solver Using Magnetic Tunneling Junctions for Travelling Salesman Problem” propose a stochastic variant of the traditional greedy algorithm, utilizing the intrinsic randomness of Magnetic Tunneling Junctions (MTJs) to introduce controllable stochasticity. They employ Bayesian inference to dynamically update the Probability Density functon(PDF), enabling the mapping of the binary Bernoulli TRNG outputs of MTJs to desired probability distributions. This capability is leveraged in their probabilistic greedy algorithm for decision-making during the optimization process. The authors put forth that this approach reduces complexity while improving solution quality for the NP-hard Travelling Salesman Problem (TSP). The work on using Bayesian inference for dynamic PDF generation with MTJ for TSP is particularly interesting, however, the concept itself is not novel and several aspects require clarification and further verification. Therefore, I cannot recommend it for publication in Nature Communications, and quite substantial improvements are necessary for further consideration.\n\n1. The utilization of MTJs in solving the travelling salesman problem (TSP) is not clearly explained. I recommend that the authors provide a more detailed description. For instance, in Figure 2, the authors present random numbers with various distributions, but the connection between this aspect and the TSP is unclear. The authors should quantify and explicitly illustrate the benefits, making the advantage of this approach more apparent.\n2. The authors emphasize the use of TRNGs, but the advantage over commonly used PRNGs remains unclear. PRNGs can effectively generate distributed random numbers, and true randomness is not typically a requirement for probabilistic algorithms like this one, or even for cryptographic operations, as dedicated PRNGs are generally sufficient. The authors should justify the necessity of true randomness in this context and discuss the potential advantages of TRNGs over PRNGs in this specific application.\n3. The concept of \"iteration\" in the manuscript is ambiguous. How is iteration defined in this context? For example, in the case of Burma14, does the iteration count increase by one only when b1 through b14 all become 1, or does it increment with every clock cycle? Clarifying this would enhance the reader's understanding.\n4. The probabilistic greedy algorithm proposed by the authors closely resembles the epsilon-greedy search widely used in reinforcement learning and machine learning. Epsilon-greedy methods strike a balance between exploration (randomness) and exploitation (greedy optimization). There is no acknowledgement of these existing methods, as epsilon greedy also combines randomness into the greedy algorithm with a Q learning parameter. There exists literature on these techniques and an instance of TSP implementation as well in “doi.org/10.1049/tje2.12303”, the details of which are missing. The authors do not discuss how their approach is unique or the impact of dynamic PDF generation with MTJs.\n5. There are specific details on their measurement setup but not on the MTJ devices they are using. Like variation in the patterned device dimension, the switching curve deviations of MTJs, cycling degradation and the impact of temperature changes on device switching characteristics. Also, what methods are employed to mitigate if such issues are present? The sigmoid switching probability curve should be discussed for all the devices being used to solve the TSP problem and mention the number of devices used to solve the problem.\n6. The voltage control as discussed by the authors is highly precise and stabilized with feedback as mentioned in the supplementary. However, there are concerns about how such precision will be maintained when scaling the system to address larger problems. When transitioning to on-chip implementations, maintaining precision will require the integration of high-resolution ADCs and DACs impacting overall system performance.\n7. The manuscript lacks a detailed evaluation of the randomness and entropy tests for the TRNG-generated random bitstream data. The authors just briefly touch upon the neighbour correlations of the data generated out of the Bayesian inference. It is also unclear whether the MTJs employed in their setup require postprocessing of the random bitstreams due to device variations, control and environment impacts that alter the device switching characteristics. The speed of random bitstream generation has not been explicitly addressed. Although they mention in their previous work on SOT-MTJ [32] that they pass the randomness tests with post-processing, there is no such discussion in this work.\n8. The conversion of binary Bernoulli TRNG to output based on any PDF, especially Gaussian distribution using the Bayesian inference is a versatile approach. The distribution is used as the prior and based on conditional probability the voltages to the MTJ are controlled, generating random numbers in the required probability distribution. The authors outline this already in their previous work in reference [32]. While dynamically computing the PDF for TSP is a good strategy, the conditional probability limits the speed and control of the MTJs as they depend on the outcome of the previous node. The authors need to address and clarify this issue.\n9. The voltage precision plays a critical role in achieving the desired probability distributions, and as the problem scales the requirement becomes more stringent. Conditional probabilities that are close in value demand highly precise and stable voltage adjustments, along with a repeatable sigmoidal switching trend. The shape and consistency of the sigmoid curve are crucial for accurately determining the resulting PDF, but variations in device characteristics can significantly impact this curve. There is no discussion on how the authors plan to address such issues when scaling, as they currently use precision instruments to apply the voltage.\n10. The authors describe that the kBT value is empirically found for optimal balance between exploration and exploitation. However, this implies that kBT would need to be tuned for every specific problem instance or whenever other hyperparameters of the algorithm are modified. The authors should provide more discussion on how this parameter is affected. One can see that kBT is 60 in the burma14 a 14 city TSP and 1 in the st70 a 70 city TSP suggesting significant variability in its value. Then this search would be similar to the Boltzmann machine-based SA, where each temperature step would govern a local search. Instead of the algorithm finding one on its own, here the optimal temperature is predetermined empirically. Finding this optimal temperature would then become a problem on its own. I suggest that the authors provide a theoretical framework or methodology to determine the optimized kBT for different scenarios.\n11. Figure 4(c) and (e) represent the density of solutions, and it is unclear how many solutions form the basis of these density metrics. The metrics can be discussed in terms of the probability of a solution for better clarity. There is no mention of the time taken to solve these TSP instances or any insight into the trend of time to solution as the problem size increases. Only algorithm space and time complexities are provided. The actual time required by their hardware to solve the problem is not discussed. The analysis of the energy and area occupied by their system is also vital, which is absent.\n12. The authors have solved st70 TSP by simulating the probabilistic greedy search algorithm. The authors of reference [36] have implemented a similar st70 problem on hardware. With simulation data provided by the authors, a proper comparison cannot be drawn on the performance of the proposed approach. Factors of voltage precision levels or the number of available hardware MTJ devices could restrict larger-scale implementation like the 70-city problem in the probabilistic greedy methods with MTJs. Benchmarking different methods in terms of hardware performance is essential to substantiate the main claim. A scalability analysis should be included, showing the computational costs and performance metrics as the number of cities increases.\n13. The information presented in Figure 5 is insufficiently detailed. The subfigures of Fig. 5 should also be cited properly in the main text. In Figure 5b, the axes lack numerical values, and concepts such as time and space complexity are not adequately defined. In Figure 5d, the comparison details are insufficient—are optimal parameters used for the alternative methods? There is only block diagram in Fig. 5e. What will the system performance be expected in Fig. 5e? Some quantitative analysis would be required. While the authors claim superior performance in solution quality and convergence speed compared to classical methods, this is not convincingly demonstrated. I further recommend that the authors scale up the number of cities incrementally using different methods and present the results to better illustrate the performance of their proposed method, and provide a quantitative comparison of their algorithm performance with other state-of-the-art approaches, particularly in terms of solution quality and scalability. Benchmarking against state-of-the-art combinatorial optimization problem (COP) solvers would also help establish the novelty and effectiveness of the proposed algorithm.\n\nMinor comments\n1. The paper mentions \"n\" in the context of scalability but does not define it clearly upon first usage.\n2. The statement that \"multiple MTJs are connected\" lacks specificity regarding the exact number of MTJs.\n3. Fig. 1e shows a switching characteristic with respect to time similar to superparamagnetic MTJ, which is against a stable STT-MTJ behaviour. This confusion should be addressed.\n4. Measuring only the neighbouring correlation of generated random numbers is insufficient to demonstrate statistical independence or high-quality randomness. The authors should validate the quality of their random numbers by testing the entire sequence using standard statistical tests.\n5. Figure 4(b) explanation on Page 8 of the main text has an error in identifying the curves.\n6. In Figure 4(e) what is Density (best*50), is it a distribution plot of solutions with 0 kilometers of the known optimal as mentioned on Page 8 of the main text? And the numbers on the peak are the maximum number of solutions giving exact distances? More clarity is required.\n7. Figure 5(d) shows the results of different heuristic algorithms with the error bars, there is no mention of how many samples is the error bar drawn. Prob-Greedy data is not present for 10^5 iterations in solving st70 on simulation?\n8. In the description and main text explanation of Figure 4(d) optimal solution with 1000 repetitions is used, but in the graph the axis says iterations. Are repetitions and iterations used interchangeably? Or are the authors performing 1000 repetitions of the iterations?\n9. More quantitative description and analysis would be beneficial in Supplemental Information.", "reviewer_3": "The manuscript introduces a probabilistic greedy algorithm based on stochastic Magnetic Tunnel Junction (MTJ) in the framework of probabilistic computing. Through dynamically modulating the degree of randomness, the algorithm herein has manifested the performance in combinatorial optimization problems. The authors claim that, when applied to the Traveling Salesman Problem, this algorithm surpasses other classical approaches, characterized by the solution quality and more rapid convergence speed.\n\nOverall Evaluation: This work is overall coherent. However, it does not meet the high standard of Nature Communications due to the lack of both novelty and enough new results:\n(1) The key experimental finding in this work is that four asynchronous MTJs are utilized to generate the desired probability distribution functon(Figure 2). These results have already been reported and well-studied in a previous paper by the same group [Advanced Science, 11(23) 2402182 (2024)]. The probability distributions are the same, just with a different set of measurement data.\n(2) The probabilistic greedy algorithm highlighted in this work is also not new. The concepts and algorithms have been previously reported in several papers many years ago [Computers & Operations Research, 37: 432 (2010); IEEE Transactions on Communications, 581: 3286 (2010); Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic (ISMVL), Victoria, CANADA, F 2012 May 14-16, (2012)].\n(3) The scale of the problem solved (14 cities by experiment and 70 cities by simulation) is not large enough as compared to a recent experimental work [ref. 36 published in NC] where 80 sMTJs are used in hardware to solve the 70-city TSP. Considering these facts, this work only has incremental contribution compared to the established literatures. It is suitable to publish in a more specified journal with a few technical issues properly addressed.\n\nTechnical Concerns:\n(1) The manuscript mentions that the magnetization direction of the free layer of the MTJ is altered by applying current pulses. However, it fails to specify the magnitude and duration of the applied pulses, as well as the measurement rate. This is important when comparing different algorithms in various platforms (CPU, FPGA etc.).\n(2) Four MTJs are utilized to generate the desired probability distribution function through a Bayesian network. Nevertheless, the impact of the differences among MTJs on the probability distribution function is not discussed in the manuscript. It is well-known that device-to-device variations have deep impact on the performance of p-computers.\n(3) The results presented in Figure 4c indicate that the average solution still has a notable deviation from the correct solution. An in-depth analysis of the underlying causes should be provided. Moreover, there is a discrepancy between the colors of the curves depicted in Figure 4b and the corresponding descriptions in the manuscript, which may cause confusion for readers.\n(4) The simulation in Figure 5c indicates that the algorithm's performance is more sensitive to the parameter k_B T. Then, for problems of a larger scale, will there be a situation where the differences in k_B T are extremely small and indistinguishable?\n(5) Although this algorithm outperforms the traditional greedy algorithm in solving the Traveling Salesman Problem (TSP), whether it is equally effective for other types of combinatorial optimization problems remains unclear.\n(6) In Figure 1d, the data points are in green, but they are miswritten as \"blue circles\" in the manuscript."}, "author_response": "Response Letter to Reviewers - NCOMMS-24-82665\n----------------------------------------------------------------------------------------------------------------------\nWe sincerely appreciate the reviewers for their time and effort in carefully evaluating our manuscript\nand for providing insightful and constructive feedback. We have carefully considered all comments\nand incorporated our responses into the revised manuscript as appropriate. We believe that our\nrevisions effectively address the reviewers' concerns. Below, we provide a point-by-point response\nto each of the reviewers' comments.\n----------------------------------------------------------------------\nReviewer #1\n----------------------------------------------------------------------\nComment: The manuscript, entitled “Probabilistic Greedy Algorithm Solver Using Magnetic\nTunneling Junctions for Traveling Salesman Problem,” presents a forward-looking approach to\nhardware-accelerated combinatorial optimization. By leveraging the inherent stochastic behavior of\nspin-transfer torque magnetic tunneling junctions (STT-MTJs), the authors demonstrate a\nprobabilistic greedy algorithm capable of addressing the traveling salesman problem (TSP) with\nnotable efficiency. Through the adjustable true random number generation of MTJs, the work\nenables dynamic probability distribution configurations and achieves a smooth transition between\npurely greedy and fully random search strategies by tuning a “temperature” parameter.\nResponse: We sincerely appreciate the reviewer’s thoughtful assessment of our work and their\nrecognition of its novelty in the context of hardware-accelerated combinatorial optimization. Our\napproach aims to harness the intrinsic stochasticity of STT-MTJs to introduce a tunable probabilistic\ngreedy algorithm, and we are pleased that the reviewer acknowledges both the fundamental\ninnovation and the practical implications of this design. The ability to dynamically configure any\narbitrarily defined probability distribution as required through MTJ-based TRNGs enables a smooth\nand controlled transition between purely greedy and fully random search strategies, which we\nbelieve represents a valuable advancement in probabilistic computing. We are encouraged by the\nreviewer’s positive evaluation and are grateful for their insightful perspective on the potential\nimpact of our methodology.\nComment: Beyond its methodological novelty, this work is substantiated by thorough experimental\nresults and simulations. The demonstrations on both a smaller-scale TSP (Burma14) and a larger\ninstance (st70) highlight the scalability and robustness of the proposed solver. In doing so, the\nauthors provide compelling evidence that integrating configurable MTJ-based TRNGs can\nsignificantly improve solution quality and convergence speed when compared to classical\napproaches such as simulated annealing and genetic algorithms. Especially, they demonstrated that\nthe encoding efficiency using these PDF-configurable TRNGs (log N) is much higher than that of\n2\nthe classic Boltzmann machines for the TSP problems (N2). Furthermore, the combination of\nhardware-level randomness with a carefully designed probabilistic search algorithm appears to be a\npromising direction for tackling NP-hard problems. The authors’ success with TSP underscores the\npotential for broader applications in fields such as scheduling, graph partitioning, and other complex\noptimization challenges.\nResponse: We greatly appreciate the reviewer’s recognition of the robustness and scalability of our\napproach, as well as the comprehensive experimental validation that supports our findings.\nDemonstrating the effectiveness of our solver across different TSP instances, from small-scale\n(Burma14) to larger-scale (st70), was an essential aspect of our study, and we are pleased and\ngrateful that the reviewer found these results compelling. In particular, the acknowledgment of our\nencoding efficiency advantage over classical Boltzmann machines (log N vs. N2) is highly\n2\nencouraging and insightful, as it highlights the fundamental efficiency gains enabled by our newly\ndeveloped PDF-configurable TRNGs compared to the classical Ising or Boltzmann machines.\nAdditionally, we appreciate the reviewer’s perspective on the broader applicability of our approach\nb approach\nbeyond TSP, including potential extensions to scheduling, graph partitioning, and other NP-hard\nproblems. We have made refinements to the manuscript to clarify these aspects and further\nemphasize the generalizability of our probabilistic framework.\nComment: Overall, this manuscript provides a compelling contribution to the burgeoning field of\nprobabilistic computing. The implementation of MTJ-based TRNGs in a customizable way —\ntogether with a carefully orchestrated algorithmic structure — illustrates a path toward higher-\nperformance solutions for large-scale optimization tasks. The multi-faceted evaluation, spanning\ndevice fabrication, experimental verification, and algorithmic benchmarking, is particularly\ncommendable. In my opinion, the paper is well-structured, clearly written, and of direct interest to\na broad cross-section of researchers working on spintronics, computational optimization, and\nhardware-accelerated algorithms. I therefore strongly recommend its publication in Nature\nCommunications, provided the authors address the questions and minor enhancements noted below.\nIn addition, I suggest adding further references that connect this work to foundational methods in\ncombinatorial optimization and TRNG-based hardware design. I believe clarifications on these\nmatters, alongside the inclusion of key additional citations, would further strengthen the\nmanuscript’s narrative and ensure maximum impact for a wide readership.\nResponse: We are sincerely grateful for the reviewer’s strong endorsement of our manuscript and\ntheir recognition of its relevance across multiple research domains, including spintronics,\ncomputational optimization, and hardware-accelerated algorithms. The reviewer’s positive remarks\non the structure and clarity of the manuscript are especially valuable, as we have strived to present\nour findings in a rigorous yet accessible manner. In response to the reviewer’s suggestion, we have\ncarefully reviewed and expanded our references to better connect our work to foundational research\nin combinatorial optimization and TRNG-based hardware design. These additional citations provide\nfurther context and reinforce the contribution of our approach within the broader landscape of\nprobabilistic computing. Worth noting, currently, we have also found that our PDF-configurable\nTRNGs with the structure of a Bayesian Inference Network have shared exactly the same network\narchitecture as the autoregression model widely adopted in many Large Language Models (LLMs).\nIn this autoregression model, the probability of sampling a new token depends on the conditional\nprobabilities of previously involved tokens, which is actually similar to what we have done in the\nprobabilistic Greedy algorithm, where tokens are replaced by cities. This similarity also highlights\nthe applicability of our developed methodology in generative AI, particularly in LLMs.\nFollowing this general response, we provide a detailed, point-by-point reply to each of the\nreviewer’s specific comments and questions. We appreciate the reviewer’s constructive feedback\nand have made careful revisions to ensure the manuscript is as clear, comprehensive, and impactful\nas possible.\nQuestion #1-1: The authors provide strong experimental evidence of repeatable MTJ switching\nprobabilities at varying voltages. However, can the authors expand on how larger-scale device\nvariations — such as minor manufacturing inconsistencies or drift over time — might affect solution\nquality? Are there calibration strategies to ensure consistent TRNG behavior across an array of\nMTJs?\nResponse: We appreciate the reviewer’s insightful comment on the impact of large-scale device\nvariations, including minor manufacturing inconsistencies and long-term drift. These challenges,\nobjectively existent and practical for current state-of-the art-technologies1,2 as realized by the referee,\nhave been indeed carefully considered in our recent work, where we proposed strategies to ensure\nstable operation of MTJ-based TRNGs across large device arrays. In one of our published papers3,\nwe introduced a self-stabilizing approach that dynamically adjusts the sampling probability based\non an MTJ’s current state. This methodology enables devices to automatically and quickly converge\nto the desired switching probability over time without pre-calibration, effectively mitigating initial\nstate differences and slight fabrication variations.\nBuilding on this, our recent work4 further addresses drift by exploring alternative control strategies.\nWhile voltage adjustment is a conventional method for correcting deviations, fine-tuning voltage\namplitude with high precision can be impractical in engineering applications. Instead, we propose\npulse width modulation (PWM) as a more feasible and precise approach, as adjusting pulse duration\nis easier to implement while still significantly influencing switching behavior. By embedding an on-\nchip calibration feedback loop that periodically evaluates each MTJ’s characteristics, our system\ncan dynamically maintain the intended probability distribution, ensuring reliable random number\ngeneration despite device-to-device variations or environmental fluctuations. Overall, adopting\npulse width modulation as a practical engineering solution enhances the robustness of the TRNG,\nmaking it well-suited for applications requiring high-quality randomness, such as secure\ncommunications and probabilistic computing.\nIn the revised manuscript, we added some discussion on the above point at the end of Methods:\n“To ensure stable operation and mitigate the impact of device-to-device variations and long-\nterm drift, we previously developed self-stabilizing techniques and pulse-width modulation\nstrategies for MTJ-based TRNGs. These methods allow each MTJ to autonomously correct its\nswitching probabilities, ensuring consistent random number generation across large-scale\ndevice arrays without frequent manual calibration.”\nFigure R1. The Downcalibration-2 strategy outputs target switching probabilities of 20% (a) and\n80% (b). The top panels show the resistance switching behavior over time, the middle panels present\nthe dynamically adjusted driving voltage of the MTJ during each calibration step, and the bottom\npanels illustrate the rolling probability (calculated over the last 50 steps). In both cases, the system\nstarts with randomly initialized voltage conditions, rapidly and automatically converges to the target\nprobabilities, and stabilizes with high precision4.\nQuestion #1-2: The manuscript focuses on the traveling salesman problem as a case study. Could\nthe authors elaborate on how seamlessly their approach can be adapted to other combinatorial\nproblems, for example, graph coloring or scheduling? Would the same “temperature” tuning\nprinciple be sufficient, or might additional modifications be required?\nResponse: Thank you for raising this excellent point. We focused on the TSP as a representative\nNP-hard problem to demonstrate the efficacy of our framework, but the underlying principles are\nindeed applicable to a wide range of combinatorial optimization tasks. The key lies in formulating\neach problem’s Loss (or Cost) function and incorporating it into the probabilistic decision-making\nprocess. For example, in graph coloring, the algorithm would probabilistically select how to color\neach node to minimize the number of conflicts, while in scheduling, it would seek to reduce overall\nmakes pan or resource contention. The “temperature” parameter would again play a similar role in\nbalancing exploration and exploitation: at low temperature, the algorithm favors local minima; at\nhigh temperature, it explores more globally. Although the specific probability distribution shaping\nmay need fine-tuning to reflect the constraints or cost landscape of each problem, the overarching\nmethod — leveraging MTJ-generated randomness within a probabilistic greedy framework —\nremains largely intact. Therefore, we anticipate that only minor modifications, such as redefining\nthe cost function and adjusting the temperature schedule, would be required and enough to\ngeneralize our approach to other NP-hard scenarios.\nHere we can easily adopt the idea of probabilistic greedy algorithm into the graph coloring problem\nwith the basic equations as follows. The graph coloring problem requires assigning colors to the\nvertices of a graph G(V, E), such that no two adjacent vertices share the same color, while\nminimizing the total number of colors used. To adapt our MTJ-assisted probabilistic greedy\nframework, we define a probabilistic selection process for color assignment at each step, guided by\na dynamically adjusted probability distribution based on a cost function. Let us define:\n V = {v , v , …, v }: the set of vertices,\n1 2 n\n C = {c , c , …, c }: the set of available colors (with k large enough to allow a feasible\n1 2 k\ncoloring),\n conflict (v, c): the number of adjacent vertices of v already assigned color c.\ni j i j\nFor each vertex v, we define the cost of assigning color c as:\ni j\nE conflict(v,c )\nij i j\nwhere 𝜆 > 0 is a penalty weight that amplifies the cost of conflicts.\nThe probability of assigning color c to vertex v is then determined by the Boltzmann distribution:\nj i\neE\nij\n/(k\nB\nT)\nP \nij k eE\nil\n/(k\nB\nT)\nl1\nThis formulation ensures that color assignments with fewer conflicts are more probable, especially\nat lower temperature 𝑇, while allowing more exploration at higher 𝑇.\nThe coloring process proceeds as follows:\n1. Initialize all vertex colors to unassigned.\n2. For each uncolored vertex v, compute P for all available colors 𝑐∈C based on the current\ni ij 𝑗\npartial coloring.\n3. Use MTJ-based TRNG and PDF control to sample from P and assign color 𝑐 to 𝑣.\nij 𝑗 𝑖\n4. Repeat steps 2 – 3 until all vertices are colored.\nOptionally, the total number of used colors can be minimized by starting from a conservative upper\nbound 𝑘, and gradually reducing it while checking feasibility.\nThis probabilistic greedy strategy preserves the same core elements from our TSP implementation:\n The stochastic nature is governed by tunable k T,\nB\n MTJ-generated Bernoulli bits are used to construct arbitrary PDFs for decision-making,\n The decision process is localized and sequential, making it naturally scalable.\nThis adaptation highlights the generality of our method: by redefining the cost function 𝐸 and\nupdating the probability calculation, the same hardware-friendly framework can be extended to a\nwide class of combinatorial optimization problems.\nQuestion #1-3: The authors note that the probability distribution used in each city-selection step\nchanges over time. Is there any significant overhead associated with frequently reconfiguring the\nMTJ TRNG voltage settings or readout circuitry during an iterative process? A brief discussion of\npotential timing constraints or hardware-level overhead would further clarify the performance.\nResponse: We appreciate this question, as practical considerations are crucial when integrating\nhardware-level randomness into iterative algorithms. Our experiments indicate that the overhead of\nupdating the MTJ-based TRNG’s probability distribution is relatively modest, mainly because the\nvoltage reconfiguration is achieved through adjusting a small set of control parameters. In practice,\neach step involves updating the “temperature” or weight parameters of the Bayesian network, which\ncan be done efficiently via well-defined write signals without requiring a complete reset of the entire\nsystem. Additionally, parallelism helps mitigate reconfiguration delays: while one set of MTJs is\nbeing tuned or read, another set can continue generating random numbers according to a previously\nestablished distribution. This pipeline approach reduces idle time and keeps the overall process\nmoving at an acceptable rate. As a result, the timing constraints introduced by dynamic PDF\nreconfiguration have not posed a significant bottleneck in our tests. Of course, if one were to scale\nthe system to very large arrays of MTJs, careful hardware design and scheduling would become\nessential to keep reconfiguration overhead low, but we remain optimistic that such optimizations\ncan be handled without drastically affecting the algorithm’s runtime performance, considering the\nbottleneck of probabilistic computing generally lies in the high-quality prediction of PDF towards\nconvergence instead of PDF reconfiguration; the former has been ensured by the Boltzmann\ndistribution and the corresponding annealing strategy in our probabilistic greedy algorithm.\nQuestion #1-4: While the authors compare their method to simulated annealing and genetic\nalgorithms, have they considered advanced metaheuristics like ant colony optimization or particle\nswarm optimization? Adding a sentence or two on how the proposed solver might be positioned\nrelative to these approaches could strengthen the discussion.\nResponse: We appreciate the reviewer’s suggestion to extend our discussion to advanced\nmetaheuristics such as ant colony optimization (ACO) and particle swarm optimization (PSO). In\nthe revised version of the manuscript, we will include a dedicated paragraph to position our proposed\nsolver relative to these approaches. More specifically:\n1. Integration of Hardware-Level Randomness\nBoth ACO and PSO rely on iterative improvement processes guided by decentralized,\nswarm-like interactions. In ACO, artificial ants traverse a problem space by depositing and\nfollowing pheromone trails, whereas PSO tracks the dynamic “velocity” and “position” of\neach particle as it searches for an optimal or near-optimal solution. A natural opportunity\narises to inject the hardware-level randomness from our STT-MTJ-based TRNGs into these\nupdates — whether it can introduce controlled noise in the pheromone intensities or\ngenerating stochastic velocity perturbations for each particle. By exploiting dynamically\nreconfigurable probability distributions, researchers could experiment with new methods\nof diversifying search trajectories and accelerating the escape from local optima.\n2. Enhanced Exploration vs. Exploitation\nA common theme in metaheuristics is balancing exploration (broad search) and exploitation\n(refining promising areas). In ACO, for example, highly valued paths become strongly\nreinforced with pheromones, potentially causing premature convergence if the algorithm\nlacks sufficient randomness to explore alternatives. Our MTJ-based TRNG framework can\nhelp mitigate such issues by regulating the level of probabilistic deviations during the ant’s\ndecision process, thereby preserving a baseline of exploration. PSO encounters a similar\ntrade-off, where particles risk clustering around a suboptimal region; injecting hardware-\nlevel randomness in velocity updates could systematically introduce controlled exploration\nat each iteration, comparable to adjusting “inertia weight” or “constriction coefficients” in\nstandard PSO formulations.\n3. Potential Benefits for Convergence\nAnother compelling aspect is speed. One challenge in advanced metaheuristics is the\ncomputational overhead needed to manage multiple agents, track their interactions, and\nupdate parameters. By using MTJ arrays as direct sources of random draws, we sidestep\npurely software-based or pseudo-random routines, potentially streamlining the stochastic\nelements that underpin ACO or PSO. This integration might lead to faster or more energy-\nefficient convergence, particularly if the TRNG can be implemented in parallel, allowing\ndifferent “ants” or “particles” to sample random numbers simultaneously with minimal\nlatency.\n4. Implications for Broader Problem Classes\nAlthough we center our discussion on TSP, ACO and PSO are routinely applied to a broad\nrange of NP-hard problems (e.g., scheduling, constraint satisfaction, continuous\noptimization). Because the probabilistic framework we propose does not depend on\nproblem-specific features but rather on a generalized cost function and temperature-like\ncontrol, we anticipate that the underlying methodology would translate well into these\ncontexts. Adjustments would primarily involve mapping the problem variables (e.g., partial\nschedules or partial graph colorings) onto the corresponding algorithm steps (pheromone\nreinforcement, velocity update, etc.) and then injecting MTJ-based randomness wherever\nit is most beneficial for diversified exploration.\nIn sum, we view our probabilistic hardware solver as highly complementary to advanced\nmetaheuristics: it provides a physically grounded, tunable source of randomness that can be tailored\nto the needs of algorithms like ACO and PSO. By adding a few sentences in the revised text, we\naim to highlight these synergies more explicitly, illustrating how our MTJ-based TRNG could be a\nvaluable resource not just for probabilistic greedy approaches, but also for a wider family of\ntechniques that seek efficiency and resilience in large-scale optimization.\nIn the revised manuscript, we added some discussion on the above point as follows:\n“Moreover, our MTJ-based probabilistic framework can also benefit advanced metaheuristics\nsuch as Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO). By\nintegrating hardware-level randomness, these metaheuristics can systematically enhance their\nexploration strategies, potentially leading to improved solution quality and faster convergence\ndue to more effective escape from local optima.”\nQuestion #1-5: While the authors compare their method to simulated annealing and genetic algorithms, have they considered advanced metaheuristics like ant colony optimization or particle swarm optimization? Adding a sentence or two on how the proposed solver might be positioned relative to these approaches could strengthen the discussion.\nResponse: We appreciate this insightful question regarding the applicability of our approach to\nmore extensive TSP scenarios and, by extension, other large-scale optimization tasks. While our\nwork currently demonstrates success up to 70 cities, we recognize that genuine industrial or\nlogistical problems often involve hundreds or thousands of nodes. From an algorithmic perspective,\nthe core probabilistic greedy principle should, in principle, remain effective at larger scales because\nthe temperature or simulated annealing mechanism (or an equivalent parameter) can still balance\nexploration and exploitation across a broader decision space. However, as the number of nodes\nincreases, two primary considerations arise:\n1. Time Complexity: Even though we have shown gains over classical methods, any TSP\nsolver contends with inherent combinatorial growth. Our hardware approach helps mitigate\nthis by accelerating the randomness generation and selection processes, but we would still\nexpect solution times to increase with larger node counts. We are therefore exploring\nstrategies such as parallelizing or “tiling” portions of the problem across multiple MTJ\narrays to handle partial sets of cities in tandem, then merging these subproblem solutions,\nthe so-called divide-and-conquer strategy as used in Ref.7 or Ref. [36] in the main text.\n2. Convergence and Parameter Tuning: With a larger search space, maintaining an\nappropriate balance between exploitation and exploration becomes more delicate. We\nforesee a need for adaptive temperature schedules or multi-phase temperature schemes that\ninitially promote greater exploration (to avoid early local optima) and gradually shift to\nmore exploitative modes. While the existing mechanism is already flexible, large-scale\ninstances may benefit from “meta-heuristic” tuning or automatic temperature adaptation.\nOverall, we do not see any fundamental barrier to scaling up, but achieving comparable solution\nquality and convergence speed will hinge on judicious parameter tuning, possible hardware\nparallelism, and potentially breaking down massive TSPs into more manageable subproblems.\nQuestion #1-6: In practical systems, transient faults or soft errors (e.g., due to electromagnetic\ninterference) can occasionally produce outlier random values. Do the authors foresee the need for\nerror-correction logic in the random number generation process, or is the probabilistic nature of the\nalgorithm itself sufficient to absorb occasional anomalies?\nResponse: We also appreciate the query concerning transient faults or soft errors, which can indeed\noccur in real-world electronics due to electromagnetic interference, cosmic rays, or other\nenvironmental factors. Within our hardware-based stochastic framework, occasional random\noutliers are less likely to derail performance for two reasons:\n1. Probabilistic Nature of the Algorithm: Since our approach inherently relies on sampling\nfrom a probability distribution, small deviations or occasional spurious values tend to be\nabsorbed in the normal iteration-to-iteration variability of the algorithm. A single outlier in\na random sample is less detrimental here than it would be in deterministic logic, especially\nwhen repeated samplings guide the search over many iterations. We can actually treat those\ntransient faults or soft errors, if any, as random initializations or resets of networks, which\nis exactly what we have done in a long-term optimization process.\n2. Built-in Redundancy and Calibration: In addition, any self-calibration or self-stabilizing\nmeasures we employ for device variation can also help detect and correct persistent\nanomalies in MTJ switching statistics. If a particular MTJ or set of MTJs starts exhibiting\nhighly aberrant behavior, the calibration routine would detect deviations from the expected\ndistribution and adjust voltage levels or exclude the faulty device(s) from the random pool.\nThat said, if a system were deployed in highly critical or noisy environments, more explicit error-\ncorrection or majority-voting schemes at the TRNG stage could be considered. Such measures\nwould provide an extra layer of confidence. However, for most use cases and standard operating\nconditions, we have found the inherent resilience of the probabilistic approach sufficient to mitigate\nissues arising from occasional soft errors.\nQuestion #1-7: The temperature-related parameter (k T) appears in several figures and equations.\nB\nA single consistent notation (e.g., always using k T or T) throughout the text, figures, and captions\nB\nwould help readability.\nResponse: We thank the reviewer for highlighting this important point regarding notation\nconsistency. In response to this comment, we have carefully revised the manuscript and figures to\nuniformly adopt the notation k T throughout the entire paper, including equations, figure captions,\nB\nand main text descriptions. This modification significantly enhances readability and ensures a clear,\nconsistent representation of the temperature-related parameter across all sections.\nQuestion #1-8: The paper occasionally shifts between “true random number generators,” “hardware\nrandomness,” and “probabilistic bits.” Standardizing the terminology — perhaps defining each\nconcept at the outset — would streamline the reader’s experience.\nResponse: We sincerely appreciate the reviewer’s helpful suggestion regarding the terminology\nstandardization. To enhance readability without disrupting the manuscript flow, we have subtly\nintegrated concise explanations of the terms \"true random number generators (TRNGs)\", \"hardware\nrandomness\", and \"probabilistic bits (p-bits)\" within their first mentions in the Introduction section.\nThis approach naturally clarifies the concepts while maintaining the manuscript’s coherent narrative\nstyle.\nQuestion #1-9: In addition to the classical references to combinatorial optimization and TSP, it\nmight be worthwhile to cite a few seminal articles on spintronic TRNGs or in-memory computing\napproaches. This could underscore how the present work builds on, and differs from, earlier device-\ncentric studies.\nResponse: We thank the reviewer for suggesting additional important references to further\ncontextualize our work within the broader field of spintronic TRNGs and in-memory computing.\nFollowing the reviewer’s advice, we have cited the recommended seminal papers (Fukushima et al.,\nAppl. Phys. Express 2014; Choi et al., IEDM 2014; Vodenicarevic et al., Phys. Rev. Applied 2017)\nin the Introduction. We explicitly clarified how our approach extends and differs from these earlier\ndevice-centric studies by highlighting our unique capability of dynamically configuring probability\ndistributions, thus enhancing flexibility and efficiency in probabilistic algorithm applications.\n----------------------------------------------------------------------\nReviewer #2\n----------------------------------------------------------------------\nComment: The authors of “Probabilistic Greedy Algorithm Solver Using Magnetic Tunneling\nJunctions for Travelling Salesman Problem” propose a stochastic variant of the traditional greedy\nalgorithm, utilizing the intrinsic randomness of Magnetic Tunneling Junctions (MTJs) to introduce\ncontrollable stochasticity. They employ Bayesian inference to dynamically update the Probability\nDensity function (PDF), enabling the mapping of the binary Bernoulli TRNG outputs of MTJs to\ndesired probability distributions. This capability is leveraged in their probabilistic greedy algorithm\nfor decision-making during the optimization process. The authors put forth that this approach\nreduces complexity while improving solution quality for the NP-hard Travelling Salesman Problem\n(TSP). The work on using Bayesian inference for dynamic PDF generation with MTJ for TSP is\nparticularly interesting, however, the concept itself is not novel and several aspects require\nclarification and further verification. Therefore, I cannot recommend it for publication in Nature\nCommunications, and quite substantial improvements are necessary for further consideration.\nResponse: We sincerely thank Reviewer #2 for carefully reading our manuscript and providing\ndetailed feedbacks and especially the encouraging comment “the work on using Bayesian inference\nfor dynamic PDF generation with MTJ for TSP is particularly interesting”. While we acknowledge\nthe concerns raised, we respectfully clarify that the presented work indeed introduces significant\nnovelty and advancement compared to previous studies. Specifically, our paper reports a novel\nintegration of hardware-based true randomness generated by Magnetic Tunnel Junctions (MTJs)\ninto a probabilistic greedy algorithm framework. Contrary to the reviewer’s general assessment of\nlimited novelty, Reviewer #1 explicitly highlights this aspect as a “forward-looking approach” and\nemphasizes its “methodological novelty,” noting that our study convincingly demonstrates\nimproved scalability and robustness compared to classical methods like simulated annealing and\ngenetic algorithms. Reviewer #1 further commends the multi-faceted evaluation spanning device\nfabrication, experimental verification, and algorithm benchmarking, acknowledging the importance\nand distinctiveness of our contributions.\nRegarding the concern about the utilization of Bayesian inference to dynamically update probability\ndistributions, we clarify that the integration of MTJ-based hardware randomness and Bayesian\nupdating within a probabilistic greedy solver framework has not previously been reported. Earlier\nstudies employing Bayesian methods or MTJ-based random number generators (TRNGs) typically\nfocused separately on either hardware-level randomness characterization or probabilistic computing\nat a conceptual or simulation level. Our paper, however, bridges these aspects uniquely,\nimplementing dynamically configurable hardware-based probability distributions directly into a\nprobabilistic greedy algorithm tailored for combinatorial optimization problems, specifically, the\nTSP for the first time. This experimental integration significantly advances beyond existing\nliteratures, enabling seamless tuning of randomness and resulting in and demonstrating substantial\npractical performance gains — precisely the novelty and utility emphasized by Reviewer #1.\nWe understand the need for further clarifications and verification highlighted by Reviewer #2, and\nwe will comprehensively address each detailed comment in the subsequent point-by-point responses.\nWe firmly believe that once the requested clarifications are made explicit and additional supporting\ndata or explanations are provided, the novel and substantial contributions of our work will become\nmore transparent, alleviating the reviewer's concerns and demonstrating the manuscript’s suitability\nfor Nature Communications.\nQuestion #2-1: The utilization of MTJs in solving the travelling salesman problem (TSP) is not\nclearly explained. I recommend that the authors provide a more detailed description. For instance,\nin Figure 2, the authors present random numbers with various distributions, but the connection\nbetween this aspect and the TSP is unclear. The authors should quantify and explicitly illustrate the\nbenefits, making the advantage of this approach more apparent.\nResponse: We appreciate the reviewer’s insightful comment, which helped us to recognize the need\nto explicitly clarify the direct connection between MTJ-generated random numbers and the\ndecision-making process of our probabilistic greedy algorithm for TSP.\nIn the probabilistic greedy algorithm presented in our manuscript, the key operation — selecting the\nnext city — relies on generating random numbers from a dynamically updated probability\ndistribution (probability density function, PDF). At each algorithmic step, the probability of\nselecting the next city is explicitly given by Eq. (1):\nP  N  1b exp  d k T  Z\ni1 i i NN B\ni\nEq. (1)\ni NN B\ni\ni1\nThis clearly indicates the necessity of accurately generating random numbers according to a well-\ndefined, step-by-step updated PDF. Here, b denotes the accessibility of City i for the (i+1)th step, b\ni i\n= 1 or 0 if City i has been visited or not. d is the distance between City i and an unvisited one\nNN\ni\nof the rest. Z is the partitional function summing over all the unvisited cities and the sampling\n \npossibility P N of an unvisited city is dependent on the Boltzmann distribution after\ni1 i\nrenormalization by Z in Eq. (1). The PDF ensures the convergence of the algorithm, the highest\nprobability for the global optima. Actually, Eq. (1) is the broadly applied softmax function, which\ndefines a unique PDF among unvisited cities in each step and should be configurated dynamically\nstep-by-step. This is exactly the reason why a PDF-configurable TRNG are desperately needed here.\nTraditional pseudo-random number generators (PRNGs) or typical hardware random number\ngenerators lack the flexibility to dynamically and accurately alter their probability distributions in\nreal-time, particularly across varying intermediate temperature states (k T).\nB\nOur MTJ-based TRNGs\nuniquely overcome this limitation by enabling highly configurable random-number distributions, as\nalready demonstrated experimentally in Figure 2. Specifically, we showed in Figure 2(b–g) that our\nMTJ-based system can reliably and accurately generate random numbers following different,\nprecisely controlled distributions, including Gaussian, uniform, exponential, and user-defined\narbitrary distributions.\nTherefore, the capability shown in Figure 2 directly correlates with the probabilistic selection\nmechanism in our TSP algorithm (Figure 3). At each step, based on Eq. (1), our MTJ-based TRNG\nsystem in real time step-by-step adjusts its random-number output distribution, providing exactly\nthe required random samples to select the next city probabilistically. This not only guarantees\nconsistency with the theoretical PDF but also offers significant encoding efficiency, as this PDF-\nconfigurable MTJ-based approach only requires log N bits of MTJs (where N is the number of cities),\n2\na significant reduction compared to classical Boltzmann-machine or Ising machine encodings that\nrequire N2 bits of binary MTJ TRNGs. This improved encoding efficiency is also the advantage\nover previous ones.\nTo clarify this essential connection, we have explicitly modified our manuscript to include a clear\nstatement on how the experimentally demonstrated random-number generation capabilities (Figure\n2) directly feed into and enable the probabilistic greedy algorithm’s city-selection process (Figure\n3).\nTo further enhance the clarity and intuitiveness of this mechanism, we provide an additional\nexplanatory schematic (Figure R2), which illustrates how different temperature values (k T) alter\nB\nthe probabilistic decision-making process in our algorithm. At low temperature, the city with the\nshortest distance is deterministically chosen, mimicking a classic greedy algorithm. At high\ntemperature, cities are selected with nearly equal probability, akin to random exploration. At\nintermediate values, the selection probability is smoothly distributed following a Boltzmann\ndistribution, striking a balance between exploration and exploitation.\nThis step-by-step probabilistic sampling is directly driven by our MTJ-based TRNGs, whose PDF\ncan be dynamically updated to reflect the current decision state. The hardware block shown in Figure\nR2 (middle-bottom) highlights the compact structure needed for such TRNG-based selection: a\nsmall number of MTJs (log N for N cities) suffices to implement arbitrary probability distributions\n2\nat each step, thereby greatly reducing hardware complexity compared to conventional Ising-based\nsolvers requiring O(N2) coupling nodes. This clear physical-to-algorithmic linkage — from MTJ\nvoltage to switching probability to next-city selection — underpins the novelty and efficiency of\nour probabilistic greedy optimization strategy.\nFigure R2. Schematic illustration of the decision-making process in the probabilistic greedy\nalgorithm for solving TSP. Top: The influence of temperature (T) on city selection probabilities —\nfrom deterministic (T→0), to balanced probabilistic (intermediate T), to fully random (T→∞).\nMiddle: A dynamically updated probability distribution is used to sample the next city. Bottom:\nThis distribution is realized in hardware using MTJ-based TRNG arrays capable of generating\nbinary outcomes according to any desired PDF, with a logic resolution of log N MTJs for N cities.\nefficiently guiding the optimization trajectory.\nQuestion #2-2: The authors emphasize the use of TRNGs, but the advantage over commonly used\nPRNGs remains unclear. PRNGs can effectively generate distributed random numbers, and true\nrandomness is not typically a requirement for probabilistic algorithms like this one, or even for\ncryptographic operations, as dedicated PRNGs are generally sufficient. The authors should justify\nthe necessity of true randomness in this context and discuss the potential advantages of TRNGs over\nPRNGs in this specific application.\nResponse: We thank the reviewer for raising an important question regarding the advantages of true\nrandom number generators (TRNGs) over commonly used pseudo-random number generators\n(PRNGs) in probabilistic algorithms. Although PRNGs indeed produce sequences that approximate\nrandomness, their deterministic nature fundamentally limits their flexibility and real-time\nconfigurability — particularly important for algorithms relying on dynamically varying probability\ndistributions, such as our probabilistic greedy approach.\nSpecifically, the key advantage of our MTJ-based TRNG over traditional PRNGs lies in its intrinsic\nphysical randomness, enabling direct, rapid, and flexible manipulation of the generated probability\ndistributions through external control parameters (such as voltage or pulse width). This feature is\ncrucial for our algorithm, as the selection probability distribution for choosing the next city changes\ndynamically at every iteration based on updated intermediate parameters (e.g., distances and\ntemperature k T). In contrast, traditional PRNGs cannot natively support direct, instantaneous, and\nB\nprecise manipulation of their output probability distributions. Achieving similar configurability with\nPRNGs would typically require additional computational overhead, such as mapping uniformly\ndistributed random numbers into desired distributions using computationally intensive\ntransformations, thus significantly reducing efficiency.\nFurthermore, from a hardware perspective, MTJ-based TRNGs inherently offer parallelization and\nultra-low-power operation, making them particularly suitable for energy-efficient, hardware-\naccelerated optimization tasks. This direct physical generation of randomness bypasses the\nalgorithmic complexities associated with PRNG-based software transformations, thus ensuring\nhigher performance, lower latency, and lower power consumption in practical implementations.\nTo clarify this point explicitly in the manuscript, we have added a concise but clear statement\ndescribing the distinct advantages of TRNGs over PRNGs within our specific application context.\nWe would like to highlight the difference between PRNG and PDF-configurable TRNG by using a\ntypical figure from the perspective paper “Probabilistic Neural Computing with Stochastic Devices”\nby S. Misra et al5. While PRNG can be used in probabilistic computing, computing overheads in\nthe soft level are indispensable to translate DPF from a uniform one generated in PRNG into a\ndesired one, which is marked as Level 0 in efficiency and integrity of probability computing systems.\nLevel 1 is more efficient than Level 0 by realizing more complex PDF in hardware than the uniform\none as we have demonstrated in Figure 2 of the revised manuscript. Level 2 can achieve even higher\nefficiency by dynamic and parallel reconfiguration of PDF in real time according to the problem\ninvolved, which is exactly what we have demonstrated in the probabilistic greedy algorithm solver.\nIn this regard, our demonstration represents a remarkable advancement compared to a PRNG system.\nFigure R3 of the perspective paper “Probabilistic Neural Computing with Stochastic Devices” by\nS. Misra et al5.\nQuestion #2-3: The concept of \"iteration\" in the manuscript is ambiguous. How is iteration defined\nin this context? For example, in the case of Burma14, does the iteration count increase by one only\nwhen b1 through b14 all become 1, or does it increment with every clock cycle? Clarifying this\nwould enhance the reader's understanding.\nResponse: We thank the reviewer for highlighting this ambiguity regarding the definition of\n\"iteration\" in our manuscript. We agree this terminology should be clarified explicitly to avoid\nconfusion. In our work, the term \"iteration\" is defined as one complete execution of the path-\nselection process, in which the algorithm sequentially selects each city exactly once until all cities\nhave been visited, forming a complete route (for example, selecting from city 1 to city 14 exactly\nonce in the Burma14 problem constitutes a single iteration). Thus, each \"iteration\" refers to the\ngeneration and evaluation of one full TSP solution (route), rather than a single incremental selection\nstep or a clock cycle.\nTo clearly communicate this definition to readers, we have explicitly clarified this terminology at\nthe first occurrence of the term \"iteration\" in the manuscript. We would like to thank the referee for\npointing out this critical issue.\nQuestion #2-4: The probabilistic greedy algorithm proposed by the authors closely resembles the\nepsilon-greedy search widely used in reinforcement learning and machine learning. Epsilon-greedy\nmethods strike a balance between exploration (randomness) and exploitation (greedy optimization).\nThere is no acknowledgement of these existing methods, as epsilon greedy also combines\nrandomness into the greedy algorithm with a Q learning parameter. There exists literature on these\ntechniques and an instance of TSP implementation as well in “doi.org/10.1049/tje2.12303”, the\ndetails of which are missing. The authors do not discuss how their approach is unique or the impact\nof dynamic PDF generation with MTJs.\nResponse: We sincerely appreciate the reviewer’s critical observation regarding the relationship\nbetween our proposed probabilistic greedy algorithm and the widely known epsilon-greedy methods\nemployed in reinforcement learning and machine learning. We acknowledge that both epsilon-\ngreedy approaches and our probabilistic greedy algorithm share the core principle of balancing\nexploration (randomness) and exploitation (greedy optimization). Nevertheless, we would like to\nemphasize the distinct differences between them and unique contributions of our work clearly:\n1) The traditional epsilon-greedy method typically introduces randomness through a fixed\nparameter (ε), determining the probability of selecting a random choice rather than the\noptimal (greedy) choice at any step. In contrast, our approach dynamically adjusts the\nprobability distribution for selecting the next city at each step. Specifically, the probability\nof selecting each unvisited city is continuously updated according to a precise and strict\nmathematical form (exponential dependence on city distance and temperature parameter\nk T, Eq. (1)). Thus, our algorithm inherently provides a more sophisticated, fine-grained,\nB\nand adaptive form of exploration, compared to the static binary \"greedy vs. random\"\ndecision-making characteristic of epsilon-greedy methods. Worth noting, the dynamic PDF\ndefined in Eq. (1) is delicately designed to force trial solutions to obey the Boltzmann\ndistribution – the lowest route having the highest probability especially at lower\ntemperatures, which ensures the effectiveness and convergence of the algorithm and\nusefulness of the simulated annealing strategy. This is the reason why the PDF at each step\nshould be dynamically modified and also the reason why a PDF-configurable TRNG\nmatches the need of this probabilistic greedy algorithm.\n2) Another major distinction is our direct integration of hardware-level randomness provided\nby MTJ-based TRNGs, enabling real-time, precise, and computationally efficient\ngeneration of dynamically configured probability distributions. While traditional epsilon-\ngreedy methods rely solely on software-generated pseudo-randomness (uniform\ndistribution), our MTJ-based TRNG system enables direct sampling from tailored, arbitrary\nprobability distributions. This intrinsic flexibility allows our algorithm to immediately and\nprecisely adapt its exploration-exploitation strategy in response to changing algorithmic\nconditions, significantly enhancing its performance and scalability, as also indicated by\nabove Figure R2.\n3) From an implementation perspective, our MTJ-based approach also drastically reduces\nhardware complexity, requiring only log N probabilistic bits to represent and select among\nuniform PRNG-based sampling, would require additional computational transformations\nor overhead to achieve similar distributional flexibility, thus potentially limiting efficiency\nand scalability.\nWe agree with the reviewer’s suggestion of explicitly discussing these distinctions, clearly\nacknowledging existing epsilon-greedy methods and highlighting the unique advantages of our\ndynamic PDF generation strategy via MTJ-based hardware randomness. We have therefore\nexplicitly included references to existing epsilon-greedy methodologies (including the reviewer’s\nsuggested reference: doi.org/10.1049/tje2.12303), clarified the conceptual differences, and\nexplicitly described how our MTJ-based approach uniquely enhances the exploration-exploitation\ntrade-off within probabilistic greedy algorithms.\nQuestion #2-5: There are specific details on their measurement setup but not on the MTJ devices\nthey are using. Like variation in the patterned device dimension, the switching curve deviations of\nMTJs, cycling degradation and the impact of temperature changes on device switching\ncharacteristics. Also, what methods are employed to mitigate if such issues are present? The\nsigmoid switching probability curve should be discussed for all the devices being used to solve the\nTSP problem and mention the number of devices used to solve the problem.\nResponse: We thank the reviewer for highlighting the need to explicitly discuss the potential\ndevice-level variations and operational challenges of the MTJs utilized in our experiments. We\nrecognize that understanding device-level variation — such as patterning dimension variability,\nswitching curve deviations, cycling-induced degradation, and sensitivity to temperature—is critical\nto ensuring stable and reliable random-number generation performance, especially in practical\nscenarios involving multiple MTJs.\nIn response to this concern, we emphasize that our research group recently conducted an in-depth\nexperimental and numerical study specifically addressing the robustness and stability of MTJ-based\ntrue random number generators under realistic operational conditions, including temperature-\ninduced drift, device aging, and environmental instability4. In this recent work, we proposed and\nexperimentally validated a hybrid control strategy combining self-stabilizing feedback loops and\npulse-width modulation schemes. Notably, we developed a \"downcalibration-2\" approach, which\nefficiently updates control parameters at two-step intervals using simple integer-resolution timing\nlogic. This method ensures excellent statistical stability of the generated random numbers without\nexternal calibration, bit discarding, or extensive pre-characterization processes.\nThe MTJ devices utilized in the current study have a similar structural and fabrication setup as\nreported in the previous work. Therefore, they naturally inherit the demonstrated robustness against\ncommon device variations and operational drift issues. Specifically:\n1) Our self-stabilizing feedback loop dynamically corrects switching probability deviations\ncaused by minor variations in patterned device dimensions or switching curves. Such\ndevice-to-device variability is automatically compensated through the hybrid control\nstrategy, ensuring consistent output characteristics across multiple MTJ units.\n2) The pulse-width modulation component of our hybrid scheme efficiently handles potential\ncycling-induced degradation, continuously adapting pulse timing parameters to maintain\nstable switching probabilities even after extended device operation.\n3) Extensive experimental validation under dynamic temperature conditions confirms that the\nemployed hybrid stabilization strategy robustly mitigates thermal fluctuation impacts,\nmaintaining stable MTJ performance over a wide operational temperature range (as detailed\nexplicitly in Ref.4).\nRegarding device numbers and characterization details used in the current TSP experiments, we\nclarify explicitly in the revised manuscript: A small number of MTJs (typically log N, e.g., four\ncharacterized and confirmed to follow closely aligned sigmoid probability curves as shown below\nin Figure R4. The devices’ statistical switching properties and consistency were validated prior to\nuse in algorithmic experiments.\nFigure R4. The P-V characteristics of the used 4 MTJs in the probabilistic greedy algorithm. As\nmentioned above, these device-to-device variation and long-term drift of the performance of a\ndevice can be compensated by our recent developed methodology as uncovered in Ref.4 explicitly.\nWe have now explicitly referenced this prior comprehensive work in our manuscript, clearly stating\nthat device-level variations and operational instabilities are effectively mitigated by the previously\nvalidated hybrid control methods, thus substantiating the reliability and consistency of the MTJs\nemployed here.\nQuestion #2-6: The voltage control as discussed by the authors is highly precise and stabilized with\nfeedback as mentioned in the supplementary. However, there are concerns about how such precision\nwill be maintained when scaling the system to address larger problems. When transitioning to on-\nchip implementations, maintaining precision will require the integration of high-resolution ADCs\nand DACs impacting overall system performance.\nResponse: We appreciate the reviewer’s thoughtful concern regarding the scalability of our system\nand the challenge of maintaining high-precision voltage control when transitioning from laboratory\nsetups to on-chip implementations. This is indeed a critical consideration for practical deployment\nof MTJ-based TRNG systems in large-scale hardware-accelerated computing.\nTo address this challenge, our recent work4 directly tackles the issue of voltage precision and\nstability in a digital system. In that study, we proposed and experimentally validated a hybrid control\nstrategy that replaces the need for ultra-precise analog voltage sources or high-resolution DACs\nwith digital pulse-width modulation (PWM). Rather than finely adjusting voltage amplitude, which\noften demands costly and power-hungry high-resolution DACs, our approach modulates the\nduration of fixed-amplitude pulses using simple integer-timed digital logic. This significantly\nsimplifies the hardware DAC and ADC requirements for large-scale implementations and ensures\nthat precise control of switching probability can be achieved even on resource-constrained platforms.\nThis PWM-based approach was shown to be highly effective in maintaining target probability\ndistributions under both device variations and environmental fluctuations, including temperature\ndrift, while being inherently more scalable and integrable into CMOS-compatible architectures. As\na result, our probabilistic greedy algorithm and TRNG architecture can be feasibly extended to\nlarge-scale and on-chip systems without relying on high-resolution analog components.\nBesides, the developed probabilistic greedy algorithm has a high encoding efficiency, only log N\n2\nbits of MTJs being used to encode a N-city TSP, which also mitigates hardware complexity when\nscaling to larger N-city TSP.\nWe have added a summary of this result to the manuscript and clarified that our approach is\nintentionally designed with hardware scalability in mind, leveraging digital timing rather than\nanalog precision to maintain performance.\nQuestion #2-7: The manuscript lacks a detailed evaluation of the randomness and entropy tests for\nthe TRNG-generated random bitstream data. The authors just briefly touch upon the neighboring\ncorrelations of the data generated out of the Bayesian inference. It is also unclear whether the MTJs\nemployed in their setup require postprocessing of the random bitstreams due to device variations,\ncontrol and environment impacts that alter the device switching characteristics. The speed of\nrandom bitstream generation has not been explicitly addressed. Although they mention in their\nprevious work on SOT-MTJ [32] that they pass the randomness tests with post-processing, there is\nno such discussion in this work.\nResponse: We thank the reviewer for highlighting the need to elaborate on the statistical evaluation\nof the TRNG-generated bitstreams, including randomness quality, entropy, post-processing, and\nspeed. These are crucial aspects for any TRNG-based system, and we appreciate the opportunity to\nclarify.\nIn this study, the MTJs used for TRNG were fabricated and tested using the same experimental\nprotocols as those detailed in our recent publication4. In that work, we performed an extensive\nevaluation of the random bitstreams using NIST SP800-22 statistical test suite. The MTJ-based\nTRNG passed all tests with high confidence without requiring post-processing, thanks to the\nimplementation of a hybrid control strategy that actively stabilizes switching probabilities across\nenvironmental and temporal variations. This demonstrates that the raw bitstreams generated by our\nMTJs already exhibit high-quality randomness and entropy, eliminating the need for whitening or\npost-processing in most use cases.\nFigure R5. The MTJ-based TRNG passed all NIST tests without requiring post-processing, under\nDowncalibration-2 strategies.\nIn the current manuscript, while we have primarily focused on demonstrating the tunable\nprobabilistic distribution for algorithmic integration, we have now added a brief summary of the\nstatistical randomness validation from our previous work and clarified that the same devices and\ntesting protocols were employed.\nRegarding speed, the current bit generation rate is limited primarily by the bandwidth of the data\nacquisition system (currently approximately 500 kHz per MTJ using our NI PXIe setup). However,\nthe intrinsic switching dynamics of STT-MTJs permit much faster operation. With appropriate\nperipheral circuitry and high-speed readout electronics, generation speeds approaching GHz rates\nhave been demonstrated, as reported in recent works such as arXiv:2501.063186. We have now\nincluded this discussion in the manuscript to clarify both the current setup and future performance\npotential.\nQuestion #2-8: The conversion of binary Bernoulli TRNG to output based on any PDF, especially\nGaussian distribution using the Bayesian inference is a versatile approach. The distribution is used\nas the prior and based on conditional probability the voltages to the MTJ are controlled, generating\nrandom numbers in the required probability distribution. The authors outline this already in their\nprevious work in reference [32]. While dynamically computing the PDF for TSP is a good strategy,\nthe conditional probability limits the speed and control of the MTJs as they depend on the outcome\nof the previous node. The authors need to address and clarify this issue.\nResponse: We thank the reviewer for this insightful observation regarding the potential impact of\nconditional probability structures on speed and control in the PDF conversion process. We also\nappreciate the recognition that dynamically computing the PDF for TSP is a valuable strategy.\nIt is true that conditional probability modeling — particularly in Bayesian inference — can\nintroduce data dependencies that may impact speed, especially when later stages depend on the\noutcomes of earlier nodes. In our framework, such conditionality is indeed present when generating\nnon-uniform distributions, as each city-selection step depends on the outcome of previous steps.\nHowever, this dependency is relatively shallow (i.e., step-by-step rather than deeply nested), and is\nhandled using synchronous clocked updates.\nSpecifically, the MTJ control voltages or pulse widths are configured at each step based on the\ncurrent problem state, which includes the previously visited cities. While this introduces some\ndegree of sequential operation, the update process is lightweight and does not involve complex\ninference trees or deep conditional chains. Moreover, the update and sampling process are\nimplemented as synchronized pipelined operations, meaning that the latency is limited to a fixed\nnumber of clock cycles per decision step.\nAs demonstrated in our recent work [Zhang et al., PR Applied 23, 054073 (2025)]4, the control logic\nrequired to generate these distributions can be efficiently implemented using digital circuitry and\npulse-width modulation (PWM), enabling fast and accurate mapping from Bernoulli bits to arbitrary\nPDFs with minimal resource overhead.\nTherefore, while conditionality is inherent to the stepwise decision-making process in TSP, it does\nnot significantly restrict speed in our implementation, especially considering that this conditionality\nis further mitigated by the log N encoding complexity. This is because the sampling does not rely\n2\non recursive inference or variable-depth logic, but instead on fixed-control updates derived from\nsimple heuristics. We have clarified this aspect in the revised manuscript to better convey how our\nimplementation balances conditional logic and runtime efficiency.\nQuestion #2-9: The voltage precision plays a critical role in achieving the desired probability\ndistributions, and as the problem scales the requirement becomes more stringent. Conditional\nprobabilities that are close in value demand highly precise and stable voltage adjustments, along\nwith a repeatable sigmoidal switching trend. The shape and consistency of the sigmoid curve are\ncrucial for accurately determining the resulting PDF, but variations in device characteristics can\nsignificantly impact this curve. There is no discussion on how the authors plan to address such issues\nwhen scaling, as they currently use precision instruments to apply the voltage.\nResponse: We appreciate the reviewer’s concern regarding the precision and stability of voltage\ncontrol, which is indeed critical for achieving accurate and repeatable probability distributions,\nespecially when conditional probabilities are closely spaced. Additionally, we fully agree that the\nshape and reproducibility of the sigmoid switching probability curve play a central role in enabling\nhigh-fidelity probability distribution generation using MTJs.\nTo address these issues, we refer to our recent work4, in which we investigated and resolved this\nchallenge through a hybrid control strategy. Instead of relying on high-resolution voltage amplitude\ntuning — which, as the reviewer correctly notes, becomes increasingly impractical with scale —\nwe implemented pulse-width modulation (PWM) to control the switching probability. In this\napproach, the amplitude of the applied voltage remains fixed, and only the duration of the pulse is\nadjusted using simple digital logic. This method allows for fine-grained control over the effective\nswitching probability while maintaining the sigmoidal characteristic of the MTJ response as\nexperimentally shown in Figure R4.\nFurthermore, our work demonstrated that this PWM-based control, in combination with a self-\nstabilizing feedback loop, results in consistent sigmoid behavior across multiple devices, despite\ninevitable variations in fabrication or temperature. The feedback mechanism periodically monitors\nand corrects the effective switching behavior using only integer-resolution timing updates,\nremoving the need for external high-precision instrumentation or costly pre-characterization.\nThis architecture was shown to maintain stable and accurate probability distributions even under\nthermal drift and aging, making it robust and scalable for hardware-accelerated probabilistic\ncomputing. In the current work, we employ the same MTJ structure and control scheme, and thus\ninherit the same robustness and precision benefits. We have clarified this point in the revised\nmanuscript to emphasize that our method remains reliable and scalable even in the presence of close-\nvalued conditional probabilities.\nQuestion #2-10: The authors describe that the k T value is empirically found for optimal balance\nB\nbetween exploration and exploitation. However, this implies that k T would need to be tuned for\nB\nevery specific problem instance or whenever other hyperparameters of the algorithm are modified.\nThe authors should provide more discussion on how this parameter is affected. One can see that k T\nB\nis 60 in the burma14 a 14 city TSP and 1 in the st70 a 70 city TSP suggesting significant variability\nin its value. Then this search would be similar to the Boltzmann machine-based SA, where each\ntemperature step would govern a local search. Instead of the algorithm finding one on its own, here\nthe optimal temperature is predetermined empirically. Finding this optimal temperature would then\nbecome a problem on its own. I suggest that the authors provide a theoretical framework or\nmethodology to determine the optimized k T for different scenarios.\nB\nResponse: We thank the reviewer for the astute observation regarding the role of the k T parameter\nB\nin governing the balance between exploration and exploitation within our probabilistic greedy\nalgorithm. Indeed, this temperature-like parameter plays a critical role in shaping the dynamic\nprobability distribution used for city selection and can strongly influence the quality of the resulting\nsolution.\nWe fully agree that the current implementation selects k T empirically for each problem instance,\nB\nwhich introduces a hyperparameter tuning overhead and may influence the generality of the method.\nThis behavior does bear similarity to the temperature schedule in Boltzmann machines and\nsimulated annealing frameworks, where the temperature controls local search characteristics. The\nparallel is well-taken.\nAt present, we lack a fully developed theoretical framework for analytically determining the optimal\nk T for arbitrary problem instances, which is generally regarded as a tough question for any\nB\nprobabilistic computing algorithms. However, in practice, we have observed a consistent heuristic:\nthe optimal k T tends to correlate with the scale of the distance values in the TSP problem. In our\nB\nworkflow, we often begin with a rough estimate based on the average or one-tenth of the maximum\npairwise distance in the TSP cost matrix, and perform a few fast exploratory runs to converge on an\neffective value. While we acknowledge that it does not constitute a principled solution, this\nempirical approach has proven effective across a range of tested problem sizes.\nWe appreciate the reviewer’s suggestion and agree that establishing a theoretically grounded or\nadaptive strategy for selecting k T remains an important direction for future work. One possible\nB\nroute is to frame the tuning of k T as an outer-loop optimization problem or to integrate temperature\nB\nadaptation heuristics drawn from thermodynamic-inspired algorithms. This remains an open and\nvaluable challenge in developing fully autonomous probabilistic solvers.\nWe have added a corresponding note in the discussion section of the revised manuscript to\nacknowledge this limitation and outline our future efforts to address it.\nQuestion #2-11: Figure 4(c) and (e) represent the density of solutions, and it is unclear how many\nsolutions form the basis of these density metrics. The metrics can be discussed in terms of the\nprobability of a solution for better clarity. There is no mention of the time taken to solve these TSP\ninstances or any insight into the trend of time to solution as the problem size increases. Only\nalgorithm space and time complexities are provided. The actual time required by their hardware to\nsolve the problem is not discussed. The analysis of the energy and area occupied by their system is\nalso vital, which is absent.\nResponse: We thank the reviewer for pointing out the lack of detail regarding solution density\nquantification, runtime evaluation, and system-level metrics such as energy and area.\nFirst, we clarify that the density plots in Figure 4(c) and 4(e) are based on 100 independent runs of\nthe algorithm for each problem instance. These were used to generate a histogram of the frequency\nof solution energies, giving a probabilistic view of the algorithm's convergence behavior. We have\nadded this detail to the figure caption for clarity.\nRegarding the runtime and scalability, we agree that providing absolute runtime is valuable.\nHowever, our current setup is an experimental hardware-in-the-loop prototype designed for proof-\nof-concept, using a NI PXIe system for MTJ voltage control and data acquisition. The time to\ngenerate a solution in this setting includes latency due to instrument communication, software\noverhead, and sequential device control — not representative of optimized hardware\nimplementations. Instead, we would like to use iteration numbers of samplings, a hardware-weakly\ndependent parameter, as the time-marker to show the convergence speed.\nHere, to give an intuitive estimation, we can achieve an iteration of samplings for the Burma 14\nTSP within 0.2 s based on our recent measurement system. Stressing again, a fully hardware solver\nshould achieve much higher speed.\nThat said, the MTJ switching time itself is in the order of nanoseconds, and our recent work4\ndemonstrated reliable switching at rates consistent with several hundred megahertz. Further, recent\nMTJ-based TRNG systems in literature6 demonstrate generation rates approaching the gigahertz\nlevel. This suggests that a fully integrated system could yield solutions orders of magnitude faster\nthan our current prototype.\nConcerning energy and area, we fully acknowledge that these are important metrics for evaluating\nhardware feasibility. However, this work primarily focuses on demonstrating the algorithmic\npotential of a probabilistic greedy solver using spintronic randomness. A rigorous energy and area\nevaluation would require a fully integrated ASIC or FPGA implementation, which lies outside the\nscope of this proof-of-concept demonstration. Nevertheless, we expect substantial benefits in\nscalability and energy efficiency due to the inherently low power consumption and non-volatility of\nMTJs, as supported by prior studies.\nWe have added clarification on the number of trials, explained the nature of the prototype system,\nand discussed the need for future integrated design exploration to address energy and area\nquantitatively.\nQuestion #2-12: The authors have solved st70 TSP by simulating the probabilistic greedy search\nalgorithm. The authors of reference [36] have implemented a similar st70 problem on hardware.\nWith simulation data provided by the authors, a proper comparison cannot be drawn on the\nperformance of the proposed approach. Factors of voltage precision levels or the number of\navailable hardware MTJ devices could restrict larger-scale implementation like the 70-city problem\nin the probabilistic greedy methods with MTJs. Benchmarking different methods in terms of\nhardware performance is essential to substantiate the main claim. A scalability analysis should be\nincluded, showing the computational costs and performance metrics as the number of cities\nincreases.\nResponse: We appreciate the reviewer’s insightful comment regarding the limitations of\nsimulation-based evaluation for large-scale problems such as ST70, and the importance of\nbenchmarking hardware performance to support claims of scalability.\nIndeed, our current implementation of the ST70 instance uses simulation to evaluate the algorithmic\nbehavior and validate that the probabilistic greedy strategy maintains high solution quality and\nrobustness as the problem size increases. The hardware demonstrations in this work — including\nthe Burma14 example — serve as proof-of-concept validations of the core MTJ-based randomness\nengine and its integration into probabilistic decision-making processes.\nWe fully agree that demonstrating large-scale deployment using actual MTJ arrays is a critical next\nstep. Worth mentioning, our method is inherently more scalable than previous Boltzmann or Ising\nmachine architectures because it only requires log N MTJs to encode a probability distribution over\nlogarithmic scaling allows for significantly more compact and energy-efficient implementations in\nfuture chip-level deployments.\nAs noted in Ref.4, our pulse-width modulated control scheme further supports this scalability by\neliminating the need for high-resolution DACs. Therefore, we believe our approach is well-suited\nfor large-scale hardware realization, but acknowledge that a full chip-level implementation and\nlayout-aware parallelization strategy will be our future direction to rigorously validate scalability in\nterms of area, energy, and performance.\nBenchmarking across different hardware platforms remains challenging due to differences in\narchitectural assumptions and design goals (e.g., parallel annealing-based arrays vs. sequential\nprobabilistic decision chains). Nevertheless, we have added a discussion in the revised manuscript\noutlining the future roadmap for scalability validation and comparative benchmarking under unified\nperformance metrics.\nQuestion #2-13: The information presented in Figure 5 is insufficiently detailed. The subfigures of\nFig. 5 should also be cited properly in the main text. In Figure 5b, the axes lack numerical values,\nand concepts such as time and space complexity are not adequately defined. In Figure 5d, the\ncomparison details are insufficient — are optimal parameters used for the alternative methods?\nThere is only block diagram in Fig. 5e. What will the system performance be expected in Fig. 5e?\nSome quantitative analysis would be required. While the authors claim superior performance in\nsolution quality and convergence speed compared to classical methods, this is not convincingly\ndemonstrated. I further recommend that the authors scale up the number of cities incrementally\nusing different methods and present the results to better illustrate the performance of their proposed\nmethod, and provide a quantitative comparison of their algorithm performance with other state-of-\nthe-art approaches, particularly in terms of solution quality and scalability. Benchmarking against\nstate-of-the-art combinatorial optimization problem (COP) solvers would also help establish the\nnovelty and effectiveness of the proposed algorithm.\nResponse: We thank the reviewer for their detailed and constructive feedback on Figure 5 and the\nassociated analysis.\nRegarding Figure 5b, we clarify that this is a theoretical schematic used to qualitatively illustrate\nthe relative scaling behavior of algorithmic complexity and randomness control. As such, precise\nnumerical values are not included on the axes, but the figure is drawn proportionally to reflect\nknown theoretical trends (e.g., logarithmic vs. linear vs. exponential scaling). We have added a\nclarification in the figure caption and main text to avoid confusion.\nFor Figure 5d, we confirm that the comparison to simulated annealing (SA) and genetic algorithm\n(GA) was performed using standard parameter settings commonly used in the combinatorial\noptimization literature. In particular, for SA we used an exponentially decaying temperature\nschedule with an initial temperature proportional to the average edge weight; for GA, we used a\npopulation size of 100 and a mutation rate of 0.1. All methods were evaluated using 100 independent\nruns to ensure statistical reliability. These details have now been included in both the figure caption\nand the main text.\nFigure 5e serves as a conceptual architectural diagram of a future MTJ-based probabilistic\ncomputing system. While performance data for this architecture are not available at this stage, we\nnow provide estimated throughput projections in the text, based on our experimental switching rate\n(~500 kHz) and existing literature showing MTJ-based TRNG operation exceeding 1 GHz. These\nestimates suggest that high-speed performance is attainable with modest parallelization in future\nintegrated platforms.\nWe agree with the reviewer that more systematic benchmarking and scalability evaluation will be\ncritical to validate the full potential of our approach. To this end, we have included a discussion\noutlining our roadmap for future work involving cross-platform comparisons with established\nsolvers such as Concorde, LKH, and neural combinatorial optimization frameworks.\nLastly, all subfigures in Figure 5 are now explicitly cited and discussed in the revised main text.\nMinor comment #2-1: The paper mentions \"n\" in the context of scalability but does not define it\nclearly upon first usage.\nResponse: We thank the reviewer for pointing this out. In the revised manuscript, we have explicitly\ndefined n as the number of cities (nodes) upon its first mention in the context of scalability and\nalgorithmic complexity.\nMinor comment #2-2: The statement that \"multiple MTJs are connected\" lacks specificity\nregarding the exact number of MTJs.\nResponse: Thank you for pointing out the lack of specificity. We have clarified the number of MTJs\nused in our implementation: for a problem with N cities, we use approximately log N MTJs to\n2\nrepresent the required probability distribution. In practice, a small number of MTJs (e.g., 4 MTJs\nfor 14 cities) are reused through time-multiplexing to reduce hardware overhead. This information\nhas been added to the revised manuscript where the MTJ connection is first discussed.\nMinor comment #2-3: Fig. 1e shows a switching characteristic with respect to time similar to\nsuperparamagnetic MTJ, which is against a stable STT-MTJ behavior. This confusion should be\naddressed.\nResponse: We thank the reviewer for pointing out this potential confusion. We confirm that our\nexperiments use thermally stable STT-MTJs with perpendicular magnetic anisotropy (PMA),\noperating near their critical switching thresholds. The stochastic switching behavior shown in Fig.\n1e corresponds to this sub-threshold regime, where probabilistic switching is induced by thermal\nactivation under finite voltage pulses — not similar to the behavior of superparamagnetic MTJs. No\nchanges were made to the manuscript, as the distinction is already implied by our discussion of STT\nswitching thresholds and device parameters, but we appreciate the opportunity to clarify this point.\nMinor comment #2-4: Measuring only the neighboring correlation of generated random numbers\nis insufficient to demonstrate statistical independence or high-quality randomness. The authors\nshould validate the quality of their random numbers by testing the entire sequence using standard\nstatistical tests.\nResponse: We appreciate the reviewer’s suggestion. We agree that evaluating statistical\nindependence and entropy over the full bitstream is critical for assessing the quality of TRNGs. In\nthis work, we reused the same STT-MTJ devices and readout setup as in our recent publication4,\nwhere comprehensive randomness testing — including full-sequence NIST SP800-22 and\nautocorrelation analysis — was conducted and passed without requiring post-processing as also\nshown in Figure R5. To avoid redundancy, we did not repeat the full statistical tests here, but have\nnow clarified this point in the manuscript.\nMinor comment #2-5: Figure 4(b) explanation on Page 8 of the main text has an error in identifying\nthe curves.\nResponse: We thank the reviewer for catching this oversight. We have carefully re-examined Figure\n4(b) and the associated explanation in the main text. The curve identification in the original version\nwas indeed incorrect, and we have now corrected the description to accurately match the legend and\ndata shown in the figure. The revised manuscript reflects this correction.\nMinor comment #2-6: In Figure 4(e) what is Density (best*50), is it a distribution plot of solutions\nwith 0 kilometers of the known optimal as mentioned on Page 8 of the main text? And the numbers\non the peak are the maximum number of solutions giving exact distances? More clarity is required.\nResponse: We appreciate the reviewer’s request for clarification regarding Figure 4(e). The term\n\"Density (best × 50)\" refers to the relative occurrence frequency of optimal solutions (i.e., solutions\nwith the same length as the known optimum). Since the absolute probability of obtaining the optimal\nsolution is relatively low, this value was scaled by a factor of 50 for better visibility. The numbers\nshown at the peaks indicate the corresponding temperature values (k T) that yield the highest density\nB\nof optimal solutions. We have clarified this in both the figure caption and the main text.\nMinor comment #2-7: Figure 5(d) shows the results of different heuristic algorithms with the error\nbars, there is no mention of how many samples is the error bar drawn. Prob-Greedy data is not\npresent for 10^5 iterations in solving st70 on simulation?\nResponse: We thank the reviewer for this observation. The error bars in Figure 5(d) reflect the\nstandard deviation 10 independent runs for each algorithm and each iteration setting.\nAs for the absence of the Prob-Greedy data point at 105 iterations for the st70 instance, this was due\nto simulation time constraints (10 hours currently for 105 iterations), since each run at such a large\nscale becomes computationally intensive. However, the trend shown up to 104 iterations already\ndemonstrates the superior performance and early convergence behavior of the Prob-Greedy\napproach compared to the other heuristics. We believe the existing results can sufficiently illustrate\nthe effectiveness of our method, and we have clarified this point in the revised manuscript and the\nfigure caption.\nMinor comment #2-8: In the description and main text explanation of Figure 4(d) optimal solution\nwith 1000 repetitions is used, but in the graph the axis says iterations. Are repetitions and iterations\nused interchangeably? Or are the authors performing 1000 repetitions of the iterations?\nResponse: We thank the reviewer for highlighting this terminology inconsistency. In the context of\nFigure 4(d), the terms repetitions and iterations are used interchangeably to refer to one full\nexecution of the algorithm that generates a complete TSP path solution. To avoid confusion, we\nhave revised the text and figure caption to use a consistent term — “iterations” — and clarified that\nin this figure, it denotes the number of repeated runs of obtaining an individual complete TSP route.\n----------------------------------------------------------------------\nReviewer #3\n----------------------------------------------------------------------\nComment: The manuscript introduces a probabilistic greedy algorithm based on stochastic\nMagnetic Tunnel Junction (MTJ) in the framework of probabilistic computing. Through\ndynamically modulating the degree of randomness, the algorithm herein has manifested the\nperformance in combinatorial optimization problems. The authors claim that, when applied to the\nTraveling Salesman Problem, this algorithm surpasses other classical approaches, characterized by\nthe solution quality and more rapid convergence speed.\nResponse: We thank the reviewer for their concise summary and for recognizing the coherence of\nour work. We would like to clarify that while probabilistic optimization is a known concept, our\nstudy presents a distinctive contribution by implementing it directly through the intrinsic\nstochasticity of magnetic tunnel junctions (MTJs). Unlike conventional algorithmic randomness,\nthe degree of stochasticity in our approach is continuously tunable via direct voltage control at the\nhardware level. This enables real-time adjustment of exploration and exploitation behavior without\nrelying on pseudo-random sequences or external calibration. Furthermore, the integration of\nBayesian inference network to map binary MTJ outputs to dynamically reconfigurable probability\ndensity functions (PDF) establishes a novel and efficient mechanism to guide the optimization\nprocess in a fully hardware-compatible manner. We believe these combined features, validated both\nexperimentally and through large-scale simulations, distinguish our work from existing probabilistic\nsolvers.\nComment: Overall Evaluation: This work is overall coherent. However, it does not meet the high\nstandard of Nature Communications due to the lack of both novelty and enough new results:\nResponse: We respectfully appreciate the reviewer’s “overall coherent” assessment, but we would\nlike to emphasize that the presented work introduces a new combination of hardware-level true\nrandomness and adaptive probabilistic control for solving combinatorial optimization problems.\nWhile MTJ-based TRNGs and greedy algorithms have been studied separately, our work is the first\nto link them in a scalable and tunable optimization framework that is experimentally validated on a\nphysical MTJ platform. The ability to dynamically adjust the probability distribution based on\nsystem state through hardware-controllable parameters offers a flexible and low-overhead solution\nthat has not been demonstrated in this context. We have revised the manuscript to better articulate\nthis novelty and to clarify the broader impact of our approach for energy-efficient, hardware-\nembedded computing.\nQuestion #3-1: The key experimental finding in this work is that four asynchronous MTJs are\nutilized to generate the desired probability distribution function (Figure 2). These results have\nalready been reported and well-studied in a previous paper by the same group [Advanced Science,\n11(23) 2402182 (2024)]. The probability distributions are the same, just with a different set of\nmeasurement data.\nResponse: We thank the reviewer for pointing this out. While it is true that the general principle of\nmapping MTJ-based binary outputs to arbitrary probability distributions was introduced in our\nearlier work [Adv. Sci. 11(23), 2402182 (2024)], the present study involves a significantly improved\nexperimental setup with enhanced device stability, signal-to-noise ratio, and control resolution. As\na result, the newly acquired data used in this work exhibit substantially higher statistical quality,\nwhich is critically indispensable for validating the performance of the probabilistic greedy algorithm\nintroduced here. In particular, the ability to precisely tune and reproduce the desired probability\ndistribution is directly linked to the algorithm’s effectiveness in solving the TSP. Therefore,\nalthough the underlying principle of the PDF-configurable TRNGs remains consistent with our prior\npublication, it is indispensable to directly demonstrate in experiment the effectiveness of more\naccurate PDF distributions from upgraded hardware within this newly-developed algorithmic\ncontext – the probabilistic Greedy algorithm context with the Boltzmann distribution–which just\nneeds the PDF-configurable TRNG.\nThe impact of direct demonstration in matchingness between algorithm and hardware can be also\nindicated by the perspective review by Misra5 et al. In this article, according to the degree of\nintegration between software and hardware and as-caused computing efficiency, probabilistic\ncomputing systems are classified into 4 levels.\n In Level 0, TRNG hardware only generates random numbers according to the uniform\ndistribution; the desired PDF by algorithm can only be further transformed from the uniform\ndistribution with extra computing overheads and less sampling efficiency, for example, via the\nAcceptance-Rejection Sampling Method.\n In Level 1, the desired or predicted PDF by an algorithm can be directly sampled from TRNG\nhardware. The sampled random numbers are fed back further into the algorithm. This\napplication scenario is broadly encountered, for example, in many Digital Twin Systems where\nsuch typical PDFs as the Gaussian or exponentials or others are widely adopted. This kind of\nTRNG hardware, especially with PDF-configurability, is reported by our Adv. Sci. paper.\n In Level 2, an algorithm in a solver, for example, of solving COPs, predicts problem-specific\nor even state-specific PDFs to improve correctness and efficiency. In this case, PDFs can be\nin any arbitrary forms and should be updated in real time; thus PDF-configurable TRNGs are\nindispensable, among which the Boltzmann or Ising machines are typical. Via the local Gibbs\nsampling protocol, the tunable PDF is constrained into binary or Bernoulli one, which can be\ndirectly sampled from MTJ hardware. However, the cost of this binarization or algorithm is\nlow encoding and sampling efficiency (N2 for N-city TSP). In order to substantially improve\nefficiency, more efficient algorithms are highly desirable, which accordingly call for a more\ngeneral PDF-configurable TRNG hardware beyond the binary one.\n In Level 3, a full hardware solver is anticipated with all the other components besides of\nstochastic samplings also implemented in hardware. In our case, the other calculation\noverheads include addition, multiplications and exponentials; they can be realized in MCU or\nvia look-up-tables, which should not impose a fundamental obstacle by an incremental\nimprovement based on Level 2.\nThe novelty and significance of our work naturally emerges from this architecture: Our work,\nproposing the efficient probabilistic greedy algorithm for TSP (log N) and experimentally\n2\ndemonstrating the matchingness between the algorithm and PDF-configurable MTJ-based TRNG\nhardware, just hits the goal of Level 2.\nFigure R3 of the perspective paper “Probabilistic Neural Computing with Stochastic Devices” by\nS. Misra et al5.\nQuestion #3-2: (2) The probabilistic greedy algorithm highlighted in this work is also not new. The\nconcepts and algorithms have been previously reported in several papers many years ago\n[Computers & Operations Research, 37: 432 (2010); IEEE Transactions on Communications, 581:\n3286 (2010); Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic\n(ISMVL), Victoria, CANADA, F 2012 May 14-16, (2012)].\nResponse: We thank the reviewer for pointing out the earlier works on probabilistic variants of\ngreedy algorithms. Indeed, the idea of introducing randomness into greedy decision-making has a\nrich history. However, our approach substantially differs both in its theoretical foundation and its\nphysical realization.\nTable R1. Comparison of our probabilistic greedy algorithm with typical pioneering others.\nEssentially, they differ in the final distribution of trial solutions, the Boltzmann style or not.\nFeature Our Work C&OR, 2010 IEEE TCOM, 2010 ISMVL 2012\nChannel Assignment in Circuit Mapping &\nTarget Problem TSP TSP\nCellular Networks Logic Assignment\nCity-by-city selection Deterministic greedy Greedy with Greedy logic\nGreedy\nwith Boltzmann- with randomized probabilistic selection selection perturbed\nStructure\nshaped probability restart using ranking weights with random choices\nExplicit Boltzmann\nSimple Weighted random choice\nProbability distribution over Stochastic gate\nuniform/random based on scheduling\nFoundation distance cost, mapping heuristics\nchoices or restarts heuristics (π, θ values)\ndynamically updated\nCore parameter\nNot used, implicit\nTemperature balancing exploration No physical\nNot used preference via h-best\nParameter (kBT) vs. exploitation, temperature analog\nranking\ntunable\nGlobal solution Localized\nNo formal Local decision\nprobability follows randomized\nPath Probability probabilistic model probability based on\nfull Boltzmann perturbation, no full\nover entire path heuristic scores\ndistribution PDF definition\nYes: penultimate city\nFinal-Step\nselection includes No Not applicable Not applicable\nCorrection\nround-trip return\nDirectly sampled from\nHardware-suggestive\nHardware MTJ-based TRNGs Software simulation\nSoftware simulation only only, not\nIntegration with voltage/PWM only\nimplemented\ncontrol\nTrue Random\nRandom Number Numbers (TRNG) Weighted pseudo- PRNG-based\nImplicit PRNG\nType from MTJs, with random choices heuristics\nconfigurable PDFs\nFully arbitrary\nPDF Heuristically defined\ndistribution generation Not considered Not considered\nConfigurability probabilities\nverified\nEncoding Requires only logN\nEfficiency MTJs for N cities\nFirst to combine\nBoltzmann-based\nAlgorithmic variant Algorithmic variant with Logic-oriented\nNovelty Claim probabilistic greedy\nonly diversification variation\nwith hardware-based\nPDF-matching TRNG\nYes — MTJ-based\nExperimental No hardware No hardware\nsetup, tested in 14-city Not hardware-tested\nRealization implementation implementation\ndemo\nSpecifically, the probabilistic greedy algorithm in this work is grounded upon the Boltzmann\ndistribution, where the selection probability for each candidate node is determined by an energy\nfunction proportional to the total path distance as shown in Eq. (1). We also introduce a correction\nat the penultimate node to ensure proper termination, which forces the entire trial solutions to obey\nto the Boltzmann distribution over global distances. To the best of our knowledge, such a\nformulation — where the global path cost distribution matches the Boltzmann form and is\nmeanwhile experimentally sampled through MTJ-based hardware — has not been previously\nreported. Though the Boltzmann or Ising machines also realize the Boltzmann distribution, their\nencoding efficiency N2 is far different from the log N efficiency of this probabilistic greedy\n2\nalgorithm. All these effectiveness and efficiency of the algorithm should be experimentally and\ndirectly verified in hardware level, especially, in the MTJ-TRNG level for developing spintronic\nprobabilistic computing system in the coming future. We believe this adds a layer of mathematical\nelegance and physical interpretability that distinguishes our method from earlier probabilistic\nheuristics.\nQuestion #3-3: (3) The scale of the problem solved (14 cities by experiment and 70 cities by\nsimulation) is not large enough as compared to a recent experimental work [ref. 36 published in NC]\nwhere 80s MTJs are used in hardware to solve the 70-city TSP.\nResponse: We appreciate the reviewer’s comparison with Ref. [36] and acknowledge that their\nhardware demonstration using 80 superparamagnetic MTJs to solve the 70-city TSP is an impressive\nexperimental achievement based on the architecture of classic Ising model. However, the focus of\nour work is fundamentally different. Rather than building a large-scale MTJ array, we propose a\nprobabilistic algorithm that is specifically designed to be hardware-efficient and scalable, requiring\nonly log N MTJs for an N-city problem — i.e., just 7 MTJs for 70 cities. This significant reduction\n2\nin hardware complexity stems from our algorithm’s design, which leverages adaptive,\nreconfigurable randomness to achieve competitive optimization results using minimal physical\nresources.\nWhile the scale of our experimental demonstration is modest, we emphasize that it serves as a proof\nof concept, and our large-problem simulations confirm the approach's potential for scaling.\nMoreover, we respectfully note that Ref. [36] primarily focuses on hardware demonstration, while\ntheir core algorithm inherits the classic Ising machine. A 70 city TSP needs in principle 4900 MTJs\nto encode. In order to reduce complexity, Ref. [36] use the divide-and-conquer strategy to first\ndivide a large map into small pieces and then use 80 MTJs to map those small maps and then\ncombine those individual routes into a whole one in solver. This divide-and-conquer strategy\nappeared in the original paper of the simulated annealing7 and more importantly, some priori\ninformation on maps is needed for the divide-and-conquer strategy. Our work, by contrast,\nintroduces a unique integration of hardware-level stochasticity and mathematically grounded\nprobabilistic search, no priori map information needed and thus applicable for all TSP. We believe\nour achievement in algorithm, hardware and especially their matchingness, provides meaningful\nvalue to the field.\nComment: Considering these facts, this work only has incremental contribution compared to the\nestablished literatures. It is suitable to publish in a more specified journal with a few technical issues\nproperly addressed.\nResponse: We thank the reviewer for their assessment. While we acknowledge that our work builds\nupon a body of established literature, we respectfully believe that it offers more than an incremental\ncontribution. Specifically, we present a novel and physically grounded probabilistic optimization\nframework that directly harnesses the stochastic switching behavior of MTJs and embeds it into a\nscalable, reconfigurable algorithm with strong mathematical foundations as highlightened in Table\nR1. The demonstrated ability to modulate randomness in real time — using only a minimal number\nof devices — is both conceptually and practically distinctive. In response to the reviewer’s concerns,\nwe have carefully revised the manuscript to better highlight these core contributions and have\naddressed all technical issues in details. We hope that the improved version more clearly conveys\nthe broader relevance of this approach at the intersection of spintronic hardware, probabilistic\ncomputing, and combinatorial optimization.\nTechnical Concern #3-1: The manuscript mentions that the magnetization direction of the free\nlayer of the MTJ is altered by applying current pulses. However, it fails to specify the magnitude\nand duration of the applied pulses, as well as the measurement rate. This is important when\ncomparing different algorithms in various platforms (CPU, FPGA etc.).\nResponse: We thank the reviewer for highlighting this important point. As mentioned in our\nresponse to Reviewer #2 (Question #2-7), the detailed measurement setup, including the magnitude\nand duration of the current pulses as well as the sampling rate, has been extensively characterized\nin our recent publication4, which used the same MTJ devices and instrumentation. In the present\nsetup, the measurement rate is approximately 500 kHz, limited by our data acquisition hardware.\nHowever, recent advances suggest that GHz-speed MTJ-based TRNGs are feasible, as demonstrated\nin Ref.6 We have clarified this point in the revised manuscript to guide readers toward the relevant\nreferences.\nTechnical Concern #3-2: Four MTJs are utilized to generate the desired probability distribution\nfunction through a Bayesian network. Nevertheless, the impact of the differences among MTJs on\nthe probability distribution function is not discussed in the manuscript. It is well-known that device-\nto-device variations have deep impact on the performance of p-computers.\nResponse: We appreciate the reviewer’s attention to the critical issue of device-to-device variation,\nwhich indeed poses a fundamental challenge in probabilistic hardware systems. To address this, we\nhave previously developed and reported a calibration-free hybrid control strategy in Ref.4 which\neffectively compensates for intrinsic differences among MTJs by combining self-stabilizing\nfeedback with pulse-width modulation. This approach allows for precise output of arbitrary\nprobability distributions, despite device nonuniformity, without requiring individual device pre-\ncalibration.\nThe MTJs used in this work are controlled under the same framework, and the measured\ndistributions (as shown in Figure 2) confirm the high fidelity of probabilistic output across devices.\nWe have added clarification in the manuscript to explicitly reference this point.\nTechnical Concern #3-3: The results presented in Figure 4c indicate that the average solution still\nhas a notable deviation from the correct solution. An in-depth analysis of the underlying causes\nshould be provided. Moreover, there is a discrepancy between the colors of the curves depicted in\nFigure 4b and the corresponding descriptions in the manuscript, which may cause confusion for\nreaders.\nResponse: We thank the reviewer for raising this point. The deviation of the average solution in\nFigure 4c is an expected outcome given the inherently stochastic and path-constructive nature of the\nprobabilistic greedy algorithm. The average serves only as an auxiliary statistical indicator to\nillustrate the improvement over classical greedy methods. In practical use, the algorithm is typically\nrepeated multiple times, and the minimum (best) solution among runs is selected as the final output.\nTherefore, it is the best-achieved solution — not the average — that reflects the algorithm’s\noptimization capability, and this is also emphasized in our comparative analysis.\nRegarding the inconsistency in curve colors in Figure 4b and the corresponding legend in the main\ntext, we acknowledge this oversight and thank the referee for this reminding. As also pointed out\nby Reviewer #2 (Minor comment #2-5), the figure was updated during revision, but the\naccompanying text was not synchronized accordingly. We have corrected this mismatch in the\nrevised manuscript to prevent confusion.\nTechnical Concern #3-4: The simulation in Figure 5c indicates that the algorithm's performance is\nmore sensitive to the parameter k T. Then, for problems of a larger scale, will there be a situation\nB\nwhere the differences in k T are extremely small and indistinguishable?\nB\nResponse: We thank the reviewer for highlighting the sensitivity of the algorithm to the parameter\nk T, particularly as demonstrated in the simulations shown in Figure 5c. Indeed, as the problem size\nB\nincreases, the energy landscape becomes more complex and crowded with local optima.\nConsequently, the selection of k T becomes more critical, as small changes in this parameter can\nB\nlead to disproportionately large effects on the solution quality due to the sharper concentration of\nthe Boltzmann distribution. This heightened sensitivity is an expected outcome, but it does not\nundermine the effectiveness of the algorithm — our simulations on 70-city problems still show\nrobust performance with carefully chosen k T values.\nB\nTo address this issue in larger-scale scenarios, we are actively exploring automated tuning strategies\nto adaptively refine the value of k T during the optimization process. For instance, a meta-heuristic\nB\nlayer that perturbs k T based on performance feedback across iterations could enable the algorithm\nB\nto self-adjust, effectively balancing exploration and exploitation without the need for manual\nparameter sweeping. While such techniques are still under development and beyond the scope of\nthis work, we recognize their importance for real-world deployment and plan to incorporate them\ninto future studies.\nAt present, we adopt a coarse-to-fine empirical approach to select k T, typically beginning with a\nB\nvalue around one-tenth of the average intercity distance in the TSP cost matrix. A few initial runs\nare performed to locate a performance peak, which we then fix for larger-scale trials. This method\nhas so far proven reliable, though we agree that a more rigorous theoretical framework would further\nenhance the generality and automation of the approach.\nTechnical Concern #3-5: Although this algorithm outperforms the traditional greedy algorithm in\nsolving the Traveling Salesman Problem (TSP), whether it is equally effective for other types of\ncombinatorial optimization problems remains unclear.\nResponse: We appreciate the reviewer’s thoughtful comment regarding the generalizability of our\nalgorithm beyond the TSP. Indeed, while the Traveling Salesman Problem serves as a representative\nbenchmark to demonstrate the feasibility and effectiveness of our MTJ-assisted probabilistic greedy\nframework, the underlying methodology is not limited to TSP and is inherently extensible to a broad\nclass of combinatorial optimization problems (COPs).\nIn response to a similar point raised by Reviewer #1 (Question 1-2), we have added a detailed\nadaptation example for graph coloring in the Supplementary Information. This example shows how\nthe cost function can be redefined (e.g., conflict penalty) while the same probabilistic selection rule,\ndriven by MTJ-generated distributions, remains intact. The same approach is also applicable to other\nproblems such as scheduling, bin packing, or constraint satisfaction, requiring only problem-specific\ncost modeling and temperature schedule adjustments.\nImportantly, this step-by-step probabilistic selection mechanism — where a solution is gradually\nconstructed by sampling from a dynamically updated distribution — shares a fundamental similarity\nwith the autoregressive architecture of large language models (LLMs). In such models, each token\nis selected based on a softmax probability distribution conditioned on prior tokens — a principle\nthat mirrors our framework's use of Boltzmann-distributed probabilities for sequential decision-\nmaking.\nThis alignment opens a promising avenue for the integration of spintronic hardware with\nprobabilistic AI, particularly in generative models, probabilistic inference engines, and sampling-\nbased reasoning. By leveraging MTJ-based TRNGs for energy-efficient, parallelizable random\nsampling, our framework could serve as a hardware-compatible front end for AI workloads that\nrequire uncertainty modeling or probabilistic token generation.\nWe have added this outlook to the revised Discussion section, highlighting the potential intersection\nbetween MTJ-based probabilistic computing and AI model acceleration. This provides not only a\nnovel application direction beyond classical COPs, but also a broader impact in probabilistic\nreasoning, where energy-based models and structured sampling are central.\nTechnical Concern #3-6: In Figure 1d, the data points are in green, but they are miswritten as \"blue\ncircles\" in the manuscript.\nResponse: We thank the reviewer for pointing out this oversight. The data points in Figure 1d are\nindeed green, not blue as originally stated. We have corrected the color description in the revised\nmanuscript to ensure consistency between the figure and its explanation.\nFinally, we would like to appreciate the three referees again for their encouraging, enlightening and\ninsightful comments and questions, without which the manuscript cannot be improved.\nReference\n1. Morsali, M., Moaiyeri, M. H. & Rajaei, R. A process variation resilient spintronic true random\nnumber generator for highly reliable hardware security applications. Microelectronics Journal\n129, 105606 (2022).\n2. Wang, C. et al. Spin–orbit torque true random number generator with thermal stability. Appl.\nPhys. Lett. 124, 102409 (2024).\n3. Xu, Y. Q. et al. Self-stabilized true random number generator based on spin–orbit torque\nmagnetic tunnel junctions without calibration. Appl. Phys. Lett. 125, 132403 (2024).\n4. Zhang, R. et al. Drift-resilient magnetic-tunnel-junction random-number generator via hybrid\ncontrol strategies. Phys. Rev. Applied 23, 054073 (2025).\n5. Misra, S. et al. Probabilistic Neural Computing with Stochastic Devices. Adv. Mat. 35, 2204569\n(2022).\n6. Valli, A. S. E., Tsao, M., Smith, J. D., Misra, S. & Kent, A. D. High-Speed Tunable Generation\nof Random Number Distributions Using Actuated Perpendicular Magnetic Tunnel Junctions.\nPreprint at https://doi.org/10.48550/ARXIV.2501.06318 (2025).\n7. Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by Simulated Annealing. Science 220,\n671–680 (1983).\nResponse Letter to Reviewers - NCOMMS-24-82665\n----------------------------------------------------------------------------------------------------------------------\nWe would like to sincerely thank all three Reviewers for their careful reading of our manuscript and\nfor the constructive and insightful comments provided. The feedback from the Reviewers has been\ninvaluable in helping us to significantly improve the clarity, depth, and positioning of our work.\nReviewer #1’s supportive remarks are greatly appreciated; Reviewer #2’s detailed questions and\nrequests for benchmarking, positioning, and additional evidence have guided us to strengthen both\nthe analysis and presentation; and Reviewer #3’s concerns about generalizability have motivated us\nto explicitly extend our discussion and provide new supplementary material demonstrating the\nbroader applicability of our approach. We are truly grateful for the Reviewers’ time and effort, which\nhave substantially enhanced the quality of the revised manuscript.\n----------------------------------------------------------------------------------------------------------------------\nReviewer #1\n----------------------------------------------------------------------------------------------------------------------\nComment: Authors have addressed all of my concerns, I recommend to publish as it is.\nReply: We sincerely thank Reviewer #1 for the positive assessment and for recommending our\nmanuscript for publication. We truly appreciate the reviewer’s encouraging comments in the first\nround and the current recognition that all concerns have been satisfactorily addressed. The\nconstructive feedback was invaluable in helping us refine the manuscript, and we are grateful for\nthe reviewer’s support and endorsement.\n----------------------------------------------------------------------------------------------------------------------\nReviewer #2\n----------------------------------------------------------------------------------------------------------------------\nComment: The authors made substantial modifications to the original manuscript. The revised\nmanuscript presents an engineering link-up between an MTJ-based, PDF-configurable TRNG and\na probabilistic-greedy TSP solver. Unfortunately, both ingredients are documented in the literature,\nand the present version does not yet provide the data or analysis needed to elevate the work from\nincremental to transformative. Some critical aspects are still missing. Thus, I recommend the authors\nrevise their manuscript according to the comments below.\nReply: We sincerely thank Reviewer #2 for the careful re-evaluation of our revised manuscript and\nfor the encouraging remark that we have made “substantial modifications to the original manuscript”.\nWe are very grateful for the reviewer’s constructive criticisms, which have helped us to identify\nimportant missing aspects and refine the presentation of our work. Following the reviewer’s\ninsightful guidance, we have further revised the manuscript in this round, adding new analyses,\nclarifications, and supporting data to address the specific points raised. We believe that these\nimprovements, motivated directly by the reviewer’s valuable feedback, have significantly\nstrengthened the manuscript.\nComment: The authors state that their hardware scales with log N, but I find this argument\n2\nunconvincing. In practice, the dominant factor in scaling is memory usage. For instance, solving an\nN-city TSP typically requires storing N sets of information, implying at least O(N) memory. If we\nfocus solely on the use of MTJs, algorithms such as simulated annealing can reuse a single MTJ\nacross problem sizes without any sacrifices in time or energy. However, this does not mean that the\nhardware is free from scaling considerations, while the MTJ count may remain constant, other\naspects, particularly memory, still scale with problem size.\nReply: We sincerely thank the Reviewer #2 for this enlightening question. The point we originally\nemphasized was specifically the number of MTJs (N ) required to encode a complete probability\nMTJ\ndistribution in the proposed greedy algorithm, which scales as N = log N, for example, 16 cities\nMTJ 2\nrequiring 4 nodes. However, a small number of MTJs alone (e.g., 4 MTJs for a 16-city TSP) cannot\ndirectly generate real routes; instead, they must be assisted by a conditional probability table (CPT)\nor a shallow forward neuron network (NN) containing a number of parameters to assist the 4 MTJs\nto implement real samplings. The data included in the CPT or NN is in the order of (2N MTJ – 1).\nTherefore, we need additional memories of (N-1) to store the CPT or NN parameters. As exactly\nspeculated by the reviewer, the needed memory scales in the order of O(N) with the increase in the\ncity number N, which is already minimal for a N-city TSP problem. We have updated the revised\nmanuscript on this point. Thanks for the question and comment again.\nSecond, besides of the scaling law O(log N) of the number of needed MTJs, the scaling law in\n2\nmemory ~O(N) for the probabilistic greedy algorithm is also favorable, compared with the\nBoltzmann or Ising machines. For the latter, O(N2) MTJs are needed to encode a map, and, for each\nMTJ, 2 floating-point bits are necessary to memorize the parameters α and V of an individual P-V\nc\nrelation of the MTJ, P=1/[1+exp(-α(V-V )/T)]. Here V is the critical switching voltage with P=50%\nc c\nand α depicts the sharpness of the sigmoid or tanh functions. In this case, the needed memory scales\nwith O(2N2) for the Boltzmann or Ising machines.\nThird, more subtly and critically, for the Boltzmann or Ising machines, sampling is implemented\nfollowing the Gibbs protocol. In details, the influence experienced by one node, for instance, the\nvoltage imposed on the node for a sampling attempt, is rescaled and biased according to the\nfingerprint parameters α and V of the node from the weighted sum of the on-time states of all the\nc\nrest nodes. Because of the diversity in performances of those MTJs, we cannot expect a uniform α\nand a uniform V for all nodes. Instead, we need to memorize all the fingerprint α and V for each\nc c\nnode. Thus, O(N2) mentioned above is involved. More critically, we have not considered the\ninfluence from performance drift in time. If this issue is concerned, time-to-time recalibration on α\nand V for each node may be indispensable, especially, for long-term runs. The need for this\nc\nrecalibration originates from the requirement of the precise sampling according to the diverse and\ndrifting P-V relations of all nodes (or real α and V parameters). However, this annoying point can\nc\nbe fortunately avoided for the probabilistic greedy algorithm because only sampling probability\n(accurate P) instead of the driving voltage is critical for the latter and this accurate sampling\nprobability P can be ensured by many self-stabilizing methodologies such as Ref. [Zhang et al. Phys.\nRev. Appl. 23 (2025) 054073].\nIn sum, both MTJ count and memory requirement scale favorably — O(log N) and O(N),\n2\nrespectively — in our method, in sharp contrast to the O(N2) scaling of Boltzmann or Ising machines\nthat may additionally require occasional calibration of device-specific parameters for long-term runs.\nComment: The rebuttal states that the new MTJ system over [Adv. Sci. 11 (23) 2402182 (2024)]\noffers “significantly higher SNR, stability and control resolution.” while no evidence is provided.\nAuthors need to present a single figure or table that overlays old-versus-new statistics, such as KL-\ndivergence to target PDFs, NIST SP 800-22 pass counts, and BER histograms. Without these metrics,\nthe improvement (and its necessity for TSP quality) remains unsubstantiated.\nReply: We sincerely thank the Reviewer for this enlightening inquiry. Following the suggestion, we\ncompared the KL divergence between the generated and target probability distributions for the MTJs\nused in this manuscript and those reported previously in [Adv. Sci. 11 (23) 2402182 (2024)]. In the\nearlier setup, due to limitations of the experimental instrumentation, only ~300 data points were\ncollected for each PDF, which made it difficult to achieve an excellent convergence of KL\ndivergence (~0.02) and accurately evaluate it. As a result, the improvement was not clearly visible.\nIn contrast, the present work benefits from an upgraded measurement system with higher sampling\nrate, higher SNR, improved stability, and finer control resolution. This allowed us to collect\nsufficient statistics to probe the KL divergence down to its minimum value (~0.001), providing a\nmuch more faithful and comprehensive assessment of distribution quality. The generated probability\ndistributions also show visibly improved agreement with the target PDFs.\nIt is important to emphasize that, in principle, the MTJs reported in our earlier publication are also\ncapable of supporting similar TSP solution quality. However, their practical performance was\nconstrained by the control and readout system. In particular, the three-terminal nature of SOT\ndevices made it challenging to realize four-channel high-speed operation simultaneously, severely\nlimiting the achievable sampling rate (~1 Random Number/s). By contrast, the upgraded setup used\nin the present study enables high-speed read/write operation with significantly improved\nmeasurement fidelity, which is essential for faithfully implementing the probabilistic greedy\nalgorithm in real experiments (~ 500k Random Numbers/s). Without these improvements in\nsampling quality, speed and control, the experimental demonstration of the proposed TSP solver\nwould not have been possible.\nFigure R1. Convergence of the KL distance obtained from two systems, the right panel showing the\nzoomed-in image from 0 to 300 Random Numbers.\nComment: The authors need to position the work correctly against prior probabilistic solvers. The\nmanuscript currently asserts “no prior integration of Bayesian PDF with MTJ randomness” yet\nsimulation or conceptual precedents exist (e.g. SPINBIS Bayesian-inference engine). Authors need\nto revise the Introduction to acknowledge these studies explicitly, and then specify what is new here.\nReply: We thank the Reviewer for pointing out the importance of correctly positioning our work\nagainst prior probabilistic solvers. We have accordingly revised the Introduction to explicitly\nacknowledge conceptual and simulation-level precedents, such as the SPINBIS spintronics-based\nBayesian inference engine (Li et al., IEEE TCAD, 2019) and spin-orbit-torque-based Bayesian\nreasoning hardware (Shim et al., Sci. Rep., 2017). While these studies demonstrated the feasibility\nof MTJ-based probabilistic inference for data-fusion and reasoning tasks, our work goes beyond\nsuch precedents by providing the first experimental integration of PDF-configurable MTJ TRNGs\nwith a probabilistic greedy algorithm for TSP optimization. This hybrid hardware-algorithm co-\ndesign highlights a concrete application scenario where hardware-level randomness and Bayesian\nprobability distributions are directly matched and experimentally validated, which has not been\nreported before. We also welcome and appreciate the referee for pointing out other pioneering works\nin case that we have missed them.\nTable R1. The comparison of our work with some precedents\nWork & Target PDF Design Randomness Experimental\nLevel\nReference Application Principle Source Validation\nBayesian\nSPINBIS (Li Weighted sum MTJ stochastic\ninference engine No (conceptual /\net al., IEEE Simulation mapped to model\nfor sensor simulated only)\nTCAD 2019) stochastic MTJs (simulated)\nfusion\nSOT-MTJ\nShim et al. Simulation + Bayesian Analog mapping\nstochastic\n(Sci. Rep. Conceptual reasoning with of switching No (conceptual)\nswitching\n2017) hardware SOT-MTJs probability\n(modeled)\nProbabilistic PDF- STT-MTJ\nYes (full\nThis work greedy configurable experimental\nExperiment experimental\n(2025) algorithm for TRNG realized randomness\nvalidation)\nTSP via MTJs (measured)\nComment: The authors need to provide transparent device and system benchmarks inside this paper.\nKey specs are scattered across earlier publications; readers cannot verify or compare. The authors\nneed to add a table providing prototype time-to-solution and energy (NI-PXIe loop) plus projected\nASIC/FPGA numbers based on published MTJ switching speeds.\nReply: We thank the Reviewer for emphasizing the need for transparent device and system\nbenchmarks. In response, we have added a benchmark table (Table 1) in the revised manuscript that\ndirectly compares our prototype implementation with projected FPGA and ASIC realizations. The\nprototype (NI-PXIe controlled, ~100 nm STT-MTJs) operates at ~0.5 MHz iteration rate and\nrequires ~20 ms per 14-city TSP solution, with energy dominated by instrumentation overhead. In\ncontrast, projections based on published MTJ switching speeds (≤10 ns) and intrinsic switching\nenergies (fJ–pJ per event) indicate that integrated FPGA or ASIC platforms could achieve sub-\nmillisecond or even sub-0.1 ms solution times with microjoule-level energy consumption. This table\nconsolidates previously scattered specifications and provides a clear, quantitative benchmark for\nreaders, thereby addressing the Reviewer’s request for transparent comparison.\nComment: I suggest adding Figures R2 and R5, along with their corresponding discussions, to the\nSupplementary Information, as they enhance understanding.\nReply: We thank the Reviewer for this helpful suggestion. Figures R2 and R5, together with the\ncorresponding discussions, have been added to the Supplementary Information to enhance clarity\nand understanding.\nComment: Figure 4(b) explanation on Page 8 of the main text has an error in identifying the curves.\nReply: We thank the Reviewer for catching this error. We have corrected the text so that the\nidentification of the maximum, minimum, and average curves in Fig. 4(b) matches the figure; the\ncaption was also cross-checked to ensure full consistency.\nComment: There is no logarithmic scaling in Fig. 5b. Please have a check “As such, precise\nnumerical values are not included on the axes, but the figure is drawn proportionally to reflect\nknown theoretical trends (e.g., logarithmic vs. linear vs. exponential scaling)”. The authors have\nresolved the issue in the figure caption, but the mismatch remains in the main text. The authors can\nmake the changes accordingly.\nReply: We thank the Reviewer for pointing this out. In our previous response we mistakenly used\nthe phrase “logarithmic vs. linear vs. exponential scaling.” We have now revised the wording to\nclarify that Fig. 5b is a schematic illustration meant to highlight qualitative scaling trends\n(exponential for brute force, polynomial for dynamic programming, and sub-exponential for\nheuristic approaches), without implying exact logarithmic scaling. This correction ensures\nconsistency between the main text and the figure caption.\n----------------------------------------------------------------------------------------------------------------------\nReviewer #3\n----------------------------------------------------------------------------------------------------------------------\nComment: The authors have made several clarifications over the previous version. Regarding the\nnovelty and significance concerns, the authors suggest an improved sMTJs quality and PDFs owing\nto better experimental setup, and compared the difference of greedy algorithms used here with\nprevious literatures.\nAfter assessment, I think the only distinct advantage of this work is the reduction on the number of\np-bits used (from N2 to log N) in the TSP problem studied. However, whether such p-bit scaling\n2\nadvantage can be well-applied to other COP problems is not demonstrated. The author stated in the\nrebuttal letter that \"we have added a detailed adaptation example for graph coloring in the\nSupplementary Information\", but I'm not able to find any information and evidence on this matter.\nThe supplementary file appears to be the same as the previous version. Overall, I still think this\nwork is better suited for a more specialized journal.\nReply: We sincerely thank Reviewer #3 for the recognition of the novelty of our work, namely “the\nreduction on the number of p-bits used (from N2 to log N) in the TSP problem studied”. We also\n2\nappreciate the reviewer’s request for a concrete demonstration of whether such a scaling advantage\ncan be generalized to other combinatorial optimization problems (COPs). In the revised version, we\nhave therefore included in the Supplementary Information a detailed adaptation example for the\ngraph coloring problem (Supplementary Information VI). In this example, we explicitly define the\ncost function (conflict penalty), derive the corresponding Boltzmann-type probability distribution\nfor color assignment, and describe the step-by-step probabilistic greedy procedure based on MTJ-\ngenerated PDFs. This demonstrates how the same framework, with only a redefinition of the cost\nfunction and the temperature parameter, can be seamlessly extended beyond TSP.\nIn terms of scaling, we clarify in the Supplementary Information that for our probabilistic greedy\nalgorithm the number of MTJs scales as O(log N) and the memory requirement as O(N), whereas\n2\nfor Ising or Boltzmann machines the required hardware resources scale as O(N2) together with\ncalibration overhead. This comparison highlights that the improvement in encoding efficiency\nindeed generalizes to other COPs such as graph coloring.\nThis improved encoding efficiency directly originates from the PDF-configurable MTJ-TRNGs,\nwhich enable real-time, reconfigurable probabilistic decision-making. More importantly, in the\npioneering probabilistic computing systems [Borders, et al. Nature 573 (2019) 390–393; J. Si, et\nal. Nat. Commun. 15 (2024) 3457], the underlying algorithms are basically Boltzmann or Ising\nmachines, which consist of many Bernoulli TRNGs (binary/bipolar TRNGs) as their elements. In\nstark contrast, the realization of arbitrary PDF-configurable TRNG releases us from the classic\nBoltzmann and Ising architectures and allows us to redesign algorithms — equivalently PDFs — in\na larger free space. This direct engineering on PDF not only brings about the higher encoding\nefficiency but also a distinct energy-landscape which is benefit for global convergence.\nFor example, in the Boltzmann machines for a TSP, N×N nodes are necessary and they form a binary\nmatrix. For a reasonable TSP route, all columns and rows of the matrix permit only one node to be\n1; all the rest nodes have to be 0. This requirement for the TSP is achieved by setting a large penalty\nenergy if the above condition is violated. From one reasonable route to another, at least 4 nodes have\nto be reversed. However, the Gibbs protocol only permits 1 node to be updated per sampling\naccording to the all-conditional probability. This means, for any search/trajectory from one\nreasonable route to another, that the system has to undergo at least 3 energy-barrier states (unrealistic\nroutes). It is not hard to image that such a rugged energy landscape is not friendly for global\noptimization especially when only simulated annealing strategy is feasible for the Boltzmann or\nIsing machines. It is also the reason why new algorithms that define a higher efficient PDF or\nlandscape is welcome. For our probabilistic greedy algorithm, no realistic route is involved, which\ncan partially account for its effectiveness. Certainly, the feasibility of the probabilistic greedy\nalgorithm keenly relies on the realization of the PDF-customizable TRNGs. In this sense, this\ngeneralization and the demonstrated prototype establish our approach as a new paradigm beyond\nthe classical Ising or Boltzmann machines and open a broad window for the algorithm redesign.\nFor example, in the Boltzmann machines for a TSP, N×N nodes are necessary and they form a binary\nmatrix. For a reasonable TSP route, all columns and rows of the matrix permit only one node to be\n1; all the rest nodes have to be 0. This requirement for the TSP is achieved by setting a large penalty\nenergy if the above condition is violated. From one reasonable route to another, at least 4 nodes have\nto be reversed. However, the Gibbs protocol only permits 1 node to be updated per sampling\naccording to the all-conditional probability. This means, for any search/trajectory from one\nreasonable route to another, that the system has to undergo at least 3 energy-barrier states (unrealistic\nroutes). It is not hard to image that such a rugged energy landscape is not friendly for global\noptimization especially when only simulated annealing strategy is feasible for the Boltzmann or\nIsing machines. It is also the reason why new algorithms that define a higher efficient PDF or\nlandscape is welcome. For our probabilistic greedy algorithm, no realistic route is involved, which\ncan partially account for its effectiveness. Certainly, the feasibility of the probabilistic greedy\nalgorithm keenly relies on the realization of the PDF-customizable TRNGs. In this sense, this\ngeneralization and the demonstrated prototype establish our approach as a new paradigm beyond\nthe classical Ising or Boltzmann machines and open a broad window for the algorithm redesign.\nFinally, we thank all the three reviewers for their enlightening questions and remarks without which\nthe manuscript cannot be substantially improved.\nReviewer’s Report\nThe manuscript, entitled “Probabilistic Greedy Algorithm Solver Using Magnetic Tunneling\nJunctions for Traveling Salesman Problem,” presents a forward-looking approach to hardware-\naccelerated combinatorial optimization. By leveraging the inherent stochastic behavior of spin-\ntransfer torque magnetic tunneling junctions (STT-MTJs), the authors demonstrate a\nprobabilistic greedy algorithm capable of addressing the traveling salesman problem (TSP) with\nnotable efficiency. Through the adjustable true random number generation of MTJs, the work\nenables dynamic probability distribution configurations and achieves a smooth transition\nbetween purely greedy and fully random search strategies bytuning a“temperature”parameter.\nBeyond its methodological novelty, this work is substantiated by thorough experimental results\nand simulations. The demonstrations on both a smaller-scale TSP (Burma14) and a larger\ninstance (st70) highlight the scalability and robustness of the proposed solver. In doing so, the\nauthors provide compelling evidence that integrating configurable MTJ-based TRNGs can\nsignificantly improve solution quality and convergence speed when compared to classical\napproaches such as simulated annealing and genetic algorithms. Especially, they demonstrated\nthat the encoding efficiency using these PDF-configurable TRNGs (log N) is much higher than\n2\nthat of the classic Boltzmann machines for the TSP problems (N2). Furthermore, the combination\nofhardware-level randomness with a carefully designed probabilisticsearch algorithm appears to\nbe a promising direction for tackling NP-hard problems. The authors’ success with TSP\nunderscores the potential for broader applications infields such as scheduling, graph partitioning,\nand other complex optimization challenges.\nOverall, this manuscript provides a compelling contribution to the burgeoning field of\nprobabilistic computing. The implementation of MTJ-based TRNGs in a customizable way—\ntogether with a carefully orchestrated algorithmic structure—illustrates a path toward higher-\nperformance solutions for large-scale optimization tasks. The multi-faceted evaluation, spanning\ndevice fabrication, experimental verification, and algorithmic benchmarking, is particularly\ncommendable. In my opinion, the paper is well-structured, clearly written, and of direct interest\nto a broad cross-section of researchers working on spintronics, computational optimization, and\nhardware-accelerated algorithms. I therefore strongly recommend its publication in Nature\nCommunications, provided the authors address the questions and minor enhancements noted\nbelow. In addition, I suggest adding further references that connect this work to foundational\nmethods in combinatorial optimization and TRNG-based hardware design. I believe\nclarifications on these matters, alongside the inclusion of key additional citations, would further\nstrengthen themanuscript’s narrativeand ensure maximumimpact for a widereadership.\nQuestions\n1. The authors provide strong experimental evidence of repeatable MTJ switching\nprobabilities at varying voltages. However, can the authors expand on how larger-scale\ndevice variations—such as minor manufacturing inconsistencies or drift over time—\nmight affect solution quality? Are there calibration strategies to ensure consistent TRNG\nbehavior across an array ofMTJs?\n2. The manuscript focuses on the traveling salesman problem as a case study. Could the\nauthors elaborate onhowseamlessly theirapproach can be adapted to othercombinatorial\nproblems, for example, graph coloring or scheduling? Would the same “temperature”\ntuningprinciple besufficient, ormight additionalmodifications be required?\n3. The authors note that the probability distribution used in each city-selection step changes\nover time. Is there any significant overhead associated with frequently reconfiguring the\nMTJ TRNG voltage settings or readout circuitry during an iterative process? A brief\ndiscussion of potential timing constraints or hardware-level overhead would further\nclarify theperformance.\n4. While the authors compare their method to simulated annealing and genetic algorithms,\nhave they considered advanced metaheuristics like ant colony optimization or particle\nswarm optimization? Adding a sentence or two on how the proposed solver might be\npositionedrelative to these approaches could strengthen thediscussion.\n5. While the manuscript discusses results for up to 70 cities in TSP, many real-world\napplications involve hundreds or even thousands of nodes (e.g., in large logistics\nnetworks). Do the authors anticipate any significant performance bottlenecks or\nalgorithmic adjustments needed to maintain solution quality or convergence speed at\nmuch larger scales?\n6. In practical systems, transient faults or soft errors (e.g., due to electromagnetic\ninterference) can occasionally produce outlier random values. Do the authors foresee the\nneed for error-correction logic in the random number generation process, or is the\nprobabilisticnature ofthealgorithm itselfsufficient to absorb occasional anomalies?\n7. The temperature-related parameter (k T) appears in several figures and equations. A\nB\nsingle consistent notation (e.g., always using k T or T ) throughout the text, figures, and\nB\ncaptions would help readability.\n8. The paper occasionally shifts between “true random number generators,” “hardware\nrandomness,” and “probabilistic bits.” Standardizing the terminology—perhaps defining\neachconcept at theoutset—would streamline thereader’s experience.\n9. In addition to the classical references to combinatorial optimization and TSP, it might be\nworthwhile to cite a few seminal articles on spintronic TRNGs or in-memory computing\napproaches. This could underscore how the present work builds on, and differs from,\nearlierdevice-centricstudies.\nSuggestions of Additional References\n1. Fukushima,A. et al. Spindice:Ascalable truly random number generatorbased on\nspintronics. Appl.Phys. Express 7,083001(2014).\n2. WonHoChoi et al.AMagneticTunnel JunctionbasedTrue RandomNumber Generator\nwithconditional perturb and real-time outputprobability tracking. in2014IEEE\nInternationalElectron Devices Meeting 12.5.1-12.5.4 (IEEE, San Francisco, CA,USA,\n2014).\n3. Vodenicarevic, D. et al. Low-EnergyTrulyRandom Number Generation with\nSuperparamagneticTunnel Junctionsfor Unconventional Computing. Phys. Rev.Applied\n8,054045(2017)."}, {"round": 2, "reviewer_comments": {"reviewer_1": "Authors have addressed all of my concerns, I recommend to publish as it is.", "reviewer_2": "The authors made substantial modifications to the original manuscript. The revised manuscript presents an engineering link-up between an MTJ-based, PDF-configurable TRNG and a probabilistic-greedy TSP solver. Unfortunately, both ingredients are documented in the literature, and the present version does not yet provide the data or analysis needed to elevate the work from incremental to transformative. Some critical aspects are still missing. Thus, I recommend the authors revise their manuscript according to the comments below.\n\nThe authors state that their hardware scales with log2N, but I find this argument unconvincing. In practice, the dominant factor in scaling is memory usage. For instance, solving an N-city TSP typically requires storing N sets of information, implying at least O(N) memory. If we focus solely on the use of MTJs, algorithms such as simulated annealing can reuse a single MTJ across problem sizes without any sacrifices in time or energy. However, this does not mean that the hardware is free from scaling considerations, while the MTJ count may remain constant, other aspects, particularly memory, still scale with problem size.\n\nThe rebuttal states that the new MTJ system over [Adv. Sci. 11 (23) 2402182 (2024)] offers “significantly higher SNR, stability and control resolution.” while no evidence is provided. Authors need to present a single figure or table that overlays old-versus-new statistics, such as KL-divergence to target PDFs, NIST SP 800-22 pass counts, and BER histograms. Without these metrics, the improvement (and its necessity for TSP quality) remains unsubstantiated.\n\nThe authors need to position the work correctly against prior probabilistic solvers. The manuscript currently asserts “no prior integration of Bayesian PDF with MTJ randomness” yet simulation or conceptual precedents exist (e.g. SPINBIS Bayesian-inference engine). Authors need to revise the Introduction to acknowledge these studies explicitly, and then specify what is new here.\n\nThe authors need to provide transparent device and system benchmarks inside this paper. Key specs are scattered across earlier publications; readers cannot verify or compare. The authors need to add a table providing prototype time-to-solution and energy (NI-PXIe loop) plus projected ASIC/FPGA numbers based on published MTJ switching speeds.\n\nI suggest adding Figures R2 and R5, along with their corresponding discussions, to the Supplementary Information, as they enhance understanding.\n\nFigure 4(b) explanation on Page 8 of the main text has an error in identifying the curves.\n\nThere is no logarithmic scaling in Fig. 5b. Please have a check “As such, precise numerical values are not included on the axes, but the figure is drawn proportionally to reflect known theoretical trends (e.g., logarithmic vs. linear vs. exponential scaling).”.\n\nThe authors have resolved the issue in the figure caption, but the mismatch remains in the main text. The authors can make the changes accordingly.", "reviewer_3": "The authors have made several clarifications over the previous version. Regarding the novelty and significance concerns, the authors suggest an improved sMTJs quality and PDFs owing to better experimental setup, and compared the difference of greedy algorithms used here with previous literatures.\n\nAfter assessment, I think the only distinct advantage of this work is the reduction on the number of p-bits used (from N^2 to log2N) in the TSP problem studied. However, whether such p-bit scaling advantage can be well-applied to other COP problems is not demonstrated. The author stated in the rebuttal letter that \"we have added a detailed adaptation example for graph coloring in the Supplementary Information\", but I'm not able to find any information and evidence on this matter. The supplementary file appears to be the same as the previous version. Overall, I still think this work is better suited for a more specialized journal."}, "author_response": "Response Letter to Reviewers - NCOMMS-24-82665\n----------------------------------------------------------------------------------------------------------------------\nWe would like to sincerely thank all three Reviewers for their careful reading of our manuscript and\nfor the constructive and insightful comments provided. The feedback from the Reviewers has been\ninvaluable in helping us to significantly improve the clarity, depth, and positioning of our work.\nReviewer #1’s supportive remarks are greatly appreciated; Reviewer #2’s detailed questions and\nrequests for benchmarking, positioning, and additional evidence have guided us to strengthen both\nthe analysis and presentation; and Reviewer #3’s concerns about generalizability have motivated us\nto explicitly extend our discussion and provide new supplementary material demonstrating the\nbroader applicability of our approach. We are truly grateful for the Reviewers’ time and effort, which\nhave substantially enhanced the quality of the revised manuscript.\n----------------------------------------------------------------------------------------------------------------------\nReviewer #1\n----------------------------------------------------------------------------------------------------------------------\nComment: Authors have addressed all of my concerns, I recommend to publish as it is.\nReply: We sincerely thank Reviewer #1 for the positive assessment and for recommending our\nmanuscript for publication. We truly appreciate the reviewer’s encouraging comments in the first\nround and the current recognition that all concerns have been satisfactorily addressed. The\nconstructive feedback was invaluable in helping us refine the manuscript, and we are grateful for\nthe reviewer’s support and endorsement.\n----------------------------------------------------------------------------------------------------------------------\nReviewer #2\n----------------------------------------------------------------------------------------------------------------------\nComment: The authors made substantial modifications to the original manuscript. The revised\nmanuscript presents an engineering link-up between an MTJ-based, PDF-configurable TRNG and\na probabilistic-greedy TSP solver. Unfortunately, both ingredients are documented in the literature,\nand the present version does not yet provide the data or analysis needed to elevate the work from\nincremental to transformative. Some critical aspects are still missing. Thus, I recommend the authors\nrevise their manuscript according to the comments below.\nReply: We sincerely thank Reviewer #2 for the careful re-evaluation of our revised manuscript and\nfor the encouraging remark that we have made “substantial modifications to the original manuscript”.\nWe are very grateful for the reviewer’s constructive criticisms, which have helped us to identify\nimportant missing aspects and refine the presentation of our work. Following the reviewer’s\ninsightful guidance, we have further revised the manuscript in this round, adding new analyses,\nclarifications, and supporting data to address the specific points raised. We believe that these\nimprovements, motivated directly by the reviewer’s valuable feedback, have significantly\nstrengthened the manuscript.\nComment: The authors state that their hardware scales with log N, but I find this argument\n2\nunconvincing. In practice, the dominant factor in scaling is memory usage. For instance, solving an\nN-city TSP typically requires storing N sets of information, implying at least O(N) memory. If we\nfocus solely on the use of MTJs, algorithms such as simulated annealing can reuse a single MTJ\nacross problem sizes without any sacrifices in time or energy. However, this does not mean that the\nhardware is free from scaling considerations, while the MTJ count may remain constant, other\naspects, particularly memory, still scale with problem size.\nReply: We sincerely thank the Reviewer #2 for this enlightening question. The point we originally\nemphasized was specifically the number of MTJs (N ) required to encode a complete probability\nMTJ\ndistribution in the proposed greedy algorithm, which scales as N = log N, for example, 16 cities\nMTJ 2\nrequiring 4 nodes. However, a small number of MTJs alone (e.g., 4 MTJs for a 16-city TSP) cannot\ndirectly generate real routes; instead, they must be assisted by a conditional probability table (CPT)\nor a shallow forward neuron network (NN) containing a number of parameters to assist the 4 MTJs\nto implement real samplings. The data included in the CPT or NN is in the order of (2N MTJ – 1).\nTherefore, we need additional memories of (N-1) to store the CPT or NN parameters. As exactly\nspeculated by the reviewer, the needed memory scales in the order of O(N) with the increase in the\ncity number N, which is already minimal for a N-city TSP problem. We have updated the revised\nmanuscript on this point. Thanks for the question and comment again.\nSecond, besides of the scaling law O(log N) of the number of needed MTJs, the scaling law in\n2\nmemory ~O(N) for the probabilistic greedy algorithm is also favorable, compared with the\nBoltzmann or Ising machines. For the latter, O(N2) MTJs are needed to encode a map, and, for each\nMTJ, 2 floating-point bits are necessary to memorize the parameters α and V of an individual P-V\nc\nrelation of the MTJ, P=1/[1+exp(-α(V-V )/T)]. Here V is the critical switching voltage with P=50%\nc c\nand α depicts the sharpness of the sigmoid or tanh functions. In this case, the needed memory scales\nwith O(2N2) for the Boltzmann or Ising machines.\nThird, more subtly and critically, for the Boltzmann or Ising machines, sampling is implemented\nfollowing the Gibbs protocol. In details, the influence experienced by one node, for instance, the\nvoltage imposed on the node for a sampling attempt, is rescaled and biased according to the\nfingerprint parameters α and V of the node from the weighted sum of the on-time states of all the\nc\nrest nodes. Because of the diversity in performances of those MTJs, we cannot expect a uniform α\nand a uniform V for all nodes. Instead, we need to memorize all the fingerprint α and V for each\nc c\nnode. Thus, O(N2) mentioned above is involved. More critically, we have not considered the\ninfluence from performance drift in time. If this issue is concerned, time-to-time recalibration on α\nand V for each node may be indispensable, especially, for long-term runs. The need for this\nc\nrecalibration originates from the requirement of the precise sampling according to the diverse and\ndrifting P-V relations of all nodes (or real α and V parameters). However, this annoying point can\nc\nbe fortunately avoided for the probabilistic greedy algorithm because only sampling probability\n(accurate P) instead of the driving voltage is critical for the latter and this accurate sampling\nprobability P can be ensured by many self-stabilizing methodologies such as Ref. [Zhang et al. Phys.\nRev. Appl. 23 (2025) 054073].\nIn sum, both MTJ count and memory requirement scale favorably — O(log N) and O(N),\n2\nrespectively — in our method, in sharp contrast to the O(N2) scaling of Boltzmann or Ising machines\nthat may additionally require occasional calibration of device-specific parameters for long-term runs.\nComment: The rebuttal states that the new MTJ system over [Adv. Sci. 11 (23) 2402182 (2024)]\noffers “significantly higher SNR, stability and control resolution.” while no evidence is provided.\nAuthors need to present a single figure or table that overlays old-versus-new statistics, such as KL-\ndivergence to target PDFs, NIST SP 800-22 pass counts, and BER histograms. Without these metrics,\nthe improvement (and its necessity for TSP quality) remains unsubstantiated.\nReply: We sincerely thank the Reviewer for this enlightening inquiry. Following the suggestion, we\ncompared the KL divergence between the generated and target probability distributions for the MTJs\nused in this manuscript and those reported previously in [Adv. Sci. 11 (23) 2402182 (2024)]. In the\nearlier setup, due to limitations of the experimental instrumentation, only ~300 data points were\ncollected for each PDF, which made it difficult to achieve an excellent convergence of KL\ndivergence (~0.02) and accurately evaluate it. As a result, the improvement was not clearly visible.\nIn contrast, the present work benefits from an upgraded measurement system with higher sampling\nrate, higher SNR, improved stability, and finer control resolution. This allowed us to collect\nsufficient statistics to probe the KL divergence down to its minimum value (~0.001), providing a\nmuch more faithful and comprehensive assessment of distribution quality. The generated probability\ndistributions also show visibly improved agreement with the target PDFs.\nIt is important to emphasize that, in principle, the MTJs reported in our earlier publication are also\ncapable of supporting similar TSP solution quality. However, their practical performance was\nconstrained by the control and readout system. In particular, the three-terminal nature of SOT\ndevices made it challenging to realize four-channel high-speed operation simultaneously, severely\nlimiting the achievable sampling rate (~1 Random Number/s). By contrast, the upgraded setup used\nin the present study enables high-speed read/write operation with significantly improved\nmeasurement fidelity, which is essential for faithfully implementing the probabilistic greedy\nalgorithm in real experiments (~ 500k Random Numbers/s). Without these improvements in\nsampling quality, speed and control, the experimental demonstration of the proposed TSP solver\nwould not have been possible.\nFigure R1. Convergence of the KL distance obtained from two systems, the right panel showing the\nzoomed-in image from 0 to 300 Random Numbers.\nComment: The authors need to position the work correctly against prior probabilistic solvers. The\nmanuscript currently asserts “no prior integration of Bayesian PDF with MTJ randomness” yet\nsimulation or conceptual precedents exist (e.g. SPINBIS Bayesian-inference engine). Authors need\nto revise the Introduction to acknowledge these studies explicitly, and then specify what is new here.\nReply: We thank the Reviewer for pointing out the importance of correctly positioning our work\nagainst prior probabilistic solvers. We have accordingly revised the Introduction to explicitly\nacknowledge conceptual and simulation-level precedents, such as the SPINBIS spintronics-based\nBayesian inference engine (Li et al., IEEE TCAD, 2019) and spin-orbit-torque-based Bayesian\nreasoning hardware (Shim et al., Sci. Rep., 2017). While these studies demonstrated the feasibility\nof MTJ-based probabilistic inference for data-fusion and reasoning tasks, our work goes beyond\nsuch precedents by providing the first experimental integration of PDF-configurable MTJ TRNGs\nwith a probabilistic greedy algorithm for TSP optimization. This hybrid hardware-algorithm co-\ndesign highlights a concrete application scenario where hardware-level randomness and Bayesian\nprobability distributions are directly matched and experimentally validated, which has not been\nreported before. We also welcome and appreciate the referee for pointing out other pioneering works\nin case that we have missed them.\nTable R1. The comparison of our work with some precedents\nWork & Target PDF Design Randomness Experimental\nLevel\nReference Application Principle Source Validation\nBayesian\nSPINBIS (Li Weighted sum MTJ stochastic\ninference engine No (conceptual /\net al., IEEE Simulation mapped to model\nfor sensor simulated only)\nTCAD 2019) stochastic MTJs (simulated)\nfusion\nSOT-MTJ\nShim et al. Simulation + Bayesian Analog mapping\nstochastic\n(Sci. Rep. Conceptual reasoning with of switching No (conceptual)\nswitching\n2017) hardware SOT-MTJs probability\n(modeled)\nProbabilistic PDF- STT-MTJ\nYes (full\nThis work greedy configurable experimental\nExperiment experimental\n(2025) algorithm for TRNG realized randomness\nvalidation)\nTSP via MTJs (measured)\nComment: The authors need to provide transparent device and system benchmarks inside this paper.\nKey specs are scattered across earlier publications; readers cannot verify or compare. The authors\nneed to add a table providing prototype time-to-solution and energy (NI-PXIe loop) plus projected\nASIC/FPGA numbers based on published MTJ switching speeds.\nReply: We thank the Reviewer for emphasizing the need for transparent device and system\nbenchmarks. In response, we have added a benchmark table (Table 1) in the revised manuscript that\ndirectly compares our prototype implementation with projected FPGA and ASIC realizations. The\nprototype (NI-PXIe controlled, ~100 nm STT-MTJs) operates at ~0.5 MHz iteration rate and\nrequires ~20 ms per 14-city TSP solution, with energy dominated by instrumentation overhead. In\ncontrast, projections based on published MTJ switching speeds (≤10 ns) and intrinsic switching\nenergies (fJ–pJ per event) indicate that integrated FPGA or ASIC platforms could achieve sub-\nmillisecond or even sub-0.1 ms solution times with microjoule-level energy consumption. This table\nconsolidates previously scattered specifications and provides a clear, quantitative benchmark for\nreaders, thereby addressing the Reviewer’s request for transparent comparison.\nComment: I suggest adding Figures R2 and R5, along with their corresponding discussions, to the\nSupplementary Information, as they enhance understanding.\nReply: We thank the Reviewer for this helpful suggestion. Figures R2 and R5, together with the\ncorresponding discussions, have been added to the Supplementary Information to enhance clarity\nand understanding.\nComment: Figure 4(b) explanation on Page 8 of the main text has an error in identifying the curves.\nReply: We thank the Reviewer for catching this error. We have corrected the text so that the\nidentification of the maximum, minimum, and average curves in Fig. 4(b) matches the figure; the\ncaption was also cross-checked to ensure full consistency.\nComment: There is no logarithmic scaling in Fig. 5b. Please have a check “As such, precise\nnumerical values are not included on the axes, but the figure is drawn proportionally to reflect\nknown theoretical trends (e.g., logarithmic vs. linear vs. exponential scaling)”. The authors have\nresolved the issue in the figure caption, but the mismatch remains in the main text. The authors can\nmake the changes accordingly.\nReply: We thank the Reviewer for pointing this out. In our previous response we mistakenly used\nthe phrase “logarithmic vs. linear vs. exponential scaling.” We have now revised the wording to\nclarify that Fig. 5b is a schematic illustration meant to highlight qualitative scaling trends\n(exponential for brute force, polynomial for dynamic programming, and sub-exponential for\nheuristic approaches), without implying exact logarithmic scaling. This correction ensures\nconsistency between the main text and the figure caption.\n----------------------------------------------------------------------------------------------------------------------\nReviewer #3\n----------------------------------------------------------------------------------------------------------------------\nComment: The authors have made several clarifications over the previous version. Regarding the\nnovelty and significance concerns, the authors suggest an improved sMTJs quality and PDFs owing\nto better experimental setup, and compared the difference of greedy algorithms used here with\nprevious literatures.\nAfter assessment, I think the only distinct advantage of this work is the reduction on the number of\np-bits used (from N2 to log N) in the TSP problem studied. However, whether such p-bit scaling\n2\nadvantage can be well-applied to other COP problems is not demonstrated. The author stated in the\nrebuttal letter that \"we have added a detailed adaptation example for graph coloring in the\nSupplementary Information\", but I'm not able to find any information and evidence on this matter.\nThe supplementary file appears to be the same as the previous version. Overall, I still think this\nwork is better suited for a more specialized journal.\nReply: We sincerely thank Reviewer #3 for the recognition of the novelty of our work, namely “the\nreduction on the number of p-bits used (from N2 to log N) in the TSP problem studied”. We also\n2\nappreciate the reviewer’s request for a concrete demonstration of whether such a scaling advantage\ncan be generalized to other combinatorial optimization problems (COPs). In the revised version, we\nhave therefore included in the Supplementary Information a detailed adaptation example for the\ngraph coloring problem (Supplementary Information VI). In this example, we explicitly define the\ncost function (conflict penalty), derive the corresponding Boltzmann-type probability distribution\nfor color assignment, and describe the step-by-step probabilistic greedy procedure based on MTJ-\ngenerated PDFs. This demonstrates how the same framework, with only a redefinition of the cost\nfunction and the temperature parameter, can be seamlessly extended beyond TSP.\nIn terms of scaling, we clarify in the Supplementary Information that for our probabilistic greedy\nalgorithm the number of MTJs scales as O(log N) and the memory requirement as O(N), whereas\n2\nfor Ising or Boltzmann machines the required hardware resources scale as O(N2) together with\ncalibration overhead. This comparison highlights that the improvement in encoding efficiency\nindeed generalizes to other COPs such as graph coloring.\nThis improved encoding efficiency directly originates from the PDF-configurable MTJ-TRNGs,\nwhich enable real-time, reconfigurable probabilistic decision-making. More importantly, in the\npioneering probabilistic computing systems [Borders, et al. Nature 573 (2019) 390–393; J. Si, et\nal. Nat. Commun. 15 (2024) 3457], the underlying algorithms are basically Boltzmann or Ising\nmachines, which consist of many Bernoulli TRNGs (binary/bipolar TRNGs) as their elements. In\nstark contrast, the realization of arbitrary PDF-configurable TRNG releases us from the classic\nBoltzmann and Ising architectures and allows us to redesign algorithms — equivalently PDFs — in\na larger free space. This direct engineering on PDF not only brings about the higher encoding\nefficiency but also a distinct energy-landscape which is benefit for global convergence.\nFor example, in the Boltzmann machines for a TSP, N×N nodes are necessary and they form a binary\nmatrix. For a reasonable TSP route, all columns and rows of the matrix permit only one node to be\n1; all the rest nodes have to be 0. This requirement for the TSP is achieved by setting a large penalty\nenergy if the above condition is violated. From one reasonable route to another, at least 4 nodes have\nto be reversed. However, the Gibbs protocol only permits 1 node to be updated per sampling\naccording to the all-conditional probability. This means, for any search/trajectory from one\nreasonable route to another, that the system has to undergo at least 3 energy-barrier states (unrealistic\nroutes). It is not hard to image that such a rugged energy landscape is not friendly for global\noptimization especially when only simulated annealing strategy is feasible for the Boltzmann or\nIsing machines. It is also the reason why new algorithms that define a higher efficient PDF or\nlandscape is welcome. For our probabilistic greedy algorithm, no realistic route is involved, which\ncan partially account for its effectiveness. Certainly, the feasibility of the probabilistic greedy\nalgorithm keenly relies on the realization of the PDF-customizable TRNGs. In this sense, this\ngeneralization and the demonstrated prototype establish our approach as a new paradigm beyond\nthe classical Ising or Boltzmann machines and open a broad window for the algorithm redesign.\nFor example, in the Boltzmann machines for a TSP, N×N nodes are necessary and they form a binary\nmatrix. For a reasonable TSP route, all columns and rows of the matrix permit only one node to be\n1; all the rest nodes have to be 0. This requirement for the TSP is achieved by setting a large penalty\nenergy if the above condition is violated. From one reasonable route to another, at least 4 nodes have\nto be reversed. However, the Gibbs protocol only permits 1 node to be updated per sampling\naccording to the all-conditional probability. This means, for any search/trajectory from one\nreasonable route to another, that the system has to undergo at least 3 energy-barrier states (unrealistic\nroutes). It is not hard to image that such a rugged energy landscape is not friendly for global\noptimization especially when only simulated annealing strategy is feasible for the Boltzmann or\nIsing machines. It is also the reason why new algorithms that define a higher efficient PDF or\nlandscape is welcome. For our probabilistic greedy algorithm, no realistic route is involved, which\ncan partially account for its effectiveness. Certainly, the feasibility of the probabilistic greedy\nalgorithm keenly relies on the realization of the PDF-customizable TRNGs. In this sense, this\ngeneralization and the demonstrated prototype establish our approach as a new paradigm beyond\nthe classical Ising or Boltzmann machines and open a broad window for the algorithm redesign.\nFinally, we thank all the three reviewers for their enlightening questions and remarks without which\nthe manuscript cannot be substantially improved.\nReviewer’s Report\nThe manuscript, entitled “Probabilistic Greedy Algorithm Solver Using Magnetic Tunneling\nJunctions for Traveling Salesman Problem,” presents a forward-looking approach to hardware-\naccelerated combinatorial optimization. By leveraging the inherent stochastic behavior of spin-\ntransfer torque magnetic tunneling junctions (STT-MTJs), the authors demonstrate a\nprobabilistic greedy algorithm capable of addressing the traveling salesman problem (TSP) with\nnotable efficiency. Through the adjustable true random number generation of MTJs, the work\nenables dynamic probability distribution configurations and achieves a smooth transition\nbetween purely greedy and fully random search strategies bytuning a“temperature”parameter.\nBeyond its methodological novelty, this work is substantiated by thorough experimental results\nand simulations. The demonstrations on both a smaller-scale TSP (Burma14) and a larger\ninstance (st70) highlight the scalability and robustness of the proposed solver. In doing so, the\nauthors provide compelling evidence that integrating configurable MTJ-based TRNGs can\nsignificantly improve solution quality and convergence speed when compared to classical\napproaches such as simulated annealing and genetic algorithms. Especially, they demonstrated\nthat the encoding efficiency using these PDF-configurable TRNGs (log N) is much higher than\n2\nthat of the classic Boltzmann machines for the TSP problems (N2). Furthermore, the combination\nofhardware-level randomness with a carefully designed probabilisticsearch algorithm appears to\nbe a promising direction for tackling NP-hard problems. The authors’ success with TSP\nunderscores the potential for broader applications infields such as scheduling, graph partitioning,\nand other complex optimization challenges.\nOverall, this manuscript provides a compelling contribution to the burgeoning field of\nprobabilistic computing. The implementation of MTJ-based TRNGs in a customizable way—\ntogether with a carefully orchestrated algorithmic structure—illustrates a path toward higher-\nperformance solutions for large-scale optimization tasks. The multi-faceted evaluation, spanning\ndevice fabrication, experimental verification, and algorithmic benchmarking, is particularly\ncommendable. In my opinion, the paper is well-structured, clearly written, and of direct interest\nto a broad cross-section of researchers working on spintronics, computational optimization, and\nhardware-accelerated algorithms. I therefore strongly recommend its publication in Nature\nCommunications, provided the authors address the questions and minor enhancements noted\nbelow. In addition, I suggest adding further references that connect this work to foundational\nmethods in combinatorial optimization and TRNG-based hardware design. I believe\nclarifications on these matters, alongside the inclusion of key additional citations, would further\nstrengthen themanuscript’s narrativeand ensure maximumimpact for a widereadership.\nQuestions\n1. The authors provide strong experimental evidence of repeatable MTJ switching\nprobabilities at varying voltages. However, can the authors expand on how larger-scale\ndevice variations—such as minor manufacturing inconsistencies or drift over time—\nmight affect solution quality? Are there calibration strategies to ensure consistent TRNG\nbehavior across an array ofMTJs?\n2. The manuscript focuses on the traveling salesman problem as a case study. Could the\nauthors elaborate onhowseamlessly theirapproach can be adapted to othercombinatorial\nproblems, for example, graph coloring or scheduling? Would the same “temperature”\ntuningprinciple besufficient, ormight additionalmodifications be required?\n3. The authors note that the probability distribution used in each city-selection step changes\nover time. Is there any significant overhead associated with frequently reconfiguring the\nMTJ TRNG voltage settings or readout circuitry during an iterative process? A brief\ndiscussion of potential timing constraints or hardware-level overhead would further\nclarify theperformance.\n4. While the authors compare their method to simulated annealing and genetic algorithms,\nhave they considered advanced metaheuristics like ant colony optimization or particle\nswarm optimization? Adding a sentence or two on how the proposed solver might be\npositionedrelative to these approaches could strengthen thediscussion.\n5. While the manuscript discusses results for up to 70 cities in TSP, many real-world\napplications involve hundreds or even thousands of nodes (e.g., in large logistics\nnetworks). Do the authors anticipate any significant performance bottlenecks or\nalgorithmic adjustments needed to maintain solution quality or convergence speed at\nmuch larger scales?\n6. In practical systems, transient faults or soft errors (e.g., due to electromagnetic\ninterference) can occasionally produce outlier random values. Do the authors foresee the\nneed for error-correction logic in the random number generation process, or is the\nprobabilisticnature ofthealgorithm itselfsufficient to absorb occasional anomalies?\n7. The temperature-related parameter (k T) appears in several figures and equations. A\nB\nsingle consistent notation (e.g., always using k T or T ) throughout the text, figures, and\nB\ncaptions would help readability.\n8. The paper occasionally shifts between “true random number generators,” “hardware\nrandomness,” and “probabilistic bits.” Standardizing the terminology—perhaps defining\neachconcept at theoutset—would streamline thereader’s experience.\n9. In addition to the classical references to combinatorial optimization and TSP, it might be\nworthwhile to cite a few seminal articles on spintronic TRNGs or in-memory computing\napproaches. This could underscore how the present work builds on, and differs from,\nearlierdevice-centricstudies.\nSuggestions of Additional References\n1. Fukushima,A. et al. Spindice:Ascalable truly random number generatorbased on\nspintronics. Appl.Phys. Express 7,083001(2014).\n2. WonHoChoi et al.AMagneticTunnel JunctionbasedTrue RandomNumber Generator\nwithconditional perturb and real-time outputprobability tracking. in2014IEEE\nInternationalElectron Devices Meeting 12.5.1-12.5.4 (IEEE, San Francisco, CA,USA,\n2014).\n3. Vodenicarevic, D. et al. Low-EnergyTrulyRandom Number Generation with\nSuperparamagneticTunnel Junctionsfor Unconventional Computing. Phys. Rev.Applied\n8,054045(2017)."}, {"round": 3, "reviewer_comments": {"reviewer_2": "The authors have addressed the issue I previously flagged, and it can now be considered for publication.", "reviewer_3": "The authors have renewed the supplementary information and demonstrated the potential scalability over a graph coloring example which addressed my concern."}, "author_response": ""}]

Decision letter