Approximation, Proof Systems, and Correlations in a Quantum World
arXiv:1301.2632
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 (89)
- Quantum entanglement
- Separability Criterion for Density Matrices
- A computable measure of entanglement
- Introducing Quantum Discord
- Quantum algorithm for solving linear systems of equations
- The density-matrix renormalization group
- Efficient classical simulation of slightly entangled quantum computations
- Classical, quantum and total correlations
- Quantifying Entanglement
- Entanglement Measures and Purification Procedures
- On the volume of the set of mixed entangled states
- Separability criterion and inseparable mixed states with positive partial transposition
- Quantum discord and the power of one qubit
- Mixed-state entanglement and distillation: is there a ``bound'' entanglement in nature?
- Necessary and sufficient condition for non-zero quantum discord
- The Role of Relative Entropy in Quantum Information Theory
- Thermodynamic limit of the density matrix renormalization for the spin-1 Heisenberg chain
- An Area Law for One Dimensional Quantum Systems
- On the Power of One Bit of Quantum Information
- Unified View of Quantum and Classical Correlations
- Geometric measure of entanglement and applications to bipartite and multipartite quantum states
- Noncommuting mixed states cannot be broadcast
- On the quantum, classical and total amount of correlations in a quantum state
- Information-theoretic aspects of quantum inseparability of mixed states
- Almost all quantum states have non-classical correlations
- Quantum versus classical correlations in Gaussian states
- Characterizing Entanglement
- Local versus non-local information in quantum information theory: formalism and phenomena
- No-local-broadcasting theorem for quantum correlations
- A complete family of separability criteria
- A class of ansatz wave functions for 1D spin systems and their relation to DMRG
- Entanglement and the Power of One Qubit
- Randomizing quantum states: Constructions and applications
- Interpreting quantum discord through quantum state merging
- Operational interpretations of quantum discord
- Separable states are more disordered globally than locally
- A Sharp Fannes-type Inequality for the von Neumann Entropy
- A generalized no-broadcasting theorem
- Largest separable balls around the maximally mixed bipartite quantum state
- Most quantum states are too entangled to be useful as computational resources
- Linking Quantum Discord to Entanglement in a Measurement
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- All non-classical correlations can be activated into distillable entanglement
- Sophisticated quantum search without entanglement
- Locking classical correlation in quantum states
- The power of quantum systems on a line
- N-representability is QMA-complete
- Signatures of non-classicality in mixed-state quantum computation
- Quantum cost for sending entanglement
- Hamiltonian complexity
- Separable states can be used to distribute entanglement
- Quantum query complexity of state conversion
- All entangled states are useful for information processing
- 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
- Quantum Computing Without Entanglement
- Separable balls around the maximally mixed multipartite quantum states
- Interplay between computable measures of entanglement and other quantum correlations
- Broadcast copies reveal the quantumness of correlations
- Assisted state discrimination without entanglement
- A new construction for a QMA complete 3-local Hamiltonian
- Generalized entropic measures of quantum correlations
- Quantum Correlations in Large-Dimensional States of High Symmetry
- Interacting boson problems are QMA-hard
- Maximally entangled three-qubit states via geometric measure of entanglement
- Quantum locking of classical correlations and quantum discord of classical-quantum states
- Quantifying non-classicality with local unitary operations
- Better bound on the exponent of the radius of the multipartite separable ball
- Merlin-Arthur Games and Stoquastic Complexity
- Entanglement entropy of multipartite pure states
- On product, generic and random generic quantum satisfiability
- Testing product states, quantum Merlin-Arthur games and tensor optimisation
- Measurable nonlocal effect of bipartite system during a local cyclic evolution of its subsystem
- Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
- Finding a maximally correlated state - Simultaneous Schmidt decomposition of bipartite pure states
- Nonclassical correlation in a multipartite quantum system: two measures and evaluation
- Entanglement quantification by local unitaries
- Characterization of separability and entanglement in - and -dimensional systems by single-qubit and single-qutrit unitary transformations
- Hardness of approximation for quantum problems
- An Efficient Algorithm for approximating 1D Ground States
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
- A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
- Local Hamiltonians in Quantum Computation
- "Quantumness" versus "Classicality" of Quantum States
- Improved Soundness for QMA with Multiple Provers
- BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
- The Local Consistency Problem for Stoquastic and 1-D Quantum Systems