Continuous-time quantum walks on star graphs

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

Related collections

Most cited references 13

Record: found
Abstract: found
Article: found

Is Open Access

Quantum random walks - an introductory overview

Julia Kempe (2003)

This article aims to provide an introductory survey on quantum random walks. Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks. We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context. We will mention recent developments in this new area and outline some open questions.

0 comments Cited 305 times – based on 0 reviews

Preprint

     Review now

Bookmark

Record: found
Abstract: found
Article: found

Is Open Access

Quantum Computation and Decision Trees

Sam Gutmann, Edward Farhi (1997)

Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node n levels from the root. We devise a quantum mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level n in time polynomial in n, then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in n, but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.

0 comments Cited 205 times – based on 0 reviews

Preprint

     Review now

Bookmark

Record: found
Abstract: found
Article: found

Is Open Access

A Quantum Random Walk Search Algorithm

K. Whaley, Julia Kempe, Neil Shenvi (2002)

Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speed-up over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random walk architecture that provides such a speed-up. It will be shown that this algorithm performs an oracle search on a database of \(N\) items with \(O(\sqrt{N})\) calls to the oracle, yielding a speed-up similar to other quantum search algorithms. It appears that the quantum random walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms.