PaperlayerView exact revision on arXiv

Source-linked AI summary

Standard Quadratic Formulations of Many NP Problems: A Simplex-Based Compilation Framework for Combinatorial Optimization

Mohammad-Ali Miri, Babak Emami, PoJen Wang

arXiv:2610.01911v1cs.ET

TL;DR

Discrete optimization is commonly compiled to binary interactions, while simplex-native states use normalized nonnegative coordinates. This paper compiles discrete problems through clique and compatibility formulations, catalogs their representation trade-offs, and identifies limits such as local minima for every complete factor-state assignment.

  • Problem

    Binary interaction formulations are a common target, but a device with a normalized nonnegative state may need a more direct interface; binary conversion can incur encoding-dependent costs.

    Source: §1 · p. 4

  • Method

    The paper composes clique formulations with compatibility graphs and factor-state constructions to encode discrete problems as quadratic optimization over a normalized nonnegative state.

    Source: §1 · p. 4, §12 · p. 43

  • Results

    The catalog covers 21 of Karp’s problems, while its representation analysis finds that direct graph routes have simple coefficients and support decoding, whereas generic factor-state routes can expand dimension and make every complete assignment a strict local minimum.

    Source: §12 · p. 43

  • Takeaways & Limitations

    A returned local minimum in the graph formulation has a maximal-clique support whose objective reports that clique’s size, making the landscape a controlled diagnostic as well as an optimization challenge.

    Source: §3.4 · p. 11

    In the complete factor-state construction, every assignment, including infeasible or suboptimal ones, is a strict local minimum, so local minima do not filter them out.

    Source: §5.2 · p. 18

Abstract

from arXiv · show

The standard quadratic program (StQP) minimizes a quadratic form over nonnegative variables that sum to one. We compose classical graph reductions with regularized Motzkin--Straus clique formulations to express discrete optimization problems in this continuous domain. The graph matrix has diagonal entries $\tau$, zeros on edges, and ones on nonedges. For $0<\tau<1$, its minimum is $\tau/\omega(G)$, where $\omega(G)$ is the clique number. Its strict local minimizers are precisely the uniform distributions on maximal cliques, and its global minimizers encode maximum cliques. At $\tau=1/2$, integer scaling gives coefficients in $\{0,1,2\}$ and minimum $1/\omega(G)$, yielding an NP-complete StQP threshold problem with a restricted coefficient alphabet. We give explicit formulations for satisfiability, coloring, Hamiltonian cycles, independent set, vertex cover, set packing, three-dimensional matching, and graph isomorphism. A regularized weighted clique formulation combined with local-state compatibility graphs gives an exact compiler for finite-domain factor models specified by complete local tables, including QUBO, with at most four simplex coordinates per binary pair factor. The catalog covers Karp's 21 problems: twelve use direct graph formulations, and nine use factor-state formulations, including six obtained through binary-linear feasibility. For each route we record dimensions, coefficient structure, and recovery rules. We analyze interaction count, coefficient range, objective separation, perturbation tolerance, support recovery, and decoding overhead. The separation bounds quantify the effects of clique size, factor weights, and offsets. In the complete factor-state construction, every assignment, including each suboptimal assignment, is a strict local minimum.

1 Introduction

The paper develops a simplex-based alternative to binary optimization encodings, compiling discrete problems through clique formulations and compatibility graphs. It catalogs direct and generic routes while analyzing their representation costs and computational scope.

1 Introduction

  • A standard quadratic program optimizes a quadratic form over a continuous, nonnegative, normalized state whose coordinates represent pairwise interactions.The paper contrasts this single-simplex interface with binary encodings, whose conversion costs depend on the encoding.Source: §1 · p. 4
  • Normalization turns positive cross terms between incompatible choices into penalties, while a three-level matrix makes maximum-clique barycenters globally optimal.The matrix encodes incompatible pairs, and diagonal terms control mass concentration on compatible supports.Source: §1 · p. 4

