TY - JOUR
T1 - Efficient quantum circuit implementation of quantum walks
AU - Douglas, B. L.
AU - Wang, J. B.
N1 - Erratum can be found in Physical Review A - Atomic, Molecular, and Optical Physics, Volume 80(5), 059901, http://dx.doi.org/10.1103/PhysRevA.80.059901
PY - 2009/5/1
Y1 - 2009/5/1
N2 - Quantum walks, being the quantum analog of classical random walks, are expected to provide a fruitful source of quantum algorithms. A few such algorithms have already been developed, including the "glued trees" algorithm, which provides an exponential speedup over classical methods, relative to a particular quantum oracle. Here, we discuss the possibility of a quantum walk algorithm yielding such an exponential speedup over possible classical algorithms, without the use of an oracle. We provide examples of some highly symmetric graphs on which efficient quantum circuits implementing quantum walks can be constructed and discuss potential applications to quantum search for marked vertices along these graphs.
AB - Quantum walks, being the quantum analog of classical random walks, are expected to provide a fruitful source of quantum algorithms. A few such algorithms have already been developed, including the "glued trees" algorithm, which provides an exponential speedup over classical methods, relative to a particular quantum oracle. Here, we discuss the possibility of a quantum walk algorithm yielding such an exponential speedup over possible classical algorithms, without the use of an oracle. We provide examples of some highly symmetric graphs on which efficient quantum circuits implementing quantum walks can be constructed and discuss potential applications to quantum search for marked vertices along these graphs.
UR - http://www.scopus.com/inward/record.url?scp=66349135590&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/record.url?scp=84921001504&partnerID=8YFLogxK
U2 - 10.1103/PhysRevA.79.052335
DO - 10.1103/PhysRevA.79.052335
M3 - Article
AN - SCOPUS:66349135590
VL - 79
SP - 1
EP - 5
JO - Physical Review A: covering atomic, molecular, and optical physics and quantum information
JF - Physical Review A: covering atomic, molecular, and optical physics and quantum information
SN - 2469-9926
IS - 5
M1 - 052335
ER -