Concept record · edition 0.1.0
QUBO and Ising models
Quadratic unconstrained binary optimization, and its equivalent spin form in which binary variables become ±1 spins with couplings and local fields.
Why it matters
It is the shared encoding target for quantum annealers, QAOA, and tensor-network optimizers, which is what makes them comparable at all.
What this does not establish
A shared encoding does not imply comparable performance, and the encoding step being exact says nothing about the resulting instance being tractable.
Claims using this concept
- tn-007 · Established resultQuadratic unconstrained binary optimization problems map exactly onto Ising spin models, and explicit Ising formulations exist for a catalogue of NP-hard problems.
- tn-012 · Active researchTensor-network methods have been applied to dynamic portfolio optimization on real datasets alongside quantum processors, but the reported work does not establish a general advantage.
- tn-013 · Active researchWhether QAOA delivers a practical advantage over strong classical baselines on real optimization instances remains unresolved.
Sources
primary paper · identifier verified
Ising formulations of many NP problems
Andrew Lucas · 2013
arXiv:1302.5843
Catalogues explicit Ising encodings for NP-hard problems — the step that turns a combinatorial problem into a spin model a tensor network can act on.
Source record →