1.1 Scope and contributions

  • The catalog covers Karp’s 21 problems: 12 use direct graph routes and nine use factor-state formulations, including six through binary-linear feasibility.Entries specify route, dimension or encoding-bit count, recovery rule, and principal representation cost.Source: §1.1 · p. 4
  • Complete rational factor tables yield a polynomial-time factor-state construction; binary models use at most 2nu + 4m simplex coordinates for nu unary and m pair factors.The construction provides exact recovery, but every complete assignment is a strict local minimum.Source: §1.1 · pp. 4–5

1.2 Relation to prior work

  • The paper builds on established clique formulations and compatibility constructions, presenting explicit matrices and thresholds rather than claiming new representability results for direct routes.The catalog is distinguished by its explicit decoding and representation-cost analysis, not by a new optimizer architecture or solver-performance result.Source: §1.2 · p. 5

1.3 Computational scope

  • The formulations characterize landscapes but do not establish solver convergence rates, success probabilities, robust analog behavior, or quantum advantage.The paper states that exact encoding is not an efficient solution method unless P = NP.Source: §1.3 · p. 5

2.1 The standard quadratic program

  • The paper distinguishes decision, value, solution, and landscape exactness, and tracks dimensions, interactions, coefficient range, objective separation, perturbation tolerance, support recovery, and decoding.Its encoding definition pairs a polynomial-time instance map with a decoder that recovers the desired answer from the optimum value, a global minimizer, or both.Source: §2.1 · p. 6, §2.2 · p. 7

2.4 Compilation pipeline

  • Compilation routes either preserve problem structure with simpler matrices or trade compactness for the universality of generic routes.The paper also distinguishes literal interactions from relative interactions after removing a redundant all-ones baseline.Source: §2.4 · p. 7, §2.2 · p. 7

3 A three-level graph-to-StQP compiler

A three-level graph matrix converts clique structure into the global and local minima of a simplex quadratic program. The paper also derives a restricted NP-complete threshold, precision bounds, landscape implications, and an equivalent relative-coupling form.

3.1 The graph matrix

  • For 0 < tau < 1, global minimizers are exactly maximum-clique barycenters, while every maximal-clique barycenter is a strict, isolated local minimizer.The minimum value is tau/omega(G); without regularization at tau = 1, the exact local-minimum correspondence can fail.Source: §3.1 · pp. 8–9

3.3 Objective separation and perturbation tolerance

  • For adjacent clique sizes k and k - 1, the integer-scaled matrix has objective separation 1/[k(k - 1)], and support coordinates equal 1/k.A midpoint threshold tolerates entrywise perturbations below g_k(tau)/2; coordinate noise substantially below 1/(2k) permits threshold decoding.Source: §3.3 · p. 10

3.4 Landscape interpretation

  • The local minima encode maximal cliques, so graphs with exponentially many maximal cliques can produce exponentially many local minima.This landscape is difficult for exact optimization but useful diagnostically: each returned local minimum identifies a maximal clique, and its value reports that clique’s size.Source: §3.4 · p. 11

3.5 Relative couplings

  • Removing the all-ones term shifts feasible objective values by a constant without changing minimizers, allowing implementation through relative edge and diagonal interactions.The relative and nonnegative formulations are equivalent but can have different implementation costs.Source: §3.5 · p. 11

4 Compatibility graphs for constraint satisfaction and assignment

Compatibility graphs encode discrete choices as vertices and pairwise consistency as adjacency; a clique selecting the required choices yields a simplex formulation. The section applies this construction to finite-domain constraints, SAT, coloring, tours, isomorphism, and explicit allowed tuples.

4 Compatibility graphs for constraint satisfaction and assignment

  • A compatibility graph makes pairwise consistency a clique condition, and the graph-to-StQP theorem converts that condition into a simplex quadratic.For grouped choices, same-group vertices are nonadjacent, so a clique of size equal to the number of groups selects one choice per group.Source: §4 · p. 11

4.1 Finite-domain constraint satisfaction

  • A finite-domain binary CSP is satisfiable exactly when its variable-value compatibility graph has a clique of size n, which decodes to one satisfying value per variable.The graph has a vertex for each variable-value pair, with adjacency enforcing linked constraints.Source: §4.1 · pp. 11–12

