# News

### Work on optimization in Science Advances

Combinatorial optimization - a field of research addressing problems that feature strongly in a wealth of scientific and industrial contexts - has been identified as one of the core potential fields of applicability of quantum computers. It is still unclear, however, to what extent quantum algorithms can actually outperform classical algorithms for this type of problems. In this work, published in the Science Advances , by resorting to computational learning theory and cryptographic notions, we prove that quantum computers feature an in-principle super-polynomial advantage over classical computers in approximating solutions to combinatorial optimization problems. Specifically, building on seminal work by Kearns and Valiant and introducing a new reduction, we identify special types of problems that are hard for classical computers to approximate up to polynomial factors. At the same time, we give a quantum algorithm that can efficiently approximate the optimal solution within a polynomial factor. The core of the quantum advantage discovered in this work is ultimately borrowed from Shor's quantum algorithm for factoring. Concretely, we prove a super-polynomial advantage for approximating special instances of the so-called integer programming problem. In doing so, we provide an explicit end-to-end construction for advantage bearing instances. This result shows that quantum devices have, in principle, the power to approximate combinatorial optimization solutions beyond the reach of classical efficient algorithms. Our results also give clear guidance on how to construct such advantage-bearing problem instances. A press release can be found here .

Mar 16, 2024

### Work on generalization in Nature Communications

Quantum machine learning models have shown successful generalization performance even when trained with few data. In this work published in Nature Communications , through systematic randomization experiments, we show that traditional approaches to understanding generalization fail to explain the behavior of such quantum models. Our experiments reveal that state-of-the-art quantum neural networks accurately fit random states and random labeling of training data. This ability to memorize random data defies current notions of small generalization error, problematizing approaches that build on complexity measures such as the VC dimension, the Rademacher complexity, and all their uniform relatives. We complement our empirical results with a theoretical construction showing that quantum neural networks can fit arbitrary labels to quantum states, hinting at their memorization ability. Our results do not preclude the possibility of good generalization with few training data but rather rule out any possible guarantees based only on the properties of the model family. These findings expose a fundamental challenge in the conventional understanding of generalization in quantum machine learning and highlight the need for a paradigm shift in the study of quantum models for machine learning tasks. A press release can be found here .

Mar 01, 2024

### Work on quantum machine learning in Nature Communications

Work being done in the group on quantum machine learning is published in the Nature Communications . Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. In this work, we show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms, scaling as O(T^2 polylog(n)), where n is the size of the models and T is the number of iterations in the training, as long as the models are both sufficiently dissipative and sparse, with small learning rates. Based on earlier efficient quantum algorithms for dissipative differential equations, we find and prove that similar algorithms work for (stochastic) gradient descent, the primary algorithm for machine learning. In practice, we benchmark instances of large machine learning models from 7 million to 103 million parameters. We find that, in the context of sparse training, a quantum enhancement is possible at the early stage of learning after model pruning, motivating a sparse parameter download and re-upload scheme. Our work shows solidly that fault-tolerant quantum algorithms could potentially contribute to most state-of-the-art, large-scale machine-learning problems.

Jan 10, 2024

### Work on many-body localization in Communications Physics

Work being done in the group is published in the Nature group journal Communications Physics . Quasi-local integrals of motion are a key concept underpinning the modern understanding of many-body localisation, a phenomenon in which interactions and disorder come together. Despite the existence of several numerical ways to compute them—and in the light of the observation that much of the phenomenology of many properties can be derived from them—it is not obvious how to directly measure aspects of them in real quantum simulations; in fact, hard experimental evidence is still missing. In this work, we propose a way to extract the real-space properties of such quasi-local integrals of motion based on a spatially-resolved entanglement probe able to distinguish Anderson from many-body localisation from non-equilibrium dynamics. We complement these findings with a rigorous entanglement bound and compute the relevant quantities using tensor networks. We demonstrate that the entanglement gives rise to a well-defined length scale that can be measured in experiments.

Dec 20, 2023

### Mentioned among top 100 researchers of Berlin

The Tagesspiegel , the leading newspaper of Berlin, has made a survey of the "100 most important minds in Berlin science 2023".

Oct 01, 2023

### Benchmarking quantum computers

How can one calibrate quantum computers to extremely high precision? Our work published in Nature Communications shows that one feasible kind of data from randomized benchmarking is sufficient to obtain a wealth of diagnostic information, ranging from randomized benchmarking with no end gate over full noise characterization and cross talk tomography. That is, from one dataset, one can in a robust and sample-optimal fashion calibrate quantum circuits. For articles in the academic press, see these links. Berlin Tagesspiegel: Forschung zu Quantencomputern: Ein Tüv für die Zukunftsrechner PhysOrg: Physicists develop series of quality control tests for quantum computers ProPhysik: Ein Qualitätstests für Quantencomputer Informationsdienst Wissenschaft: Quantencomputer: Gewissheit aus dem Zufall ziehen ScienMag: Quantum computing: Benchmarking performance by random data

Sep 01, 2023

### Quantum simulation with light

How can one think of pursuing quantum simulations of non-Gaussian states with light? Our new work in Nature Communications addresses this question. It shows how the emergence of properties of statistical physics in quantum theory can be reconciled and empirically probed. The significance of this work may not only stem from the actual application in quantum simulation, but from nitty gritty method development on how one can certify and witness certain quantum properties in integrated optical devices, with applications in optical quantum computing in mind. For articles in the academic press, see these links. PhysOrg, "Photonics experiment resolves quantum paradox " Photonics World, "Twente photonics experiment resolves longstanding quantum paradox" Yahoo, "Paradox, Solved: Thermodynamics and quantum mechanics CAN be true at the same time" SciTech Daily, "Time reversal photonics experiment resolves quantum paradox" NewsBeezer, "Time-reversal photonics experiment solves quantum paradox"

