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

Mrityunjay Ghosh, Amlan Chakrabarti, Niraj Kumar Jha

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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
Volume13
Issue number4
DOIs
StatePublished - Jun 1 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint 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