4.2 CNF satisfiability

  • A CNF formula is satisfiable exactly when its clause-literal graph has a clique of size m; the construction uses N_lit coordinates, at most 3m for 3-SAT.A global solution decodes by selecting one mutually consistent literal occurrence per clause; a local minimum may omit clauses and need not certify satisfiability.Source: §4.2 · p. 12

4.3 Graph coloring and clique cover

  • A graph is k-colorable exactly when its compatibility graph has a clique of size |V|, using k|V| coordinates to select one color per vertex.The same construction gives a clique-cover formulation by applying it to the complement graph.Source: §4.3 · p. 13

4.4 Hamiltonian cycles

  • A directed graph has a Hamiltonian cycle exactly when its position-vertex compatibility graph has a clique of size n, using n^2 coordinates.Compatibility enforces distinct positions and vertices, plus graph edges between consecutive tour positions; nonconsecutive positions have no edge condition.Source: §4.4 · p. 13

4.5 Graph isomorphism and association graphs

  • Two n-vertex graphs are isomorphic exactly when their association graph has a clique of size n, equivalently an StQP optimum of 1/n, using n^2 coordinates.The construction also extends to subgraph isomorphism and maximum common induced subgraph formulations.Source: §4.5 · p. 14

4.6 Arbitrary-arity hard constraints

  • For arbitrary-arity constraints, vertices represent allowed tuples and edges join tuples agreeing on shared variables; a clique with one tuple per constraint encodes a consistent assignment.The construction is polynomial in the explicit tuple list, but expanding succinct high-arity constraints can require exponentially many tuples.Source: §4.6 · p. 14

5 Weighted clique and a generic factor-state compiler

This section extends the clique-based StQP framework to positive vertex weights and finite-domain factor objectives via weighted compatibility graphs. It gives exactness and structural guarantees, approximation results for decoding the positive transformed objective, and separation bounds that support decision and decoding under stated conditions, with original-energy guarantees depending on offsets.

5.1 A weighted clique StQP theorem

  • Weighted clique StQP minimizers correspond to maximum-weight cliques, while every local minimizer is a strict weighted barycenter of a maximal clique.The number of strict local minimizers equals the number of maximal cliques, independently of the positive vertex weights.Source: §5.1 · pp. 15–16

5.2 Finite-domain factor models

  • Under complete local-state tables, the factor-state compatibility graph exactly compiles finite-domain objectives, and every global minimizer decodes to an optimal assignment.Maximum-weight cliques contain one consistent state per factor and have weight B − E(z); the simplex dimension is specified in the theorem.Source: §5.2 · pp. 17–18
  • Every assignment becomes a strict local minimum, so the compiled landscape does not filter infeasible or suboptimal configurations; pruning states can also invalidate exactness.Completeness can be relaxed when every shared-variable assignment extends to a retained factor state; hard constraints can instead be represented by penalties.Source: §5.2 · p. 18

5.3 Sparsity of the incompatibility matrix

  • With bounded domain sizes, factor arity, and variable incidence, the incompatibility matrix has O(N∆) nonzeros and maximum degree O(1).Without a bound on local-state counts, even a unary factor can create a dense incompatibility block.Source: §5.3 · p. 19

5.4 QUBO as a special case

  • A QUBO with nu unary factors and m nonzero pair factors has an exact weighted StQP encoding, using O(n^2) coordinates when dense and O(n + m) when sparse.Its off-diagonal coefficient alphabet remains {0, 1}, while objective values appear in positive diagonal entries.Source: §5.4 · p. 19

5.5 Worked example: weighted Max-Cut

  • The weighted Max-Cut construction assigns four local states to each edge and uses exactly 4|E| simplex coordinates before optional preprocessing.Compatible edge states agree on shared endpoints, and a full consistent clique represents a cut assignment.Source: §5.5 · p. 20

5.6 Approximation distortion

  • For a feasible simplex point evaluated with the intended matrix, purification and clique-face minimization yield a decoded assignment with E⋆ ≤ E(z) ≤ bE.The stated additive gap is 0 ≤ E(z) − E⋆ ≤ τwminδ/[ν(ν + δ)]; this guarantee does not automatically extend to decoders that may increase the StQP objective.Source: §5.6 · pp. 20–21
  • Offsets determine additive and multiplicative guarantees for the original energy, even though the route preserves ratios for B − E.Restoring an omitted constant c in c + E(z) changes neither the assignment nor additive suboptimality; coefficient and evaluation errors are separate.Source: §5.6 · p. 21

