Information Theory & Cryptography

Our research in quantum information theory has a focus on quantum Shannon theory and quantum cryptography. The former is about the general theory of information processing in the quantum setting, whereas the latter is more specifically about techniques for secure communication in the presence of malicious parties. Good examples for our work are the following results:

• The uncertainty principle in the presence of quantum memory
  Mario Berta, Matthias Christandl, Roger Colbeck, Joseph M. Renes, and Renato Renner
  Manifold applications of this extended uncertainty principle – in particular in quantum cryptography – are discussed in our recent review article Entropic uncertainty relations and their applications.

• One-shot decoupling
  Frédéric Dupuis, Mario Berta, Jürg Wullschleger, and Renato Renner
  Applications of decoupling range from quantum Shannon theory to quantum cryptography to quantum thermodynamics to quantum many body physics to the study of black hole radiation. We were able to extend our results to Catalytic decoupling of quantum information and Conditional decoupling of quantum Information.

Algorithms

We are interested in the development and rigorous complexity analysis of quantum algorithms for the early fault-tolerance regime. Here, quantum processing units feature a limited number of logical qubits allowing to run small size digital schemes. The idea is to (i) allow for strong parallelization of quantum routines (ii) complement these quantum efforts with extensive use of classical pre- and post-processing, and (iii) avoid or minimize the use of QRAM:

• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
  Sam McArdle, András Gilyén, and Mario Berta
  Topological invariants of a dataset, such as the number of holes that survive from one length scale to another can be used to analyse and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms.
• Randomized quantum algorithm for statistical phase estimation
  Kianna Wan, Mario Berta, and Earl T. Campbell

  We propose and rigorously analyze a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, such as those based on qDRIFT, all algorithmic errors in our method can be suppressed by collecting more data samples, without increasing the circuit depth.

Mathematics of Quantum Information

In our work, we focus on the underlying mathematical methods, including in particular matrix analysis and optimization theory. Good examples for this fruitful interplay are the following results:

• Multivariate trace inequalities
  David Sutter, Mario Berta, and Marco Tomamichel
  From the abstract: We prove several trace inequalities that extend the Golden-Thompson and the Araki-Lieb-Thirring inequality to arbitrarily many matrices.  Our proofs rely on complex interpolation theory as well as asymptotic spectral pinching, providing a transparent approach to treat generic multivariate trace inequalities. As an application, we prove explicit remainder terms for the monotonicity of the quantum relative entropy and strong sub-additivity of the von Neumann entropy in terms of recoverability, which are tight in the commutative case.

• Quantum bilinear optimization
  Mario Berta, Omar Fawzi and Volkher B. Scholz
  From the abstract: We study optimization programs given by a bilinear form over non-commutative variables subject to linear inequalities. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. As applications we study the entangled value of two-prover games, entanglement assisted channel coding, quantum-proof randomness extractors, and the positive semidefinite cone as introduced by Laurent and Piovesan.

Some introductory books and notes can be found under links. (More detailed research statement available upon request.)