Joseph Traub (Columbia University (on sabbatical at Harvard))
We introduce the notion of strong quantum speedup. To compute this speedup one must know the classical computational complexity. What is it about the problems of quantum physics and quantum chemistry that enable us to get lower bounds on the classical complexity?
Juerg Froehlich (ETH Zurich)
After a brief general introduction to the subject of quantum probability theory, quantum dynamical systems are introduced and some of their probabilistic features are described. On the basis of a few general principles - "duality between observables and indeterminates", "loss of information" and "entanglement generation" - a quantum theory of experiments and measurements is developed, and the "theory of von Neumann measurements" is outlined. Finally, a theory of non-demolition measurements is sketched, and, as an application of the Martingale Convergence Theorem, it is shown how facts emerge in non-demolition measurements.
Matthias Troyer (ETH Zurich)
About a century after the development of quantum mechanics we have now reached an exciting time where non-trivial devices that make use of quantum effects can be built. While a universal quantum computer of non-trivial size is still out of reach there are a number commercial and experimental devices: quantum random number generators, quantum encryption systems, and analog quantum simulators. In this colloquium I will present some of these devices and validation tests we performed on them. Quantum random number generators use the inherent randomness in quantum measurements to produce true random numbers, unlike classical pseudorandom number generators which are inherently deterministic. Optical lattice emulators use ultracold atomic gases in optical lattices to mimic typical models of condensed matter physics. Finally, I will discuss the devices built by Canadian company D-Wave systems, which are special purpose quantum simulators for solving hard classical optimization problems.
Sean Hallgren (Penn State (visiting MIT))
Computing the unit group of a number field is one of the main problems in computational algebraic number theory. Polynomial time algorithms for problems for arbitrary degree number fields should be polynomial time in both the degree and log of the discriminant. The best classical algorithms for computing the unit group takes time exponential in both parameters. There is a quantum algorithm that runs in time polynomial in log the discriminant but exponential in the degree. We give a quantum algorithm that is polynomial in both parameters of the number field. The proof works via a reduction to a continuous Hidden Subgroup Problem.