5.7 Objective separation

  • For integer-valued factor tables, distinct assignment values have separation at local minima; the relative gap is at least 1/(W − 1) when W ≥ 2.This does not separate the global minimum from every other feasible simplex point. The bound is exact when a maximal clique has weight W − 1; otherwise the gap is larger.Source: §5.7 · pp. 21–22
  • For decision threshold E⋆ ≤ T, gK = τwmin/[K(K−1)] separates the possible optimum-value classes, and midpoint testing is valid below gK/2 total error.The total error is the sum of the entrywise coefficient-error bound and the two-sided optimal-value estimation error; a feasible value without a suboptimality bound is insufficient.Source: §5.7 · p. 22
  • Objective-nonincreasing decoding recovers an optimal assignment when r + 2ϵ < gW under the stated uniform perturbation bound.A valid gW,∆E can replace gW; more generally, a known energy spacing ∆E yields a bound exact when the next assignment level is attained and invariant to common positive scaling.Source: §5.7 · pp. 21–22
  • A common integer slack η gives wmin = η and W = D + Fη; increasing η improves coefficient range but eventually reduces the unit-step separation bound.The coefficient-range ratio is wmax/wmin = 1 + Rmax/η; when a nonedge entry equals one, κcoef = (η + Rmax)/(τη), otherwise this is an upper bound.Source: §5.7 · pp. 22–23
  • For hard constraints with a feasible assignment, P > Ssoft suffices; for integer soft-factor data, P = Ssoft + 1 meets that condition.Increasing P after feasibility is ensured leaves the feasible optimum unchanged but can increase Φ, D, and coefficient range, affecting the separation bound.Source: §5.7 · p. 23

6 Selection, packing, covering, and matching formulations

The section compiles selection and coverage problems through clique formulations, using direct compatibility graphs when feasible and weighted graphs or factor-state and binary-linear routes for collective constraints.

6.1 Clique, independent set, and vertex cover

  • Clique, independent-set, and vertex-cover formulations use n simplex coordinates and no auxiliary variables.Independent set is clique in the complement; a vertex cover of size at most k corresponds to an independent set of size at least n − k.Source: §6.1 · p. 23

6.2 Set packing

  • A set-packing instance becomes a disjointness graph, where cliques are pairwise disjoint subfamilies and a packing of at least k sets is equivalent to StQP optimum at most 1/k.The formulation uses m simplex coordinates; positive set weights extend it to weighted packing.Source: §6.2 · p. 23

6.3 Three-dimensional matching

  • Three-dimensional matching becomes clique selection among triples disjoint in all three coordinates, using |T| simplex coordinates.For equal-sized X, Y, and Z, the cited proposition gives a corresponding perfect-matching criterion.Source: §6.3 · p. 24

6.4 Exact cover through weighted clique

  • Exact cover uses a weighted disjointness graph: a clique’s weight is the size of its union, and a clique-supported minimizer decodes to an exact-cover subfamily.The construction assigns each set its cardinality as weight; the proposition states the exact-cover criterion.Source: §6.4 · p. 24

6.5 Hitting set and set cover

  • Karp’s hitting set is represented by a weighted graph on elements, with weights equal to incidence counts; a solution exists exactly when the maximum clique weight is m.Elements occurring in no constraint are discarded, and edges join pairs that never occur together in a constraint.Source: §6.5 · p. 25
  • Set cover and the Garey–Johnson hitting-set variant need collective-coverage encodings, via binary-linear feasibility or local-state factors that encode infeasible patterns as high-cost states.A degree-d factor has 2d local states, none deletable; binary-linear compilation remains polynomial in the ordinary bit model and is preferred for unbounded incidence.Source: §6.5 · p. 25

6.6 Dominant sets and weighted graph structure

  • For dominant sets, the simplex quadratic is the graph model itself rather than a reduction from a discrete NP problem.The passage places this native continuous graph-model use alongside exact combinatorial encodings as an application of the same StQP hardware primitive.Source: §6.6 · p. 25

