Implicit Binarization via Complex Phase Dynamics in Combinatorial Optimization
For researchers tackling NP-hard combinatorial optimization problems, this framework offers a novel continuous relaxation that significantly improves solution quality and robustness to noise.
This work introduces a continuous relaxation for NP-hard combinatorial optimization by parameterizing binary variables as complex phases, which smooths energy landscapes and enables implicit regularization toward discrete states. The method achieves zero error on 160x160 QUBO tasks under severe noise and outperforms OMP and LASSO in sparse coding with perfect recovery at sigma=0.15.
We introduce a physics-inspired continuous relaxation framework that yields substantially improved solutions for NP-hard combinatorial optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), binary sparse coding, and planted-solution Ising models. By parameterizing discrete binary variables as continuous wave-like states on the complex unit circle, we inherently smooth highly non-convex energy landscapes. We show that representing binary variables as complex phases reveals an implicit regularization mechanism that promotes convergence toward discrete states. Extracting this mechanism yields significant improvements even within standard real-valued optimization frameworks, using this regularizer explicitly. Empirically, this regularization yields vastly higher ground-state convergence rates than standard real-valued alternatives. Our models achieved zero error in large-scale 160x160 QUBO tasks under severe noise (sigma=0.25), and outperformed traditional algorithms (OMP and LASSO) in underdefined sparse coding with perfect recovery at sigma=0.15. The solver's robustness was further validated by recovering exact ground-state configurations in 8 out of 11 rigorously engineered planted-solution benchmarks.