### Abstract

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 language | English (US) |
---|---|

Title of host publication | Proceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012 |

Pages | 135-140 |

Number of pages | 6 |

DOIs | |

State | Published - Oct 29 2012 |

Event | 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012 - Amherst, MA, United States Duration: Aug 19 2012 → Aug 21 2012 |

### Publication series

Name | Proceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012 |
---|

### Other

Other | 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012 |
---|---|

Country | United States |

City | Amherst, MA |

Period | 8/19/12 → 8/21/12 |

### All Science Journal Classification (ASJC) codes

- Control and Systems Engineering
- Electrical and Electronic Engineering

### Keywords

- Quantum Algorithms
- quantum circuits
- quantum cost
- quantum random walk

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

## Cite this

*Proceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012*(pp. 135-140). [6296462] (Proceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012). https://doi.org/10.1109/ISVLSI.2012.45