{"id":"arxiv/2608.14941","url":"https://arxiv.org/abs/2608.14941","tags":["cs.LG","quant-ph"],"score":0,"title":"Degeneracy Counting Quantum Algorithm using Decoherence","domain":"cs.LG","source":"arxiv","authors":["Malay Marut Das","Mark A. Novotny","Yaroslav Koshka"],"reviews":0,"subject":"cs.LG","summary":"Counting the global optima of a classical optimization problem is a #P-hard task. We develop the canonical thermal pure quantum (CTPQ) state-based degeneracy counting (CTPQsd#) algorithm that determines the number of global optima of a classical optimization problem P by measuring only a small probe S, without finding individual minima. The method exploits a perturbative relation between the decoherence measure of S and the degeneracy of P when S and P are together in a CTPQ state. We provide the first numerical demonstration that this relation can be used to count the global minima,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-14","reactions":{}}