Design of quantum circuits for random walk algorithms

Amlan Chakrabarti, Chiachun Lin, Niraj K. Jha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


A quantum algorithm is defined by a sequence of operations that runs on a realistic model of quantum computation. Since the first quantum algorithm proposed by David Deutsch(1985), a large number of impressive quantum algorithms have been developed. Quantum random walks on a graph, which are analogous to classical stochastic walk, form the basis for some of the recent quantum algorithms that promise to significantly outperform existing classical random walk algorithms. Though research has been done on the application of quantum random walk to important computational problems, very little work has been done on its quantum circuit design. There are two types of quantum random walk algorithms: discrete-time and continuous-time. In this paper, we propose quantum circuit designs for both types of random walk algorithms that operate on various graphs. We consider in detail two important problems to which random walk algorithms are applicable: the triangle finding problem and binary welded tree problem. Though there exist a few research works related to quantum circuit design for random walk on graphs, to the best of our knowledge, the circuit designs we present here are first of their kind. We also provide an estimate of the quantum cost of these circuits for several physical machine descriptions (PMDs)of quantum systems, based on the number of quantum operations and execution cycles.

Original languageEnglish (US)
Title of host publicationProceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012
Number of pages6
StatePublished - 2012
Event2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012 - Amherst, MA, United States
Duration: Aug 19 2012Aug 21 2012

Publication series

NameProceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012


Other2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012
Country/TerritoryUnited States
CityAmherst, MA

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


  • Quantum Algorithms
  • quantum circuits
  • quantum cost
  • quantum random walk


Dive into the research topics of 'Design of quantum circuits for random walk algorithms'. Together they form a unique fingerprint.

Cite this