{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:23:00Z","timestamp":1775874180712,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T00:00:00Z","timestamp":1654041600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T00:00:00Z","timestamp":1654041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"crossref","award":["JPMJPR1867"],"award-info":[{"award-number":["JPMJPR1867"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K17711"],"award-info":[{"award-number":["JP17K17711"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H04090"],"award-info":[{"award-number":["JP18H04090"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H04138"],"award-info":[{"award-number":["JP20H04138"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05966"],"award-info":[{"award-number":["JP20H05966"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The fastest known classical algorithm deciding the <jats:italic>k<\/jats:italic>-colorability of <jats:italic>n<\/jats:italic>-vertex graph requires running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (2^n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\ge 5$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>5<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(1.9140^n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>.<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>9140<\/mml:mn>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> using quantum random access memory (QRAM). Our approach is based on Ambainis et al\u2019s quantum dynamic programming with applications of Grover\u2019s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(1.9575^n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>.<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>9575<\/mml:mn>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For the polynomial-space quantum algorithm, we essentially develop <jats:inline-formula><jats:alternatives><jats:tex-math>$$(4-\\epsilon )^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>4<\/mml:mn>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mi>\u03f5<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time <jats:italic>classical<\/jats:italic> algorithms that can be improved quadratically by Grover\u2019s search.<\/jats:p>","DOI":"10.1007\/s00453-022-00976-2","type":"journal-article","created":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T05:02:31Z","timestamp":1654059751000},"page":"3603-3621","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Exponential-Time Quantum Algorithms for Graph Coloring Problems"],"prefix":"10.1007","volume":"84","author":[{"given":"Kazuya","family":"Shimizu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5474-5145","authenticated-orcid":false,"given":"Ryuhei","family":"Mori","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,1]]},"reference":[{"key":"976_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Balodis, K., Iraids, J., Kokainis, M., Pr\u016bsis, K., Vihrovs, J.: Quantum speedups for exponential-time dynamic programming algorithms. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919), pp. 1783\u20131793. SIAM (2019)","DOI":"10.1137\/1.9781611975482.107"},{"issue":"2","key":"976_CR2","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time $$O(1.3289^n)$$. J. Algorithms 54(2), 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"key":"976_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), pp. 575\u2013582. IEEE (2006)","DOI":"10.1109\/FOCS.2006.41"},{"issue":"2","key":"976_CR4","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/s00453-007-9149-8","volume":"52","author":"A Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica 52(2), 226\u2013249 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"976_CR5","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4\u20135","key":"976_CR6","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: Prog. Phys. 46(4\u20135), 493\u2013505 (1998)","journal-title":"Fortschritte der Physik: Prog. Phys."},{"issue":"6","key":"976_CR7","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"JM Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32(6), 547\u2013556 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"976_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"976_CR9","unstructured":"D\u00fcrr, C., H\u00f8yer, P.: A quantum algorithm for finding the minimum. arXiv preprint arXiv:quant-ph\/9607014 (1996)"},{"key":"976_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Improved exact algorithms for counting 3-and 4-colorings. In: Proceedings of the Thirteenth Annual International Computing and Combinatorics Conference (COCOON\u201907), pp. 65\u201374. Springer (2007)","DOI":"10.1007\/978-3-540-73545-8_9"},{"key":"976_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"key":"976_CR12","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: Solving NP-complete problems with quantum search. In: Latin American Symposium on Theoretical Informatics (LATIN\u201908), pp. 784\u2013792. Springer (2008)","DOI":"10.1007\/978-3-540-78773-0_67"},{"key":"976_CR13","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Lee, E.J.: Faster graph coloring in polynomial space. In: Proceedings of the Twenty-third Annual International Computing and Combinatorics Conference (COCOON\u201917), pp. 371\u2013383. Springer (2017)","DOI":"10.1007\/978-3-319-62389-4_31"},{"issue":"16","key":"976_CR14","doi-asserted-by":"publisher","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100(16), 160501 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"976_CR15","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing (STOC\u201996), pp. 212\u2013219. ACM (1996)","DOI":"10.1145\/237814.237866"},{"key":"976_CR16","doi-asserted-by":"crossref","unstructured":"Koivisto, M.: An $$O^*(2^{n})$$ algorithm for graph coloring and other partitioning problems via inclusion\u2013exclusion. In: Proceedings of the Forty-seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), pp. 583\u2013590. IEEE (2006)","DOI":"10.1109\/FOCS.2006.11"},{"key":"976_CR17","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Proc. Lett. 5, 66\u201367 (1976)","journal-title":"Inf. Proc. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00976-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00976-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00976-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T12:11:33Z","timestamp":1669637493000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00976-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,1]]},"references-count":17,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["976"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00976-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,1]]},"assertion":[{"value":"23 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}