Algorithms · Optimization · Ising encoding
Ising formulations of NP-complete and NP-hard problems
Given a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all.
Attested & literatureUpdated
- Record typeLiterature reference
- Reference implementationtraveling_salesman_problem
- Reported costAt most cubic in the size of the problem, counted in spins — an encoding size, not a running time. No speedup is claimed: the abstract states no time to solution, no query or gate count and no comparison with classical solvers, and its only forward-looking statement is that the work may be useful in designing adiabatic quantum optimization algorithms.
- Papers1
This record, used inside a worked example
This page says mappings to the Ising model
— here is a concrete, runnable instance of it.
QAOA, p=1, MaxCut on a 4-cycle
4 qubits on a 4-cycle (edges 0-1, 1-2, 2-3, 3-0), one QAOA layer with gamma=pi/8, beta=3*pi/8.
Where it ends up
- 010127%
- 101027%
- 00118%
- 01108%
- 12 more outcomes31%
0101 and 1010 are the two optimal cuts of a 4-cycle (alternating around the ring); at these angles measuring the register returns one of them clearly more often than any other cut.
Open that example in StudioThis record, used inside a worked example
This page says an Ising Hamiltonian whose ground states are the problem's solutions
— here is a concrete, runnable instance of it.
VQE on a 2-qubit transverse-field Ising Hamiltonian
2 qubits, H = Z⊗Z + 0.5*(X⊗I + I⊗X), a stated toy Hamiltonian (not a molecule), minimised with a hardware-efficient ansatz.
Where it ends up
- 1043%
- 0143%
- 007%
- 117%
At these angles the ansatz's energy ⟨H⟩ reaches E0 = −√2, the Hamiltonian's exact ground energy; a real VQE run reaches these angles by repeating measure-the-energy then update-the-angles, not by a closed-form solution.
Open that example in StudioGiven a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all. An Ising formulation restates a combinatorial problem in the language of ±1 spins: the problem's degrees of freedom become spins, and its constraints and objective are carried by the couplings and fields of an Ising Hamiltonian whose ground states are the problem's solutions. The paper provides such formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems, collecting and extending mappings to the Ising model from partitioning, covering and satisfiability. It reports that in each case the required number of spins is at most cubic in the size of the problem, so the encoding itself stays polynomial across the problems it covers. The stated purpose is downstream of the encoding: the author writes that the work may be useful in designing adiabatic quantum optimization algorithms, which makes the formulation the input such an algorithm consumes rather than an algorithm in its own right.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
An Ising formulation restates a combinatorial problem in the language of ±1 spins: the problem's degrees of freedom become spins, and its constraints and objective are carried by the couplings and fields of an Ising Hamiltonian whose ground states are the problem's solutions. The paper provides such formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems, collecting and extending mappings to the Ising model from partitioning, covering and satisfiability. It reports that in each case the required number of spins is at most cubic in the size of the problem, so the encoding itself stays polynomial across the problems it covers. The stated purpose is downstream of the encoding: the author writes that the work may be useful in designing adiabatic quantum optimization algorithms, which makes the formulation the input such an algorithm consumes rather than an algorithm in its own right. Reported cost: At most cubic in the size of the problem, counted in spins — an encoding size, not a running time. No speedup is claimed: the abstract states no time to solution, no query or gate count and no comparison with classical solvers, and its only forward-looking statement is that the work may be useful in designing adiabatic quantum optimization algorithms..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Reference implementation
- traveling_salesman_problem
- Reported cost
- At most cubic in the size of the problem, counted in spins — an encoding size, not a running time. No speedup is claimed: the abstract states no time to solution, no query or gate count and no comparison with classical solvers, and its only forward-looking statement is that the work may be useful in designing adiabatic quantum optimization algorithms.
- Complexity basis
- abstract of arXiv:1302.5843: "In each case, the required number of spins is at most cubic in the size of the problem." The scope of "each case" is set by the preceding clause, "Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems". The same abstract states no running time and no classical comparison; its closing claim is "This work may be useful in designing adiabatic quantum optimization algorithms." The demonstration this record covers states no complexity bound of its own.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Optimization · Ising encoding with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Ising formulations of NP-complete and NP-hard problems
PROBLEM: Given a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all.
IDEA: An Ising formulation restates a combinatorial problem in the language of ±1 spins: the problem's degrees of freedom become spins, and its constraints and objective are carried by the couplings and fields of an Ising Hamiltonian whose ground states are the problem's solutions. The paper provides such formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems, collecting and extending mappings to the Ising model from partitioning, covering and satisfiability. It reports that in each case the required number of spins is at most cubic in the size of the problem, so the encoding itself stays polynomial across the problems it covers. The stated purpose is downstream of the encoding: the author writes that the work may be useful in designing adiabatic quantum optimization algorithms, which makes the formulation the input such an algorithm consumes rather than an algorithm in its own right.
REPORTED COST: At most cubic in the size of the problem, counted in spins — an encoding size, not a running time. No speedup is claimed: the abstract states no time to solution, no query or gate count and no comparison with classical solvers, and its only forward-looking statement is that the work may be useful in designing adiabatic quantum optimization algorithms.
BASIS: abstract of arXiv:1302.5843: "In each case, the required number of spins is at most cubic in the size of the problem." The scope of "each case" is set by the preceding clause, "Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems". The same abstract states no running time and no classical comparison; its closing claim is "This work may be useful in designing adiabatic quantum optimization algorithms." The demonstration this record covers states no complexity bound of its own.
PRIMARY SOURCE: Andrew Lucas (2013), Ising formulations of many NP problems — https://arxiv.org/abs/1302.5843
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- QAOA MaxCut on a 5-node ring
Algorithms
- Quantum adiabatic evolution
Algorithms
- Quantum simulated annealing
Algorithms
- QUBO operator mapping
Operators
References
- Ising formulations of many NP problems
Andrew Lucas · 2013
Primary source. It collects and extends mappings to the Ising model from partitioning, covering and satisfiability into formulations for many NP-complete and NP-hard problems, including all of Karp's 21, and states that the required number of spins is at most cubic in the size of the problem in every case. Consult it for the individual constructions, their penalty terms and weights, and for which problems it treats: the abstract names them only as a class.