A quantum graph-coloring framework with log-color encoding and a QFT-based mixer is presented; its chromatic-number term is flawed because label-sum minimization does not imply color-count minimization.
Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We discuss several mappings from well-known NP-hard problems to Quadratic Unconstrained Binary Optimisation problems which are treated incorrectly by Lucas. We provide counterexamples and correct the mappings. We also extend the body of QUBO formulations of NP-complete and NP-hard optimisation problems by discussing additional problems.
fields
quant-ph 1years
2026 1verdicts
REJECT 1representative citing papers
citing papers explorer
-
A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation
A quantum graph-coloring framework with log-color encoding and a QFT-based mixer is presented; its chromatic-number term is flawed because label-sum minimization does not imply color-count minimization.