7 A generic binary-linear feasibility compiler

The generic compiler turns binary-linear feasibility into a zero-penalty QUBO and then an StQP threshold instance. The section also accounts for size and precision, and gives representative encodings for numerical, scheduling, and graph problems.

7 A generic binary-linear feasibility compiler

  • Direct graph formulations are preferred when available; the generic route supplies a polynomial route from binary-linear feasibility for problems with polynomial-size 0–1 integer-programming formulations.The route also provides a uniform compiler for remaining members of Karp’s list.Source: §7 · p. 25

7.1 From inequalities to a zero-penalty QUBO

  • A binary-linear system is encoded by squared residuals whose zero value characterizes feasibility, yielding a QUBO and then a polynomial-size StQP threshold encoding.Rational data can be scaled to integers with polynomial bit-length growth; infeasible rows with negative slack upper bound can be rejected immediately.Source: §7.1 · p. 26

7.2 Size accounting

  • The factor-state compiler’s coordinate bound is polynomial in input length because slack-bit counts are logarithmic in encoded integers, though the stated bound is intentionally simple rather than tight.Factor aggregation, quadratization reuse, and direct CSP constructions can reduce it.Source: §7.2 · p. 26

7.3 Adding an objective or decision threshold

  • Optimization objectives can be handled by repeated feasibility thresholds or by adding a sufficiently dominant feasibility penalty to one QUBO.For integer objectives, the threshold sequence takes O(log(2 + Σ|ci|)) StQP solves after feasibility is checked.Source: §7.3 · p. 27

7.4 Precision of the binary-linear route

  • Residual-square coefficients depend on input numbers, and precision bounds depend on factorization, offsets, and attainable energy spacings; integer magnitudes alone do not determine the physical precision burden.An alternative 3-SAT route gives separation at least 1/[m(m −1)] for m ≥2 clauses, while the residual-square route can have bounds exponentially small in input bit length.Source: §7.4 · p. 27

7.5 Representative constructions

  • Representative encodings cover subset sum, partition, set cover, hitting set, job sequencing, feedback arc and vertex sets, and Steiner tree, with size bounds depending on their variables, constraints, and numerical ranges.Feedback arc set and feedback vertex set use Θ((n + |E|) log n) bits; Steiner tree uses |E| + O(|E| log |R|) + ⌈log2(K + 1)⌉ bits. These are standard integer-programming patterns, not claims of novel polyhedral strength.Source: §7.5 · p. 28
  • The feedback-arc and feedback-vertex formulations each use Θ((n + |E|) log n) bits, while the Steiner-tree encoding uses |E| + O(|E| log |R|) + ⌈log2(K + 1)⌉ bits.The constructions use an order for acyclicity and binary-encoded directed flow for Steiner connectivity.Source: §7.5 · pp. 28–29

8 A catalog for Karp’s 21 NP-complete problems

The catalog assigns StQP routes and recovery rules to Karp’s 21 problems, combining direct graph formulations with weighted and generic factor-state routes. It compares their representation costs and explains how objective thresholds recover decision answers.

8 A catalog for Karp’s 21 NP-complete problems

  • The catalog covers Karp’s 21 problems through several routes: ten numbered rows use unweighted compatibility graphs, two use weighted graphs, and six use binary-linear feasibility followed by residual-square QUBO and factor-state compilation.Knapsack and Partition start from residual-square QUBOs, Max-Cut uses factor states directly, and primed rows are excluded from these counts.Source: §8 · p. 29

8.1 Direct versus generic routes

  • Direct graph routes suit pairwise-compatible selections, weighted graphs suit exact cover and related weighted choices, and binary-linear or local-state routes handle collective constraints.Generic binary-linear bounds are polynomial but not necessarily optimal; local-state encodings can expand succinct high-arity constraints exponentially, and either representation may be too large or numerically demanding for a device.Source: §8 · p. 30, §8.1 · p. 34

