Simon's Algorithm, Clebsch-Gordan Sieves, and Hidden Symmetries of Multiple Squares

Abstract

The first quantum algorithm to offer an exponential speedup (in the query complexity setting) over classical algorithms was Simon's algorithm for identifying a hidden exclusive-or mask. Here we observe how part of Simon's algorithm can be interpreted as a Clebsch-Gordan transform. Inspired by this we show how Clebsch-Gordan transforms can be used to efficiently find a hidden involution on the group G^n where G is the dihedral group of order eight (the group of symmetries of a square.) This problem previously admitted an efficient quantum algorithm but a connection to Clebsch-Gordan transforms had not been made. Our results provide further evidence for the usefulness of Clebsch-Gordan transform in quantum algorithm design.

10 pages

References in corpus (4)

• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• The Hidden Subgroup Problem - Review and Open Problems
• An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups