arXiv 1301.2632
Approximation, Proof Systems, and Correlations in a Quantum World
By Sevag Gharibian
Published 2013-01-11
Citation lineage
Review the prior work and downstream research connected to this paper.
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…