{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T11:09:54Z","timestamp":1770462594300,"version":"3.49.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,8,25]],"date-time":"2021-08-25T00:00:00Z","timestamp":1629849600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,25]],"date-time":"2021-08-25T00:00:00Z","timestamp":1629849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s42979-021-00813-3","type":"journal-article","created":{"date-parts":[[2021,8,25]],"date-time":"2021-08-25T13:04:12Z","timestamp":1629896652000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Circuit Design for k-Coloring Problem and Its Implementation in Any Dimensional Quantum System"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2583-9825","authenticated-orcid":false,"given":"Amit","family":"Saha","sequence":"first","affiliation":[]},{"given":"Debasri","family":"Saha","sequence":"additional","affiliation":[]},{"given":"Amlan","family":"Chakrabarti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,25]]},"reference":[{"key":"813_CR1","doi-asserted-by":"publisher","DOI":"10.1109\/iSES50453.2020.00015","author":"A Saha","year":"2020","unstructured":"Saha A, Saha D, Chakrabarti A. Circuit design for K-coloring problem and its implementation on near-term quantum devices. IEEE Int Symp Smart Electron Syst. 2020. https:\/\/doi.org\/10.1109\/iSES50453.2020.00015.","journal-title":"IEEE Int Symp Smart Electron Syst"},{"key":"813_CR2","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2002","unstructured":"Nielsen MA, Chuang IL. Quantum computation and quantum information. Cambridge: Cambridge University Press; 2002."},{"issue":"2","key":"813_CR3","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1103\/PhysRevA.58.915","volume":"58","author":"E Farhi","year":"1998","unstructured":"Farhi E, Gutmann S. Quantum computation and decision trees. Phys Rev A. 1998;58(2):915\u201328. https:\/\/doi.org\/10.1103\/PhysRevA.58.915.","journal-title":"Phys Rev A"},{"key":"813_CR4","doi-asserted-by":"publisher","unstructured":"Shor PW. Algorithms for quantum computation: discrete logarithms and factoring. Found Comput Sci. 1994 pp. 124\u2013134. https:\/\/doi.org\/10.1109\/SFCS.1994.365700.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"813_CR5","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79","author":"J Preskill","year":"2018","unstructured":"Preskill J. Quantum computing in the NISQ era and beyond. Quantum. 2018. https:\/\/doi.org\/10.22331\/q-2018-08-06-79.","journal-title":"Quantum"},{"key":"813_CR6","unstructured":"Sanyal A, Saha A, Saha B, Chakrabarti A. Circuit design of clique problem and its implementation on NISQ using combinatorial approach of classical-quantum hybrid model. 2020. arXiv:2004.10596."},{"key":"813_CR7","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations, (The IBM Research Symposia Series)","author":"RM Karp","year":"1972","unstructured":"Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD, editors. Complexity of computer computations, (The IBM Research Symposia Series). Boston: Springer; 1972. p. 85\u2013103."},{"key":"813_CR8","first-page":"212","volume":"96","author":"L Grover","year":"1996","unstructured":"Grover L. A fast quantum mechanical algorithm for database search. Proc ACM Symp Theory Comput. 1996;96:212\u20139.","journal-title":"Proc ACM Symp Theory Comput"},{"issue":"4","key":"813_CR9","doi-asserted-by":"publisher","first-page":"042319","DOI":"10.1103\/PhysRevA.76.042319","volume":"A76","author":"J Koch","year":"2007","unstructured":"Koch J, Yu TM, Gambetta J, Houck AA, Schuster DI, Majer J, Blais A, Devoret MH, Girvin SM, Schoelkopf RJ. Charge-insensitive qubit design derived from the cooper pair box. Phys Rev A. 2007;A76(4):042319. https:\/\/doi.org\/10.1103\/PhysRevA.76.042319.","journal-title":"Phys Rev A"},{"issue":"6","key":"813_CR10","doi-asserted-by":"publisher","first-page":"062313","DOI":"10.1103\/PhysRevA.67.062313","volume":"A67","author":"AB Klimov","year":"2003","unstructured":"Klimov AB, Guzm\u00e1n R, Retamal JC, Saavedra C. Qutrit quantum computer with trapped ions. Phys Rev. 2003;A67(6):062313. https:\/\/doi.org\/10.1103\/PhysRevA.67.062313.","journal-title":"Phys Rev"},{"issue":"4","key":"813_CR11","doi-asserted-by":"publisher","first-page":"1361","DOI":"10.1007\/s11128-015-1229-0","volume":"15","author":"MRA Adcock","year":"2016","unstructured":"Adcock MRA, H\u00f8yer P, Sanders BC. Quantum computation with coherent spin states and the closeHadamard problem. Quant Inform Process. 2016;15(4):1361\u201386. https:\/\/doi.org\/10.1007\/s11128-015-1229-0.","journal-title":"Quant Inform Process"},{"key":"813_CR12","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1103\/physreva.65.052316","volume":"A65","author":"SD Bartlett","year":"2002","unstructured":"Bartlett SD, de Guise H, Sanders BC. Quantum encodings in spin systems and harmonic oscillators. Phys Rev. 2002;A65:5. https:\/\/doi.org\/10.1103\/physreva.65.052316.","journal-title":"Phys Rev"},{"key":"813_CR13","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.96.012306","author":"A Bocharov","year":"2017","unstructured":"Bocharov A, Roetteler M, Svore KM. Factoring with qutrits: shor\u2019s algorithm on ternary and metaplectic quantum architectures. Phys Rev A. 2017. https:\/\/doi.org\/10.1103\/PhysRevA.96.012306.","journal-title":"Phys Rev A"},{"issue":"8","key":"813_CR14","doi-asserted-by":"publisher","first-page":"2687","DOI":"10.1007\/s11128-015-1016-y","volume":"14","author":"SX Cui","year":"2015","unstructured":"Cui SX, Hong SM, Wang Z. Universal quantum computation with weakly integral anyons. Quant Inform Process. 2015;14(8):2687\u2013727. https:\/\/doi.org\/10.1007\/s11128-015-1016-y.","journal-title":"Quant Inform Process"},{"issue":"46","key":"813_CR15","doi-asserted-by":"publisher","first-page":"3452","DOI":"10.1016\/j.physleta.2014.10.003","volume":"A378","author":"S Dogra","year":"2014","unstructured":"Dogra S, Arvind Dorai K. Determining the parity of a permutation using an experimental NMR qutrit. Phys Lett. 2014;A378(46):3452\u20136. https:\/\/doi.org\/10.1016\/j.physleta.2014.10.003.","journal-title":"Phys Lett"},{"key":"813_CR16","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.125.050501","author":"X Gao","year":"2020","unstructured":"Gao X, Erhard M, Zeilinger A, Krenn M. Computer-inspired concept for high-dimensional multipartite quantum gates. Phys Rev Lett. 2020. https:\/\/doi.org\/10.1103\/physrevlett.125.050501.","journal-title":"Phys Rev Lett"},{"issue":"6830","key":"813_CR17","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1038\/35071024","volume":"410","author":"M. N Leuenberger","year":"2001","unstructured":"Leuenberger M. N, Loss D. Quantum computing in molecular magnets. Nature. 2001;410(6830):789\u201393. https:\/\/doi.org\/10.1038\/35071024.","journal-title":"Nature"},{"key":"813_CR18","doi-asserted-by":"crossref","unstructured":"Saha A, Saha D, Chakrabarti A. Moving quantum states without SWAP via intermediate higher dimensional qudits. 2021. arXiv:2106.09089.","DOI":"10.1103\/PhysRevA.106.012429"},{"key":"813_CR19","doi-asserted-by":"publisher","first-page":"0523091","DOI":"10.1103\/PhysRevA.62.052309","volume":"62","author":"A Muthukrishnan","year":"2000","unstructured":"Muthukrishnan A, Stroud CR Jr. Multi-valued logic gates for quantum computation. Phys Rev A. 2000;62:0523091\u20138.","journal-title":"Phys Rev A"},{"key":"813_CR20","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3074707","author":"A Saha","year":"2021","unstructured":"Saha A, Mandal SB, Saha D, Chakrabarti A. One-dimensional lazy quantum walk in ternary system. IEEE Trans Quant Eng. 2021. https:\/\/doi.org\/10.1109\/TQE.2021.3074707.","journal-title":"IEEE Trans Quant Eng"},{"key":"813_CR21","unstructured":"Fan Y. Application of multi-valued quantum algorithm. 2008. arXiv:0809.0932."},{"key":"813_CR22","doi-asserted-by":"crossref","unstructured":"Li X, Yang G, Zheng D. Logic synthesis of ternary quantum circuits with minimal qutrits. Proc J Comput. 2013;8(8):1941\u201346.","DOI":"10.4304\/jcp.8.8.1941-1946"},{"key":"813_CR23","unstructured":"Bocharov A, Cui SX, Roetteler M, Svore KM. Improved quantum ternary arithmetics. 2015. arXiv:1512.03824."},{"issue":"08","key":"813_CR24","doi-asserted-by":"publisher","first-page":"1550121","DOI":"10.1142\/S0218126615501212","volume":"24","author":"F Fan","year":"2015","unstructured":"Fan F, Yang G, Yang G, Hung WNN. A synthesis method of quantum reversible logic circuit based on elementary qutrit quantum logic gates. J Circuits Syst Comput. 2015;24(08):1550121. https:\/\/doi.org\/10.1142\/S0218126615501212.","journal-title":"J Circuits Syst Comput"},{"issue":"3","key":"813_CR25","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.tcs.2006.09.006","volume":"367","author":"FS Khan","year":"2006","unstructured":"Khan FS, Perkowski M. Synthesis of multi-qudit hybrid and d-valued quantum logic circuits by decomposition. Theoret Comput Sci. 2006;367(3):336\u201346. https:\/\/doi.org\/10.1016\/j.tcs.2006.09.006.","journal-title":"Theoret Comput Sci"},{"key":"813_CR26","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.101.022304","author":"EO Kiktenko","year":"2020","unstructured":"Kiktenko EO, Nikolaeva AS, Peng X, Shlyapnikov GV, Fedorov AK. Scalable quantum computing with qudits on a graph. Phys Rev. 2020. https:\/\/doi.org\/10.1103\/physreva.101.022304.","journal-title":"Phys Rev"},{"key":"813_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1109\/iNIS.2015.55","volume":"2015","author":"A Saha","year":"2015","unstructured":"Saha A, Chongder A, Mandal SB, Chakrabarti A. Synthesis of vertex coloring problem using Grover\u2019s algorithm. IEEE Int Symp Nanoelectron Inform Syst. 2015;2015:101\u20136. https:\/\/doi.org\/10.1109\/iNIS.2015.55.","journal-title":"IEEE Int Symp Nanoelectron Inform Syst"},{"key":"813_CR28","doi-asserted-by":"crossref","unstructured":"Mandal SB, Chakrabarti A, Sur-Kolay S. Synthesis of ternary Grovers algorithm. In: IEEE 44th International Symposium on Multiple-Valued Logic (ISMVL), 2014.","DOI":"10.1109\/ISMVL.2014.40"},{"key":"813_CR29","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.85.062321","author":"SS Ivanov","year":"2012","unstructured":"Ivanov SS, Tonchev HS, Vitanov NV. Time-efficient implementation of quantum search with qudits. Phys Rev A. 2012. https:\/\/doi.org\/10.1103\/PhysRevA.85.062321.","journal-title":"Phys Rev A"},{"key":"813_CR30","unstructured":"Hunt S, Gadouleau M. Grover\u2019s Algorithm and many-valued quantum logic. 2020. arXiv:2001.06316."},{"key":"813_CR31","unstructured":"Shimizu K, Mori R. Exponential-time quantum algorithms for graph coloring problems. arXiv:1907.00529."},{"issue":"6","key":"813_CR32","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1109\/MC.2019.2909709","volume":"52","author":"S Hu","year":"2019","unstructured":"Hu S, Liu P, Chen CR, Pistoia M, Gambetta J. Reduction-based problem mapping for quantum computing. Computer. 2019;52(6):47\u201357. https:\/\/doi.org\/10.1109\/MC.2019.2909709.","journal-title":"Computer"},{"key":"813_CR33","unstructured":"IBM Research, Quantum Experience. http:\/\/www.research.ibm.com\/quantum\/."},{"key":"813_CR34","unstructured":"Wang Y, Perkowski M. Improved complexity of quantum oracle for ternary Grover algorithm for graph coloring. In: 41st International Symposium on Multiple-Valued Logic, Tusulu: Finland, 2009, pp. 294\u2013301."},{"key":"813_CR35","unstructured":"Khan MHA. Design of reversible\/quantum ternary comparator circuits. Eng Lett. 2008."},{"key":"813_CR36","doi-asserted-by":"publisher","DOI":"10.1109\/qce49297.2020.00018","author":"Z Tabi","year":"2020","unstructured":"Tabi Z, El-Safty KH, Kallus Z, Haga P, Kozsik T, Glos A, Zimboras Z. Quantum optimization for the graph coloring problem with space-efficient embedding. IEEE Int Conf Quant Comput Eng. 2020. https:\/\/doi.org\/10.1109\/qce49297.2020.00018.","journal-title":"IEEE Int Conf Quant Comput Eng"},{"key":"813_CR37","unstructured":"Glos A, Krawiec A, Zimboras Z. Space-efficient binary optimization for variational computing. 2020. arXiv:2009.07309."},{"issue":"5","key":"813_CR38","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A Barenco","year":"2019","unstructured":"Barenco A, Bennett CH, Cleve R, DiVincenzo DP, Margolus N, Shor P, Sleator T, Smolin JA, Weinfurter H. Elementary gates for quantum computation. Phys Rev A. 2019;52(5):3457\u201367.","journal-title":"Phys Rev A"},{"key":"813_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1103\/PhysRevA.87.012325","volume":"87","author":"YM Di","year":"2013","unstructured":"Di YM, Wei HR. Synthesis of multi-valued quantum logic circuits by elementary gates. Phys Rev A. 2013;87:1. https:\/\/doi.org\/10.1103\/PhysRevA.87.012325.","journal-title":"Phys Rev A"},{"key":"813_CR40","unstructured":"Di YM, Wei HR. Elementary gates for ternary quantum logic circuit. 2020. arXiv:1105.5485."},{"key":"813_CR41","unstructured":"Saha A, Majumdar R, Saha D, Chakrabarti A, Sur-Kolay S. Asymptotically improved Grover\u2019s algorithm in any dimensional quantum system with novel decomposed n-qudit Toffoli gate. 2020. arXiv:2012.04447."},{"key":"813_CR42","doi-asserted-by":"publisher","unstructured":"Acasiete F, Agostini FP, Khatibi Moqadam J, Portugal R. Experimental implementation of quantum walks on IBM quantum computers. 2020. https:\/\/doi.org\/10.1007\/s11128-020-02938-5.","DOI":"10.1007\/s11128-020-02938-5"},{"key":"813_CR43","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023","author":"G Li","year":"2019","unstructured":"Li G, Ding Y, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices. Proc Int Conf Archit Support Program Lang Oper Syst. 2019. https:\/\/doi.org\/10.1145\/3297858.3304023.","journal-title":"Proc Int Conf Archit Support Program Lang Oper Syst"},{"key":"813_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3400302.3415620","volume":"137","author":"B Tan","year":"2020","unstructured":"Tan B, Cong J. Optimal layout synthesis for quantum computing. Proc Int Conf Comput-Aided Des. 2020;137:1\u20139. https:\/\/doi.org\/10.1145\/3400302.3415620.","journal-title":"Proc Int Conf Comput-Aided Des"},{"key":"813_CR45","unstructured":"MATLAB, R2012b, The MathWorks, Natick, MA, 2012."},{"key":"813_CR46","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322253","author":"P Gokhale","year":"2019","unstructured":"Gokhale P, Baker JM, Duckering C, Brown NC, Brown KR, Chong FT. Asymptotic improvements to quantum circuits via qutrits. Proc Int Symp Comput Archit. 2019. https:\/\/doi.org\/10.1145\/3307650.3322253.","journal-title":"Proc Int Symp Comput Archit"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00813-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00813-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00813-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T01:06:13Z","timestamp":1673139973000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00813-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,25]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["813"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00813-3","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,25]]},"assertion":[{"value":"29 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"427"}}