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
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
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
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
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
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
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
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
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
Recent years have enjoyed an overwhelming interest in quantum thermodynamics, a field of research aimed at understanding thermodynamic tasks performed in the quantum regime. Further progress, however, seems to be obstructed by the lack of experimental implementations of thermal machines in which quantum effects play a decisive role. In this work , we introduce a blueprint of quantum field machines, which - once experimentally realized - would fill this gap. We provide a detailed proposal how to realize a quantum machine in one-dimensional ultra-cold atomic gases using a set of modular operations giving rise to a piston that can be coupled sequentially to thermal baths with the innovation that a quantum field takes up the role of the working fluid. We study the operational primitives numerically in the Tomonaga-Luttinger liquid framework proposing how to model the compression of the system during strokes of a piston and the coupling to a bath giving rise to a valve controlling phononic heat flow. By composing the numerically modeled operational primitives we design complete quantum thermodynamic cycles that are shown to enable cooling and hence giving rise to a quantum field refrigerator. The active cooling achieved in this way can operate in regimes where existing cooling methods become ineffective. We describe the consequences of operating the machine at the quantum level and give an outlook of how this work serves as a road map to explore open questions in quantum information, quantum thermodynamics and the study of non-Markovian quantum dynamics. This work has been published in PRX Quantum and has enjoyed a substantial coverage in the scientific press .
Jun 16, 2021
Notions of circuit complexity and cost play a key role in quantum computing and simulation where they capture the (weighted) minimal number of gates that is required to implement a unitary. Similar notions also become increasingly prominent in high energy physics in the study of holography. While notions of entanglement have in general little implications for the quantum circuit complexity and the cost of a unitary, in this work, we discuss a simple such relationship when both the entanglement of a state and the cost of a unitary take small values, building on ideas on how values of entangling power of quantum gates add up. This bound implies that if entanglement entropies grow linearly in time, so does the cost. The implications are two-fold: It provides insights into complexity growth for short times. In the context of quantum simulation, it allows to compare digital and analog quantum simulators. The main technical contribution is a continuous-variable small incremental entangling bound. This work is in press at the Physical Review Letters . It is the 80th group publication in the Physical Review Letters.
Jun 15, 2021
In 2021, we welcome Yihui Quek (Stanford), Sumeet Khatri (Baton Rouge and Stanford), Giacomo Guarnieri (Trinity College), Nora Tischler (Griffith), Austin Lund (Queensland), Philipp Schmoll (Mainz), Joschka Roffe (Sheffield), Steven Thomson (École Polytechnique), Ellen Derbyshire (Edinburgh), Spyros Sotiriadis (Ljubljana) as postdocs, most already being here. Very warm welcome again.
Jun 14, 2021
Artificial intelligence (AI) is a potentially disruptive tool for physics and science in general. One crucial question is how this technology can contribute at a conceptual level to help acquiring new scientific understanding. Scientists used AI techniques to rediscover previously known concepts. So far, however, no examples of that kind have been reported that are applied to open problems for getting new scientific concepts and ideas. In work in press in the Physical Review X , we present an algorithm that can provide new conceptual understanding, and we demonstrate its applications in the field of experimental quantum optics. To do so, we make four crucial contributions. (i) We introduce graph-based representation of quantum optical experiments that can be interpreted and used algorithmically. (ii) We develop an automated design approach for new quantum experiments, which is orders of magnitudes faster than the best previous algorithms at concrete design tasks for experimental configuration. (iii) We solve several crucial open questions in experimental quantum optics which involve practical blueprints of resource states in photonic quantum technology and quantum states and transformations that allow for new foundational quantum experiments. Finally, and most importantly, (iv) the interpretable representation and enormous speed-up allow us to produce solutions that a human scientist can interpret and gain new scientific concepts from outright. We anticipate that will become an essential tool in quantum optics for developing new experiments and photonic hardware. It can further be generalized to answer open questions and provide new concepts in a large numbers of other quantum physical questions beyond quantum optical experiments. is a demonstration of explainable AI (XAI) in physics that shows a way how AI algorithms can contribute to science on a conceptual level.
Jun 09, 2021
We have set up a new major research network on near-term quantum devices and quantum computing within the Berlin University Alliance of Freie Universität Berlin , Humboldt-Universität zu Berlin , Technische Universität Berlin und Charité - Universitätsmedizin Berlin . The premise of this network is particularly fun and exciting since people working on quantum information theory are coming together with experts in combinatorical optimization, other readings of applied mathematics, with machine learning, high energy physics and quantum chemistry, as well as with experimentalists in quantum optics. So ideas of quantum software meet those of quantum hardware implementation. It is the first project within the Berlin Excellence Initiative of the Berlin University Alliance. We sincerely hope it will be good for the research field and for the Berlin academic landscape. A press release can be found here .
May 06, 2021
The team "Notorious FUB", a team composed of the PhD students of our group Peter-Jan Derks , Paul K. Faehrmann , Elies Gil-Fuster , Thomas S. Hubregtsen , Johannes Jakob Meyer , and the friend of the family David Wierichs have won the prestigious QHack 2021—the quantum machine learning hackathon. https://medium.com/xanaduai/qhack-the-quantum-machine-learning-hackathon-7f2cd7348e2b Participants from more than 85 countries tested their skills against one another to claim the top spots on the leaderboard on a topic of near-term quantum computing. At stake was more than bragging rights: top teams could unlock a share of $100k in credits for quantum computing platforms, early access to unreleased services, and internships at a world-famous scientific lab. A press release can be found here . Congratulations to this amazing achievement!
May 01, 2021
Work on cold atomic quantum simulators probing "Gaussification dynamics" is going to press in Nature Physics . Gaussian models provide an excellent effective description of a plethora of quantum many-body systems ranging from a large variety of condensed matter systems all the way to neutron stars. Gaussian states are common at equilibrium when the interactions are weak. Recently it was proposed that they can also emerge dynamically from a non-Gaussian initial state evolving under non-interacting dynamics. In this work, we present the first experimental observation of such a dynamical emergence of Gaussian correlations in a quantum many-body system. For this, we monitor the connected fourth-order correlations during non-equilibrium dynamics. These dynamics are triggered by abruptly switching off the effective interaction between the collective degrees of freedom that we observe, while leaving the interactions between the microscopic constituents unchanged. Starting from highly non-Gaussian correlations, we observe a Gaussian description becoming increasingly accurate over time. In our closed system with non-interacting effective degrees of freedom, we do not expect full thermalization. This memory of the initial state is confirmed by observing recurrences of non-Gaussian correlations. Our study points to a natural way for Gaussian models to emerge in a wide class of (microscopically interacting) quantum many-body systems.
Jan 18, 2021
Two group contributions to QIP 2021 , the largest conference on quantum information processing, one on random quantum circuits and one on quantum metrology, have been accepted as talks. Congratulations.
Jan 04, 2021
Understanding the conditions under which physical systems thermalize is one of the long-standing questions in many-body physics. While it has been observed that generic quantum systems do thermalize, rather little is known about the precise underlying mechanism. Furthermore, instances in which thermalization is hindered for many-body systems have been uncovered, now known as many-body localization, offering promising insights into the mechanisms that underlie thermalization. In this work, we derive upper and lower bounds on the size of a heat bath required to thermalize a many-body localized system, for a broad class of collision models. To obtain these bounds, we employ a recently developed tool from quantum information theory known as the convex split lemma. We apply our results to the disordered Heisenberg chain, which we study numerically, and we characterize the robustness of the MBL phase in this system for the family of thermalization processes considered, in terms of the required bath size. Part of the significance of this work, published in Communications Physics (Nature) , stems from transferring tools from resource-theoretic quantum thermodynamics to the study of interacting quantum many-body systems.
Jan 04, 2021
Demonstrating a quantum computational speedup is a crucial milestone for near-term quantum technology. Recently, quantum simulation architectures have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme - as of other comparable schemes such as boson sampling - is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for these architectures for Hamiltonian quantum simulators: Anticoncentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we develop new techniques that exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We prove that the 2D translation-invariant, constant depth architectures of quantum simulation form approximate 2-designs in a specific sense, thus obtaining a significantly stronger result. Our work, freshly published in the Physical Review Letters , provides the strongest evidence to date that Hamiltonian quantum simulation architectures are classically intractable.
Dec 10, 2020