{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T14:42:31Z","timestamp":1750603351169},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2009,2]]},"DOI":"10.1007\/s11128-008-0091-8","type":"journal-article","created":{"date-parts":[[2009,1,15]],"date-time":"2009-01-15T16:00:01Z","timestamp":1232035201000},"page":"13-24","source":"Crossref","is-referenced-by-count":15,"title":["Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families"],"prefix":"10.1007","volume":"8","author":[{"given":"Harumichi","family":"Nishimura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masanao","family":"Ozawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,16]]},"reference":[{"key":"91_CR1","doi-asserted-by":"crossref","first-page":"1524","DOI":"10.1137\/S0097539795293639","volume":"26","author":"L.M. Adleman","year":"1997","unstructured":"Adleman L.M., DeMarrais J., Huang M.A.: Quantum computability. SIAM J. Comput. 26, 1524\u20131540 (1997)","journal-title":"SIAM J. Comput."},{"key":"91_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., DiVicenzo D.P., Margolus N., Shor P., Sleator T., Smolin J., Weinfurter H.: Elementary gates for quantum computation. Phys. Rev. A 52, 3457\u20133467 (1995)","journal-title":"Phys. Rev. A"},{"key":"91_CR3","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P.W. Beame","year":"1986","unstructured":"Beame P.W., Cook S.A., Hoover H.J.: Log depth circuits for division and related problems. SIAM J. Comput. 15, 994\u20131003 (1986)","journal-title":"SIAM J. Comput."},{"key":"91_CR4","doi-asserted-by":"crossref","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory (preliminary abstract). In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 11\u201320. ACM Press, New York (1993)","DOI":"10.1145\/167088.167097"},{"key":"91_CR5","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, 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"key":"91_CR6","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"Borodin A.: On relating time and space to and size and depth. SIAM J. Comput. 6, 733\u2013743 (1977)","journal-title":"SIAM J. Comput."},{"key":"91_CR7","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lon. Ser. A 400, 96\u2013117 (1985)","journal-title":"Proc. R. Soc. Lon. Ser. A"},{"key":"91_CR8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1098\/rspa.1989.0099","volume":"425","author":"D. Deutsch","year":"1989","unstructured":"Deutsch D.: Quantum computational networks. Proc. R. Soc. Lon. Ser. A 425, 73\u201390 (1989)","journal-title":"Proc. R. Soc. Lon. Ser. A"},{"key":"91_CR9","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1103\/RevModPhys.68.733","volume":"68","author":"A. Ekert","year":"1996","unstructured":"Ekert A., Jozsa R.: Shor\u2019s quantum algorithm for factoring numbers. Rev. Modern Phys. 68, 733\u2013753 (1996)","journal-title":"Rev. Modern Phys."},{"key":"91_CR10","first-page":"35","volume":"2","author":"F. Green","year":"2002","unstructured":"Green F., Homer S., Moore C., Pollett C.: Counting, fanout, and the complexity of quantum ACC. Quantum Inf. Comput. 2, 35\u201365 (2002)","journal-title":"Quantum Inf. Comput."},{"key":"91_CR11","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska J.: Quantum Computing. McGraw-Hill, Berkshire (1999)"},{"key":"91_CR12","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(82)80003-0","volume":"20","author":"K.-I. Ko","year":"1982","unstructured":"Ko K.-I., Friedman H.: Computational complexity of real functions. Theor. Comput. Sci. 20, 323\u2013352 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"91_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions","author":"K.-I. Ko","year":"1991","unstructured":"Ko K.-I.: Complexity Theory of Real Functions. Birkh\u00e4user, Basel (1991)"},{"key":"91_CR14","doi-asserted-by":"crossref","unstructured":"Kitaev, A., Watrous, J.: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 608\u2013617. ACM Press, New York (2000)","DOI":"10.1145\/335305.335387"},{"key":"91_CR15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1142\/S0219749904000109","volume":"2","author":"M. Mosca","year":"2004","unstructured":"Mosca M., Zalka C.: Exact quantum Fourier transforms and discrete logarithm algorithms. Int. J. Quantum Inf. 2, 91\u2013100 (2004)","journal-title":"Int. J. Quantum Inf."},{"key":"91_CR16","unstructured":"M\u00f6tt\u00f6nen, M., Vartiainen, J.J.: Decomposition of general quantum gates. Available via http:\/\/arxiv.org\/quant-ph\/0504100"},{"key":"91_CR17","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen M.A., Chuang I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"91_CR18","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1142\/S0129054103002059","volume":"14","author":"H. Nishimura","year":"2003","unstructured":"Nishimura H.: Quantum computation with restricted amplitudes. Int. J. Found. Comput. Sci. 14, 853\u2013870 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"91_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0304-3975(01)00111-6","volume":"276","author":"H. Nishimura","year":"2002","unstructured":"Nishimura H., Ozawa M.: Computational complexity of uniform quantum circuit families and quantum Turing machines. Theor. Comput. Sci. 276, 147\u2013181 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"91_CR20","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/j.tcs.2004.12.020","volume":"392","author":"H. Nishimura","year":"2005","unstructured":"Nishimura H., Ozawa M.: Uniformity of quantum circuit families for error-free algorithms. Theor. Comput. Sci. 392, 487\u2013496 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"91_CR21","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1051\/ita:2000123","volume":"34","author":"M. Ozawa","year":"2000","unstructured":"Ozawa M., Nishimura H.: Local transition functions of quantum Turing machines. RAIRO Theor. Inform. Appl. 34, 379\u2013402 (2000)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"91_CR22","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou C.H.: Computational Complexity. Addison-Wesley, Reading, MA (1994)"},{"key":"91_CR23","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"21","author":"W.L. Ruzzo","year":"1981","unstructured":"Ruzzo W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 21, 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"91_CR24","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput 26, 1484\u20131509 (1997)","journal-title":"SIAM J. Comput"},{"key":"91_CR25","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Fault-tolerant quantum computation. In: Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pp. 56\u201365. IEEE Computer Society Press, Los Alamitos, CA (1996)","DOI":"10.1109\/SFCS.1996.548464"},{"key":"91_CR26","doi-asserted-by":"crossref","unstructured":"Yamakami, T.: A foundation of programming a multi-tape quantum Turing machine. In: Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 1672, pp. 430\u2013441 (1999)","DOI":"10.1007\/3-540-48340-3_39"},{"key":"91_CR27","unstructured":"Yao, A.C.-C.: Quantum circuit complexity. In: Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 352\u2013361. IEEE Computer Society Press, Los Alamitos, CA (1993)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-008-0091-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T09:18:01Z","timestamp":1558084681000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-008-0091-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,16]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["91"],"URL":"https:\/\/doi.org\/10.1007\/s11128-008-0091-8","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,16]]}}}