Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The biggest experimental obstacle to manipulating quantum information and realizing quantum computers is noise, or decoherence. Entangled quantum states are typically difficult to prepare without accumulating errors, and are highly susceptible to noise that collapses them down to merely classical states. General quantum fault-tolerance techniques, invented about a decade ago, can in theory solve both problems, but often require unrealistically low noise rates before they kick in.

Over the last few years we have seen a renaissance in fault-tolerance schemes. These new schemes rely on quantum phenomena such as quantum teleportation to isolate the data from errors. I will describe these schemes that simulations indicate may tolerate as much as 3-6% noise per operation!

However, as classical simulations of quantum systems are difficult, it is also important to develop rigorous methods to determine if, and how well, these schemes will really work. I will describe a new technique for analyzing these schemes---maintaining analytic control over large, noisy quantum systems---that leads to a rigorous proof that 0.1% gate depolarizing noise is tolerable (in a nonlocal gate model), lending support to the simulations. If the noise model is known, then the rigorous bound is as high as 1%.

In the second part of my talk, I will present a new quantum algorithm for evaluating span programs (a linear-algebraic model of computation) that was originally inspired by scattering waves against trees. Applied to the formula evaluation problem (e.g., evaluating two-player game trees), the algorithm is optimal for many formulas for which the classical complexity is unknown. Its analysis boils down to spectral analysis of certain bipartite graphs near eigenvalue zero.

Job Talk - refreshments provided