---
res:
bibo_abstract:
- "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. \r\n\r\nIn 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 direction, we next introduce a quantum generalization of the polynomial-time
hierarchy, and define problems which we prove are not only complete for the second
level of this hierarchy, but are in fact hard to approximate. \r\n\r\nIn the second
area, we study variants of the interesting and stubbornly open question of whether
a quantum proof system with multiple unentangled quantum provers is equal in expressive
power to a proof system with a single quantum prover. Our results concern classes
such as BellQMA(poly), and include a novel proof of perfect parallel repetition
for SepQMA(m) based on cone programming duality. \r\n\r\nIn the third area, we
study non-classical quantum correlations beyond entanglement, often dubbed \"non-classicality\".
Among our results are two novel schemes for quantifying non-classicality: The
first proposes the new paradigm of exploiting local unitary operations to study
non-classical correlations, and the second introduces a protocol through which
non-classical correlations in a starting system can be \"activated\" into distillable
entanglement with an ancilla system. \r\n\r\nAn introduction to all required linear
algebra and quantum mechanics is included.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
dct_date: 2013^xs_gYear
dct_language: eng
dct_title: Approximation, Proof Systems, and Correlations in a Quantum World@
...