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

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; extends repository into quantum complexity
Non-trivial	⚠️ Warn	Genuinely distinct but trait compatibility needs discussion
Correctness	✅ Pass	All 5 references verified; minor date error
Well-written	✅ Pass	Thorough, well-structured with verified examples

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

No KLocalHamiltonian exists in the codebase. This is the canonical QMA-complete problem (quantum analog of Cook-Levin). The issue correctly identifies that SpinGlass and QUBO are classical special cases (diagonal 2-local Hamiltonians), providing natural connections to the existing reduction graph.

Non-trivial — WARN

Genuinely distinct from all 24 existing problems:

• QMA-complete complexity class (strictly harder than NP under standard assumptions)
• Exponential-dimensional continuous quantum state space (2^n complex amplitudes)
• Promise structure (YES/NO gap) novel in the codebase

Architectural concern: The Problem trait requires dims() -> Vec<usize> and evaluate(&self, config: &[usize]) -> Metric. For KLocalHamiltonian, the natural configuration is a 2^n-dimensional complex unit vector. The issue should discuss how to map this to the existing trait hierarchy during implementation planning.

Correctness

Reference	Status	Notes
Kitaev, Russian Math. Surveys 52(6)	✅ Verified	Date correction: The paper year is 1997, not "1999/2002". DOI 10.1070/RM1997v052n06ABEH002155 confirmed.
Kitaev, Shen & Vyalyi (2002), AMS GSM-47	✅ Verified	"Classical and Quantum Computation", Section 14.4 covers 5-local QMA-completeness
Kempe, Kitaev & Regev (2006), SIAM J. Comput. 35(5)	✅ Verified	Proves 2-local Hamiltonian is QMA-complete
Oliveira & Terhal (2008)	✅ Verified	QIC 8, 900–924. 2D lattice QMA-completeness
Cubitt, Perez-Garcia & Wolf (2015)	✅ Verified	Nature 528, 207–211. Undecidability of spectral gap

Complexity claims verified:

• 5-local QMA-complete (Kitaev 2002) ✅
• 2-local QMA-complete (Kempe, Kitaev & Regev 2006) ✅
• 1-local in P ✅
• Exact diagonalization O(8^n) time, O(4^n) space ✅

Examples verified:

• Instance 1 (Heisenberg): Eigenvalues {-3/4, 1/4, 1/4, 1/4} correct. YES conclusion valid.
• Instance 2 (1-local): H = diag(2, 0, 0, -2). Ground energy -2 ≥ -2.5 = b, so NO. Correct.

Well-written

All sections present and substantive. The comparison table (vs SpinGlass, Satisfiability, QUBO) is excellent. Examples are well-chosen: one nontrivial quantum ground state, one classical/1-local.

Minor fix: Kitaev's Russian Math. Surveys paper should be dated 1997, not "1999/2002." The "2002" refers to the book.

Recommendations

• Fix Kitaev reference date from "1999/2002" → 1997 (paper) / 2002 (book)
• Address how quantum state space maps to Problem trait during implementation planning
• Note dependency on num-complex crate for Complex64 type

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but QMA-complete problems are outside the library's NP-hard scope; no reduction rules proposed
Non-trivial	✅ Pass	Genuinely distinct from all existing problems (quantum state space, not combinatorial)
Correctness	⚠️ Warn	References verified; one year citation error (Kitaev 1997, not 1999); 5-local QMA-completeness is in the book (2002), not the 1997 paper
Well-written	❌ Fail	Fundamental architectural incompatibility with Problem trait; missing concrete declare_variants! complexity string; schema incomplete

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The k-Local Hamiltonian problem is a foundational problem in quantum complexity theory and is indeed the canonical QMA-complete problem. However, this library is specifically designed for NP-hard problem reductions among classical combinatorial problems. All 24 existing problems operate on discrete combinatorial configuration spaces.

The issue mentions connections to SpinGlass and QUBO (as classical special cases), but:

• No specific reduction rules are proposed in either direction
• The relationship is "SpinGlass is a special case of KLocalHamiltonian" — this is a subsumption, not a reduction rule that the library can implement
• A problem without any planned reduction rules would be an orphan node in the reduction graph

