Quantum Algorithms and Basis Changes

Quantum Algorithms and Basis Changes

ABSTRACT:

The state of an n-bit quantum computer is described by a unit vector in a 2^n-dimensional complex vector space. This means that transformations are possible, such as a square root of NOT or a Fourier transform of the amplitudes of a state, that would not even make sense for classical probability distributions. Some of these transformations, like the quantum Fourier transform, allow for exponential speedups over classical computation. In my talk, I'll review what these transformations mean and what can be accomplished with them. Then I'll talk about work I've done on efficiently implementing an operation known as the Schur transform, which is based on a quantum analogue of the type classes used in classical information theory.