{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T15:08:42Z","timestamp":1726758522075},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,10]]},"abstract":"\n The\n quantum Fourier transform<\/jats:italic>\n (QFT) is a principal ingredient appearing in many efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by \u201cquantizing\u201d the highly successful\n separation of variables<\/jats:italic>\n technique for the construction of efficient classical Fourier transforms. Specifically, we apply Bratteli diagrams, Gel'fand-Tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all families of groups for which efficient QFTs are currently known and many new families as well. Moreover, our method provides the first subexponential-size quantum circuits for the QFT over the linear groups GL\n \n k<\/jats:italic>\n <\/jats:sub>\n (\n q<\/jats:italic>\n ), SL\n \n k<\/jats:italic>\n <\/jats:sub>\n (\n q<\/jats:italic>\n ), and the finite groups of Lie type, for any fixed prime power\n q<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/1198513.1198525","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"707-723","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Generic quantum Fourier transforms"],"prefix":"10.1145","volume":"2","author":[{"given":"Cristopher","family":"Moore","sequence":"first","affiliation":[{"name":"University of New Mexico and the Santa Fe Institute, Albuquerque, NM"}]},{"given":"Daniel","family":"Rockmore","sequence":"additional","affiliation":[{"name":"Dartmouth College"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[{"name":"University of Connecticut"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258548"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90041-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90021-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968599"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_7_1","volume-title":"Tech. Rep. RC19642","author":"Coppersmith D.","year":"1994"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1030655-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380769"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796589"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335392"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","volume-title":"Graph Theory","author":"Harary F.","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378679"},{"key":"e_1_2_1_15_1","volume-title":"II. Lecture Notes in Mathematics","author":"Kerber A."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-97-00219-1"},{"key":"e_1_2_1_18_1","first-page":"1151","article-title":"The Cooley-Tukey FFT and group theory","volume":"48","author":"Maslen D.","year":"2001","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Maslen D. K."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Moore C."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (AAECC-13)","volume":"1719","author":"P\u00fcschel M."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(90)90008-M"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/acha.1995.1020"},{"key":"e_1_2_1_24_1","volume-title":"Linear Representations of Finite Groups","author":"Serre J.-P."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_26_1","volume-title":"Graduate Studies in Mathematics","volume":"10","author":"Simon B.","year":"1996"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380759"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1198513.1198525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:34:03Z","timestamp":1672259643000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1198513.1198525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1198513.1198525"],"URL":"https:\/\/doi.org\/10.1145\/1198513.1198525","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
