[Rule]SpinGlass to KLocalHamiltonian

[QingyunQian]

Source: SpinGlass
Target: KLocalHamiltonian
Motivation: Embeds the classical Ising model into the quantum local Hamiltonian framework as a diagonal (purely classical) special case. This establishes SpinGlass as a strict subproblem of KLocalHamiltonian and bridges the repository's classical optimization models to the quantum complexity hierarchy.
Reference:

• Barahona, F. (1982). "On the computational complexity of Ising spin glass models." J. Phys. A, 15(10), 3241. (NP-hardness of Ising ground-state problem)
• Lucas, A. (2014). "Ising formulations of many NP problems." Frontiers in Physics, 2, 5. (Ising ↔ combinatorial optimization dictionary)

Reduction Algorithm

Notation:

• Source (SpinGlass): $n$ spin variables $s_0, \dots, s_{n-1} \in {-1, +1}$; interaction graph $G = (V, E)$ with $|V| = n$, $|E| = m$; couplings $J_{ij}$ per edge $(i,j) \in E$; on-site fields $h_i$ per vertex $i \in V$. All coefficients are integers or rationals with denominators bounded by $\text{poly}(n)$. Binary representation: $x_i \in {0, 1}$, $s_i = 2x_i - 1$ (so $x_i = 0 \to s_i = -1$, $x_i = 1 \to s_i = +1$). Hamiltonian: $H_{\text{Ising}}(s) = \sum_{(i,j) \in E} J_{ij} , s_i , s_j + \sum_{i \in V} h_i , s_i$.
• Target (KLocalHamiltonian): $n$ qubits, Hamiltonian terms $H_1, \dots, H_p$, thresholds $a, b$.

