Current Search: Markov chain  random walk  quantum walk  phase estimation  perturbation  approximation algorithm  quantum algorithm  circuit implementation  hitting time  quantum hitting time  delayed perturbed quantum hitting time (x)


Title

The Power of Quantum Walk: Insights, Implementation, and Applications.

Creator

Chiang, ChenFu, Wocjan, Pawel, Marinescu, Dan, Dechev, Damian, Mucciolo, Eduardo, University of Central Florida

Abstract / Description

In this thesis, I investigate quantum walks in quantum computing from threeaspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two...
Show moreIn this thesis, I investigate quantum walks in quantum computing from threeaspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two reflections in the walk operator provides a quadratic speedup, in comparison to the classical counterpart. For the implementation of quantum walks, I show the construction of an efficient circuit for realizing one single step of the quantum walk operator. Furthermore, I devise a more succinct circuit to approximately implement quantum phase estimation with constant precision controlled phase shift operators. From an implementation perspective, efficient circuits are always desirable because the realization of a phase shift operator with high precision would be a costly task and a critical obstacle. For the applications of quantum walks, I apply the quantum walk technique along with other fundamental quantum techniques, such as phase estimation, to solve the partition function problem. However, there might be some scenario in which the speedup of spectral gap is insignificant. In a situation like that that,I provide an amplitude amplificationbased approach to prepare the thermal Gibbs state. Such an approach is useful when the spectral gap is extremely small. Finally, I further investigate and explore the effect of noise (perturbation)on the performance of quantum walks.
Show less

Date Issued

2011

Identifier

CFE0004094, ucf:49148

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0004094