|Meeting ID||945 7732 1297|
|Time||The regular time for the event is 4pm. However, we will adapt to the time zone of the speaker if necessary.|
|Organizers||Ignacio Cirac (MPQ) and Kurt Mehlhorn (MPI-INF)|
|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, 4pm||Renato Renner( ETH )|
|November 18, 4pm||Ashley Montanaro (Bristol)|
|December 16, 4pm||Aram Harrow (MIT)|
|January 20, 4pm||Stephanie Wehner (Delft)|
|February 17, 4pm||to be announced|
Matthias Christandl (Copenhagen), September 16, 4pm
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.
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.