1306.2008 (Li Yang et al.)

A note on Simon's period-finding quantum algorithm    [PDF]

Li Yang, Hong-Wei Li

We propose a quantum algorithm to determine the linear structure of a Boolean function executed by a quantum oracle, and show that Simon's original problem can also be solved with this method. For a Boolean function provided with polynomial size representation, we find an efficient algorithm to compute its linear structure. In addition, we present some interesting properties of the linear structure of Boolean functions.

View original: http://arxiv.org/abs/1306.2008