Heidelberg 1999 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

KY: Kybernetik

KY 1: Quantum Computing

KY 1.3: Talk

Monday, March 15, 1999, 16:00–16:45, ZO 3

Fast Signal Transforms for Quantum Computers — •Martin R"otteler, Markus P"uschel, and Thomas Beth — Universit"at Karlsruhe

We present the discrete Fourier transform as a basic primitive in the treatment of controlled quantum systems. Based on the complexity model for quantum circuits the Fourier transform of size 2ⁿ surprisingly can be realised with O(n²) elementary operations which is an exponential speedup compared to the classical case. This is the reason for its presence in almost all known quantum algorithms among which Shor’s algorithm for factoring is the most prominent example.

We show how recent results in the theory of signal processing (for a classical computer) can be applied to obtain fast quantum algorithms for various discrete signal transforms. As an example we derive a quantum circuit implementing the discrete cosine transform DCT_IV(8) efficiently.