Research Highlights

In collaboration with researchers from QuSoft in Amsterdam, we provided a tool to study asymptotic transformations of multiparticle entanglement. Our work has also applications in algebraic complexity and combinatorics.

In order to understand the power of quantum computation, it is important to understand the entanglement properties of many-particle quantum systems. Multiparticle entanglement, however, is notoriously difficult to study, even in the setting of local operations and classical communication which may be executed stochastically (SLOCC), as there are an infinite number of different types of entanglement.

Using a connection between quantum states of multiple particles and the mathematical concept of a tensor (a multi-dimensional array of numbers), we have investigated this classification in an asymptotic setting, where many copies of a quantum state are given. In classical information theory, such a scenario has first been studied by Shannon and our work now builds on the tensor version of Strassen from the 1980s.

Building on earlier work on entanglement polytopes, we have constructed the Quantum functionals as the first family of multiplicative entanglement monotones. Quantum functionals can be used as lower bounds on entanglement transformations.

M. Christandl, P. Vrana & J. Zuiddam, Universal points in the asymptotic spectrum of tensors, Journal of the American Mathematical Society, 36, 31–79, 2023.

M. Walter, B. Doran, D. Gross and M. Christandl, Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information, Science, 340, 1205, 2013

We show that quantum communication can be performed at optimal rates even if the encoding and decoding devices are noisy – the standard situation for realistic quantum devices. Our work paves the way for optimal connecting quantum computers.

The standard paradigm in classical as well as quantum communication theory assumes that a noisy communication channel is given and that noise-free encoders and decoders prepare the codes for optimal communication. Essentially all of classical and quantum information theory has been built on this scenario and books have been written about the subject.

Whereas this is a realistic scenario in classical communication theory, it is not believed that noise-free quantum devices can be produced in the mid- or even long-term. This raises the question how well (if at all) noisy quantum devices can be used. Inspired by threshold theorems for quantum computation that allow to perform exact computation on top of noisy hardware, we have proved a threshold theorem for quantum communication: For low gate noise, it is indeed possible to communicate almost at the same rate as in the noiseless case.

This establishes a fundamental theorem about the possibility of quantum communication and computation in a network and paves the way for future work towards practical implementation of a quantum internet.

M. Christandl and A. Müller-Hermes, Fault-tolerant coding for quantum communication, IEEE Trans. Inf. Th. (2022)

Cold atomic gases are an important ingredient in quantum simulators. We recently solved a 60 year old conjecture about its behaviour, a result that led to the Henri Poincare prize to Prof. Jan Philip Solovej.

Bose gases exhibit both Bose-Einstein condensation (BEC) as well as superfluidity at very low temperature. In 1957, Lee, Huang, and Yang suggested a two term asymptotic formula for the ground state energy of a Bose gas in the dilute limit. The formula can be seen as a sign of the superfluid character of the gas and has been verified in recent experiments. Lee, Huang and Yang analysed the hard sphere gas but predicted that the formula should be universally valid for much more general interaction potentials. This universal formula was finally established in 2020 by Søren Fournais and Jan Philip Solovej. The first paper, however, did not cover the hard sphere case as it posed some serious mathematical difficulties. In 2022, Fournais and Solovej established that the Lee-Huang-Yang formula gives a valid lower bound on the ground state energy also for the hard sphere gas. The matching upper bound is the final missing piece to this, over half a century, old problem.

The energy of dilute Bose gases
By: Fournais, Søren; Solovej, Jan Philip
Annals of Mathematics, 192, 3, 893–976. Published: Nov 2020

The energy of dilute Bose gases II: the general case.
By: Fournais, Søren; Solovej, Jan Philip
Invent. math. Published online 2022

In a series of works together with my co-authors we have introduced and developed a theory around graph-based nonlocal games [1,2]. These games allow for quantum generalisations of classical graph-theoretic notions such as independence number, graph homomorphism and isomorphism. They open a new interdisciplinary area of quantum graph theory with rich connections to combinatorics, quantum groups, counting complexity, and other fields. Entanglement-assisted strategies for general nonlocal games are mathematically unwieldy. In contrast, our quantum morphisms provide a highly structured combinatorial setting, in which to study the power and limitations of quantum entanglement and explore how it can be harnessed by distant agents. These games have gained popularity and their mathematical structure has been independently investigated from the perspectives of operator algebras, optimisation, category theory, and others. This line of work has culminated in a result [3] that deeply links together central concepts from three different fields of research: quantum information, discrete mathematics, and quantum groups. A classic result of Lovasz says that two graphs are the same if and only if they have the same homomorphism counts from all graphs. In [3] we show that two graphs are quantum isomorphic if and only if they have the same homomorphism counts from all planar graphs. This characterisation of quantum isomorphism opens up the possibility to study entanglement using combinatorial tools.

