Hardness of Approximation for Quantum Problems

DOI10.1007/978-3-642-31594-7_33zbMath1272.68133arXiv1209.1055OpenAlexW2952437585MaRDI QIDQ2843264

Sevag Gharibian, Julia Kempe

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (7)

Ground State Connectivity of Local Hamiltonians ⋮ Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\) ⋮ Unnamed Item

This page was built for publication: Hardness of Approximation for Quantum Problems