{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T06:05:23Z","timestamp":1738130723135,"version":"3.33.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,3,8]],"date-time":"2008-03-08T00:00:00Z","timestamp":1204934400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s00200-008-0072-2","type":"journal-article","created":{"date-parts":[[2008,3,7]],"date-time":"2008-03-07T10:20:57Z","timestamp":1204885257000},"page":"177-193","source":"Crossref","is-referenced-by-count":3,"title":["Representation-theoretical properties of the approximate quantum Fourier transform"],"prefix":"10.1007","volume":"19","author":[{"given":"Martin","family":"R\u00f6tteler","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Beth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,3,8]]},"reference":[{"key":"72_CR1","unstructured":"Aharonov, D., Landau, Z., Makowsky, J.: The quantum FFT can be classically simulated. ArXiv quant-ph\/0611156 (2006) (preprint)"},{"issue":"5","key":"72_CR2","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A. Barenco","year":"1995","unstructured":"Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457\u20133467 (1995)","journal-title":"Phys. Rev. A"},{"issue":"1","key":"72_CR3","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1103\/PhysRevA.54.139","volume":"54","author":"A. Barenco","year":"1996","unstructured":"Barenco, A., Ekert, A., Suominen, K.-A., T\u00f6rm\u00e4, P.: Approximate qantum Fourier transform and decoherence. Phys. Rev. A 54(1), 139\u2013146 (1996)","journal-title":"Phys. Rev. A"},{"issue":"5","key":"72_CR4","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"key":"72_CR5","unstructured":"Beth, Th.: Verfahren der Schnellen Fourier transformation. Teubner (1984)"},{"key":"72_CR6","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/0304-3975(87)90041-7","volume":"51","author":"Th. Beth","year":"1987","unstructured":"Beth, Th.: On the computational complexity of the general discrete Fourier transform. Theor. Comput. Sci. 51, 331\u2013339 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"72_CR7","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF01192776","volume":"40","author":"Th. Beth","year":"1983","unstructured":"Beth, Th., Fumy, W., M\u00fchlfeld, R.: Zur algebraischen diskreten Fourier-Transformation. Arch. Math. 40, 238\u2013244 (1983)","journal-title":"Arch. Math."},{"key":"72_CR8","doi-asserted-by":"crossref","unstructured":"Beth, Th., R\u00f6tteler, M.: Quantum algorithms: applicable algebra and quantum physics. In: Quantum Information: An Introduction to Basic Theoretical Concepts and Experiments, vol.173, Springer Texts in Modern Physics, pp. 96\u2013150. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44678-8_4"},{"key":"72_CR9","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P.: An exact polynomial-time algorithm for Simon\u2019s problem. In: Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS), pp. 12\u201323. IEEE Computer Society Press (1997)","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"72_CR10","unstructured":"Cheung, D.: Using generalized quantum Fourier transforms in quantum phase estimation algorithms. PhD thesis, University of Waterloo (2003)"},{"key":"72_CR11","unstructured":"Cheung, D.: Improved bounds for the approximate QFT. In: Proceedings of the Winter International Symposium on Information and Communication Technologies (WISICT\u201904), vol.58. ACM International Conference Proceeding Series, pp. 1\u20136, Cancun, Mexico (2004)"},{"issue":"1969","key":"72_CR12","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R. Cleve","year":"1998","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. Lond. Ser. A 454(1969), 339\u2013354 (1998)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"72_CR13","doi-asserted-by":"crossref","unstructured":"Cleve, R., Watrous, J.: Fast parallel circuits for the quantum Fourier transform. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS\u201900), pp. 526\u2013536. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892140"},{"key":"72_CR14","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J.W. Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"72_CR15","unstructured":"Coppersmith, D.: An approximate Fourier transform useful in quantum factoring. Technical Report RC 19642, IBM Research Division, see also ArXiv preprint quant-ph\/0201067 (1994)"},{"key":"72_CR16","volume-title":"Representation Theory of Finite Groups and Algebras","author":"W.C. Curtis","year":"1962","unstructured":"Curtis, W.C., Reiner, I.: Representation Theory of Finite Groups and Algebras. Wiley, London (1962)"},{"key":"72_CR17","volume-title":"Matrix Computations","author":"G. Golub","year":"1996","unstructured":"Golub, G., Van Loan, Ch.F.: Matrix Computations. The Johns Hopkins University Press, Baltimore (1996)"},{"issue":"17","key":"72_CR18","doi-asserted-by":"crossref","first-page":"3228","DOI":"10.1103\/PhysRevLett.76.3228","volume":"76","author":"R. Griffiths","year":"1996","unstructured":"Griffiths, R., Niu, C.: Semiclassical Fourier transform for quantum computation. Phys. Rev. Lett. 76(17), 3228\u20133231 (1996)","journal-title":"Phys. Rev. Lett."},{"key":"72_CR19","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s00200-007-0045-x","volume":"18","author":"B. Grohmann","year":"2007","unstructured":"Grohmann, B.: Slim normal bases and basefield transforms. Appl. Algebra Eng. Commun. Comput. 18, 397\u2013406 (2007)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"72_CR20","doi-asserted-by":"crossref","unstructured":"Hales, L., Hallgren, S.: Quantum Fourier sampling simplified. In: Proceedings of the Symposium on Theory of Computing (STOC\u201999), pp. 330\u2013338 (1999)","DOI":"10.1145\/301250.301336"},{"key":"72_CR21","doi-asserted-by":"crossref","unstructured":"Hales, L., Hallgren, S.: An improved quantum Fourier transform algorithm and applications. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS\u201900), pp. 515\u2013525. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892139"},{"issue":"1","key":"72_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206039","volume":"54","author":"S. Hallgren","year":"2007","unstructured":"Hallgren, S.: Polynomial-time quantum algorithms for Pell\u2019s equation and the principal ideal problem. J. ACM 54(1), 1\u201319 (2007)","journal-title":"J. ACM"},{"issue":"3","key":"72_CR23","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1109\/5.272145","volume":"82","author":"J. Hong","year":"1994","unstructured":"Hong, J., Vetterli, M., Duhamel, P.: Basefield transforms with the convolution property. Proc. IEEE 82(3), 400\u2013412 (1994)","journal-title":"Proc. IEEE"},{"key":"72_CR24","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1098\/rspa.1998.0163","volume":"454","author":"R. Jozsa","year":"1998","unstructured":"Jozsa, R.: Quantum algorithms and the Fourier transform. Proc. R. Soc. Lond. A 454, 323\u2013337 (1998)","journal-title":"Proc. R. Soc. Lond. A"},{"key":"72_CR25","unstructured":"Kitaev, A.Yu.: Quantum measurements and the abelian stabilizer problem. ArXiv quant\u2013ph\/9511026 (1995) (preprint)"},{"issue":"6","key":"72_CR26","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1070\/RM1997v052n06ABEH002155","volume":"52","author":"A.Yu. Kitaev","year":"1997","unstructured":"Kitaev, A.Yu.: Quantum computations: algorithms and error correction. Russ. Math. Surv. 52(6), 1191\u20131249 (1997)","journal-title":"Russ. Math. Surv."},{"key":"72_CR27","doi-asserted-by":"crossref","unstructured":"Klappenecker, A.: Basefield transforms derived from character tables. In: Proceedings of the 1997 International Conference on Acoustics, Speech, and Signal Processing (ICASSP\u201997), pp. 1997\u20132000 (1997)","DOI":"10.1109\/ICASSP.1997.599307"},{"key":"72_CR28","volume-title":"Algebra","author":"S. Lang","year":"1993","unstructured":"Lang, S.: Algebra. Addison-Wesley, Reading (1993)"},{"key":"72_CR29","doi-asserted-by":"crossref","unstructured":"Mosca, M., Ekert, A.: The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: Quantum Computing and Quantum Communications, QCQC\u201998, Palm Springs, vol. 1509, Lecture Notes in Computer Science, pp. 174\u2013188. Springer, Heidelberg (1998)","DOI":"10.1007\/3-540-49208-9_15"},{"key":"72_CR30","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"2000","unstructured":"Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"72_CR31","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithm and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134, Los Alamitos. Institute of Electrical and Electronic Engineers Computer Society Press (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"72_CR32","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0024-3795(90)90398-V","volume":"139","author":"G. Steidl","year":"1990","unstructured":"Steidl, G.: Generalization of the algebraic discrete Fourier transform with application to fast convolutions. Linear Algebra Appl. 139, 181\u2013206 (1990)","journal-title":"Linear Algebra Appl."},{"key":"72_CR33","doi-asserted-by":"crossref","unstructured":"Yoran, N., Short, A.J.: Efficient classical simulation of the approximate quantum Fourier transform. ArXiv quant\u2013ph\/0611241 (2006) (preprint)","DOI":"10.1103\/PhysRevA.76.042321"},{"issue":"2","key":"72_CR34","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1109\/TC.2007.35","volume":"56","author":"Z. Zilic","year":"2007","unstructured":"Zilic, Z., Radecka, K.: Scaling and better approximating quantum Fourier transforms by higher radices. IEEE Trans. Comput. 56(2), 202\u2013207 (2007)","journal-title":"IEEE Trans. Comput."}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-008-0072-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00200-008-0072-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-008-0072-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T23:18:06Z","timestamp":1738106286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00200-008-0072-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,8]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["72"],"URL":"https:\/\/doi.org\/10.1007\/s00200-008-0072-2","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"type":"print","value":"0938-1279"},{"type":"electronic","value":"1432-0622"}],"subject":[],"published":{"date-parts":[[2008,3,8]]}}}