8.2 Threshold normalization

  • For direct graph decision problems with ω(H) ≤ K, feasibility is equivalent to StQP optimum τ/K, or 1/K after integer scaling at τ = 1/2.The threshold rule gives a direct recovery criterion for SAT, coloring, and Hamiltonian cycle.Source: §8.2 · p. 34

9 Representation cost and comparison with QUBO/Ising

Section 9 compares simplex and binary formulations through state semantics, coefficients, connectivity, dimension, precision, landscapes, and decoding. Their practical trade-offs depend on the formulation and implementation; neither representation dominates uniformly.

9.1 State semantics

  • A QUBO state is binary, while an StQP state is normalized and continuous; approximate StQP readout requires feasibility and support tolerances.In graph-coded StQP, the discrete choice is encoded by the support, and normalized magnitudes are determined analytically.Source: §9.1 · p. 35

9.2 Coefficient structure

  • The integer graph compiler uses coefficients {0, 1, 2} without instance-dependent penalties, but its decision-value separation shrinks with target support size.Zero marks compatibility, one the diagonal concentration term, and two incompatibility.Source: §9.2 · p. 35

9.3 Connectivity and baseline removal

  • Table 2 reports representative formulation-level sizes excluding hardware embedding auxiliaries; factor-state interaction degree stays bounded when domain sizes, arity, and incidence are bounded.One-hot QUBO may add dense penalty blocks, while domain-wall encoding changes the penalty connectivity.Source: §9.3 · pp. 35–36, Table 2 · p. 36

9.4 Dimension

  • The basic factor-state compiler expands local configurations, whereas clique, set-packing, and exact-cover formulations can use one coordinate per original candidate.For factor-state matrices, coefficient ranges depend on the weights and whether unit nonedge entries occur.Source: §9.4 · p. 36

9.5 Precision and dynamic range

  • Clique-size separation decreases with target size, and weighted coefficient range depends on weight ratios; objective accuracy and support recovery therefore need separate checks.The paper recommends reporting coefficient precision and error, objective-estimation error, feasibility error, support threshold and stability, and the relevant separation.Source: §9.5 · p. 37

9.6 Landscape and local solvers

  • Maximal cliques are strict local minima for graph formulations, whereas every complete factor-state assignment is a strict local minimum, so factor-state descent does not filter assignments.Stationarity alone is insufficient: the two-vertex edgeless example has a stationary point that is a strict maximum.Source: §9.6 · p. 37

9.7 Decoding and verification

  • Ranking coordinates and greedily extending a compatible support is heuristic; the stated guarantees require objective-nonincreasing purification, face minimization, and extension.Weighted factor-state decoding repairs consistency across shared variables and locally reoptimizes conflicting factors.Source: §9.7 · p. 38

9.8 Summary of representation costs

  • Factor-state expansion can make the model substantially larger than direct QUBO, while the case for StQP depends on native-state alignment and device-specific precision, readout, and search costs.The formulations do not establish a universally superior model.Source: §9.8 · p. 38

10 A hardware-neutral simplex quadratic optimizer/annealer

Section 10 specifies a hardware-neutral interface for a simplex quadratic optimizer or annealer, including its inputs, state, energy, search, outputs, and evaluation. It proposes a restricted graph-coded target but does not establish hardware advantage or solver performance.

10.1 Input contract

  • The logical input is a symmetric matrix with onsite terms, programmable pair interactions, declared scaling and gauge, and stated coefficient precision, range, and sign restrictions.Graph instances need diagonal values and binary compatibility or incompatibility couplings; weighted factor instances need programmable positive diagonal ratios.Source: §10.1 · p. 39

10.2 State contract

  • If normalization is approximate, the device should report its unnormalized state so feasibility correction is accounted for as postprocessing.Changing the normalization constant rescales quadratic energy by its square.Source: §10.2 · p. 39

10.3 Energy contract

  • Physical interactions may implement the requested matrix, a relative gauge, or a factorized approximation, so the realized matrix should be measured or calibrated.The effective energy should match the intended objective up to a simplex-constant shift.Source: §10.3 · p. 39

10.4 Search contract

  • The paper lists noise schedules, nonlocal support moves, restarts, continuation, replicas, and hybrid certification as candidate search mechanisms, but does not analyze them as global algorithms.Their success rates and certification capability require separate evaluation.Source: §10.4 · p. 39

