[Rule] KSatisfiability to KLocalHamiltonian

[QingyunQian]

Source: KSatisfiability (k-SAT)
Target: KLocalHamiltonian
Motivation: Embeds classical satisfiability into the quantum Hamiltonian framework via a standard clause-to-projector mapping ( frustration-free local Hamiltonians). Enables a unified reduction chain from classical NP-complete problems into quantum complexity.
Reference:

• Kitaev, A. Yu., Shen, A. H. & Vyalyi, M. N. (2002). Classical and Quantum Computation. AMS, Section 14.4.
• Kempe, J., Kitaev, A. & Regev, O. (2006). "The Complexity of the Local Hamiltonian Problem." SIAM J. Comput., 35(5), 1070–1097.

Reduction Algorithm

Notation:

• Source (KSatisfiability): $n$ Boolean variables $x_0, \dots, x_{n-1}$; $m$ clauses $C_1, \dots, C_m$, each containing exactly $k$ literals on distinct variables (standard for k-SAT; if duplicates exist, preprocess by removing repeated literals and shrinking the clause). Literal $l$ is either $x_i$ (positive) or $\neg x_i$ (negative). DIMACS convention: positive integer $i+1$ for $x_i$, negative integer $-(i+1)$ for $\neg x_i$.
• Target (KLocalHamiltonian): $n$ qubits, $m$ Hamiltonian terms $H_1, \dots, H_m$, thresholds $a, b$.

Convention: qubit computational basis $|0\rangle$ = FALSE, $|1\rangle$ = TRUE.

Variable mapping:

Each Boolean variable $x_i$ maps one-to-one to qubit $i$. A classical assignment $(x_0, \dots, x_{n-1}) \in {0,1}^n$ corresponds to the computational basis state $|x_0 x_1 \cdots x_{n-1}\rangle$.

Constraint/objective transformation:

For each clause $C_j$ acting on variable indices $S_j = {q_1, \dots, q_k}$:

1. Identify the unique violating assignment: the $k$-bit string $|v_j\rangle = |b_1 b_2 \cdots b_k\rangle$ where

   • $b_i = 0$ if the literal on variable $q_i$ is positive ($x_{q_i}$), because the clause is violated when $x_{q_i} = 0$
   • $b_i = 1$ if the literal on variable $q_i$ is negative ($\neg x_{q_i}$), because the clause is violated when $x_{q_i} = 1$

2. Construct the $k$-local projector:

$$H_j = \Big(|v_j\rangle\langle v_j|\Big)_{S_j} \otimes I_{\overline{S_j}}$$

where $\overline{S_j}$ denotes the remaining $n - k$ qubits. The local part $|v_j\rangle\langle v_j|$ is the tensor product (taken in the fixed ordering of qubits in $S_j$):

$$|v_j\rangle\langle v_j| = \bigotimes_{i=1}^{k} P_{q_i}$$

where $P_{q_i} = |0\rangle\langle 0|$ if the literal is positive, $P_{q_i} = |1\rangle\langle 1|$ if negative. In matrix form:

$$|0\rangle\langle 0| = \begin{pmatrix} 1 & 0 \ 0 & 0 \end{pmatrix}, \quad |1\rangle\langle 1| = \begin{pmatrix} 0 & 0 \ 0 & 1 \end{pmatrix}$$

3. Set thresholds:
   • $a = 0$ (SAT: there exists a basis state with energy 0)
   • $b = 1$ (UNSAT: every basis state violates $\geq 1$ clause)

Total Hamiltonian: $H = \sum_{j=1}^{m} H_j$

Correctness

• $H$ is diagonal in the computational basis. For a classical assignment $z \in {0,1}^n$:

$$\langle z | H | z \rangle = \text{number of clauses violated by } z$$

