Stoquastic Models

Key: LHP-SLH-001
Hamiltonian: The 6-Local Stoquastic Hamiltonian H=∑j=1mHj
Problem: Local Hamiltonian
Complexity: StoqMA–complete
Ref: [BBT06]
Conditionals:
  • Each Hamiltonian term Hj is stoquastic
  • Each Hj acts on at most 6 of the n qubits
  • m=O(poly(n))
Reductions:
  • To the 2–local stoquastic Hamiltonian
Key: LHP-SLH-002
Hamiltonian: The 2-Local Stoquastic Hamiltonian H=∑j=1mHj
Problem: Local Hamiltonian
Complexity: StoqMA–complete
Ref: [BBT06]
Conditionals:
  • Each Hamiltonian term Hj is stoquastic
  • Each Hj acts on at most 2 of the n qubits
  • m=O(poly(n))
Reductions:
  • To the 2–local stoquastic Hamiltonian
Techniques:
  • Subdivision gadget
  • 3–to–2 local gadget
Key: QMC*-SLH-001
Hamiltonian: The weighted (xyz/.) Hamiltonian HQMC(EPR)(G)=12∑{i,j}∈E(G)wij(I+XiXj−YiYj+ZiZj)
Problem: Quantum Max-Cut (EPR)
Complexity: StoqMA
Ref: [Kin23]
Conditionals:
  • The graph G has edge weights wij
  • wij≥0 and wij=O(poly(n))
  • $S_{i}\in\{\pm 1\}
Key: PLHP-SLH-001
Hamiltonian: Pinned Stoquastic 3-Local Hamiltonian H=∑j=1mHj
Problem: Pinned Stoquastic Local Hamiltonian
Complexity: QMA–complete
Ref: [NHES20]
Conditionals:
  • 3–local interactions
  • stoquastic interactions
  • |ϕ⟩ is a fixed state over p<n qubits
Key: GSCON-SLH-005
Hamiltonian: 5-Local Stoquastic Hamiltonian H=∑j=1mHj
Problem: Ground state connectivity
Complexity: QCMA–complete
Ref: [NHES20]
Conditionals:
  • 5–local interactions
  • stoquastic interactions
  • 2–local unitaries
  • Δ is polynomially–small