Hamiltonian: The 2–local Hamiltonian $$H = \displaystyle\sum_{e\in E(G)} H_e + \displaystyle\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$^L_W(G)$

Hamiltonian: The 2–local Hamiltonian $$H = \displaystyle\sum_{e\in E(G)} H_e + \displaystyle\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

Hamiltonian: The 2–local Hamiltonian $$H = \displaystyle\sum_{e\in E(G)} H_e + \displaystyle\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

Hamiltonian: The 2–local Hamiltonian $$H = \displaystyle\sum_{e\in E(\Lambda)} H_e + \displaystyle\sum_{v\in V(\Lambda)}H_v$$

Problem: Ground state energy

Complexity: QMA–complete

Ref: [OT08]

Conditionals:

• 2–local interactions
• $\Lambda$ 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

Hamiltonian: The 2–local Real Hamiltonian $$H = \displaystyle\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

Hamiltonian: The 2–local Hamiltonian $$H = \displaystyle\sum_{e\in E(G)} H_e + \displaystyle\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

Hamiltonian: The 3–local Hamiltonian $$H = \displaystyle\sum_{j=1}^m H_j$$

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KR03]

Conditionals:

• $m = O\big(\mathsf{poly}(n)\big)$
• 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

Hamiltonian: The 3–local Hamiltonian $$H = \displaystyle\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

Hamiltonian: The 5–local Hamiltonian $$H = \displaystyle\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

Hamiltonian: The $O(\log n)$–local Hamiltonian $$H = \displaystyle\sum_{j=1}^m H_j$$

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KSV02]

Conditionals:

• $m = O\big(\mathsf{poly}(n)\big)$
• Each $H_j$ acts on at most $O(\log n)$ of the $n$ qubits

Reductions:

• To the 5–local Hamiltonian

Hamiltonian: The 5–local Hamiltonian $$H = \displaystyle\sum_{j=1}^m H_j$$

Problem: Ground state energy

Complexity: QMA–complete

Ref: [KSV02]

Conditionals:

• $m = O\big(\mathsf{poly}(n)\big)$
• 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

Hamiltonian: The 5–local Hamiltonian $$H = \displaystyle\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 $||\Pi_- \ket{s}|| \geq \delta^2$
• $\delta \in (0, 1 - \Omega(1/\mathsf{poly}(n)))$
• $a,b \in [0,1]$ such that $b-a \in \Omega(1/\mathsf{poly}(n))$
• $m = O\big(\mathsf{poly}(n)\big)$

Hamiltonian: The 2–local Hamiltonian $$H = \displaystyle\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 $||\Pi_- \ket{s}|| \geq \delta^2$
• $\delta \in (0, 1 - \Omega(1/\mathsf{poly}(n)))$
• $a,b \in [0,1]$ such that $b-a \in \Omega(1/\mathsf{poly}(n))$
• $m = O\big(\mathsf{poly}(n)\big)$

Reductions:

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

Hamiltonian: General $2$-local Hamiltonian $$H = \sum_{e\in E(G)} H_e$$

Problem: Partition function

Ref: [MH20]

Conditionals:

• $2$–local interactions
• $||H_e|| \leq 1$
• The interaction graph $G$ has maximum degree $\Delta$
• $\beta \in \mathbb{C}$
• $\beta \leq 1 / (e^4 \Delta)$

Hamiltonian: General $k$-local Hamiltonian $$H = \sum_{e\in E(G)} H_e$$

Problem: Partition function

Ref: [MM24]

Conditionals:

• $2$–local interactions
• $||H_e|| \leq 1$
• The interaction (hyper)graph $G$ has maximum degree $\Delta$
• $\beta \in \mathbb{C}$
• $\beta \leq 1 / (e^4 \Delta{k \choose 2})$

Hamiltonian: Stable quantum perturbations of a classical spin system Hamiltonian $$H = H_{\Phi} + \lambda H_{\Psi}$$

Problem: Partition function

Ref: [MH23]

Conditionals:

• $H_{\Phi}$ is diagonal in a basis indexed by a classical spin system
• $H_{\Psi}$ is local
• $|\lambda|$ is small and $|\lambda|\leq \lambda^{\star}$
• Stable quantum perturbation of classical spin system
• $G$ is a finite induced subgraph of $\mathbb{Z}^\nu$
• $\beta \geq \beta^{\star}$

Hamiltonian: The Ferromagnetic $q$-state Potts Model $$H(\sigma) = \sum_{\{i,j\} \in E(G)} \delta{\sigma_i \neq \sigma_j}$$

Problem: Partition function

Ref: [BCHPT19]

Conditionals:

• $G$ is $\mathbb{T}_n^d$ where $d\geq 2$
• $q \geq q_0(d)$
• $\beta \in \mathbb{R}^+$

Hamiltonian: $2$-local Hamiltonian $$H = \sum_j h_j$$

Problem: Low Complexity Low Energy States

Complexity: QCMA–complete

Ref: [Chen19]

Conditionals:

• $2$–local interactions

Hamiltonian: The 2D circuit-to-Hamiltonian $H_C$ $$H_C := H_{\mathrm{clock}} + H_{\mathrm{in}} + H_{\mathrm{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 = \mathrm{poly}(n)$ gates; $H_{\mathrm{clock}}, H_{\mathrm{in}}, H_{\mathrm{prop}}$ defined as in Definition 14
• Inverse temperature $\beta$ and time scale $\tau$ satisfy $0 \le \beta, \tau \le \mathrm{poly}(n)$
• $m = \mathrm{poly}(n)$ local jump operators $\{A_a\}$ generate the thermal Lindbladian
• Observable $O$ is single–qubit with $\|O\|_\infty \le 1$
• $\epsilon = 1/\mathrm{poly}(n)$ for $\epsilon$–approximate local minimum

Reductions:

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

Hamiltonian: Dense 2-local Hamiltonian $$H = \sum_{i\lt j} H_{ij}$$

Problem: Free energy approximation

Complexity: PTAS

Ref: [BCGW23]

Conditionals:

• H is $\Delta$–dense: $||H||_{\max} \leq \frac{1}{\Delta n^2}\sum ||H_{ij}||$
• Inverse temperature $\beta$
• Precision parameter $\varepsilon \in (0,1)$
• $n \ge \varepsilon^{–3}\Delta^{–2}$

Techniques:

• Convex relaxation
• Variational characterization
• Quantum rounding map

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
• $|\phi\rangle$ is a fixed state over $p < n$ qubits

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

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
• $\Delta$ exponentially–small

Hamiltonian: $3$-Local Hamiltonian $$H = \displaystyle\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(\mathsf{poly}(n))$
• There is a unique ground state

Techniques:

• Feynman–Kitaev circuit–to–Hamiltonian construction

Hamiltonian: The EXACT $3$-Local Hamiltonian $$H = \displaystyle\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(\mathsf{poly}(n))$

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$

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$

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
• $\Delta$ polynomially–small

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
• $\Delta$ exponentially–small
• $H$ on exponentially many qubits

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
• $\Delta$ is polynomially–small

Hamiltonian: $k$-Local Hamiltonian $$H = \displaystyle\sum_{j=1}^m H_j$$

Problem: Spectral Gap

Ref: [Amb14]

Conditionals:

• Each Hamiltonian term $H_j$ is $k$–local
• $m = O(\mathsf{poly}(n))$
• $\gamma \leq \frac{1}{\mathsf{poly}(n)}$ or $\gamma \geq \frac{2}{\mathsf{poly}(n)}$