Information Theory & Cryptography

My research is in quantum information theory, with 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 my work are the following results:


I am 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 my work I 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.)