10.5 Output contract

  • Reported outputs should include the raw state, device time, programmed matrix, estimated realized matrix, and reproducibility traces.For feasible states, a zero projected-gradient residual certifies first-order stationarity only, not local or global minimality.Source: §10.5 · p. 40

10.6 Timing and energy accounting

  • End-to-end timing should account separately for compilation, programming and calibration, evolution, sampling or restarts, readout, repair, and verification.Native-device and end-to-end times are both useful and should not be substituted for one another without clarification.Source: §10.6 · p. 40

10.7 A minimal graph-coded device mode

  • A minimal graph-coded mode needs one common diagonal strength and one common repulsive conflict strength; its global optimum is 1/ω(G), but this target remains NP-complete.A fixed coefficient alphabet simplifies programming but does not remove NP-hardness or guarantee efficient global search.Source: §10.7 · p. 40

10.8 Evaluation metrics

  • Evaluation should distinguish finding a clique of size at least k, finding a maximum clique, and certifying its size, since these are increasingly demanding targets.For stochastic solvers, the paper recommends time-to-target at multiple levels and separate reporting of programming, readout, and postprocessing costs.Source: §10.8 · p. 41

11 Limitations and open research questions

Section 11 identifies limits in universal reductions, continuous precision, approximation guarantees, and local-search interpretation. It also outlines open directions in alternative simplex lifts, certification, formulation search, and empirical evaluation.

11.1 Universality can hide poor formulations

  • Composing reductions to CLIQUE proves universality but can hide application structure and yield impractical expansions, motivating direct, sparse, or low-rank encodings and problem-specific decoders.Even a polynomial expansion may be impractical.Source: §11.1 · p. 41

11.2 Continuous precision is a computational resource

  • Continuous precision is a computational resource: objective levels converge as solution size grows, while weighted compilers may require large diagonal ranges and reciprocal value recovery.The paper calls for characterizing bit complexity, noise sensitivity, and finite-temperature behavior.Source: §11.2 · p. 41

11.3 Approximation theory

  • Objective-nonincreasing decoding preserves multiplicative clique approximation, but N^(1−ε)-approximation for the restricted N-coordinate family is NP-hard; general StQP's additive scheme does not contradict this.For factor-state models, no uniform multiplicative guarantee for the original energy follows without additional assumptions.Source: §11.3 · pp. 41–42

11.4 Local landscape beyond cliques

  • Local-minimum correspondences identify possible descent endpoints but do not determine their attraction basins, decoded quality, convergence times, or dependence on search dynamics.Every assignment being a local minimum does not mean assignments are reached with equal probability.Source: §11.4 · p. 42

11.5 Alternative simplex lifts

  • Product-simplex formulations impose prescribed mass per block, unlike single-simplex constructions; dropping the corresponding constraints changes the feasible set and voids automatic transfer of the stated landscape results.Comparisons should account for local-state counts and the cost of enforcing multiple normalization constraints.Source: §11.5 · p. 42

11.6 Global certification

  • The paper suggests hybrid certification, with devices generating primal candidates and classical conic, combinatorial, or exact StQP methods supplying bounds.This division of labor may be more realistic than expecting a physical relaxer to certify globality internally.Source: §11.6 · p. 43

11.7 Formulation search as an optimization problem

  • Formulation selection can be framed as multiobjective optimization over dimension, interactions, coefficient range, decision gap, and decoder robustness.Automated formulation search is proposed as a counterpart to compiler optimization.Source: §11.7 · p. 43

11.8 Empirical question

  • The paper reports no solver-performance experiments, basin measurements, or hardware benchmarks, leaving practical benefit for chosen instance families to empirical comparison.Suggested studies include decoded outcomes, success probabilities, and sensitivity to offsets.Source: §11.8 · p. 43

12 Conclusion

The conclusion presents a catalog of discrete-problem formulations over one normalized nonnegative state and summarizes their representation costs. It emphasizes that practical comparisons depend on implementation and require performance measurements beyond exact formulations.

