Quantum computation of Fourier transforms over symmetric groups
Quantum computation of Fourier transforms over symmetric groups
复制标题
对称群上傅里叶变换的量子计算
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
R. Beals
中科院分区：
文献类型：
--
作者：
R. Beals
量子复杂性理论中的许多算法发展，包括Shor著名的因子分解和离散对数算法，都利用了阿贝尔群上的傅里叶变换。也就是说，在计算中的某个点处，macline处于与有限阿贝尔群G的元素相对应的状态的叠加中，并且处于量子多项式时间（即，logIGI中的多项式），根据傅里叶变换将机器变换为对应于G的不可约表示的状态的叠加。我们给出了一个量子多项式时间算法的傅里叶变换的对称群Sn，适应克劳森和Diaconis-Rockmore的量子设置。
Many algorithmic developments in quantum complexity theory, including Shor’s celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups. That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G. We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis–Rockmore to the quantum setting.