{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T01:08:41Z","timestamp":1768266521810,"version":"3.49.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,6,29]],"date-time":"2017-06-29T00:00:00Z","timestamp":1498694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>Quantum computing is a new computational paradigm that promises an exponential speed-up over classical algorithms. To develop efficient quantum algorithms for problems of a non-deterministic nature, random walk is one of the most successful concepts employed. In this article, we target both continuous-time and discrete-time random walk in both the classical and quantum regimes. Binary Welded Tree (BWT), or glued tree, is one of the most well-known quantum walk algorithms in the continuous-time domain. Prior work implements quantum walk on the BWT with static welding. In this context, static welding is randomized but case-specific. We propose a solution to automatically generate the circuit for the Oracle for welding. We implement the circuit using the Quantum Assembly Language, which is a language for describing quantum circuits. We then optimize the generated circuit using the Fault-Tolerant Quantum Logic Synthesis tool for any BWT instance. Automatic welding enables us to provide a generalized solution for quantum walk on the BWT.<\/jats:p>","DOI":"10.1145\/3060582","type":"journal-article","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T12:36:19Z","timestamp":1498826179000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Automated Quantum Circuit Synthesis and Cost Estimation for the Binary Welded Tree Oracle"],"prefix":"10.1145","volume":"13","author":[{"given":"Mrityunjay","family":"Ghosh","sequence":"first","affiliation":[{"name":"Computer Science and Engineering Department, Amity University, Kolkata, Amity University, Kolkata"}]},{"given":"Amlan","family":"Chakrabarti","sequence":"additional","affiliation":[{"name":"A. K. Choudhury School of Information Technology, University of Calcutta"}]},{"given":"Niraj K.","family":"Jha","sequence":"additional","affiliation":[{"name":"Electrical Engineering Department, Princeton University"}]}],"member":"320","published-online":{"date-parts":[[2017,6,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.48.1687"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749903000383"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1646353.1646375"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.88.137901"},{"key":"e_1_2_1_5_1","unstructured":"R. M. Burton Y. Kovchegov and T. Nguyen. 2010. Quantum Random Walk Via Classical Random Walk with Internal States. Technical report. Department of Mathematics Oregon State University.  R. M. Burton Y. Kovchegov and T. Nguyen. 2010. Quantum Random Walk Via Classical Random Walk with Internal States. Technical report. Department of Mathematics Oregon State University."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2012.45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-009-0930-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780552"},{"key":"e_1_2_1_9_1","first-page":"123","article-title":"Quantum algorithms for graph traversals and related problems","volume":"7","author":"D\u00f6rn S.","year":"2007","unstructured":"S. D\u00f6rn . 2007 . Quantum algorithms for graph traversals and related problems . In Proc. CIE , Vol. 7. 123 -- 131 . S. D\u00f6rn. 2007. Quantum algorithms for graph traversals and related problems. In Proc. CIE, Vol. 7. 123--131.","journal-title":"Proc. CIE"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.871622"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989263"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485922.2485937"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2227518"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2013.2269869"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2014.2337302"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.57.120"},{"key":"e_1_2_1_18_1","first-page":"353","article-title":"Random walks on graphs: A survey","volume":"80","author":"Lo L.","year":"1993","unstructured":"L. Lo &vgrave;asz. 1993 . Random walks on graphs: A survey . Boly. Soc. Math. Stud. 2 Combin. 80 (1993), 353 -- 397 . L. Lo&vgrave;asz. 1993. Random walks on graphs: A survey. Boly. Soc. Math. Stud. 2 Combin. 80 (1993), 353--397.","journal-title":"Boly. Soc. Math. Stud. 2 Combin."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447311"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.81.042330"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.052307"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3060582","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3060582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:21Z","timestamp":1750215801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3060582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,29]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3060582"],"URL":"https:\/\/doi.org\/10.1145\/3060582","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"value":"1550-4832","type":"print"},{"value":"1550-4840","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,29]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}