arXiv 1301.2632
Approximation, Proof Systems, and Correlations in a Quantum World
By Sevag Gharibian
Published 2013-01-11
Wiki summary
Explore the paper's summary, context, and related research on Papiers.
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…