{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:56Z","timestamp":1725488576801},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540443117"},{"type":"electronic","value":"9783540458333"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45833-6_25","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T10:25:53Z","timestamp":1186827953000},"page":"300-314","source":"Crossref","is-referenced-by-count":2,"title":["Quantum Optimization Problems"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,10]]},"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","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, 1510\u20131523, 1997.","journal-title":"SIAM J. Comput"},{"key":"25_CR3","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, 1411\u20131473, 1997.","journal-title":"SIAM J. Comput"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s002240000079","volume":"31","author":"H. Buhrman","year":"1998","unstructured":"H. Buhrman, J. Kadin, and T. Thierauf, Functions computable with nonadaptive queries to NP, Theory of Computing Systems, 31 (1998), 77\u201392.","journal-title":"Theory of Computing Systems"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1142\/S0129054191000133","volume":"2","author":"Z. Chen","year":"1991","unstructured":"Z. Chen and S. Toda, On the complexity of computing optimal solutions, International Journal of Foundations of Computer Science 2 (1991), 207\u2013220.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"97","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, A, 400 (1985), 97\u2013117.","journal-title":"Proc. Roy. Soc. London, A"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz, Gap-definable counting classes, J. Comput. System Sci. 48 (1994), 116\u2013148.","journal-title":"J. Comput. System Sci"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01202284","volume":"26","author":"F. Green","year":"1993","unstructured":"F. Green, On the power of deterministic reductions to C=P, Mathematical Systems Theory 26 (1993), 215\u2013233.","journal-title":"Mathematical Systems Theory"},{"key":"25_CR9","unstructured":"A. Kitaev, \u201cQuantum NP\u201d, Public Talk at AQIP\u201999: 2nd Workshop on Algorithms in Quantum Information Processing, DePaul University, 1999."},{"key":"25_CR10","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF00276023","volume":"26","author":"J. K\u00f6bler","year":"1989","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n, On counting and approximation, Acta Informatica, 26 (1989), 363\u2013379.","journal-title":"Acta Informatica"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. W. Krentel","year":"1988","unstructured":"M. W. Krentel, The complexity of optimization problems, J. Comput. System Sci., 36 (1988), 490\u2013509.","journal-title":"J. Comput. System Sci."},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(92)90073-O","volume":"97","author":"M. W. Krentel","year":"1992","unstructured":"M. W. Krentel, Generalizations of OptP to the polynomial hierarchy, Theoretical Computer Science, 97 (1992), 183\u2013198.","journal-title":"Theoretical Computer Science"},{"key":"25_CR13","unstructured":"L. Li, On the counting functions, Ph.D. thesis, Department of Computer Science, University of Chicago, 1993. Also see technical report TR 93-12."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"M. Ogiwara and L. Hemachandra, A complexity theory for feasible closure properties, J. Comput. System Sci. 46 (1993), 295\u2013325.","journal-title":"J. Comput. System Sci."},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"L. A. Hemaspaandra and M. Ogihara, The Complexity Theory Companion, Springer, 2002.","DOI":"10.1007\/978-3-662-04880-1"},{"key":"25_CR16","unstructured":"M. Ozawa and H. Nishimura, Local transition functions of quantum Turing machines, in Proceedings of the 4th International Conference on Quantum Communication, Complexity, and Measurement, 1999."},{"key":"25_CR17","unstructured":"C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998."},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant, The complexity of computing the permanent, Theor. Comput. Sci. 8 (1979), 189\u2013201.","journal-title":"Theor. Comput. Sci."},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"J. Watrous, Succinct quantum proofs for properties of finite groups, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 537\u2013546, 2000.","DOI":"10.1109\/SFCS.2000.892141"},{"key":"25_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1007\/3-540-48340-3_39","volume-title":"Proceedings of the 24th International Symposium on Mathematical Foundation of Computer Science","author":"T. Yamakami","year":"1999","unstructured":"T. Yamakami, A foundation of programming a multi-tape quantum Turing machine, in Proceedings of the 24th International Symposium on Mathematical Foundation of Computer Science, Lecture Notes in Computer Science, Vol. 1672, pp. 430\u2013441, 1999."},{"key":"25_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/3-540-46691-6_33","volume-title":"Proceedings of the 19th International Conference on Foundations of Software Technology and Theoretical Computer Science","author":"T. Yamakami","year":"1999","unstructured":"T. Yamakami, Analysis of quantum functions, in Proceedings of the 19th International Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 1738, pp. 407\u2013419, 1999."},{"key":"25_CR22","unstructured":"A. C. Yao, Quantum circuit complexity, in Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pp. 352\u2013361, 1993."}],"container-title":["Lecture Notes in Computer Science","Unconventional Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45833-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T10:12:06Z","timestamp":1708164726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45833-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540443117","9783540458333"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-45833-6_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}