Algorithms & Complexity

Max Planck Distinguished Speaker Series in
Quantum Computing and Quantum Information

Basic Information

Meeting ID 945 7732 1297
Passcode 205903
Time The regular time for the event is Thursday afternoon. However, we will adapt to the time zone of the speaker if necessary.
Organizers Ignacio Cirac (MPQ) and Kurt Mehlhorn (MPI-INF)

Schedule (Links to Videos of Past Talks can be found under Past Talks)

February 11, 5pm Thomas Vidick (Caltech) Testing quantum systems in the high-complexity regime
July 22, 4pm Andrew Childs (Maryland) Efficient quantum algorithm for dissipative nonlinear differential equations
September 16, 4pm Matthias Christandl (Copenhagen) Fault-tolerant Coding for Quantum Communication
October 28, 2pm Renato Renner( ETH ) Optimal universal programming of unitary gates
November 18, 2pm Ashley Montanaro (Phasecraft and University of Bristol) Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
December 16, 2pm Aram Harrow (MIT) Entanglement Spread in Communication Complexity and Many-Body Physics
February 17, 4pm Stephanie Wehner (Delft) Quantum Networks: From a Physics Experiment to a Quantum Network System

Next Talk Information

Stephanie Wehner (TU Delft)

Quantum Networks: From a Physics Experiment to a Quantum Network System

The internet has had a revolutionary impact on our world. The vision of a quantum internet is to provide fundamentally new internet technology by enabling quantum communication between any two points on Earth. Such a quantum internet can —in synergy with the “classical” internet that we have today—connect quantum information processors in order to achieve unparalleled capabilities that are provably impossible by using only classical information.

At present, such technology is under development in physics labs around the globe, but no large-scale quantum network systems exist. We start by providing a gentle introduction to quantum networks for computer scientists, and briefly review the state of the art. We highlight some of the many open questions to computer science in the domain of quantum networking, illustrated with a very recent result realizing the first quantum link layer protocol on a programmable 3 node quantum network based on Nitrogen-Vacancy Centers in Diamond.

We close by providing a series of pointers to learn more, as well as tools to download that allow play with simulated quantum networks without leaving your home.

Past Talks

Thomas Vidick (Caltech): Testing quantum systems in the high-complexity regime.

From carefully crafted quantum algorithms to information-theoretic security in cryptography, a quantum computer can achieve impressive feats with no classical analogue. Can their correct realization be verified? When the power of the device greatly surpasses that of the user, computationally as well as cryptographically, what means of control remain available to the user?

Recent lines of work in quantum cryptography and complexity develop approaches to this question based on the notion of an interactive proof. Generally speaking an interactive proof models any interaction whereby a powerful device aims to convince a restricted user of the validity of an agree-upon statementsuch as that the machine generates perfect random numbers or executes a specific quantum algorithm.

Two models have emerged in which large-scale verification has been shown possible: either by placing reasonable computational assumptions on the quantum device, or by requiring that it consists of isolated components across which Bell tests can be performed.

In the talk I will discuss recent results on the verification power of interactive proof systems between a quantum device and a classical user, focusing on the certification of quantum randomness from a single device (arXiv:1804.00640) and the verification of arbitrarily complex computations using two devices (arXiv:2001.04383).


Andrew Childs (University of Maryland): Efficient quantum algorithm for dissipative nonlinear differential equations.

While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R < 1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2 poly( log T, log n, log(1/ϵ) ) / ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give a novel convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R ≥ sqrt( 2 ). Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.

Based on joint work with Jin-Peng Liu, Herman Kolden, Hari Krovi, Nuno Loureiro, and Konstantina Trivisa.


Matthias Christandl (Copenhagen): Fault-tolerant Coding for Quantum Communication

Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. As our main result, we prove threshold theorems for quantum communication, i.e. we show that coding near the (standard noiseless) classical or quantum capacity is possible when the gate error is below a threshold.

The recording is from an earlier presentation by Matthias at Harvard.


Renato Renner (ETH): Optimal universal programming of unitary gates

The “No-Programming Theorem” asserts that perfect universal quantum processors cannot exist. These are hypothetical devices that execute a unitary gate that is choosable arbitrarily and itself provided as a (quantum) input. This impossibility result depends however strongly on the requirement that the processor makes no errors. In my talk, I will present a recent robust version of the No-Programming Theorem. It basically answers the following question: Given a bound on the maximum tolerated error, what is the minimum size of the program that implements a unitary gate on a universal processor? As I shall explain, the answer to this question has an interesting connection to the Heisenberg limit of quantum metrology.


Ashley Montanaro (Phasecraft and University of Bristol): Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer


The famous, yet unsolved, Fermi-Hubbard model for strongly-correlated electronic systems is a prominent target for quantum computers. However, accurately representing the Fermi-Hubbard ground state for large instances may be beyond the reach of near-term quantum hardware. In this talk I will discuss recent results showing experimentally that an efficient, low-depth variational quantum algorithm with few parameters can reproduce important qualitative features of medium-size instances of the Fermi-Hubbard model. We address 1x8 and 2x4 instances on 16 qubits on a superconducting quantum processor, substantially larger than previous work based on less scalable compression techniques, and going beyond the family of 1D Fermi-Hubbard instances, which are solvable classically. Consistent with predictions for the ground state, we observe the onset of the metal-insulator transition and Friedel oscillations in 1D, and antiferromagnetic order in both 1D and 2D. We use a variety of error-mitigation techniques, including symmetries of the Fermi-Hubbard model and a technique tailored to simulating fermionic systems. We also introduce a new variational optimisation algorithm based on iterative Bayesian updates of a local surrogate model. Our scalable approach is a first step to using near-term quantum computers to determine low-energy properties of strongly-correlated electronic systems that cannot be solved exactly by classical computers.




Aram Harrow (MIT)

Entanglement Spread in Communication Complexity and Many-Body Physics

Entanglement spread is an information-theoretic resource that (roughly) measures the gap between the highest and lowest Schmidt values of a pure bipartite quantum state. It turns out to characterize the communication cost needed to prepare the state starting from EPR pairs, as well as the cost of reflecting about the state. I will discuss the role of entanglement spread in two settings: communication complexity, and in the ground states of interacting quantum systems.

Based in part on work with Anurag Anshu, Matt Coudron and Mehdi Soleimanifar.