From quantum communication to computation
Since 2015, the Focus Group Complex Quantum Systems has been studying to what extent quantum effects can be exploited to enhance information processing. We have made a variety of contributions to quantum information theory and the theory of quantum computation. Our work provides new fundamental physical limits to communication using quantum systems, as well as novel ways of harnessing quantum effects to enhance computation.
Focus Group Theory of Complex Quantum Systems
Prof. Robert König (TUM), Alumnus Rudolf Mößbauer Tenure Track Professor | Dr. Lisa Hänggli, Dr. Cambyse Rouzé, (TUM), Postdoctoral Researchers | Margret Heinze, Alexander Kliesch, (TUM), Doctoral Candidates | Host: Theory of Complex Quantum Systems, TUM
Our research focuses on the question of whether and how imperfect quantum devices can provide robust information-processing primitives. To this end, we have studied the design and use of error-correcting codes both for qubits as well as bosonic (infinite-dimensional) quantum systems. In addition to finding near-optimal codes for communication over so-called additive bosonic noise channels, we have shown how to render certain computational schemes for near-term quantum computing devices fault-tolerant.
Recent contributions of our Focus Group advance the state-of-the-art of our current understanding of the potential of small- to intermediate-scale quantum devices. This is becoming particularly important with the currently accelerating experimental developments in this area.
Unconditional computational quantum advantage with near-term devices
Arguably the most significant result we have found is an unconditional separation between two analogously defined quantum and classical computational models: It is the first complexity-theoretic result that provides a rigorous proof that quantum devices are superior to classical ones without relying on unproven hardness conjectures.
The result immediately raises the question of whether and how such a so-called quantum advantage can be observed in the lab. We have made progress in this direction by establishing schemes relying on noisy components (qubits and gates, respectively) only [1]. We are now seeking even simpler schemes that could be realized more easily, and more generally working toward a theory of computation with near-term quantum devices. Such devices are typically small and subject to noise. Dealing with these limitations and understanding their impact remains a major challenge.
Toward practically useful quantum algorithms
Demonstrating that quantum devices can solve certain problems more efficiently or using fewer resources than comparable classical devices is important as a proof-of-principle on the road towards quantum computing. Ultimately, though, one would like to use quantum devices to tackle real-world problems of practical relevance.
Our present work is aimed at finding new ways of using quantum devices for ubiquitous problems such as combinatorial optimization. While there are some corresponding proposals, assessing their merits is often challenging in the absence of an actual device. It is therefore important to develop classical simulation tools and new analytical techniques to assess the performance of quantum algorithms. Ideally, one would like to establish performance guarantees for generic instances when comparing a quantum algorithm to the best known, or best possible, classical efficient algorithm.
In [2], we have established the first upper bounds on approximation ratios achievable by near-term realizations of the so-called quantum approximate optimization algorithm (QAOA). This is a popular proposal intended to solve combinatorial optimization problems. Unfortunately, our results demonstrate that for generic instances, the famous (classical) Goemans-Williamson algorithm outperforms the QAOA. At the same time, we proposed a modification of the quantum algorithm that overcomes its current limitations. Preliminary numerical evidence suggests that this modified algorithm (which we call the recursive quantum approximate optimization algorithm) has significant potential. Future work will seek to establish performance guarantees for such approaches.
Figure 1
[1]
S. Bravyi, D. Gosset, R. König and M. Tomamichel, “Quantum advantage with noisy shallow circuits”, Nature Physics, vol. 16, pp. 1040-1045, 2020.
[2]
S. Bravyi, A. Kliesch, R. König and E. Tang, “Obstacles to State Preparation and Variational Optimization from Symmetry Protection”, Physical Review Letters, 125 (26), 260505, 2020.
[3]
L. Hänggli, M. Heinze and R. König, “Enhanced noise resilience of the surface-GKP code via designed bias”, Physical Review A, 102, 052408, 2020.