The motivation is well-written and accurate regarding the problem's importance, but it does not explain how this problem integrates into the existing reduction graph.

Non-trivial

Pass. KLocalHamiltonian is genuinely distinct from all existing problems:

• Configuration space is continuous (unit vectors in C^{2^n}) rather than discrete combinatorial
• Feasibility constraint is quantum (unit-norm quantum state) rather than classical
• The objective involves Hermitian operator eigenvalues, not combinatorial counting
• Complexity class (QMA) is strictly different from NP under standard assumptions

This is not a variant or renaming of any existing problem.

Correctness

References verified:

1. Kitaev (1997/2002): The issue cites "1999/2002" but the Russian Math. Surveys paper is from 1997 (volume 52, issue 6, pages 1191-1249). The DOI 10.1070/RM1997v052n06ABEH002155 is correct. Note: the 1997 paper covers quantum computation and error correction generally; the 5-local Hamiltonian QMA-completeness result appears in the 2002 book, not the 1997 paper. The issue's parenthetical "(Section 14.4: QMA-completeness of 5-local Hamiltonian)" is correctly attributed to the book.

2. Kitaev, Shen & Vyalyi (2002): Confirmed — "Classical and Quantum Computation," AMS Graduate Studies in Mathematics vol. 47. The AMS bookstore link is correct.

3. Kempe, Kitaev & Regev (2006): Confirmed — "The Complexity of the Local Hamiltonian Problem," SIAM J. Comput. 35(5), 1070-1097. DOI 10.1137/S0097539704445226 is correct. The paper does prove QMA-completeness of 2-local Hamiltonian.

4. Oliveira & Terhal (2008): Confirmed — "The complexity of quantum spin systems on a two-dimensional square lattice," Quantum Information & Computation 8, 900-924 (2008). arXiv: quant-ph/0504050. The claim about QMA-completeness on 2D lattice with 2-local terms is correct.

Complexity claims: The statements about QMA-completeness for k>=2 and polynomial-time solvability for k=1 are accurate.

Year error: The Kitaev paper should be cited as 1997, not 1999.

Well-written

Fails on architectural compatibility. The issue proposes a problem that fundamentally cannot implement the library's Problem trait:

1. dims() -> Vec<usize> requires a finite discrete configuration space. KLocalHamiltonian's configuration space is the unit sphere in C^{2^n} — a continuous manifold. The issue's Variables section acknowledges this ("each qubit lives in C^2; classically, a full state vector has 2^n complex amplitudes") but does not address how to discretize this for the trait.

2. evaluate(&self, config: &[usize]) -> Metric expects a discrete configuration &[usize]. There is no natural way to represent a quantum state as a sequence of small integers. The brute-force solver enumerates all configurations via dims() — this is impossible for a continuous space.

3. declare_variants! complexity string: The issue discusses complexity qualitatively but does not provide a concrete complexity expression using getter method variables (e.g., "2^num_qubits" or "8^num_qubits"). This is required for every model.

4. Schema completeness: The LocalTerm.matrix field uses Complex64, which is not a standard type in this crate. The issue does not address how complex number arithmetic would be integrated.

5. Missing solver integration details: The "How to solve" section checks brute-force, but exact diagonalization of a 2^n x 2^n Hermitian matrix is fundamentally different from the library's BruteForce solver (which enumerates discrete configurations). The issue does not explain how to bridge this gap.

Other well-written aspects (positive):

• The formal definition is mathematically precise
• Examples are non-trivial and fully worked with eigenvalues
• The relationship table to existing problems is excellent
• Symbol usage is consistent throughout

Recommendations

• Consider whether this problem should instead be tracked as a future extension requiring trait generalization (e.g., a ContinuousProblem trait), rather than a model issue under the current architecture
• If the goal is to connect quantum problems to the existing graph, consider proposing a classical restriction (e.g., DiagonalKLocalHamiltonian) that reduces to SpinGlass/QUBO and fits within the discrete Problem trait
• Fix the Kitaev citation year from 1999 to 1997
• Add a concrete declare_variants! complexity string (e.g., "8^num_qubits" for dense diagonalization or "2^num_qubits" for Lanczos-style approaches)

[GiggleLiu]

Closing as part of batch cleanup.