Source-linked AI summary
Ising formulations of many NP problems
Andrew Lucas
TL;DR
The paper addresses how to represent NP-complete and NP-hard problems as Ising models for adiabatic quantum optimization. It develops mappings across partitioning, covering, satisfiability, and other problem classes, including all of Karp’s 21 NP-complete problems. The constructions use at most cubicly many spins, while their practical usefulness remains an open question because hardware embedding can require substantial connectivity and energy-scale control.
Problem
Adiabatic quantum optimization requires Ising Hamiltonians whose ground states encode solutions to many NP-complete and NP-hard problems.
Method
The paper develops Ising-spin-glass mappings for a wide range of NP problems, using constraint penalties, auxiliary spins, and constructions for all of Karp’s 21 NP-complete problems.
Results
The presented formulations require at most cubicly many spins in the problem size and include mappings for partitioning, covering, satisfiability, and other NP problems.
Takeaways & Limitations
The mappings provide candidate Hamiltonians for experimental AQO studies, but whether AQO yields efficient exact or approximate solutions remains open.
Takeaways & Limitations
Experimental use is constrained by ancilla overhead, required energy-scale separations, and the difficulty of embedding highly connected Hamiltonians on available hardware.
Abstract
from arXiv · showhide
We provide Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems. This collects and extends mappings to the Ising model from partitioning, covering and satisfiability. In each case, the required number of spins is at most cubic in the size of the problem. This work may be useful in designing adiabatic quantum optimization algorithms.
1. Introduction
The paper motivates mapping NP-complete and NP-hard problems to Ising Hamiltonians for adiabatic quantum optimization, while emphasizing embedding costs and unresolved efficiency questions.
- 1.1. Quantum Adiabatic Optimization: AQO encodes a problem’s solution in the ground state of a problem Hamiltonian and reaches it by adiabatically evolving from an easy ground state.The final measurement returns a problem solution when the evolution is sufficiently slow and the endpoint Hamiltonians do not commute.
- 1.1. Quantum Adiabatic Optimization: Exponential energy-gap constraints may make exact AQO solutions difficult, although smaller exponents could still permit advantages on some problem classes.The relevant runtime scaling is tied to avoiding Landau-Zener transitions into excited states.
- 1.3. The Goal of This Paper: The paper maps NP problems to Ising spin glasses, using pseudo-Boolean formulations and gadgets to reduce higher-order interactions to pairwise Ising terms.The authors distinguish decision problems from optimization problems and generally focus on the latter.
- 1.4. What Problems Are Easy (to Embed) on Experimental AQO Devices?: Experimental embeddings must be assessed by ancilla count, energy-scale separation, and connectivity, because these can dominate implementation difficulty.Ancilla spins enforce constraints, while highly connected graphs and large coupling ratios are difficult to encode on restricted hardware.
2. Partitioning Problems
The paper expresses partitioning and clique problems as Ising models, showing how ground states encode feasible or optimal solutions and how auxiliary-spin tricks reduce overhead.
- 2.1. Number Partitioning: Number partitioning asks whether positive numbers can be divided into two equal-sum subsets, an NP-complete problem represented directly with Ising spins.The two spin signs identify the two subsets, and zero ground-state energy corresponds to an exact partition.
- 2.1. Number Partitioning: If exact partitioning is impossible, the same Hamiltonian finds a ground state minimizing the mismatch, thereby solving the NP-hard optimization version.No additional construction is required to move from the decision to the optimization formulation.
- 2.2. Graph Partitioning: Graph partitioning assigns spins to vertices and penalizes both unequal subset sizes and edges crossing between the two subsets.The coupling scale must preserve the equal-size constraint while optimizing the number of crossing edges.
- 2.2. Graph Partitioning: N spins on a complete graph encode graph partitioning, with one spin removable by fixing a vertex under the model’s gauge symmetry.The supplied passages state the complete-graph requirement and the gauge-based reduction separately.
- 2.4. Reducing N to log N Spins in Some Constraints: N+1+⌊log ∆⌋ spins suffice for the NP-hard clique problem when an auxiliary-spin trick reduces the number of added y spins.The trick recurs throughout the paper’s constructions and is recommended for computational encodings.
3. Binary Integer Linear Programming
The paper constructs an Ising Hamiltonian for binary integer linear programming by combining constraint-penalty and objective terms, with coefficient scales chosen to preserve feasibility.
- 3. Binary Integer Linear Programming: Binary integer linear programming maximizes c · x over binary variables subject to a matrix constraint Sx = b.The formulation is NP-hard and includes applications such as profit maximization under regulatory constraints.
- 3. Binary Integer Linear Programming: The Hamiltonian H = HA+HB uses HA to enforce Sx = b in its ground states and HB to encode the objective.Positive constants A and B separate constraint enforcement from objective optimization.
- 3. Binary Integer Linear Programming: The ratio A/B must be large enough that violating a constraint is less favorable than any possible objective improvement.The bound compares the smallest constraint-violation penalty with the largest objective gain.
- 3. Binary Integer Linear Programming: A/B ≳N when the coefficients ci and Sij are O(1) integers, using C ≤N max(ci) and S ≥1.This is the stated scaling bound under the supplied coefficient assumptions.
4. Covering and Packing Problems
The section maps covering, packing, satisfiability, and minimax matching problems to Ising Hamiltonians by enforcing exact constraints and optimizing valid configurations. It also highlights a previously unreported minimax matching formulation and connects satisfiability to maximum independent set.
- Covering and Packing: Covering and packing formulations encode exact constraints through Hamiltonian penalties, with additional energy terms selecting minimum covers or maximum disjoint families.For smallest exact cover, the ground state selects the fewest subsets; for set packing, B < A preserves disjointness while counting included sets.
- Exact Cover: For exact cover, HA = 0 means every element appears exactly once, and a zero-energy ground state exists exactly when a solution exists.The formulation uses N spins, one for each subset Vi.
- Set Packing and MIS: Set packing is isomorphic to maximal independent set when overlapping subsets become adjacent graph vertices, so the largest disjoint family is the largest independent set.The graph contains one vertex per subset and an edge whenever two subsets intersect.
- Satisfiability: 3SAT reduces to MIS on a graph of 3m nodes formed from clause triangles and consistency edges, with satisfiability equivalent to an independent set of size m.The optimization version of MIS also handles the NP-hard problem of minimizing violated clauses.
- Minimal Maximal Matching: The minimax matching Ising formulation is presented as new to the paper’s literature review and requires |E| = O(∆N) spins.The edge set determines the spin count, with ∆ denoting the graph’s maximal degree.
- Minimal Maximal Matching: The minimax matching Hamiltonian uses edge spins and three energy terms so valid configurations satisfy the constraints while minimizing the number of colored edges.Choosing C < B prevents violating earlier constraints, and each ground state corresponds to a minimax matching solution.
5. Problems with Inequalities
The paper converts inequality-constrained problems into equality-constrained Ising formulations by adding spins, then encodes set cover and knapsack with constraint and objective terms.
- Inequality constraints are rewritten as equality constraints by expanding the number of spins.
- Set Cover: Set cover selects the smallest number of subsets whose union equals U, without requiring elements to appear only once.Unlike exact cover, repeated coverage is allowed.
- Set Cover: Set-cover Hamiltonians use selection variables and auxiliary counting variables to enforce each element’s coverage count consistently.
- Set Cover: N + n⌊1 + log M⌋ spins encode set cover when M is the maximum number of sets containing any element.
- Knapsack: Knapsack maximizes total value subject to a weight limit, using auxiliary variables to represent the final weight and enforce consistency.The model uses H = HA + HB, with HA enforcing weight constraints and HB representing the objective.
- Knapsack: The knapsack formulation requires N + ⌊1 + log W⌋ spins, with 0 < B max(cα) < A preventing overweight solutions from being favored.
6. Coloring Problems
Coloring formulations represent vertex-color assignments with binary spins and penalize violations of assignment or adjacency constraints; clique cover uses a closely related construction.
- Potts-model coloring formulations can be converted to Ising models by expanding each multi-valued spin into multiple binary spins.
- Graph Coloring: Graph coloring assigns one of n colors to each vertex so adjacent vertices have different colors.
- Graph Coloring: Binary variables xv,i indicate whether vertex v has color i, while the Hamiltonian penalizes multiple colors per vertex and equal colors across edges.
- Graph Coloring: A zero-energy ground state exists exactly when the graph is colorable with n colors, using nN spins before symmetry reduction.
- Clique Cover: Clique cover asks whether each color class induces a complete graph.
- Clique Cover: The clique-cover Hamiltonian checks assignment constraints and whether each color class contains the maximum possible number of internal edges.
- Clique Cover: A zero-energy ground state solves clique cover, and the formulation uses nN spins.
7. Hamiltonian Cycles
Hamiltonian-cycle formulations encode vertex orderings with binary position variables, enforce unique placement and valid consecutive edges, and extend naturally to traveling salesman objectives.
- The Hamiltonian cycle problem asks whether a graph contains a cycle visiting every vertex exactly once and returning to its start.
- Hamiltonian Cycles: The formulation uses N^2 bits xv,i, where v identifies a vertex and i its position in a prospective cycle.
- Hamiltonian Cycles: Its energy enforces one occurrence per vertex, one vertex at every cycle position, and penalties for consecutive positions lacking an edge.
- Hamiltonian Cycles: A zero-energy ground state corresponds to a valid Hamiltonian cycle.
- Hamiltonian Paths: Hamiltonian paths use the same construction but omit the constraint connecting the final and first positions, requiring N^2 spins.
- Hamiltonian Cycles: Fixing node 1 as the first vertex reduces the Hamiltonian-cycle formulation to (N −1)^2 spins.
- Traveling Salesman: Traveling salesman adds edge weights to the Hamiltonian-cycle model and minimizes the total weight while retaining the cycle constraints.
8. Tree Problems
Tree problems require global connectivity information, so their Ising formulations use auxiliary depth, orientation, inclusion, and degree variables; the resulting spin counts can reach cubic order.
- Tree-subgraph formulations are subtle because determining whether a subgraph is a tree requires global connectivity information.
- Minimal Spanning Tree: Minimal spanning tree selects a minimum-cost spanning tree while imposing a maximum degree Δ constraint.
- Minimal Spanning Tree: The formulation uses edge-selection variables plus vertex depths, edge orientations, and degree-counting variables to encode tree structure.
- Minimal Spanning Tree: Choosing 0 < B max(cuv) < A preserves the structural constraints while the objective selects the minimum-cost degree-bounded spanning tree.
- Minimal Spanning Tree: |V |(⌊|V | + 1⌋+ 2)/2 + |E|(|V | + 1) + |V |⌊1 + log Δ⌋ spins are required, potentially reaching O(|V |^3).
- Steiner Tree: Steiner tree adapts the spanning-tree model by allowing vertices outside the required subset U to be excluded.
- Steiner Tree: The Steiner-tree formulation requires |V |(⌊|V | + 1⌋+ 4 + 2|E|)/2 + |E| spins.
- Feedback Vertex Set: Feedback vertex set removes a smallest vertex subset so the remaining directed graph is acyclic, using height variables to enforce increasing heights along edges.
9. Graph Isomorphisms
The paper formulates graph isomorphism as an Ising-model optimization using binary assignment variables, bijectivity constraints, and penalties for adjacency mismatches. A zero-energy ground state certifies an isomorphism, using N^2 spins.
- Problem: Graph isomorphism asks whether two equal-sized graphs can be relabeled to have identical adjacency matrices.The formulation restricts attention to graphs with N vertices and represents isomorphism through a permutation matrix.
- Ising formulation: Binary variables x_v,i indicate whether vertex v in G2 maps to vertex i in G1.The variables encode a proposed vertex correspondence.
- Ising formulation: A constraint energy enforces that the proposed vertex map is bijective.
- Ising formulation: A second energy penalizes mappings that disagree with the graphs' edge sets.It penalizes both edges present in G2 but absent in G1 and edges present in G1 but absent in G2.
- Result: N^2 spins are required, and a ground-state energy H = 0 indicates that the graphs are isomorphic.
- Related work: An earlier approximate quantum-annealing method distinguished non-isomorphic graphs using spectra of graph-dependent Hamiltonians.
10. Conclusions
The paper compiles Ising-spin-glass constructions for a wide variety of NP problems, including each of Karp’s 21 NP-complete problems, while emphasizing that AQO’s efficiency remains unresolved. It also cautions that apparent hardness may reflect encoding choices, instance distributions, or small spectral gaps.
- Conclusions: The paper presents Ising-spin-glass mappings for a wide variety of NP problems, including all of Karp’s 21 NP-complete problems.
- Conclusions: Universal quantum computers could accelerate some easy problems, but whether Ising-based AQO can outperform classical polynomial-time algorithms remains unclear.The paper notes that this possibility is not obvious for hardware implementing Ising models.
- Conclusions: An Ising encoding can represent finding the largest integer in a list, although the task has an O(N) classical algorithm.The paper states that programming this instance into a quantum device would take longer than solving it classically.
- Hardness caveats: NP-completeness does not imply that typical instances are difficult, since many popular NP problems can be solved exactly in polynomial time on large random instances.The text also describes randomized algorithms that approach solutions with arbitrarily low failure probability in polynomial time, with diverging coefficients or exponents as error probabilities tend to zero.
- Limitations: The proposed Hamiltonians may appear hard because they use too many spins or have small spectral gaps, issues the paper does not resolve.The paper identifies increasing energy gaps as a needed direction because larger gaps can reduce the required runtime T.