Fault-tolerant quantum computation in the 21st century
Daniel Gottesman is a faculty member at the Perimeter Institute in Waterloo, Ontario. He is also a Senior Scientist with the company Quantum Benchmark. He received his Ph.D. at Caltech in 1997, and did postdocs at Los Alamos National Lab and Microsoft Research, after which he served in the UC Berkeley CS department as a Long-Term CMI Prize Fellow with the Clay Mathematics Institute.
Sparse Polynomial Approximations and their applications to Quantum Advantage, Parallel Computation, and Pseudorandomness
This talk is motivated by three (seemingly unrelated) questions:1. For which tasks do quantum algorithms outperform classical computation? 2. Does parallel computing always offer a speed-up, or are some tasks inherently sequential? 3. Do randomized algorithms have deterministic counterparts with similar memory footprint?We make progress on all three questions by exploiting a common phenomenon at the core of their analysis: in all cases, the studied computational devices can be well-approximated by sparse multivariate polynomials.
From Monogamy of Entanglement to Quantum Programming Languages: A Theorist’s Adventure in Quantum Wonderland
Recent years have witnessed a rapid development of quantum information technologies. In this talk, I will describe my personal strategies on how to contribute to this exciting field as a theorist and how my own research fits in the big picture.
Quantum cryptography and quantum information
When we encode information into physical systems that are small enough to be governed by the laws of quantum mechanics, a large part of our intuition about how information behaves goes out the window -- for example, information can no longer be copied perfectly. This has far-reaching implications in several areas of computer science, including cryptography, where it changes the rules of the game for both honest participants and potential attackers. In this talk, I will present an overview of quantum cryptography and how my own work fits in the picture.
The Nature of Quantum Speedups
Quantum algorithms appear to outperform classical algorithms on various tasks. They generally come in two flavors: those like Shor's factoring algorithm, which appears to give an exponential speedup over classical computation but only for a structured problem (and not for NP-complete problems), and those like Grover's algorithm, which gives only a polynomial (quadratic) speedup but works even for unstructured problems.
Quantum Speedups over Classical Computation
I'll talk about two questions related to quantum speedups over classical computation. First, if we had a universal quantum computer, which computational problems should we solve on it? I'll argue that the task of simulating physical systems is one of the best choices for this and discuss the state of the art for quantum algorithms solving this problem.