{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T05:22:57Z","timestamp":1698729777155},"reference-count":21,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,9,15]],"date-time":"2021-09-15T00:00:00Z","timestamp":1631664000000},"content-version":"am","delay-in-days":365,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#am"},{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100006235","name":"Lawrence Berkeley National Laboratory","doi-asserted-by":"publisher","award":["DE\u2010AC02\u201005CH11231"]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Numerical Linear Algebra App"],"published-print":{"date-parts":[[2021,1]]},"abstract":"Summary<\/jats:title>The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank\u20101 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix\u20102 QFT decomposition to a radix\u2010d<\/jats:italic> QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.<\/jats:p>","DOI":"10.1002\/nla.2331","type":"journal-article","created":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T11:27:55Z","timestamp":1601033275000},"update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Quantum Fourier transform revisited"],"prefix":"10.1002","volume":"28","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-0236-4353","authenticated-orcid":false,"given":"Daan","family":"Camps","sequence":"first","affiliation":[{"name":"Computational Research Division Lawrence Berkeley National Laboratory Berkeley California USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-2276-1153","authenticated-orcid":false,"given":"Roel","family":"Van Beeumen","sequence":"additional","affiliation":[{"name":"Computational Research Division Lawrence Berkeley National Laboratory Berkeley California USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-7172-7539","authenticated-orcid":false,"given":"Chao","family":"Yang","sequence":"additional","affiliation":[{"name":"Computational Research Division Lawrence Berkeley National Laboratory Berkeley California USA"}]}],"member":"311","published-online":{"date-parts":[[2020,9,15]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"issue":"1","key":"e_1_2_9_3_1","first-page":"22","article-title":"The top 10 algorithms","volume":"2","author":"Sullivan F","year":"2000","journal-title":"Comput Sci Eng"},{"key":"e_1_2_9_4_1","volume-title":"An approximate Fourier transform useful in quantum factoring. IBM Research Report RC 19642","author":"Coppersmith D.","year":"1994"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_2_9_6_1","unstructured":"LomontC.Quantum convolution and quantum correlation algorithms are physically impossible.2003. arXiv:quantph\/0309070."},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321450.321457"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1974.1083790"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223306"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970999"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1088\/0253-6102\/55\/5\/11"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/09500340210123947"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749915500598"},{"key":"e_1_2_9_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm192761164"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-012-9227-4"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2011.11.008"},{"issue":"1868","key":"e_1_2_9_17_1","first-page":"73","article-title":"Quantum computational networks","volume":"425","author":"Deutsch D","year":"1989","journal-title":"Proc R Soc Lond Ser A Math Phys Eng Sci"},{"key":"e_1_2_9_18_1","volume-title":"On the synthesis of quantum circuits for diagonal operators in quantum computation","author":"Welch JM","year":"2015"},{"issue":"1","key":"e_1_2_9_19_1","first-page":"27","article-title":"Asymptotically optimal circuits for arbitrary n\u2010qubit diagonal computations","volume":"4","author":"Bullock SS","year":"2004","journal-title":"Quantum Inf Comput"},{"issue":"10","key":"e_1_2_9_20_1","first-page":"1749","article-title":"Fault\u2010tolerant quantum computation with higher\u2010dimensional systems","volume":"10","author":"Gottesman D","year":"1999","journal-title":"Chaos Soliton Fract"},{"key":"e_1_2_9_21_1","unstructured":"KitaevAY. Quantum measurements and the Abelian stabilizer problem;1995. arXiv preprint quant\u2010ph\/9511026."},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"}],"container-title":["Numerical Linear Algebra with Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2331","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/nla.2331","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/am-pdf\/10.1002\/nla.2331","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T07:14:27Z","timestamp":1693811667000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/nla.2331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,15]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1002\/nla.2331"],"URL":"http:\/\/dx.doi.org\/10.1002\/nla.2331","archive":["Portico"],"relation":{},"ISSN":["1070-5325","1099-1506"],"issn-type":[{"value":"1070-5325","type":"print"},{"value":"1099-1506","type":"electronic"}],"subject":["Applied Mathematics","Algebra and Number Theory"],"published":{"date-parts":[[2020,9,15]]},"assertion":[{"value":"2020-03-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-13","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}