Mastering the Exponential Complexity of Exact Physical Simulation of Silicon Dangling Bonds

Silicon Dangling Bond (SiDB) logic is a promising technology for energy-efficient computation, supported by significant advancements in manufacturing and design automation. However, physical simulation, essential for accurately predicting the behavior of SiDB logic prior to costly manufacturing, lags behind these developments. In particular, exact physical simulation, which scales exponentially with base 3, remains infeasible for larger SiDB assemblies, limiting its utility to small structures such as single gates. This computational bottleneck slows progress in SiDB technology and hinders the establishment of reliable ground truths for heuristic approaches. To address the challenge, this work presents a novel methodology for exact SiDB simulation that restructures the exponential search space according to a hierarchical clustering. The hierarchy structure enables a systematic pruning of the search space at its different levels: it provides an ordering of interactions between clusters of SiDBs to facilitate efficacious exploitation of dynamically-inferred problem-specific constraints—like solving a Sudoku. Experimental results demonstrate that the effective exponential base can be lowered to approximately 1.3, enabling, for the first time, the exact physical simulation of entire multi-gate SiDB circuits in minutes that would take the state of the art millions of years to compute. This breakthrough establishes a robust ground truth for SiDB logic validation, marking a pivotal step toward scalable, energy-efficient, and atomic-scale computing.

Download here