Convention: qubit computational basis $|0\rangle \to s = -1$, $|1\rangle \to s = +1$ (matching the repository's config_to_spins: s = 2x - 1).

Variable mapping:

Each spin variable $s_i$ maps one-to-one to qubit $i$. The Pauli-Z operator acts as: $Z|0\rangle = +|0\rangle$, $Z|1\rangle = -|1\rangle$, so the spin operator is $\hat{s}_i = -Z_i$ (since $s_i = 2x_i - 1$ gives $s = -1$ for $|0\rangle$ and $s = +1$ for $|1\rangle$, while $Z$ gives $+1$ for $|0\rangle$ and $-1$ for $|1\rangle$).

Constraint/objective transformation:

1. For each edge $(i,j) \in E$ with coupling $J_{ij}$, construct a 2-local diagonal term:

$$H^{(ij)} = J_{ij} \cdot (Z \otimes Z)_{S} \otimes I_{\overline{S}}, \quad S = (i, j)$$

where $Z \otimes Z$ is the $4 \times 4$ local matrix acting on the qubit pair $(i, j)$, and $I_{\overline{S}}$ is the identity on the remaining $n - 2$ qubits. Explicitly:

$$J_{ij} \cdot Z \otimes Z = J_{ij} \cdot \text{diag}(1, -1, -1, 1)$$

This reproduces $J_{ij} , s_i , s_j$ because $(-Z_i)(-Z_j) = Z_i Z_j$ and the product of signs cancels.

1. For each vertex $i \in V$ with field $h_i \neq 0$, construct a 1-local diagonal term:

$$H^{(i)} = -h_i \cdot (Z)_{S} \otimes I_{\overline{S}}, \quad S = (i)$$

The local $2 \times 2$ matrix (on qubit ${i}$) is:

$$-h_i \cdot Z = -h_i \cdot \text{diag}(1, -1) = \text{diag}(-h_i, , h_i)$$

The sign flip ($-h_i$ instead of $+h_i$) is because $\hat{s}_i = -Z_i$: for $|0\rangle$ ($s_i = -1$), the energy contribution is $h_i \cdot (-1) = -h_i$; for $|1\rangle$ ($s_i = +1$), it is $h_i \cdot (+1) = +h_i$.

1. Set thresholds: the decision version of Ising ground energy asks "is OPT $\leq E$?" for a given threshold $E$. Set $a = E$ and $b = E + \Delta$ where $\Delta$ is determined by the coefficient encoding:
   • Integer couplings/fields: all energy levels are integers, so $\Delta = 1$ suffices.
   • Rational couplings/fields with denominators bounded by $\text{poly}(n)$ (the standard assumption in combinatorial Ising / Barahona / Lucas settings): let $D$ be the least common denominator of all $J_{ij}$ and $h_i$. Then $D \leq \text{poly}(n)$, so choosing $\Delta = 1/D \geq 1/\text{poly}(n)$ satisfies the KLocalHamiltonian promise gap requirement. Equivalently, multiply all coefficients by $D$ to integerize, then use $\Delta = 1$ on the scaled instance.

Total Hamiltonian: $H = \sum_{(i,j) \in E} H^{(ij)} + \sum_{i \in V} H^{(i)}$

Correctness

$H$ is diagonal in the computational basis. For any classical configuration $x \in {0,1}^n$:

$$\langle x | H | x \rangle = H_{\text{Ising}}(s) = \sum_{(i,j) \in E} J_{ij} , s_i , s_j + \sum_{i \in V} h_i , s_i$$

where $s_i = 2x_i - 1$. This follows from $\langle x_i | Z | x_i \rangle = (-1)^{x_i} = -s_i$ and the sign conventions above.

The ground-state energy of $H$ equals the minimum Ising energy. Since $H$ is diagonal, no quantum entanglement is involved and the minimum is always achieved by a computational basis state.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_qubits	$n$ (= num_spins)
num_terms	$\leq m + n$ (one 2-local per edge + one 1-local per non-zero field)
locality $k$	$2$
matrix_dim per term	$4 \times 4$ (2-local) or $2 \times 2$ (1-local)

Each term is encoded as: qubit indices (1 or 2 integers) plus a constant-size local matrix ($4 \times 4$ or $2 \times 2$) with entries of bit-length $\leq L$. Total encoding length is $O((m + n) \cdot L)$, where $L$ is the maximum bit-length of any coefficient $J_{ij}$ or $h_i$.

Validation Method

• Compute Ising energy $H_{\text{Ising}}(s)$ for all $2^n$ configurations via SpinGlass::compute_energy, and verify it matches the diagonal of the constructed $H$
• Cross-check ground-state energy: the minimum over SpinGlass brute-force solutions equals the minimum eigenvalue of $H$
• Test with known instances: antiferromagnetic chain (unique/degenerate ground states), frustrated triangle (6-fold degeneracy), random instances up to $n = 16$
• Verify all terms are diagonal: each $H_j$ should satisfy $H_j = \text{diag}(\cdots)$ with no off-diagonal entries

Example

Source: SpinGlass on antiferromagnetic triangle

n = 3 spins, graph = K_3 (complete graph on 3 vertices)
Edges: {(0,1), (1,2), (0,2)}, m = 3
Couplings: J_01 = 1, J_12 = 1, J_02 = 1 (all antiferromagnetic)
Fields: h_0 = 0, h_1 = 0, h_2 = 0 (no external field)

H_Ising(s) = s_0*s_1 + s_1*s_2 + s_0*s_2

This is the classic frustrated antiferromagnet: no assignment can simultaneously satisfy all three antiferromagnetic couplings.

Target: KLocalHamiltonian instance

Three 2-local terms (no 1-local terms since all fields are zero):

$H^{(01)}$ on qubits ${0, 1}$: $Z \otimes Z = \text{diag}(1, -1, -1, 1)$

$H^{(12)}$ on qubits ${1, 2}$: $Z \otimes Z = \text{diag}(1, -1, -1, 1)$

$H^{(02)}$ on qubits ${0, 2}$: $Z \otimes Z = \text{diag}(1, -1, -1, 1)$

num_qubits = 3, num_terms = 3, k = 2
threshold_a = -1, threshold_b = 0

Verification (all 8 configurations)

$x_0 x_1 x_2$	$s_0 s_1 s_2$	$s_0 s_1$	$s_1 s_2$	$s_0 s_2$	$H_{\text{Ising}}$
000	$(-1,-1,-1)$	$+1$	$+1$	$+1$	$+3$
001	$(-1,-1,+1)$	$+1$	$-1$	$-1$	$-1$
010	$(-1,+1,-1)$	$-1$	$-1$	$+1$	$-1$
011	$(-1,+1,+1)$	$-1$	$+1$	$-1$	$-1$
100	$(+1,-1,-1)$	$-1$	$+1$	$-1$	$-1$
101	$(+1,-1,+1)$	$-1$	$-1$	$+1$	$-1$
110	$(+1,+1,-1)$	$+1$	$-1$	$-1$	$-1$
111	$(+1,+1,+1)$	$+1$	$+1$	$+1$	$+3$

Ground-state energy = $-1$, achieved by 6 configurations (any state with exactly one spin differing from the other two). This 6-fold degeneracy is a hallmark of geometric frustration on the triangle.

Since ground energy $= -1 \leq -1 = a$, the answer is YES.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Target problem KLocalHamiltonian does not exist in the codebase; cannot implement rule without the model first
Non-trivial	❌ Fail	Subtype coercion: SpinGlass is the diagonal special case of KLocalHamiltonian; no structural transformation
Correctness	✅ Pass	Both cited references verified; claims are accurate
Well-written	⚠️ Warn	Overhead table uses informal metric names not validated against a target schema; minor notation issues

Overall: 1 passed, 1 failed, 2 warnings

---

Usefulness

The target problem KLocalHamiltonian does not currently exist in the codebase (pred show KLocalHamiltonian returns "Unknown problem"). Since no path can exist to a nonexistent target, the reduction is technically novel. However, this rule cannot be implemented until the KLocalHamiltonian model is added first. There is no [Model] issue referenced for KLocalHamiltonian.

The motivation is reasonable in principle -- bridging classical optimization to the quantum complexity hierarchy -- but the practical value depends entirely on whether KLocalHamiltonian will be added and what further reductions it enables.

Non-trivial

This reduction maps each spin variable s_i one-to-one to qubit i with no auxiliary variables, no gadgets, and no penalty terms. The construction is:

• Coupling J_ij * s_i * s_j becomes J_ij * (Z_i tensor Z_j), a diagonal matrix
• Field h_i * s_i becomes -h_i * Z_i, a diagonal matrix

The resulting target Hamiltonian is purely diagonal in the computational basis. For any configuration x, the diagonal entry equals the classical Ising energy exactly. No quantum entanglement is involved; the minimum is always a computational basis state.

This is a subtype coercion: SpinGlass is precisely the diagonal (classical) special case of KLocalHamiltonian. The "reduction" wraps classical energy terms in quantum operator notation without constructing new constraints, new variables, or new problem structure. The issue itself acknowledges this: "Embeds the classical Ising model into the quantum local Hamiltonian framework as a diagonal (purely classical) special case."

Per the check-issue criteria, a reduction that "merely casts to a more general type with no structural change to the problem instance" is flagged as trivial. While the sign convention (s_i = -Z_i) adds minor implementation detail, the overall mapping is a direct embedding with no genuine structural transformation.

Correctness

Barahona (1982): Verified. "On the computational complexity of Ising spin glass models," J. Phys. A, 15(10), 3241. The paper establishes NP-hardness of the Ising ground-state problem on general graphs (and in 2D with external fields). This is already in the project bibliography as barahona1982. The issue's citation is accurate.

Lucas (2014): Verified. "Ising formulations of many NP problems," Frontiers in Physics, 2, 5. DOI: 10.3389/fphy.2014.00005. The paper provides Ising formulations for many NP problems including all of Karp's 21 NP-complete problems. Already in the bibliography as lucas2014. The issue's citation is accurate.

Neither paper specifically discusses a "reduction from SpinGlass to KLocalHamiltonian" -- they address the classical Ising model. The embedding into the quantum local Hamiltonian framework is a standard construction in quantum complexity theory (see Kitaev, Kempe-Regev for the formal framework), but the cited papers support the classical side of the claim.

Well-written

Strengths:

• The algorithm section is detailed with explicit matrix constructions
• The notation section defines all symbols clearly
• The example (frustrated antiferromagnetic triangle) is well-chosen and fully worked with all 8 configurations verified
• The correctness argument is clear

Issues:

• The overhead table uses metric names (num_qubits, num_terms, matrix_dim) that cannot be validated against a target schema since KLocalHamiltonian does not exist. These are informal and may not match the eventual implementation.
• Step numbering in the algorithm restarts at 1 three times (steps 1, 1, 1 instead of 1, 2, 3) -- likely a markdown rendering issue.
• The threshold discussion (section on Delta) mixes the decision version semantics with the optimization framing of SpinGlass, which could be clearer.
• The "Validation Method" references SpinGlass::compute_energy which does not appear to be an actual method name in the codebase (the Problem trait uses evaluate).

Recommendations

• A [Model] issue for KLocalHamiltonian should be created first, since this rule depends on the target problem existing.
• Consider whether this embedding is better modeled as a variant/subtype relationship rather than a reduction rule, given its trivial structural nature.
• If proceeding as a rule, the overhead expressions will need to use getter method names that match the eventual KLocalHamiltonian implementation.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Target problem KLocalHamiltonian does not exist in the codebase; no path comparison possible
Non-trivial	❌ Fail	Diagonal embedding is a direct encoding with no structural transformation
Correctness	✅ Pass	Both references verified (Barahona 1982, Lucas 2014)
Well-written	✅ Pass	All sections present, detailed example, consistent notation

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

The target problem KLocalHamiltonian does not exist in the reduction graph. Running pred show KLocalHamiltonian fails — the problem has not been implemented. Since the target does not exist, no existing path SpinGlass -> KLocalHamiltonian can exist, so the reduction would be novel in that sense. However, this means a [Model] issue for KLocalHamiltonian must be implemented first before this rule can be added.

Note: KLocalHamiltonian is a QMA-complete problem (Kitaev 1999; 2-local case: Kempe, Kitaev & Regev 2004). It sits in a different complexity hierarchy (quantum) than the NP-hard problems currently in the reduction graph. Adding it would bridge classical optimization to quantum complexity, which is potentially valuable — but only if additional non-trivial reductions to/from KLocalHamiltonian are planned.

Non-trivial

This reduction maps each classical spin variable $s_i$ one-to-one to a qubit $i$, and each Ising interaction $J_{ij} s_i s_j$ to the diagonal operator $J_{ij} Z_i Z_j$, with fields $h_i s_i$ mapped to $-h_i Z_i$. The resulting quantum Hamiltonian $H$ is entirely diagonal in the computational basis, meaning:

• No auxiliary qubits are introduced (num_qubits = num_spins)
• No gadget construction or penalty terms are used
• No new constraints or structural transformation occurs
• The energy of every classical configuration is exactly preserved: $\langle x | H | x \rangle = H_{\text{Ising}}(s)$
• The ground state is always a computational basis state (no quantum entanglement involved)

This is a subtype coercion: the classical Ising model is embedded as a strict special case (diagonal subclass) of the quantum local Hamiltonian framework. The "reduction" amounts to re-notating spin variables as Pauli-Z operators — a change of mathematical formalism, not a structural transformation of the problem instance.

Per the skill criteria: "The reduction merely casts to a more general type within an existing variant hierarchy with no structural change to the problem instance" — this fits that pattern. A valid reduction must construct new constraints, objectives, or graph structure, which this does not do.

Correctness

Barahona (1982) — "On the computational complexity of Ising spin glass models", J. Phys. A, 15(10), 3241. Verified. The paper establishes NP-hardness of the Ising ground-state problem on 3D lattices and in 2D with external field. DOI: 10.1088/0305-4470/15/10/028. Already in the project bibliography as barahona1982.

Lucas (2014) — "Ising formulations of many NP problems", Frontiers in Physics, 2, 5. Verified. The paper provides Ising formulations for many NP-complete problems including all of Karp's 21 problems. DOI: 10.3389/fphy.2014.00005. Already in the project bibliography as lucas2014.

Both references are correctly cited and support the claims made. However, neither paper describes this as a "reduction" per se — rather, they establish that classical Ising is a subproblem of broader frameworks.

Well-written

The issue is thoroughly written with all required sections present:

• Source/Target: Clearly identified
• Motivation: Explains the bridge between classical and quantum complexity
• Reduction Algorithm: Detailed step-by-step with explicit notation and sign conventions
• Size Overhead: Table provided with formulas (though target metrics cannot be verified since KLocalHamiltonian does not exist)
• Validation Method: Concrete verification steps
• Example: Fully worked antiferromagnetic triangle with all 8 configurations verified — well chosen to illustrate frustration

Minor notes:

• The overhead table references target metrics (num_qubits, num_terms, matrix_dim) that cannot be checked against pred show since the target problem does not exist yet
• Symbol usage is consistent throughout

Recommendations

• Consider whether this belongs as a variant relationship (subtype edge) rather than a standalone reduction rule, given that the mapping is a direct diagonal embedding with no structural overhead
• If KLocalHamiltonian is added as a model, plan non-trivial reductions (e.g., CircuitSAT -> KLocalHamiltonian via Kitaev's clock construction) that would justify the model's inclusion in the graph
• The issue would benefit from a [Model] issue for KLocalHamiltonian being filed and implemented first

[GiggleLiu]

Closing as part of batch cleanup.