arXiv 1301.2632
Approximation, Proof Systems, and Correlations in a Quantum World
By Sevag Gharibian
Published 2013-01-11
Mindmap
Browse the paper's core ideas, clusters, and relationships in a structured outline.
This thesis studies three topics in quantum computation and information: The approximability of quantum problems, quantum proof systems, and non-classical correlations in quantum systems. In the first area, we demonstrate a polynomial-time (classical) approximation algorithm for dense instances of the canonical QMA-complete quantum constraint satisfaction problem, the local Hamiltonian problem. In the opposite direc…