Abstract: The era of quantum computers has already started. One important question that we can do now that we have these quantum devices ready is which quantum model of computation will be a good choice for encoding the huge number of quantum algorithms available. Another important question which is also extremely important to people that work in the industry that very often employs numerical methods to solve differential equations is that if these numerical methods are a promising application for quantum computers. Going to these directions we will present in this seminar our latest results where we introduce a partitioned model of quantum cellular automata and show how it can simulate, with the same amount of resources, various models of quantum walks. All the algorithms developed within quantum walk models are thus directly inherited by the quantum cellular automata. The latter, however, has its structure based on local interactions between qubits, and as such it can be more suitable for present (and future) experimental implementations. In the part related with numerical methods to solve differential equations, we will present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. Relative to classical algorithms for simulating the D-dimensional wave equation, our quantum algorithm achieves exponential space savings, and a speedup which is polynomial for fixed D and exponential in D. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell’s equations.
17 May 2018, 14h0015h00
Salle des commissions, Bât TPR 2 - 1er étage (Luminy)