Universal quantum computation using the discrete-time quantum walk

Neil B. Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, Viv Kendon

Research output: Contribution to journalArticlepeer-review

364 Citations (Scopus)
12 Downloads (Pure)


A proof that continuous-time quantum walks are universal for quantum computation, using unweighted graphs of low degree, has recently been presented by A. M. Childs [Phys. Rev. Lett. 102, 180501 (2009)]. We present a version based instead on the discrete-time quantum walk. We show that the discrete-time quantum walk is able to implement the same universal gate set and thus both discrete and continuous-time quantum walks are computational primitives. Additionally, we give a set of components on which the discrete-time quantum walk provides perfect state transfer.
Original languageEnglish
Article number042330
Number of pages7
JournalPhysical Review A
Issue number4
Publication statusPublished - 30 Apr 2010


  • continuous-time quantum walks
  • discrete-time
  • low degree
  • quantum computation
  • quantum walk
  • state transfer
  • universal gates
  • unweighted graphs
  • computational linguistics
  • continuous time systems
  • quantum computers
  • quantum theory


Dive into the research topics of 'Universal quantum computation using the discrete-time quantum walk'. Together they form a unique fingerprint.

Cite this