All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

Convexity and Positivity in Quantum Information: Part I

Howard Barnum, Los Alamos National Laboratory

(Session 101 : Thursday from 16:00-18:00)

Abstract. Convex sets and convex cones occur frequently in quantum information theory. For example, normalized density matrices, completely positive maps, separable states, and POVMs all form convex sets. Finding an optimal quantum information processing protocol can often be cast as minimizing a linear function over a compact convex set, a problem for which much is known. This tutorial will cover some of the basic theory of convex sets and optimization over them, and applications to quantum information processing.

The first half of the tutorial will be given by Howard Barnum and will focus on the basic theory in finite dimensions, with topics selected for their applicability to quantum information. It will cover the following:

Outline of Tutorial:

I. Basic definitions and facts
• Definition of convex and affine sets.
• Compact convex sets, preservation of convexity by affine maps.
• Krein-Milman theorem.
• Brief note on infinite vs. finite dimension.
• Caratheodory's theorem.
• Suspending d-dimensional convex sets as cone bases in d+1 real dimensions.
• Regular (convex, pointed, full, closed) cones.
• Ordered linear spaces, equivalence of OLS's to spaces with distinguished regular cones.
• Examples: positive orthant, Lorentz cones, and positive semidefinite matrices.
• Quantum information examples: unentangled states, positive maps, and completely positive maps.
II. Separation and duality
• Separating hyperplanes, separation theorems.
• Definition of dual cone.
• Exposed points.
• Order units and operational theories.
• Direct sums of cones.
• Simplices: equivalent definitions, simplices as state-spaces of classical theories. Homogeneity, self-duality, examples.
• Koecher-Vinberg characterization of self-dual homogeneous cones.
III. Optimization and applications
• Basic results about optimizing convex and concave functions over compact convex sets.
• General conic convex programming with linear objective function.
• Linear, quadratic, and semidefinite programming.
• Different presentations of programs.
• Sufficient conditions for efficient algorithms; ellipsoid and other methods; LP/SDP/quadratic examples. NP-hard examples.
• Hard convex-set membership problems and Gurvits' proof of NP-hardness of entanglement testing.
• Quantum applications of SDP.
• Reducing dimension with symmetry.
• Duality in convex conic optimization, lower bounds on query complexity via relaxation and duality (if time permits).
  
  

Basing quantum theory on information-processing principles

Howard Barnum, Los Alamos National Laboratory

(Session 5 : Friday from 18:00-20:00)

Abstract. The rise of quantum information science has been paralleled by the development of a vigorous research program aimed at obtaining an informational characterization or reconstruction of the quantum formalism, in a broad framework for stochastic theories that encompasses quantum and classical theory, but also a wide variety of other theories that can serve as foils to them. Such a reconstruction, at its most ambitious, is envisioned as playing a role in quantum physics similar to Einstein's reconstruction of the dynamics and kinetics of macroscopic bodies, and later of their gravitational interactions, on the basis of simple principles with clear operational meanings and experimental consequences. Short of such an ambitious goal, it could still lead to a principled understanding of the features of quantum mechanics that account for its greater-than-classical information-processing power, an understanding which could help guide the search for new quantum algorithms and protocols.

As part of this project, I give a precis of the convex operational framework for possible physical theories, and review work by me and my collaborators, on the information-processing properties of theories in this framework. The main results reviewed are the the fact that the only information that can be obtained in the framework without disturbance is inherently classical, no-cloning and no-broadcasting theorems in the generalized framework, the existence of exponentially secure bit commitment in non-classical theories without entanglement, and the consequences for theories of the existence of a conclusive teleportation scheme. I'll also discuss sufficient conditions for "remote steering" of ensembles using entanglement, rendering insecure bit commitment protocols of the form shown to be secure in the unentangled case.

Acknowledgements: Joint work with various groups of collaborators including Jonathan Barrett, Matthew Leifer, Alexander Wilce, Oscar Dahlsten, and Ben Toner.

Howard Barnum,

(Session 8 : Saturday from )

Abstract.