Quantum Walk Schemes for Universal Quantum Computation

Underwood, Michael S.

Quantum Walk Schemes for Universal Quantum Computation

atmire.migration.oldid	627
dc.contributor.advisor	Feder, David L.
dc.contributor.author	Underwood, Michael S.
dc.date.accessioned	2013-01-24T16:55:29Z
dc.date.available	2013-06-15T07:01:47Z
dc.date.issued	2013-01-24
dc.date.submitted	2013	en
dc.description.abstract	Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.	en_US
dc.identifier.citation	Underwood, M. S. (2013). Quantum Walk Schemes for Universal Quantum Computation (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27514	en_US
dc.identifier.doi	http://dx.doi.org/10.11575/PRISM/27514
dc.identifier.uri	http://hdl.handle.net/11023/455
dc.language.iso	eng
dc.publisher.faculty	Graduate Studies
dc.publisher.institution	University of Calgary	en
dc.publisher.place	Calgary	en
dc.rights	University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subject	Physics--Theory
dc.subject	Physics--Theory
dc.subject.classification	quantum walks	en_US
dc.subject.classification	Quantum computation	en_US
dc.title	Quantum Walk Schemes for Universal Quantum Computation
dc.type	doctoral thesis
thesis.degree.discipline	Physics and Astronomy
thesis.degree.grantor	University of Calgary
thesis.degree.name	Doctor of Philosophy (PhD)
ucalgary.item.requestcopy	true