{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:26:37Z","timestamp":1778732797086,"version":"3.51.4"},"reference-count":24,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2002,4,1]],"date-time":"2002-04-01T00:00:00Z","timestamp":1017619200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4125,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,4]]},"DOI":"10.1016\/s0304-3975(01)00111-6","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T15:44:18Z","timestamp":1027611858000},"page":"147-181","source":"Crossref","is-referenced-by-count":28,"title":["Computational complexity of uniform quantum circuit families and quantum Turing machines Communicated by O. Watanabe"],"prefix":"10.1016","volume":"276","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":"78","reference":[{"key":"10.1016\/S0304-3975(01)00111-6_BIB1","doi-asserted-by":"crossref","first-page":"1524","DOI":"10.1137\/S0097539795293639","article-title":"Quantum computability","volume":"26","author":"Adleman","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB2","doi-asserted-by":"crossref","unstructured":"L.M. Adleman, M.A. Huang, in: Primality testing and two dimensional Abelian varieties over finite fields, Lecture Notes in Math., Vol. 1512, Springer, New York, 1992.","DOI":"10.1007\/BFb0090185"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB3","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","article-title":"Elementary gates for quantum computation","volume":"52","author":"Barenco","year":"1995","journal-title":"Phys. Rev. A"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB4","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF01011339","article-title":"The computer as a physical system","volume":"22","author":"Benioff","year":"1980","journal-title":"J. Statist. Phys."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB5","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1147\/rd.176.0525","article-title":"Logical reversibility of computation","volume":"17","author":"Bennett","year":"1973","journal-title":"IBM J. Res. Develop."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB6","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","article-title":"Strengths and weaknesses of quantum computing","volume":"26","author":"Bennett","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB7","series-title":"Quantum complexity theory (preliminary abstract), Proc. 25th Annual ACM Symp. on Theory of Computing","first-page":"11","author":"Bernstein","year":"1993"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB8","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","article-title":"Quantum complexity theory","volume":"26","author":"Bernstein","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB9","doi-asserted-by":"crossref","first-page":"2521","DOI":"10.1080\/09500349414552351","article-title":"Oracle quantum computing","volume":"41","author":"Berthiaume","year":"1994","journal-title":"J. Modern Opt."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB10","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1098\/rspa.1985.0070","article-title":"Quantum theory, the Church-Turing principle and the universal quantum computer","volume":"400","author":"Deutsch","year":"1985","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB11","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1098\/rspa.1989.0099","article-title":"Quantum computational networks","volume":"425","author":"Deutsch","year":"1989","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB12","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","article-title":"Rapid solution of problems by quantum computation","volume":"439","author":"Deutsch","year":"1992","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB13","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1103\/RevModPhys.68.733","article-title":"Shor's quantum algorithm for factoring numbers","volume":"68","author":"Ekert","year":"1996","journal-title":"Rev. Modern Phys."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB14","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","article-title":"Simulating physics with computers","volume":"21","author":"Feynman","year":"1982","journal-title":"Internat. J. Theoret. Phys."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB15","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1070\/RM1997v052n06ABEH002155","article-title":"Quantum computations","volume":"52","author":"Kitaev","year":"1997","journal-title":"Russian Math. Surveys"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB16","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(82)80003-0","article-title":"Computational complexity of real functions","volume":"20","author":"Ko","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB17","unstructured":"M. Ozawa, H. Nishimura, Local transition functions of quantum Turing machines, RAIRO Theor. Inform. Appl. to appear. Eprint available from http:\/\/xxx.lanl.gov\/archive\/quant-ph\/9811069."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB18","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB19","series-title":"Algorithms for quantum computations: discrete log and factoring, Proc. 35th Annual IEEE Symp. on Foundations of Computer Science","first-page":"124","author":"Shor","year":"1994"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB20","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB21","series-title":"On the power of quantum computation, Proc. 35th Annual IEEE Symp. on Foundations of Computer Science","first-page":"116","author":"Simon","year":"1994"},{"key":"10.1016\/S0304-3975(01)00111-6_BIB22","unstructured":"R. Solovay, Private communication."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB23","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","article-title":"A fast Monte-Carlo test for primality","volume":"6","author":"Solovay","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00111-6_BIB24","series-title":"Quantum circuit complexity, Proc. 34th Annual IEEE Symp. on Foundations of Computer Science","first-page":"352","author":"Yao","year":"1993"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001116?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001116?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T04:25:52Z","timestamp":1555907152000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501001116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,4]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2002,4]]}},"alternative-id":["S0304397501001116"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00111-6","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,4]]}}}