skip to content

Mathematical challenges in quantum information

Participation in INI programmes is by invitation only. Anyone wishing to apply to participate in the associated workshop(s) should use the relevant workshop application form.

27th August 2013 to 20th December 2013

Organisers: Richard Jozsa (Cambridge), Noah Linden (Bristol), Peter Shor (MIT) and Andreas Winter (Bristol/Barcelona)

Programme Theme

Image showing Paul Dirac and Claude Shannon

Quantum information is currently one of the most dynamic and exciting areas of science and technology. Its breadth of significance ranges from deep fundamental issues of the ultimate physical limits of information processing and foundations of quantum mechanics, to the technological exploitation of quantum physics for exponentially enhanced computing power and novel possibilities for communication and information security. It is a highly cross-disciplinary subject with essential inputs from computer science, information theory, mathematics, quantum physics, engineering and others. In view of the central role of information processing and communication in most aspects of modern society, government and daily life, the transformative potential of Quantum Information for 21st century technology is immense.

A notable aspect of many of the most important recent developments is the importance of increasingly sophisticated techniques from mathematics and theoretical computer science: examples include the use of random states and operations, techniques from operator theory and functional analysis, and convex geometry. The range of mathematical techniques already employed is diverse, but the expertise is rather scattered within the community. We also see other areas of mathematics that offer the potential to make a major future impact in the field, random matrix theory being an example of particular current interest.

Among the mathematical challenges addressed during the semester will be some of the big open questions in the field, as well as recently opened up directions:

  • Additivity violations of capacities and minimal output entropies; “weak additivity” for certain quantities?
  • Existence of bound entanglement with non-positive partial transpose? The question, originally of information theoretic origin, can be cast as a problem about positivity and 2-positivity of matrix maps.
  • Abstract positivity and complete positivity: In quantum zero-error communication a link to operator systems was exhibited, promising a functional analytic generalisation of graph theory.
  • Techniques from convexity and convex optimisation have had high impact in non-local games. One question of particular importance is whether non-local games with shared entanglement obey a parallel repetition theorem (Raz) – this is known with only classical correlation and with arbitrary no-signalling help, but for shared entanglement it is only proved in special cases. Another one is the complexity of maximum quantum violations of Bell inequalities.
  • Is there a quantum version of the PCP theorem? Likewise, it is open whether in QMA, witnesses can be made unique (echoing a well-known classical probabilistic reduction of Valiant-Vazirani).
  • Measurement-based quantum computation poses questions on characterising the complexity of quantum computations via the properties of the “resource states” used.
  • Random matrix theory: starting with its use in proofs of non-additivity, new problems motivated by quantum information have emerged. These include largest eigenvalue fluctuations and spectra of higher tensor equivalents of Wishart ensembles; perturbations of Wigner ensembles by diagonal matrices with fixed or deterministic statistics – information on the distribution of eigenvectors of such matrices would have deep implications on quantum statistical mechanics.

We plan to hold a week-long workshop at the beginning, drawing together all topics of the above proposal. In addition we propose to hold a smaller and more focussed workshop, in the middle of the meeting. Finally we will hold a workshop at the end of the programme that will survey the state of the field as it stands following the work during the programme; there will be an emphasis on open problems and directions for the future.

Details on all workshops can be found on the Workshop page.


Image of Claude Shannon copyright MFO


Final Scientific Report: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons