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^{+}$

Key: LCLES-2LH-001

Hamiltonian:

2

-local Hamiltonian

H = \sum_{j} h_{j}

Problem: Low Complexity Low Energy States

Complexity: QCMA–complete

Ref: [Chen19]

Conditionals:

$2$ –local interactions

Key: LMTP-2LH-001

Hamiltonian: The 2D circuit-to-Hamiltonian

H_{C}

H_{C} := H_{clock} + H_{in} + H_{prop}

Problem: Local minimum under thermal perturbations

Complexity: BQP–hard

Ref: [CHPZ23]

Conditionals:

Hamiltonian $H_{C}$ encodes a polynomial–size quantum circuit $U_{C}$ via a modified Kitaev circuit–to–Hamiltonian construction on a 2D lattice with $n + T$ qubits
$T = poly (n)$ gates; $H_{clock}, H_{in}, H_{prop}$ defined as in Definition 14
Inverse temperature $β$ and time scale $τ$ satisfy $0 \leq β, τ \leq poly (n)$
$m = poly (n)$ local jump operators ${A_{a}}$ generate the thermal Lindbladian
Observable $O$ is single–qubit with $‖ O ‖_{\infty} \leq 1$
$ϵ = 1 / poly (n)$ for $ϵ$ –approximate local minimum

Reductions:

From any polynomial–time quantum decision problem via circuit–to–Hamiltonian

Key: FEP-2LH-001

Hamiltonian: Dense 2-local Hamiltonian

H = \sum_{i < j} H_{i j}

Problem: Free energy approximation

Complexity: PTAS

Ref: [BCGW23]

Conditionals:

H is $Δ$ –dense: $| | H | |_{max} \leq \frac{1}{Δ n^{2}} \sum | | H_{i j} | |$
Inverse temperature $β$
Precision parameter $ε \in (0, 1)$
$n \geq ε^{- 3} Δ^{- 2}$

Techniques:

Convex relaxation
Variational characterization
Quantum rounding map

Key: PLH-2LH-001

Hamiltonian: The Pinned 2-Local Hamiltonian

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

Problem: Pinned Local Hamiltonian

Complexity: QMA–complete

Ref: [NHES20]

Conditionals:

$2$ –local interactions
$| ϕ ⟩$ is a fixed state over $p < n$ qubits

Key: LCLES-3LH-001

Hamiltonian:

3

-local Hamiltonian

H = \sum_{j} h_{j}

Problem: Low Complexity Low Energy States

Complexity: QCMA–complete

Ref: [WJB03]

Conditionals:

$3$ –local interactions
Gates in the Shor basis

Key: GSCON-3LH-001

Hamiltonian:

3

-local Hamiltonian

H = \sum_{j} h_{j}

Problem: Ground State Connectivity

Complexity: PSPACE–complete

Ref: [GS15]

Conditionals:

$3$ –local interactions
$1$ –local unitaries
$Δ$ exponentially–small

Key: ULHP-3LH-001

Hamiltonian:

3

-Local Hamiltonian

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

Problem: Unique Local Hamiltonian

Complexity: UQMA–complete

Ref: [Amb14]

Conditionals:

Each Hamiltonian term $H_{j}$ is $3$ –local
$m = O (poly (n))$
There is a unique ground state

Techniques:

Feynman–Kitaev circuit–to–Hamiltonian construction

Key: ELHP-3LH-001

Hamiltonian: The EXACT

3

-Local Hamiltonian

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

Problem: Exact Local Hamiltonian

Complexity: DQMA–complete

Ref: [Amb14]

Conditionals:

Each Hamiltonian term $H_{j}$ is $3$ –local
$m = O (poly (n))$

Key: APXSIM-kLH-001

Hamiltonian:

5

-local Hamiltonian

H

and

1

-lcoal observable

A

H = \sum_{j} h_{j}

Problem: Approximate Simulation

Complexity: P^QMA[log]–complete

Ref: [GY19]

Conditionals:

$5$ –local Hamiltonian interactions
$1$ –local observable $A$

Key: APXCORR-kLH-001

Hamiltonian:

5

-local Hamiltonian

H

and a pair of

1

-local observables

A

and

B

H = \sum_{j} h_{j}

Problem: Approximate Correlation

Complexity: P^QMA[log]–complete

Ref: [GY19]

Conditionals:

$5$ –local Hamiltonian interactions
$1$ –local observables $A$ and $B$

Key: GSCON-kLH-001

Hamiltonian:

5

-local Hamiltonian

H = \sum_{j} h_{j}

Problem: Ground State Connectivity

Complexity: QCMA–complete

Ref: [GS15]

Conditionals:

$5$ –local interactions
$2$ –local unitaries
$Δ$ polynomially–small

Key: GSCON-kLH-101

Hamiltonian:

5

-local Hamiltonian

H = \sum_{j} h_{j}

Problem: Succinct Ground State Connectivity

Complexity: NEXP–complete

Ref: [GS15]

Conditionals:

$5$ –local interactions
$1$ –local unitaries
$Δ$ exponentially–small
$H$ on exponentially many qubits

Key: CGSCON-kLH-001

Hamiltonian:

21

-local Hamiltonian

H = \sum_{j} h_{j}

Problem: Commuting Ground State Connectivity

Complexity: QCMA–complete

Ref: [GMV17]

Conditionals:

$21$ –local interactions
Commuting interactions
$2$ –local unitaries
$Δ$ is polynomially–small

Key: SG-kLH-001

Hamiltonian:

k

-Local Hamiltonian

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

Problem: Spectral Gap

Complexity: P^QMA[log]

Ref: [Amb14]

Conditionals:

Each Hamiltonian term $H_{j}$ is $k$ –local
$m = O (poly (n))$
$γ \leq \frac{1}{poly (n)}$ or $γ \geq \frac{2}{poly (n)}$

General Local Models