White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Application of quantum walks on graph structures to quantum computing

Lovett, Neil Brian (2011) Application of quantum walks on graph structures to quantum computing. PhD thesis, University of Leeds.

Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (4Mb)


Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.

Item Type: Thesis (PhD)
ISBN: 978-0-85731-073-6
Academic Units: The University of Leeds > Faculty of Maths and Physical Sciences (Leeds) > School of Physics and Astronomy (Leeds)
Identification Number/EthosID: uk.bl.ethos.535671
Depositing User: Ethos Import
Date Deposited: 06 Oct 2011 13:09
Last Modified: 07 Mar 2014 11:24
URI: http://etheses.whiterose.ac.uk/id/eprint/1689

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)