{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:20Z","timestamp":1759638320419,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_34","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"388-397","source":"Crossref","is-referenced-by-count":6,"title":["Reconstructing Strings from Substrings with Quantum Queries"],"prefix":"10.1007","author":[{"given":"Richard","family":"Cleve","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seiichiro","family":"Tani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junichi","family":"Teruyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeru","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"34_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0020-0190(99)00079-4","volume":"71","author":"A. Ambainis","year":"1999","unstructured":"Ambainis, A.: A note on quantum black-box complexity of almost all Boolean functions. Inf. Process. Lett.\u00a071(1), 5\u20137 (1999)","journal-title":"Inf. Process. Lett."},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: A better lower bound for quantum algorithms searching an ordered list. In: Proc. 40th FOCS, pp. 352\u2013357 (1999)","DOI":"10.1109\/SFFCS.1999.814606"},{"issue":"4","key":"34_CR3","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci.\u00a064(4), 750\u2013767 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"34_CR4","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R. Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM\u00a048(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Hassidim, A.: The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In: Proc. 49th FOCS, pp. 221\u2013230 (2008)","DOI":"10.1109\/FOCS.2008.58"},{"issue":"5","key":"34_CR6","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J.\u00a0Comput.\u00a026(5), 1411\u20131473 (1997)","journal-title":"SIAM J.\u00a0Comput."},{"key":"34_CR7","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. Fortschritte Der Physik\u00a046, 493\u2013505 (1998)","journal-title":"Fortschritte Der Physik"},{"issue":"5","key":"34_CR8","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(99)00069-1","volume":"70","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., de Wolf, R.: A lower bound for quantum search of an ordered list. Inf.\u00a0Process.\u00a0Lett.\u00a070(5), 205\u2013209 (1999)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"van Dam, W.: Quantum oracle interrogation: Getting all information for almost half the price. In: Proc.\u00a039th FOCS, pp. 362\u2013367 (1998)","DOI":"10.1109\/SFCS.1998.743486"},{"key":"34_CR10","unstructured":"Dramanac, R., Crkvenjakov, R.: DNA sequencing by hybridization. Yugoslav Patent Application 570 (1987)"},{"issue":"3","key":"34_CR11","doi-asserted-by":"crossref","first-page":"032335","DOI":"10.1103\/PhysRevA.75.032335","volume":"75","author":"A.M. Childs","year":"2007","unstructured":"Childs, A.M., Landahl, A.J., Parrilo, P.A.: Improved quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A\u00a075(3), 032335 (2007)","journal-title":"Physical Review A"},{"key":"34_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1007\/978-3-540-70575-8_71","volume-title":"Automata, Languages and Programming","author":"A.M. Childs","year":"2008","unstructured":"Childs, A.M., Lee, T.: Optimal Quantum Adversary Lower Bounds for Ordered Search. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 869\u2013880. Springer, Heidelberg (2008)"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Cleve, R., Iwama, K., Le Gall, F., Nishimura, H., Tani, S., Teruyama, J., Yamashita, S.: Reconstructing Strings from Substrings with Quantum Queries. arXiv:1204.4691 (2012)","DOI":"10.1007\/978-3-642-31155-0_34"},{"key":"34_CR14","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: A limit on the speed of quantum computation for insertion into an ordered list, arXiv:quant-ph\/9812057"},{"key":"34_CR15","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Invariant quantum algorithms for insertion into an ordered list, arXiv:quant-ph\/9901059"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. 28th STOC, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"4","key":"34_CR17","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00453-002-0976-3","volume":"34","author":"P. H\u00f8yer","year":"2002","unstructured":"H\u00f8yer, P., Neerbek, J., Shi, Y.: Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica\u00a034(4), 429\u2013448 (2002)","journal-title":"Algorithmica"},{"key":"34_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-17517-6_10","volume-title":"Algorithms and Computation","author":"K. Iwama","year":"2010","unstructured":"Iwama, K., Nishimura, H., Raymond, R., Teruyama, J.: Quantum Counterfeit Coin Problems. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol.\u00a06506, pp. 85\u201396. Springer, Heidelberg (2010)"},{"key":"34_CR19","first-page":"1508","volume":"303","author":"Y.P. Lysov","year":"1988","unstructured":"Lysov, Y.P., Florent\u2019ev, V.L., Khorlin, A.A., Khrapko, K., Shik, V.V., Mirzabekov, A.D.: DNA Sequencing by hybridization with oligonucleotides. A novel method. Dokl. Acad. Sci USSR\u00a0303, 1508\u20131511 (1988)","journal-title":"Dokl. Acad. Sci USSR"},{"key":"34_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-58338-6_64","volume-title":"Mathematical Foundations of Computer Science 1994","author":"P.A. Pevzner","year":"1994","unstructured":"Pevzner, P.A., Lipshutz, R.J.: Towards DNA Sequencing Chips. In: Privara, I., Ru\u017ei\u010dka, P., Rovan, B. (eds.) MFCS 1994. LNCS, vol.\u00a0841, pp. 143\u2013158. Springer, Heidelberg (1994)"},{"issue":"1","key":"34_CR21","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S1570-8667(03)00010-8","volume":"1","author":"H. Ramesh","year":"2003","unstructured":"Ramesh, H., Vinay, V.: String matching in \u00d5 $(\\sqrt{n}+\\sqrt{m})$ quantum time. J.\u00a0Discrete Algorithms\u00a01(1), 103\u2013110 (2003)","journal-title":"J.\u00a0Discrete Algorithms"},{"issue":"2","key":"34_CR22","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1089\/cmb.1995.2.333","volume":"2","author":"S.S. Skiena","year":"1995","unstructured":"Skiena, S.S., Sundaram, G.: Reconstructing strings from substrings. J.\u00a0Computational Biol.\u00a02(2), 333\u2013353 (1995)","journal-title":"J.\u00a0Computational Biol."},{"issue":"5","key":"34_CR23","doi-asserted-by":"publisher","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.\u00a0Comput.\u00a026(5), 1484\u20131509 (1997)","journal-title":"SIAM J.\u00a0Comput."},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"Snir, M.: Lower bounds on probabilistic linear decision trees. Theoret.\u00a0Comput.\u00a0Sci.\u00a038, 69\u201382 (1985)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."},{"issue":"1","key":"34_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2006.v002a001","volume":"2","author":"R. \u0160palek","year":"2006","unstructured":"\u0160palek, R., Szegedy, M.: All quantum adversary methods are equivalent. Theory of Computing\u00a02(1), 1\u201318 (2006)","journal-title":"Theory of Computing"},{"issue":"2-3","key":"34_CR26","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2005.01.019","volume":"339","author":"S. Zhang","year":"2005","unstructured":"Zhang, S.: On the power of Ambainis lower bounds. Theoret.\u00a0Comput.\u00a0Sci.\u00a0339(2-3), 241\u2013256 (2005)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T01:29:35Z","timestamp":1743384575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}