1. Quantum homomorphisms.
   Laura Mančinska, David E. Roberson.
   Journal of Combinatorial Theory, Series B 118(C), 228–267, 2016, arXiv:1212.1724.
2. Quantum and non-signalling graph isomorphisms.
   Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, Antonios Varvitsiotis.
   Journal of Combinatorial Theory, Series B 136, 289–328, 2019, arXiv:1611.09837.
3. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. Laura Mančinska, David E. Roberson.
   Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS'20), 661–672, 2020, arXiv:1910.06958.

In collaboration with researchers from IBM Watson, the University of Waterloo, and the National University of Singapore, we provided the first unconditional proof of a quantum advantage of faulty quantum computers.

A key challenge lying at the heart of quantum computing is to prove that quantum computers indeed provide computational advantages over comparable classical devices. In order to do so, scientists face the task of finding computational problems that can be solved efficiently by a quantum circuit, but cannot be solved using similar classical computational resources. In a previous paper titled "Quantum advantage with shallow circuits" a theoretical result demonstrated that shallow quantum circuits are strictly more powerful than analogous classical circuits. While this result is of complexity-theoretic interest because it does not rely on any unproven hardness assumptions, its relevance to experimental quantum computing is limited – it is assumed that quantum circuits can be executed perfectly, i.e. without any errors (or noise). This limitation has now been overcome. It was established that even faulty quantum circuits are superior to their classical (noise-free) counterparts.

The challenge consisted in developing the right computational problem to test and prove a quantum advantage. The proposed computational problem satisfies two conditions. Firstly, it can be solved by a constant-depth quantum circuit with overwhelming probability even if all building blocks (preparation, gates, and measurements) are imperfect. Secondly, it cannot be solved by any (ideal) constant-depth classical circuit with high probability.

The considered computational problem is motivated by the structure of long-range entanglement generated when measuring a 3-dimensional cluster state. It incorporates new fault-tolerance techniques related to surface codes.

The new result shows that quantum advantage experiments, that is, experimental demonstrations of quantum computational benefits, are possible, in principle, even if the hardware is noisy. These techniques are specifically developed for constant-depth quantum circuits and are likely to be of use for other NISQ applications.

Quantum advantage with noisy shallow circuits
Sergey Bravyi, David Gosset, Robert König and Marco Tomamichel
Nature Physics (2020)
DOI: 10.1038/s41567-020-0948-z

Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, Robert König
Science Vol. 362, Issue 6412, pp. 308–311 (2018)
DOI: 10.1126/science.aar3106

We have developed quantum speedups for a number of important optimisation problems which are hard classically.

NP-complete optimisation problems (such as the famous Travelling Salesman Problem in which one has to find the best route through a number of cities) are among the main examples of problems which are hard for conventional computers. The best algorithms for solving them exactly require an exponential time and a considerable effort has gone into optimising them.

We show that many of these algorithms can be combined with quantum effects to obtain faster quantum algorithm. For example, for Travelling Salesman Problem, the best classical algorithm takes O*(2ⁿ) time while our quantum algorithm solves the problem in O(1.729...ⁿ) time. Our speedup applies to a number of problems for which the best classical solution method is dynamic programming.

[1] Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. Proceedings of ACM-SIAM Conference on Discrete Algorithms (SODA’2019), pp. 1783-1793.

[2] Adam Glos, Martins Kokainis, Ryuhei Mori, Jevgenijs Vihrovs. Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs. Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS’2021), 50:1-50:23.

In collaboration with researchers from QuSoft (Amsterdam), we have shown a quantum improvement over any classical algorithm based on search by random walk.

Search by random walk is a classical search strategy, in which one walks randomly on a search space. We have shown that any search algorithm of this type allows a quadratic quantum speedup. This has found a number of applications, from finding equal elements in an array (the element distinctness problem) to finding substructures (such as triangles) in graphs.

[1] Andris Ambainis. Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing, 37(1): 210–239, 2007.

[2] Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis. Quadratic speedup for finding marked vertices by quantum walks. Proceedings of the ACM Symposium on the Theory of Computing (STOC’2020), pp. 412–424.