Pith. sign in

REVIEW 1 cited by

Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1911.08043 v4 pith:X5I3AJ4I submitted 2019-11-18 cs.DS cond-mat.stat-mechcs.CCquant-ph

Bas Lodewijks This is my paper · ORCID
classification cs.DScond-mat.stat-mechcs.CCquant-ph
keywords problemsoptimisationnp-hardbinarymappingsnp-completequadraticunconstrained
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation

    quant-ph 2026-08 reject novelty 3.0 of 10

    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.

Pith tools