12 Conclusion

  • The catalog covers Karp's 21 problems: twelve use direct graph formulations and nine use factor-state compilation, including six through binary-linear feasibility.It supplies explicit matrices, dimensions, thresholds, and decoding rules for both route types.Source: §12 · p. 43
  • The analysis identifies simple coefficients and support-based decoding for direct graph routes, while factor-state compilation can expand dimension and makes every complete assignment a strict local minimum.Reciprocal objective recovery depends on weights, offsets, and attainable energy spacings; separation bounds specify accuracy conditions under stated assumptions.Source: §12 · p. 43
  • Strong binary formulations can match candidate counts for clique, packing, and exact cover, so practical comparison depends on normalization, interactions, precision, search, and readout.The paper does not establish performance for a device; that requires measurement.Source: §12 · p. 43

A Compilation procedures

The compilation procedures turn graphs, CNF formulas, and finite-domain factor tables into StQP matrices. The factor-state compiler encodes local assignments as weighted vertices and compatibility as zero-valued matrix entries.

Graph-to-StQP compiler

  • The graph compiler sets diagonal entries to τ, assigns zero to edges and one to nonedges, and returns a symmetric matrix.Its input is a nonempty simple undirected graph with 0 < τ < 1.Source: A Compilation procedures · p. 44

Clause–literal compatibility graph

  • The clause–literal compatibility graph creates one vertex per literal occurrence and connects occurrences from distinct clauses unless they are complementary.The construction requires a nonempty CNF formula.Source: A Compilation procedures · p. 44

Factor-state weighted StQP compiler

  • The factor-state compiler assigns each local assignment a weight Bα − ϕα(a) and marks states compatible when distinct factors agree on their shared variables.It sets diagonals to τwmin/wv, uses zero for compatible pairs and one otherwise, and returns recovery constants.Source: A Compilation procedures · p. 44

B.1 Purifying an approximate graph solution

The section describes recovery procedures for approximate solutions, matrix structures for several reductions, and a copositive certificate for StQP lower bounds. It also distinguishes local consistency from global optimality and states when decoding remains heuristic.

B.1 Purifying an approximate graph solution

  • A graph solution can be purified by moving mass off nonedges until its support is a clique, but these steps do not certify maximum weight.Purification never increases the objective and takes at most n − 1 eliminations; a greedy extension can make the clique maximal.Source: §B.1 · p. 44

B.2 Factor-state decoding

  • At a clique-supported factor-state local minimizer, one state per factor agrees across overlaps and forms a complete assignment; approximate nonclique recovery remains heuristic.The proposed repair selects each factor’s largest-mass state, resolves disagreements by weighted voting, and performs local updates, which should be reported separately.Source: §B.2 · p. 45

C.1 Independent set and vertex cover

  • The independent-set formulation has minimum 1/α(G), and a minimizing support gives a maximum independent set whose complement is a minimum vertex cover..Source: §C.1 · p. 45

C.2 Coloring matrix blocks

  • In the integer-scaled coloring matrix, compatible coordinates have coefficient zero and all other distinct-coordinate pairs have coefficient two.Same-vertex blocks encode conflicts, as do equal-color pairs across graph edges.Source: §C.2 · p. 45

C.3 Hamiltonian matrix blocks

  • The Hamiltonian matrix assigns coefficient zero to consecutive-position pairs only when their vertices share a graph edge, and to nonconsecutive-position pairs with different vertices.Same-position and same-vertex pairs receive coefficient two; the block structure avoids materializing all n^4 assignment pairs.Source: §C.3 · p. 45

C.4 Max-Cut local states

  • For Max-Cut, each edge has four binary endpoint states weighted L or L + ce, while incident edges conflict when their states disagree on the shared endpoint.Disjoint edges are always compatible, yielding sparse 4 × 4 conflict blocks for incident edge-factor pairs.Source: §C.4 · p. 45

D A note on copositive certification

  • A copositive shift of Q provides an exact global lower-bound certificate for the simplex objective, though optimizing over the copositive cone is computationally hard.Tractable inner approximations, semidefinite hierarchies, and combinatorial bounds can certify many instances; the formulation connects the physical energy minimum to a classical conic certificate.Source: D A note on copositive certification · p. 46
Loading 2610.01911v1…