[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.