This paper introduces a novel method for unsupervised neural combinatorial optimization (UCO) using diffusion models. The approach leverages a loss function that upper bounds the reverse Kullback-Leibler divergence, allowing the use of expressive latent variable models like diffusion models without requiring exact sample likelihoods. The method, named *Diffusion for Unsupervised Combinatorial Optimization* (DiffUCO), is validated on various benchmark problems in UCO, demonstrating state-of-the-art performance. DiffUCO uses an iterative sampling process to generate solutions, with the number of diffusion steps increasing during training to improve solution quality. The paper also introduces a more efficient sampling strategy, *Conditional Expectation* (CE), which, when combined with DiffUCO, allows for time-efficient generation of high-quality solutions. The method is shown to be highly efficient and general, making it a promising approach for data-free approximation of discrete distributions in various scientific fields.This paper introduces a novel method for unsupervised neural combinatorial optimization (UCO) using diffusion models. The approach leverages a loss function that upper bounds the reverse Kullback-Leibler divergence, allowing the use of expressive latent variable models like diffusion models without requiring exact sample likelihoods. The method, named *Diffusion for Unsupervised Combinatorial Optimization* (DiffUCO), is validated on various benchmark problems in UCO, demonstrating state-of-the-art performance. DiffUCO uses an iterative sampling process to generate solutions, with the number of diffusion steps increasing during training to improve solution quality. The paper also introduces a more efficient sampling strategy, *Conditional Expectation* (CE), which, when combined with DiffUCO, allows for time-efficient generation of high-quality solutions. The method is shown to be highly efficient and general, making it a promising approach for data-free approximation of discrete distributions in various scientific fields.