[Model] KLocalHamiltonian

[QingyunQian]

Motivation

Add the famous k-local Hamiltonian problem. It is the canonical QMA-complete problem (the generalization of NPC) and sits at the heart of complexity theory. It connects naturally to existing classical models in the repository (SpinGlass is a special case when k=2 and all terms are diagonal/classical), and serves as a target for reductions from classical NP-hard problems and a source for quantum-specific hardness results.

Definition

Name: KLocalHamiltonian
Reference:

• Kitaev, A. Yu. (1999/2002). Quantum computations: algorithms and error correction. Russian Math. Surveys 52(6), 1191–1249.
• Kitaev, A. Yu., Shen, A. H. & Vyalyi, M. N. (2002). Classical and Quantum Computation. AMS. (Section 14.4: QMA-completeness of 5-local Hamiltonian)
• Kempe, J., Kitaev, A. & Regev, O. (2006). "The Complexity of the Local Hamiltonian Problem." SIAM J. Comput., 35(5), 1070–1097. (QMA-completeness of 2-local Hamiltonian)

Given:

• n qubits (Hilbert space (C^2)^{⊗n}, dimension 2^n)
• k is a fixed constant independent of n in the standard complexity-theoretic formulation
• m = poly(n) Hermitian operators (terms) H_1, ..., H_m, each acting non-trivially on at most k qubits
• Each term satisfies ||H_j|| <= poly(n) (operator norm bound; many formulations normalize to ||H_j|| <= 1 by rescaling)
• All matrix entries are rationals with poly(n)-bit numerator and denominator
• Thresholds a < b with b - a >= 1/poly(n) (promise gap)

The Hamiltonian is H = sum_{j=1}^m H_j.

Promise decision version:

• YES: the smallest eigenvalue (ground-state energy) of H is <= a
• NO: the smallest eigenvalue of H is >= b

Variables

• Count: n qubits
• Per-variable domain: quantum — each qubit lives in C^2; classically, a full state vector has 2^n complex amplitudes
• Meaning: the ground state |psi> minimizing <psi|H|psi> over all 2^n-dimensional unit vectors
• Constraint: unit-norm quantum state (<psi|psi> = 1)

Schema (data type)

Type name: KLocalHamiltonian
Variants: locality parameter k (commonly k = 2 or k = 5); qubit vs. qudit; real vs. complex entries

Field	Type	Description
num_qubits	usize	Number of qubits n
terms	Vec<LocalTerm>	Each term specifies which qubits it acts on and its local Hermitian matrix
threshold_a	f64	Lower threshold a (YES if ground energy <= a)
threshold_b	f64	Upper threshold b (NO if ground energy >= b)

Implementation note: coefficients are stored in floating-point; the formal complexity definition assumes rational encodings with poly(n)-bit precision.

Where LocalTerm contains:

Field	Type	Description
qubits	Vec<usize>	Indices of the (at most k) qubits this term acts on
matrix	Vec<Vec<Complex64>>	Hermitian matrix of dimension 2^s × 2^s where s = len(qubits)

Complexity

• Baseline exact approach: exact diagonalization requires exponential resources — at least Ω(2^n) memory for state vectors; dense-matrix diagonalization is O(8^n) time and O(4^n) memory if the full 2^n × 2^n matrix is formed (iterative methods like Lanczos avoid forming the full matrix but remain exponential)
• Complexity class:
  • 1-local Hamiltonian: in P — aggregate all terms acting on each qubit and sum the minimum eigenvalues; runs in O(m) (up to constant-size diagonalizations per qubit)
  • 5-local Hamiltonian: QMA-complete (Kitaev, 2002)
  • 2-local Hamiltonian: QMA-complete (Kempe, Kitaev & Regev, 2006)
  • QMA is the quantum analog of NP: a verifier is a polynomial-time quantum circuit, and the witness is a polynomial-size quantum state
• Classical special case: when all H_j are diagonal in the computational basis, the problem reduces to classical constraint satisfaction (e.g., MAX-SAT, SpinGlass)
• References:
  • Kitaev (2002): 5-local QMA-completeness
  • Kempe, Kitaev & Regev (2006): 2-local QMA-completeness
  • Oliveira & Terhal (2008): QMA-completeness on 2D lattice with 2-local terms

Extra Remark

Relationship to existing problems in the repository:

Problem	KLocalHamiltonian	Key Difference
SpinGlass	SpinGlass is a 2-local classical Hamiltonian (diagonal terms only)	KLocalHamiltonian allows off-diagonal (quantum) terms; SpinGlass is a strict special case
Satisfiability	SAT is a classical constraint satisfaction problem	KLocalHamiltonian generalizes weighted k-CSP to quantum (minimizing a sum of local energy penalties); in the special case where each term is a projector, it becomes Quantum k-SAT
QUBO	QUBO minimizes a quadratic pseudo-Boolean function	Equivalent to a 2-local diagonal Hamiltonian; KLocalHamiltonian is strictly more general

Why KLocalHamiltonian is distinct:

• Complexity class: QMA-complete (strictly harder than NP under standard assumptions), whereas all existing models in the repository are NP-hard or below
• Configuration space: exponential-dimensional quantum state space (2^n amplitudes), not a discrete combinatorial search
• Promise structure: the YES/NO gap b - a >= 1/poly(n) is essential for the standard QMA-completeness formulation; without a polynomially bounded gap, the complexity classification changes and may require exponentially fine precision, but the finite-dimensional problem remains decidable (undecidability arises only in the thermodynamic limit / spectral gap problem, cf. Cubitt, Perez-Garcia & Wolf, 2015)

Applications:

• Quantum chemistry: estimating ground-state energies of molecular Hamiltonians
• Condensed matter physics: phase classification and critical phenomena
• Quantum algorithms: variational quantum eigensolver (VQE), quantum phase estimation

How to solve

• It can be solved by bruteforce (exact diagonalization of the 2^n × 2^n matrix)
• It can be solved by reducing to integer programming, through #issue-number.
• Other: Lanczos / DMRG for approximate ground-state energy; VQE on quantum hardware.

Example Instance

Instance 1: 2-qubit antiferromagnetic Heisenberg (YES)

n = 2, k = 2, m = 1
H = H_1 acting on qubits {0, 1}:
H_1 = (1/4)(XX + YY + ZZ)
    = [[1/4,  0,    0,   0  ],
       [0,   -1/4,  1/2, 0  ],
       [0,    1/2, -1/4, 0  ],
       [0,    0,    0,   1/4]]

(where XX = sigma_x ⊗ sigma_x, etc.)

Eigenvalues: {-3/4, 1/4, 1/4, 1/4}
Ground-state energy: -3/4 (the singlet state)

a = -0.5, b = 0
Ground energy = -3/4 <= -0.5 = a => YES

Instance 2: Trivial ferromagnetic (NO)

n = 2, k = 1, m = 2
H_1 = Z ⊗ I = diag(1, 1, -1, -1) acting on qubit 0
H_2 = I ⊗ Z = diag(1, -1, 1, -1) acting on qubit 1

H = H_1 + H_2 = diag(2, 0, 0, -2)
Eigenvalues: {-2, 0, 0, 2}
Ground-state energy: -2

a = -3, b = -2.5
Ground energy = -2 >= -2.5 = b => NO

Validation Method

• Exact diagonalization on small instances (n <= 16) and comparison with known ground-state energies
• Cross-check 2-local diagonal instances against SpinGlass model in the repository
• Verify promise gap: ensure b - a >= 1/poly(n) for all test instances
• Compare with established quantum chemistry benchmarks (e.g., H2 molecule Hamiltonian at equilibrium bond length)