Home
Resource
Quantum walks and ground state problems
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(529.20 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Richter, Peter C. (Peter Courtland). Quantum walks and ground state problems. Retrieved from https://doi.org/doi:10.7282/T3W37WQ1

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

Uniform TitleQuantum walks and ground state problems
NameRichter, Peter C. (Peter Courtland) (author); Szegedy, Mario (chair); Allender, Eric (internal member); Kilian, Joe (internal member); Kendon, Viv (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2007
Other Date2007 (degree)
SubjectComputer Science, Computer algorithms, Quantum field theory, Random walks (Mathematics)
Extentviii, 101 pages
DescriptionSince the appearance of Shor's factoring algorithm in 1994, the search for novel quantum computer algorithms has proved surprisingly difficult. Two design approaches that have yielded some progress are quantum walks and adiabatic computing. The former has been shown to speed up algorithms whose complexity is related to the classical hitting time of a symmetric Markov chain, and there is evidence that the latter speeds up simulated annealing algorithms for computing ground states of classical Hamiltonians.
In this thesis, we look into the possibility of obtaining a quantum speedup for the mixing time of a symmetric Markov chain. We prove that by subjecting a quantum walk to a small amount of decoherence (typically the adversary of a quantum computer), it can be forced to mix to the correct stationary distribution, often considerably faster than its classical counterpart. A more general theorem to this effect would imply quantum speedups for a variety of approximation algorithms for #P-complete problems.
We conclude with some observations on adiabatic computing -- a time-dependent generalization of the quantum walk framework -- and the problem of estimating the ground state energy of a quantum Hamiltonian with local spin interactions.
NotePh.D.
NoteIncludes bibliographical references (p. 94-100).
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3W37WQ1
LanguageEnglish
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024