# News

### 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

### What a year

Thanks so much to the group members of our team for the good vibes, the wonderful scientific discussions, all those excellent ideas. It has not always been easy outside our control, but we have been doing well. The revived discussion culture in the department has been fun. And over the summer and fall the many garden meetings we have had. This may also be a good moment to think what good lessons can be learned from the crisis. The garden meetings we will surely maintain. While this may be a somewhat superficial metric, it is still nice to see that five publications came out of the group this year in the Nature and Science groups, six in Physical Review X and PRX Quantum , seven in the Physical Review Letters , and one in the Reviews of Modern Physics . What is particularly pleasing is that five pieces of work have been published in the community driven Quantum and SciPost Physics . Happy new year.

Dec 31, 2021

### Second place in best paper award

Work on the randomized implementation of multi-product formulas for Hamiltonian simulation ( https://arxiv.org/abs/2101.07808 ) has been awarded the USRA- Q2B ANISQC Best Paper Award 2021. Congratulations, Paul Faehrmann and coauthors.

Dec 14, 2021

### Work on a quantum network advantage in PRX Quantum

Is a quantum network advantage in practical quantum communication conceivable. New work to be published in PRX Quantum is addressing this question to the affirmative. Secret sharing is a multi-party cryptographic primitive that can be applied to a network of partially distrustful parties for encrypting data that is both sensitive (it must remain secure) and important (it must not be lost or destroyed). When sharing classical secrets (as opposed to quantum states), one can distinguish between protocols that leverage bi-partite quantum key distribution (QKD) and those that exploit multi-partite entanglement. The latter class are known to be vulnerable to so-called participant attacks and, while progress has been made recently, there is currently no analysis that quantifies their performance in the composable, finite-size regime which has become the gold standard for QKD security. Given this - and the fact that distributing multi-partite entanglement is typically challenging - one might well ask: Is there is any virtue in pursuing multi-partite entanglement based schemes? Here, we answer this question in the affirmative for a class of secret sharing protocols based on continuous variable graph states. We establish security in a composable framework and identify a network topology, specifically a bottleneck network of lossy channels, and parameter regimes within the reach of present day experiments for which a multi-partite scheme outperforms the corresponding QKD based method in the asymptotic and finite-size setting. Finally, we establish experimental parameters where the multi-partite schemes outperform any possible QKD based protocol. This one of the first concrete compelling examples of multi-partite entangled resources achieving a genuine advantage over point-to-point protocols for quantum communication and represents a rigorous, operational benchmark to assess the usefulness of such resources.

Nov 22, 2021

### Work on quantum machine learning in Quantum

How well do quantum-assisted machine learning algorithms perform on unseen data? New w ork pushlished in Quantum is addressing this question. A large body of recent work has begun to explore the potential of parametrized quantum circuits (PQCs) as machine learning models, within the framework of hybrid quantum-classical optimization. In particular, theoretical guarantees on the out-of-sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC-based models that depend explicitly on the strategy used for data-encoding. These imply bounds on the performance of trained PQC-based models on unseen data. Moreover, our results facilitate the selection of optimal data-encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC-based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC-based models via trigonometric functions. Our generalization bounds emphasize the importance of well-considered data-encoding strategies for PQC-based models.

Nov 01, 2021

### Launch of the first Einstein Research Unit of the Berlin University Alliance on the topic of quantum computing

How can quantum computers revolutionize the computational power of computers? What new insights do quantum computers offer for high energy physics or quantum chemistry? These are the questions that the first Einstein Research Unit (ERU) of the Berlin University Alliance (BUA) will address. The interdisciplinary research team of the partner institutions Freie Universität Berlin, Humboldt-Universität zu Berlin, Technische Universität Berlin, and Charité – Universitätsmedizin Berlin has set itself the task of clarifying the potential of the quantum digital transformation. This uniquely brings together expertise in theoretical and experimental physics, applied mathematics, computer science, and machine learning. The Einstein Research Unit “Perspectives of a quantum digital transformation: Near-term quantum computational devices and quantum processors” will be funded with two million euros annually for an initial three years. Quantum computers are considered one of the key technologies of the 21st century. With them, scientists hope to solve computational problems that cannot be solved nowadays, even with supercomputers. The continued development of quantum computers also holds great potential for the economy. Only the technological progress of recent years has made it possible to build the first prototypes of such quantum computers. Unlike classical computers, they handle information based on quantum mechanical laws. This means that memory contents on these computers can, at the same time, contain multiple, superimposed values, on which computing instructions have a simultaneous effect. The research team led by Prof. Dr. Jens Eisert, physicist and mathematician at Freie Universität Berlin, Prof. Dr. Oliver Benson, physicist at Humboldt-Universität zu Berlin, Prof. Dr. Jean-Pierre Seifert, Einstein professor and computer scientist at Technische Universität Berlin, and Prof. Dr. Robert Gütig, member of the NeuroCure Cluster of Excellence at Charité – Universitätsmedizin Berlin, explores quantum computing from an interdisciplinary perspective. Web page Press release

Oct 01, 2021

### Johannes Meyer wins Quantum Futur Award

After Paul Faehrmann winning the Quantum Futur Award 2020, and our team the QHack 2020, Johannes Meyer has won the prestigious Quantum Futur Award 2021 of the German ministry for Research and Education BMBF. Warmest congratulations, very well deserved.

Aug 26, 2021

### Work on generic quantum phases in PRX Quantum

The study of generic properties of quantum states has led to an abundance of insightful results. A meaningful set of states that can be efficiently prepared in experiments are ground states of gapped local Hamiltonians, which are well approximated by matrix product states. In this work, we introduce a picture of generic states within the trivial phase of matter with respect to their non-equilibrium and entropic properties: We do so by rigorously exploring non-translation-invariant matrix product states drawn from a local i.i.d. Haar-measure. We arrive at these results by exploiting techniques for computing moments of random unitary matrices and by exploiting a mapping to partition functions of classical statistical models, a method that has lead to valuable insights on local random quantum circuits. Specifically, we prove that such disordered random matrix product states equilibrate exponentially well with overwhelming probability under the time evolution of Hamiltonians featuring a non-degenerate spectrum. Moreover, we prove two results about the entanglement Renyi entropy: The entropy with respect to sufficiently disconnected subsystems is generically extensive in the system-size, and for small connected systems the entropy is almost maximal for sufficiently large bond dimensions. This work is in press in PRX Quantum .

Aug 09, 2021

### Work on quantum readout in optical lattice systems in PRL

Quantum simulations with ultra-cold atoms in optical lattices open up an exciting path towards understanding strongly interacting quantum systems. Atom gas microscopes are crucial for this as they offer single-site density resolution, unparalleled in other quantum many-body systems. However, currently a direct measurement of local coherent currents is out of reach. In this work, we show how to achieve that by measuring densities that are altered in response to quenches to non-interacting dynamics, e.g., after tilting the optical lattice. For this, we establish a data analysis method solving the closed set of equations relating tunnelling currents and atom number dynamics, allowing to reliably recover the full covariance matrix, including off-diagonal terms representing coherent currents. The signal processing builds upon semi-definite optimization, providing bona fide covariance matrices optimally matching the observed data. We demonstrate how the obtained information about non-commuting observables allows to lower bound entanglement at finite temperature which opens up the possibility to study quantum correlations in quantum simulations going beyond classical capabilities. This work is in press at the Physical Review Letters .

Jul 13, 2021