You are here
The Power of Quantum Walk: Insights, Implementation, and Applications
 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 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.
Title:  The Power of Quantum Walk: Insights, Implementation, and Applications. 
33 views
15 downloads 

Name(s): 
Chiang, ChenFu, 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 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.  
Identifier:  CFE0004094 (IID), ucf:49148 (fedora)  
Note(s): 
20111201 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 20111215  
Host Institution:  UCF 