• SAT $\implies$ $\exists z$ with $\langle z|H|z\rangle = 0 \leq a$. Since $H$ is positive semidefinite, the ground-state energy is exactly 0.
• UNSAT $\implies$ $\forall z$, $\langle z|H|z\rangle \geq 1 \geq b$. Since $H$ is diagonal, the quantum ground-state energy equals the minimum over computational basis states, so ground energy $\geq 1$.
• Promise gap: $b - a = 1 \geq 1/\text{poly}(n)$, always satisfied.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_qubits	$n$ (= num_vars)
num_terms	$m$ (= num_clauses)
matrix_dim per term	$2^k \times 2^k$ (constant for fixed $k$)
threshold_a	$0$
threshold_b	$1$

The reduction is linear: dense encoding of each local matrix requires $4^k$ entries, giving total storage $O(m \cdot 4^k)$, which is $O(m)$ for fixed $k$. Sparse/structured representations can reduce this further since each $H_j$ is rank-1.

Validation Method

• Exact diagonalization of $H$ on small instances ($n \leq 20$) and comparison with brute-force SAT solving: ground energy = 0 iff SAT, $\geq 1$ iff UNSAT
• Verify each $H_j$ is a rank-1 projector: $H_j^2 = H_j$, $\text{Tr}(H_j) = 1$, $||H_j|| = 1$
• Cross-check: for every satisfying assignment $z$, confirm $\langle z|H_j|z\rangle = 0$ for all $j$; for every unsatisfying assignment, confirm $\langle z|H|z\rangle \geq 1$
• Test on known UNSAT instances (e.g., pigeonhole-principle formulas) to confirm ground energy $\geq 1$

Example

Source: 3-SAT instance

n = 3 variables: x_0, x_1, x_2
m = 2 clauses (k = 3):
  C_1 = (x_0 ∨ x_1 ∨ x_2)          DIMACS: 1 2 3
  C_2 = (¬x_0 ∨ ¬x_1 ∨ x_2)       DIMACS: -1 -2 3

Clause-to-projector construction

Clause $C_1 = (x_0 \vee x_1 \vee x_2)$:

• Violated when $x_0=0, x_1=0, x_2=0$
• Violating state: $|000\rangle$
• $H_1 = |0\rangle\langle 0| \otimes |0\rangle\langle 0| \otimes |0\rangle\langle 0|$ on qubits ${0, 1, 2}$

$$H_1 = \text{diag}(1, 0, 0, 0, 0, 0, 0, 0)$$

Clause $C_2 = (\neg x_0 \vee \neg x_1 \vee x_2)$:

• Violated when $x_0=1, x_1=1, x_2=0$
• Violating state: $|110\rangle$
• $H_2 = |1\rangle\langle 1| \otimes |1\rangle\langle 1| \otimes |0\rangle\langle 0|$ on qubits ${0, 1, 2}$

$$H_2 = \text{diag}(0, 0, 0, 0, 0, 0, 1, 0)$$

Target: KLocalHamiltonian instance

num_qubits = 3, num_terms = 2, k = 3
H = H_1 + H_2 = diag(1, 0, 0, 0, 0, 0, 1, 0)
threshold_a = 0, threshold_b = 1

Verification (all 8 assignments):

$x_0 x_1 x_2$	$C_1$	$C_2$	$\langle z \mid H \mid z \rangle$
000	violated	sat	1
001	sat	sat	0
010	sat	sat	0
011	sat	sat	0
100	sat	sat	0
101	sat	sat	0
110	sat	violated	1
111	sat	sat	0

Ground-state energy = 0 (achieved by 6 out of 8 assignments). Since $0 \leq a = 0$, the answer is YES (SAT).

Note: the resulting Hamiltonian is diagonal in the computational basis. This means the reduction embeds a classical problem into the quantum framework without introducing quantum entanglement in the ground state. The non-trivial quantum aspect arises when this reduction is composed with further transformations (e.g., perturbation gadgets for locality reduction from $k$-local to 2-local).