Jul 10, 2023

### Probing curved light cones on an analog quantum simulator

How can the non-equilibrium dynamics of a quantum field featuring curved light cones be simulated with an analog quantum simulato r ? We show this based on two tunneling-coupled superfluids in one-dimensional traps. We are happy to see this work in the Proceedings of the National Academy of Sciences . A press release can be found here .

May 16, 2023

### A comprehensive review on quantum advantages with quantum random sampling

Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently, first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. In this article , we comprehensively review the theoretical underpinning of quantum random sampling in terms of computational complexity and verifiability, as well as the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. We discuss in detail open questions in the field and provide perspectives for the road ahead, including potential applications of quantum random sampling. This work is in press with the Reviews of Modern Physics .

Mar 10, 2023

### Our team wins the best poster award at QIP

The team of Marcel Hinsche , Marios Ioannou , Alexander Nietner , Jonas Haferkamp , Yihui Quek , Dominik Hangleiter , Jean-Pierre Seifert , Jens Eisert , Ryan Sweke wins the best poster award at QIP 2023 .

Feb 02, 2023

### Talk at QIP 2023

We will present a talk at QIP 2023 on limitations of quantum error mitigation of even log-log-deep quantum circuits, based on arXiv:2210.11505 .

Jan 01, 2023

### Deutsche Welle interview on quantum computing

The international German public television broadcaster Deutsche Welle interviews Rainer Blatt and Jens Eisert on the perspectives of quantum computing .

Dec 21, 2022

### Work on a super-polynomial quantum advantage in combinatorial optimization

Combinatorial optimization - a field of research addressing problems that feature strongly in a wealth of practical and industrial contexts - has been identified as one of the core potential fields of applicability of near-term quantum computers. It is still unclear, however, to what extent variational quantum algorithms can actually outperform classical algorithms for this type of problems. In this work , by resorting to computational learning theory and cryptographic notions, we prove that fault-tolerant quantum computers feature a super-polynomial advantage over classical computers in approximating solutions to combinatorial optimization problems. Specifically, building on seminal work of Kearns and Valiant, we construct special instances of the integer programming problem (which in its most general form is NP-complete) that we prove to be hard-to-approximate classically but give an efficient quantum algorithm to approximate the optimal solution of those instances, hence showing a super-polynomial quantum advantage. This result shows that quantum devices have the power to approximate combinatorial optimization solutions beyond the reach of classical efficient algorithms.

Dec 20, 2022

### A group outing on Peacock Island

We are enjoying a wonderful group outing on Peacock Island, a small island in lake Wannsee. Thanks, Elies, for organizing this.

Sep 22, 2022

### An article in Tagesspiegel

In Berlin's daily newspaper Tagesspiegel , Jens Eisert explains in a long article how quantum computers function and what we can expect from them in the near future.

Sep 22, 2022

### Work on "quantum homeopathy" in the Communications of Mathematical Physics

Unitary designs are important tools in quantum information theory, as collections of unitaries that resemble averages over the Haar measure. So-called k-designs recover k-th moments exactly. They have a wealth of applications in technology-oriented fields such as benchmarking, certification as well as in fundamental quantum physics. Random Clifford operations are 3-designs, but just not 4-designs, which constitutes a roadblock in some applications. Adding (expensive) T-gates will uplift such random circuits to k-designs of arbitrary order. But the question arises how of those many one needs? It turns out that strikingly, a non-extensive number is sufficient: One will still arrive at a design of arbitrary order. This technical and mathematically minded work - that jokingly can be explained as quantum homeopathy actually working - goes to press in the Communications of Mathematical Physics , the most prestigious venue for mathematical physics. .

Sep 21, 2022

### Campus run 2022

Our team has participated in the Berlin Campus Run 2022 . It has been great fun.

Jun 16, 2022

### Re:publica 2022

As part of an outreach activity at re:publica 2022 , the quantum scientist Jasmin Meincke, the quantum scientist and artist Libby Heaney and Jens Eisert have organized a session on " living in a quantum state ", bringing together ideas of science and the arts.

Jun 10, 2022

### Proof of the Brown Susskind conjecture in Nature Physics

Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. In our work in Nature Physics we prove a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary's exact circuit complexity. We prove that this complexity grows linearly in the number of random gates, with unit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits. This work has received substantial attention and it has been greeted by several articles in the popular press and by press releases . This work is also the first in the group to hit over 100 scites on Scirate .

Apr 02, 2022

### Work on quantum advantages in Science Advances

Can near-term quantum devices outperform classical computers? This question is also at the heart of efforts of the Einstein Research Unit on near-term quantum devices . We address this question here for high-dimensional Gaussian boson sampling in work that has been published in the Science Advances . Photonics is a promising platform for demonstrating quantum computational supremacy (QCS) by convincingly outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing photonics proposals and demonstrations face significant hurdles. Experimentally, current implementations of Gaussian boson sampling lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make significant progress in improving both the theoretical evidence and experimental prospects. On the theory side, we provide strong evidence for the hardness of Gaussian boson sampling, placing it on par with the strongest theoretical proposals for QCS. On the experimental side, we propose a new QCS architecture, high-dimensional Gaussian boson sampling, which is programmable and can be implemented with low loss rates using few optical components. We show that particular classical algorithms for simulating GBS are vastly outperformed by high-dimensional Gaussian boson sampling experiments at modest system sizes. This work thus opens the path to demonstrating QCS with programmable photonic processors.

Jan 10, 2022