You are here

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

Download pdf | Full Screen View

Date Issued:
2011
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 reflections in the walk operator provides a quadratic speed-up, 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 speed-up of spectral gap is insignificant. In a situation like that that,I provide an amplitude amplification-based 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.
Title: The Power of Quantum Walk: Insights, Implementation, and Applications.
0 views
0 downloads
Name(s): Chiang, Chen-Fu, Author
Wocjan, Pawel, Committee Chair
Marinescu, Dan, Committee Member
Dechev, Damian, Committee Member
Mucciolo, Eduardo, Committee Member
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2011
Publisher: University of Central Florida
Language(s): English
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 reflections in the walk operator provides a quadratic speed-up, 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 speed-up of spectral gap is insignificant. In a situation like that that,I provide an amplitude amplification-based 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.
Identifier: CFE0004094 (IID), ucf:49148 (fedora)
Note(s): 2011-12-01
Ph.D.
Engineering and Computer Science, Computer Science
Doctoral
This record was generated from author submitted information.
Subject(s): 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
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0004094
Restrictions on Access: public 2011-12-15
Host Institution: UCF

In Collections