Approximation algorithms for QMA-complete problems

DOI10.1137/110842272MaRDI QIDQ3143301zbMATH OpenOpenAlexFDO

Authors 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

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)

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.

Recommendations

• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• The Complexity of the Local Hamiltonian Problem
• Product-state approximations to quantum ground states
• Hardness of approximation for quantum problems
• Complexity classification of local Hamiltonian problems

Cited in

(9)

• scientific article; zbMATH DE number 7651034 (Why is no real title available?)
• scientific article; zbMATH DE number 7650098 (Why is no real title available?)
• Consistency of Local Density Matrices Is QMA-Complete
• Product-state approximations to quantum ground states
• scientific article; zbMATH DE number 7758361 (Why is no real title available?)
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• Hardness of approximation for quantum problems
• Product-state approximations to quantum states
• Approximation algorithms for quantum many-body problems

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)