Approximation Algorithms for QMA-Complete Problems

DOI10.1137/110842272zbMath1286.68496arXiv1101.3884OpenAlexW3106178575MaRDI QIDQ3143301

Sevag Gharibian, Julia Kempe

Publication date: 29 November 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.3884

zbMATH Keywords

approximation algorithmconstraint satisfactionlocal HamiltonianQMA-complete

Mathematics Subject Classification ID

Quantum computation (81P68) Many-body theory; quantum Hall effect (81V70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for quantum many-body problems ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Product-state approximations to quantum states

This page was built for publication: Approximation Algorithms for QMA-Complete Problems