The Hamiltonian Jungle | General Local

Key: 2LH901

Hamiltonian: The 2–local Hamiltonian

H = \sum_{e \in E (G)} H_{e} + \sum_{v \in V (G)} H_{v}

Problem: Extremal product state

Complexity: NP–complete

Ref: [KPT+24]

Conditionals:

2–local interactions
$G$ representing an interaction graph
Constant magnitude interaction strengths

Reductions:

From Max–Cut $_{W}^{L} (G)$

Key: 2LH04

Hamiltonian: The 2–local Hamiltonian

H = \sum_{e \in E (G)} H_{e} + \sum_{v \in V (G)} H_{v}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [OT08]

Conditionals:

2–local interactions
$G$ representing a spatially sparse graph

Reductions:

From 5–local Hamiltonian on a spatially sparse graph
To 2–local Hamiltonian on planar graph

Gadgets:

3–to–2 local

Key: 2LH05

Hamiltonian: The 2–local Hamiltonian

H = \sum_{e \in E (G)} H_{e} + \sum_{v \in V (G)} H_{v}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [OT08]

Conditionals:

2–local interactions
$G$ represents a planar graph
Pauli degree $\leq 3$

Reductions:

From 2–local Hamiltonian on a spatially sparse graph
To 2–local Hamiltonian on 2D square lattice

Gadgets:

Subdivision, Fork, Cross

Key: 2LH06

Hamiltonian: The 2–local Hamiltonian

H = \sum_{e \in E (Λ)} H_{e} + \sum_{v \in V (Λ)} H_{v}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [OT08]

Conditionals:

2–local interactions
$Λ$ represents a 2D square lattice
Pauli degree $\leq 3$

Reductions:

From 2–local Hamiltonian on planar graph via embedding on a square lattice of sufficient granularity
To Heisenberg Hamiltonian with external field on spatially sparse graph

Key: 2LH07

Hamiltonian: The 2–local Real Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [BL08]

Conditionals:

2–local interactions
Real coefficients and gates

Reductions:

From 2–local Hamiltonian
To an instance of the (x–z/x–z)–Hamiltonian on some interaction graph and an instance of the ( $[[$ xz $]]$ ^*/x–z)–Hamiltonian on some interaction graph

Key: 2LH15

Hamiltonian: The 2–local Hamiltonian

H = \sum_{e \in E (G)} H_{e} + \sum_{v \in V (G)} H_{v}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KKR05]

Conditionals:

2–local interactions
$G$ representing an interaction graph

Reductions:

From the 3–local Hamiltonian
To the 2–local Hamiltonian on a spatially sparse lattice and the 2–local real Hamiltonians

Gadgets:

3–to–2 local

Key: 3LH13

Hamiltonian: The 3–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KR03]

Conditionals:

$m = O (poly (n))$
Each $H_{j}$ acts on at most 3 of the $n$ qubits

Reductions:

From the 5–local Hamiltonian
To the 3–local Hamiltonian on a spatially sparse lattice and the 3–local real Hamiltonian

Key: 3LH14

Hamiltonian: The 3–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [W23]

Conditionals:

3–local interactions
A spatially sparse interaction graph

Reductions:

From the 3–local Hamiltonian or the 5–local Hamiltonian on a spatially sparse graph
To the 2–local Hamiltonian on a spatially sparse lattice

Key: kLH10

Hamiltonian: The 5–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [OT08]

Conditionals:

5–local interactions
A spatially sparse interaction graph

Reductions:

From 5–local Hamiltonian on a generic graph
To 2–local Hamiltonian on a spatially sparse graph

Key: kLH11

Hamiltonian: The

O (\log n)

–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KSV02]

Conditionals:

$m = O (poly (n))$
Each $H_{j}$ acts on at most $O (\log n)$ of the $n$ qubits

Reductions:

To the 5–local Hamiltonian

Key: kLH12

Hamiltonian: The 5–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KSV02]

Conditionals:

$m = O (poly (n))$
Each $H_{j}$ acts on at most 5 of the $n$ qubits

Reductions:

From the $O (\log n)$ –local Hamiltonian
To the 5–local Hamiltonian on a spatially sparse lattice and the 3–local Hamiltonian

Key: GLH01

Hamiltonian: The 5–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy (Guided)

Complexity: BQP–hard

Ref: [CFG+23]

Conditionals:

A (semi–classical) guiding state such that $| | Π_{-} | s ⟩ | | \geq δ^{2}$
$δ \in (0, 1 - Ω (1 / poly (n)))$
$a, b \in [0, 1]$ such that $b - a \in Ω (1 / poly (n))$
$m = O (poly (n))$

Key: GLH02

Hamiltonian: The 2–local Hamiltonian

H = \sum_{j = 1}^{m} H_{j}

Problem: Ground state energy (Guided)

Complexity: BQP–hard

Ref: [CFG+23]

Conditionals:

A (semi–classical) guiding state such that $| | Π_{-} | s ⟩ | | \geq δ^{2}$
$δ \in (0, 1 - Ω (1 / poly (n)))$
$a, b \in [0, 1]$ such that $b - a \in Ω (1 / poly (n))$
$m = O (poly (n))$

Reductions:

From the $5$ –local Hamiltonian (guided) problem
To $2$ –local Hamiltonians such as the (xy/.) and Heisenberg Hamiltonians

Key: PFP-2LH-001

Hamiltonian: General

2

-local Hamiltonian

H = \sum_{e \in E (G)} H_{e}

Problem: Partition function

Complexity: FPTAS

Ref: [MH20]

Conditionals:

$2$ –local interactions
$| | H_{e} | | \leq 1$
The interaction graph $G$ has maximum degree $Δ$
$β \in C$
$β \leq 1 / (e^{4} Δ)$

Key: PFP-kLH-001

Hamiltonian: General

k

-local Hamiltonian

H = \sum_{e \in E (G)} H_{e}

Problem: Partition function

Complexity: FPTAS

Ref: [MM24]

Conditionals:

$2$ –local interactions
$| | H_{e} | | \leq 1$
The interaction (hyper)graph $G$ has maximum degree $Δ$
$β \in C$
$β \leq 1 / (e^{4} Δ (\binom{k}{2}))$

Key: PFP-GLH-001

Hamiltonian: Stable quantum perturbations of a classical spin system Hamiltonian

H = H_{Φ} + λ H_{Ψ}

Problem: Partition function

Complexity: FPTAS

Ref: [MH23]

Conditionals:

$H_{Φ}$ is diagonal in a basis indexed by a classical spin system
$H_{Ψ}$ is local
$| λ |$ is small and $| λ | \leq λ^{⋆}$
Stable quantum perturbation of classical spin system
$G$ is a finite induced subgraph of $Z^{ν}$
$β \geq β^{⋆}$

Key: PFP-GLH-002

Hamiltonian: The Ferromagnetic

q

-state Potts Model

H (σ) = \sum_{{i, j} \in E (G)} δ σ_{i} \neq σ_{j}

Problem: Partition function

Complexity: FPRAS

Ref: [BCHPT19]

Conditionals:

$G$ is $T_{n}^{d}$ where $d \geq 2$
$q \geq q_{0} (d)$
$β \in R^{+}$

General Local Models