TY - GEN

T1 - Design of quantum circuits for random walk algorithms

AU - Chakrabarti, Amlan

AU - Lin, Chiachun

AU - Jha, Niraj K.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Quantum Algorithms

KW - quantum circuits

KW - quantum cost

KW - quantum random walk

UR - http://www.scopus.com/inward/record.url?scp=84867789697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867789697&partnerID=8YFLogxK

U2 - 10.1109/ISVLSI.2012.45

DO - 10.1109/ISVLSI.2012.45

M3 - Conference contribution

AN - SCOPUS:84867789697

SN - 9780769547671

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

SP - 135

EP - 140

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

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

Y2 - 19 August 2012 through 21 August 2012

ER -