Fast parallel circuits for the quantum Fourier transform

被引:127
作者
Cleve, R [1 ]
Watrous, J [1 ]
机构
[1] Univ Calgary, Dept Comp Sci, Calgary, AB T2N 1N4, Canada
来源
41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2000年
关键词
D O I
10.1109/SFCS.2000.892140
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(logn + log log(1/epsilon)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2(n) with error bounded by epsilon. Thus, even for exponentially small error, our circuits have depth O(logn). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log(n/epsilon)). As an application of this depth bound, we show that Shor's factoring algorithm may be based on quantum circuits with depth only O(logn) and polynomial size, in combination with classical polynomial-time pre- and postprocessing. Next, we prove an 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 epsilon). We also give an upper bound of O(n(log n)(2) log log n) on the circuit size of the exact QFT module 2(n), for which the best previous bound was O(n(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 epsilon with circuits of depth O((log log m) (log log 1/epsilon)) and size polynomial in log m + log(1/epsilon).
引用
收藏
页码:526 / 536
页数:11
相关论文
共 36 条
[1]  
Aharonov D., 1997, P 29 ANN ACM S THEOR, P176, DOI DOI 10.1145/258533.258579
[2]  
[Anonymous], 1995, QUANTPH9511026
[3]  
Bach E., 1996, ALGORITHMIC NUMBER T
[4]   ELEMENTARY GATES FOR QUANTUM COMPUTATION [J].
BARENCO, A ;
BENNETT, CH ;
CLEVE, R ;
DIVINCENZO, DP ;
MARGOLUS, N ;
SHOR, P ;
SLEATOR, T ;
SMOLIN, JA ;
WEINFURTER, H .
PHYSICAL REVIEW A, 1995, 52 (05) :3457-3467
[5]   LOG DEPTH CIRCUITS FOR DIVISION AND RELATED PROBLEMS [J].
BEAME, PW ;
COOK, SA ;
HOOVER, HJ .
SIAM JOURNAL ON COMPUTING, 1986, 15 (04) :994-1003
[6]   LOGICAL REVERSIBILITY OF COMPUTATION [J].
BENNETT, CH .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1973, 17 (06) :525-532
[7]   Strengths and weaknesses of quantum computing [J].
Bennett, CH ;
Bernstein, E ;
Brassard, G ;
Vazirani, U .
SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1510-1523
[8]  
Boneh D, 1995, LECT NOTES COMPUT SC, V963, P424
[9]  
Brassard G, 1998, LECT NOTES COMPUT SC, V1443, P820, DOI 10.1007/BFb0055105
[10]  
CHIU A, 1999, UNPUB NC1 DIV