Automated quantum circuit synthesis and cost estimation for the binary welded tree oracle

Mrityunjay Ghosh, Amlan Chakrabarti, Niraj K. Jha

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Article number51
JournalACM Journal on Emerging Technologies in Computing Systems
Issue number4
StatePublished - Jun 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


  • Binary welded tree
  • Quantum computing
  • Quantum logic synthesis
  • Quantum walk
  • Reversible circuit


Dive into the research topics of 'Automated quantum circuit synthesis and cost estimation for the binary welded tree oracle'. Together they form a unique fingerprint.

Cite this