3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH

Documenti analoghi

• Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
  di: Chia, Nai-Hui, et al.
  Pubblicazione: (2026)
• Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
  di: Gall, François Le
  Pubblicazione: (2024)
• Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
  di: Mao, Songtao
  Pubblicazione: (2026)
• Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
  di: Esmer, Barış Can, et al.
  Pubblicazione: (2022)
• Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
  di: Kumar, Mrinal, et al.
  Pubblicazione: (2024)