{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:07Z","timestamp":1725489127906},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540432838"},{"type":"electronic","value":"9783540458418"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_25","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:11:17Z","timestamp":1186906277000},"page":"311-322","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Quantum Computation with Some Restricted Amplitudes"],"prefix":"10.1007","author":[{"given":"Harumichi","family":"Nishimura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1137\/S0097539795293639","volume":"26","author":"L. M. Adleman","year":"1997","unstructured":"L. M. Adleman, J. DeMarrais, and M. A. Huang: Quantum computability. SIAM J. Comput. 26 (1997) 1524\u20131540.","journal-title":"SIAM J. Comput"},{"key":"25_CR2","unstructured":"L. Adleman and M. Huang: Recognizing primes in random polynomial time. in Proc. of 19th ACM Symposium on Theory of Computing, ACM (1987) 462\u2013470."},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"2521","DOI":"10.1080\/09500349414552351","volume":"41","author":"A. Berthiaume","year":"1994","unstructured":"A. Berthiaume and G. Brassard: Oracle quantum computing. J. Modern Opt. 41 (1994) 2521\u20132535.","journal-title":"J. Modern Opt."},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A. Barenco","year":"1995","unstructured":"A. Barenco, C. H. Bennett, R. Cleve, D. DiVicenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin and H. Weinfurter: Elementary gates for quantum computation. Phys. Rev. A, 52 (1995) 3457\u20133467.","journal-title":"Phys. Rev. A"},{"key":"25_CR5","unstructured":"E. Bernstein and U. Vazirani: Quantum complexity theory (Preliminary abstract). in Proc. of 25th ACM Symposium on Theory of Computing, ACM (1993) 11\u201320."},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"E. Bernstein and U. Vazirani: Quantum complexity theory. SIAM J. Comput. 26 (1997) 1411\u20131473.","journal-title":"SIAM J. Comput."},{"key":"25_CR7","unstructured":"G. Brassard and P. H\u00f8yer: An exact quantum polynomial-time algorithm for Simon\u2019s problem. in Proc. of 5th Israeli Symposium on Theory of Computing and Systems, IEEE (1997) 12\u201323."},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. H. Bennett","year":"1997","unstructured":"C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26 (1997) 1510\u20131523.","journal-title":"SIAM J. Comput"},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"D. Deutsch: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. London Ser. A, 400 (1985) 96\u2013117.","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"25_CR10","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1098\/rspa.1989.0099","volume":"425","author":"D. Deutsch","year":"1989","unstructured":"D. Deutsch: Quantum computational networks. Proc. Roy. Soc. London Ser. A, 425 (1989) 73\u201390.","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D. Deutsch","year":"1992","unstructured":"D. Deutsch and R. Jozsa: Rapid solution of problems by quantum computation. Proc. Roy. Soc. London Ser. A, 439 (1992) 553\u2013558.","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"25_CR12","unstructured":"S. Fenner, F. Green, S. Homer and R. Pruim: Determining acceptance probability for a quantum computation is hard for PH. in Proc. 6th Italian Conference on Theoretical Computer Science, World-Scientific (1998) 241\u2013252"},{"key":"25_CR13","unstructured":"L. Fortnow and J. Rogers: Complexity limitations on quantum computation. in Proc. 13th Conference on Computational Complexity, IEEE (1998) 202\u2013209."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(82)80003-0","volume":"20","author":"K.-I. Ko","year":"1982","unstructured":"Ker-I. Ko and H. Friedman: Computational complexity of real functions. Theoret. Comput. Sci. 20 (1982) 323\u2013352.","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1070\/RM1997v052n06ABEH002155","volume":"52","author":"A. Kitaev","year":"1997","unstructured":"A. Kitaev: Quantum computations: algorithms and error correction. Russian Math. Surveys 52 (1997) 1191\u20131249.","journal-title":"Russian Math. Surveys"},{"key":"25_CR16","unstructured":"M. A. Nielsen and I. L. Chuang: Quantum Computation and Quantum Information, Cambridge (2000)."},{"key":"25_CR17","unstructured":"H. Nishimura and M. Ozawa: Computational complexity of uniform quantum circuit families and quantum Turing machines. Theoret. Comput. Sci. (to appear). Also quant-ph\/9906095 2."},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1103\/PhysRevLett.80.631","volume":"80","author":"M. Ozawa","year":"1998","unstructured":"M. Ozawa: Quantum nondemolition monitoring of universal quantum computers. Phys. Rev. Lett. 80 (1998) 631\u2013634.","journal-title":"Phys. Rev. Lett."},{"key":"25_CR19","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1051\/ita:2000123","volume":"34","author":"M. Ozawa","year":"2000","unstructured":"M. Ozawa and H. Nishimura: Local transition functions of quantum Turing machines. RAIRO Theoret. Informatics Appl. 34 (2000) 379\u2013402.","journal-title":"RAIRO Theoret. Informatics Appl"},{"key":"25_CR20","unstructured":"C. H. Papadimitriou: Computational Complexity, Addison-Wesley (1994)."},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1098\/rspa.1998.0167","volume":"454","author":"J. Preskill","year":"1998","unstructured":"J. Preskill: Reliable quantum computers. Proc. Roy. Soc. London ser A, 454 (1998) 385\u2013410.","journal-title":"Proc. Roy. Soc. London ser A"},{"key":"#cr-split#-25_CR22.1","unstructured":"D. Simon: On the power of quantum computation. in Proc. 35th IEEE Symposium on Foundations of Computer Science, IEEE (1994) 116-123"},{"key":"#cr-split#-25_CR22.2","unstructured":"SIAM J. Comput. 26 (1997) 1474-1483."},{"key":"#cr-split#-25_CR23.1","unstructured":"P. W. Shor: Algorithms for quantum computations: Discrete log and factoring. in Proc. 35th IEEE Symposium on Foundations of Computer Science, IEEE (1994) 124-134."},{"key":"#cr-split#-25_CR23.2","doi-asserted-by":"crossref","unstructured":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484-1509.","DOI":"10.1137\/S0097539795293172"},{"key":"25_CR24","unstructured":"P. W. Shor: Fault-tolerant quantum computation. in Proc. 37th IEEE Symposium on Foundations of Computer Science, IEEE (1996) 56\u201365."},{"key":"25_CR25","unstructured":"U. V. Vazirani and V. V. Vazirani: Random polynomial time equals semi-random polynomial time. in Proc. 26th IEEE Symposium on Foundations of Computer Science, IEEE (1985) 417\u2013428."},{"key":"25_CR26","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"K. Wagner: The complexity of combinatorial problems with succinct input representation. Acta Inf. 23 (1986) 325\u2013361.","journal-title":"Acta Inf."},{"key":"25_CR27","unstructured":"T. Yamakami: A foundation of programming a multi-tape quantum Turing machine. in Proc. 24th International Symposium on Mathmatical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1672 (1999) 430\u2013441."},{"key":"25_CR28","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(99)00084-8","volume":"71","author":"T. Yamakami","year":"1999","unstructured":"T. Yamakami and A. Yao: NQPC = co-C=P. Inform. Process. Lett. 71 (1999) 63\u201369.","journal-title":"Inform. Process. Lett."},{"key":"25_CR29","unstructured":"A. Yao: Quantum circuit complexity. in Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, IEEE (1993) 352\u2013361."}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T00:53:55Z","timestamp":1558486435000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"21 February 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}