Quantum Circuits Seminar:
 Fast Spectral Transforms and Applications

 DoRon Motter
 Thursday, August 2 at 2:30pm
 EECS 2311

Discrete Spectral Transforms have been shown to be useful in 
obtaining global information about a Boolean function.  It has long
been known that leveraging this global information can be useful
in digital logic.  With the success of BDDs as a representation
for Boolean functions,  several new techniques have emerged for
calculating a spectral transform of a given function.

There is a fundamental relationship between the decision diagram
and a spectral transform.  The Walsh-Hadamard transform and its 
recursive definition lead naturally to a graph-based algorithm which 
efficiently computes it based on an implicit representation.  

The current applications of this technique include logic synthesis
and verification, however with the efficiency of the transformation
other applications may be possible.  After the presentation, the 
possibility of quantum speedups in these algorithms will be discussed.