{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:30:14Z","timestamp":1725507014791},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_67","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"784-792","source":"Crossref","is-referenced-by-count":8,"title":["Solving NP-Complete Problems with Quantum Search"],"prefix":"10.1007","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"67_CR1","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L.K. Grover","year":"1997","unstructured":"Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters\u00a079(2), 325\u2013328 (1997)","journal-title":"Physical Review Letters"},{"key":"67_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/276698.276712","volume-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998)","author":"L.K. Grover","year":"1998","unstructured":"Grover, L.K.: A framework for fast quantum mechanical algorithms. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 53\u201362. ACM Press, New York (1998)"},{"key":"67_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-45687-2_7","volume-title":"Mathematical Foundations of Computer Science 2002","author":"O. Angelsmark","year":"2002","unstructured":"Angelsmark, O., Dahll\u00f6f, V., Jonsson, P.: Finite domain constraint satisfaction using quantum computation. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 93\u2013103. Springer, Heidelberg (2002)"},{"key":"67_CR4","first-page":"329","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001)","author":"D. Eppstein","year":"2001","unstructured":"Eppstein, D.: Improved algorithms for 3-Coloring, 3-Edge-Coloring, and constraint satisfaction. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 329\u2013337. ACM Press, New York (2001)"},{"issue":"3","key":"67_CR5","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1103\/PhysRevA.61.032303","volume":"61","author":"N. Cerf","year":"2000","unstructured":"Cerf, N., Grover, L., Williams, C.: Nested quantum search and structured problems. Phys. Rev. A\u00a061(3) (2000) 14 032303.","journal-title":"Phys. Rev. A"},{"key":"67_CR6","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Lomonaco Jr., S.J., Brandt, H.E. (eds.) Quantum Computation and Information, AMS Contemporary Mathematics, vol.\u00a0305, pp. 53\u201374 (2002), http:\/\/arxiv.org\/abs\/quant-ph\/0005055","DOI":"10.1090\/conm\/305\/05215"},{"issue":"2","key":"67_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/992287.992296","volume":"35","author":"A. Ambainis","year":"2004","unstructured":"Ambainis, A.: Quantum search algorithms. ACM SIGACT News\u00a035(2), 22\u201335 (2004)","journal-title":"ACM SIGACT News"},{"issue":"4","key":"67_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/1107523.1107524","volume":"36","author":"E. Dantsin","year":"2005","unstructured":"Dantsin, E., Kreinovich, V., Wolpert, A.: On quantum versions of record-breaking algorithms for sat. ACM SIGACT News\u00a036(4), 103\u2013108 (2005)","journal-title":"ACM SIGACT News"},{"key":"67_CR9","first-page":"410","volume-title":"40th Annual Symposium on Foundations of Computer Science (FOCS 1999)","author":"U. Sch\u00f6ning","year":"1999","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: 40th Annual Symposium on Foundations of Computer Science (FOCS 1999), Washington - Brussels - Tokyo, pp. 410\u2013414. IEEE, Los Alamitos (1999)"},{"key":"67_CR10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. Journal of Association Computer Machinery\u00a07, 201\u2013215 (1960)","journal-title":"Journal of Association Computer Machinery"},{"issue":"7","key":"67_CR11","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Communications of the ACM\u00a05(7), 394\u2013397 (1962)","journal-title":"Communications of the ACM"},{"key":"67_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G. Woeginger","year":"2003","unstructured":"Woeginger, G.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"},{"issue":"1","key":"67_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2\u2009\u2212\u20092\/(k\u2009+\u20091)) n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"67_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science\u00a0223, 1\u201372 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"67_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V. Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2SAT and 3SAT formulae. Theoretical Computer Science\u00a0332(1-3), 265\u2013291 (2005)","journal-title":"Theoretical Computer Science"},{"key":"67_CR16","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M. Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortsch. Phys.\u00a046, 493\u2013506 (1998)","journal-title":"Fortsch. Phys."},{"key":"67_CR17","doi-asserted-by":"publisher","first-page":"4329","DOI":"10.1103\/PhysRevLett.80.4329","volume":"80","author":"L.K. Grover","year":"1998","unstructured":"Grover, L.K.: Quantum computers can search rapidly by using almost any transformation. Physical Review Letters\u00a080, 4329\u20134332 (1998)","journal-title":"Physical Review Letters"},{"key":"67_CR18","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: Rapid sampling through quantum computing. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 618\u2013626 (2000)","DOI":"10.1145\/335305.335389"},{"key":"67_CR19","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1201\/9781420035377","volume-title":"Mathematics of Quantum Computation. Computational Mathematics","author":"G. Chen","year":"2002","unstructured":"Chen, G., Sun, S.: Generalization of Grover\u2019s algorithm to multiobject search in quantum computing, Part II: general unitary transformations. In: Brylinski, R., Chen, G. (eds.) Mathematics of Quantum Computation. Computational Mathematics, pp. 161\u2013168. Chapman & Hall\/CRC, Boca Raton, London, New York, Washington, D.C (2002)"},{"issue":"3","key":"67_CR20","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput.\u00a06(3), 537\u2013546 (1977)","journal-title":"SIAM J. Comput."},{"key":"67_CR21","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: SODA 1999. Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, pp. 856\u2013857 (1999)"},{"key":"67_CR22","unstructured":"Dantsin, E., Hirsch, E.A., Ivanov, S., Vsemirnov, M.: Algorithms for SAT and upper bounds on their complexity. Technical Report TR01-012, Electronic Colloquium on Computational Complexity (ECCC) (2001)"},{"key":"67_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/11682462_46","volume-title":"LATIN 2006: Theoretical Informatics","author":"M. F\u00fcrer","year":"2006","unstructured":"F\u00fcrer, M.: A faster algorithm for finding maximum independent sets in sparse graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 491\u2013501. Springer, Heidelberg (2006)"},{"key":"67_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-540-69507-3_22","volume-title":"SOFSEM 2007: Theory and Practice of Computer Science","author":"M. F\u00fcrer","year":"2007","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Exact Max 2-SAT: Easier and faster. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Pl\u00e1\u0161il, F. (eds.) SOFSEM 2007. LNCS, vol.\u00a04362, pp. 272\u2013283. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:21:49Z","timestamp":1619522509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_67","relation":{},"subject":[]}}