Fast parallel circuits for the quantum Fourier transform
Fast parallel circuits for the quantum Fourier transform
复制标题
DOI：
10.1109/sfcs.2000.892140
复制
发表时间：
2000-06
期刊：
影响因子：
--
通讯作者：
R. Cleve;John Watrous
中科院分区：
文献类型：
--
作者：
R. Cleve;John Watrous
给出了量子傅立叶变换（QFT）电路复杂度的新边界。我们给出了电路深度的上界O(log n+log log(1//spl epsiv/))，用于计算QFT对模数2/sup n/的近似，误差以/spl epsiv/为界。因此，即使是指数级的小误差，我们的电路的深度也是O（log n）。最好的以前的深度范围是O(n)，即使对于具有恒定误差的近似。此外，我们的电路尺寸为O（n log(n//spl epsiv/)）。作为该深度界的一个应用，我们证明了P. Shor（1997）分解算法可以基于深度仅为O（log n）和多项式大小的量子电路，并结合经典的多项式时间预处理和后处理。接下来，我们证明了具有恒定误差的QFT近似的深度复杂度的/spl ω /(log n)下界。这意味着上面的上界是渐近紧密的（对于/spl / epsiv/的合理范围）。我们还给出了精确QFT模2/sup n/电路大小的上界为O(n(log n)/sup 2/ log log n)，其中最佳上界为O（n/sup 2/）。最后，基于我们的2次幂模QFT电路，我们证明了QFT关于任意模m的精度/spl epsiv/可以用深度为O((log log m)（log log 1//spl epsiv/）和大小为log m+log（1//spl epsiv/）的电路近似。
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n+log log(1//spl epsiv/)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2/sup n/ with error bounded by /spl epsiv/. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log(n//spl epsiv/)). As an application of this depth bound, we show that P. Shor's (1997) factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time pre- and postprocessing. Next, we prove an /spl Omega/(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically tight (for a reasonable range of values of /spl epsiv/). We also give an upper bound of O(n(log n)/sup 2/ log log n) on the circuit size of the exact QFT modulo 2/sup n/, for which the best previous bound was O(n/sup 2/). Finally, based on our circuits for the QFT with power-of-2 moduli, we show that the QFT with respect to an arbitrary modulus m can be approximated with accuracy /spl epsiv/ with circuits of depth O((log log m)(log log 1//spl epsiv/)) and size polynomial in log m+log(1//spl epsiv/).