Approximation Algorithms for QMA-Complete Problems

DOI10.1137/110842272zbMATH Open1286.68496arXiv1101.3884OpenAlexW3106178575MaRDI QIDQ3143301FDOQ3143301

Julia Kempe, Sevag Gharibian

Publication date: 29 November 2012

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

Abstract: Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.

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

zbMATH Keywords

approximation algorithmconstraint satisfactionlocal HamiltonianQMA-complete

Mathematics Subject Classification ID

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

Cited In (6)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143301)