Approximation, Proof Systems, and Correlations in a Quantum World

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. 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 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. In 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. In 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. An introduction to all required linear algebra and quantum mechanics is included.

PhD Thesis, 240 pages

References in corpus (32)

• Quantum algorithm for solving linear systems of equations
• Quantum discord and the power of one qubit
• Necessary and sufficient condition for non-zero quantum discord
• On the quantum, classical and total amount of correlations in a quantum state
• No-local-broadcasting theorem for quantum correlations
• A complete family of separability criteria
• Randomizing quantum states: Constructions and applications
• Interpreting quantum discord through quantum state merging
• Operational interpretations of quantum discord
• A generalized no-broadcasting theorem
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Linking Quantum Discord to Entanglement in a Measurement
• All non-classical correlations can be activated into distillable entanglement
• The power of quantum systems on a line
• N-representability is QMA-complete
• Quantum cost for sending entanglement
• Correlations in local measurements on a quantum state, and complementarity as an explanation of nonclassicality
• Quantum NP - A Survey
• Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases
• Broadcast copies reveal the quantumness of correlations
• A new construction for a QMA complete 3-local Hamiltonian
• Maximally entangled three-qubit states via geometric measure of entanglement
• Merlin-Arthur Games and Stoquastic Complexity
• Nonclassical correlation in a multipartite quantum system: two measures and evaluation
• Finding a maximally correlated state - Simultaneous Schmidt decomposition of bipartite pure states
• Entanglement quantification by local unitaries
• Characterization of separability and entanglement in $(2\times D)$- and $(3\times D)$-dimensional systems by single-qubit and single-qutrit unitary transformations
• Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
• Local Hamiltonians in Quantum Computation
• "Quantumness" versus "Classicality" of Quantum States
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems